Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
0answers
37 views

Laplacian Regularization with Sparse group Lasso

I have an optimization problem that is of the form: $\{\textbf{A}\} = argmin \{tr(\textbf{A}^\top L \textbf{A}) + \lambda_1||\textbf{A}||_1 + \lambda_2||\textbf{A}||_{2,1}\}$ where $\textbf{A}$ is a ...
1
vote
3answers
24 views

Constraint to unconstraint optimization problem by subsitution

Given the following convex optimization problem $\min_{x,p} ||x|| - p$ subject to $p > 0$ Can I change the above to an unconstrained convex optimization problem by substituting $c = ...
1
vote
1answer
26 views

Could I get the explicit solution to the following problem relate to generalized rayleigh quotient?

$\bf x$ and $\bf a$ are complex vectors, $\bf C$ is positive definite complex matrix, $\bf B$ is positive-semidefinite complex matrix. What's the objective value? Thanks! $$\max_{\bf x} ...
1
vote
1answer
51 views

A particular quadratic minimization problem

Given $n^2$ constants $a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{nn}$ and $n^2$ non-negative variables $x_{11},x_{12},\ldots,x_{1n},x_{21},\ldots,x_{nn}$. Find the minimum value of $$\sum_{i=1}^n ...
1
vote
0answers
27 views

First order necessary conditions for nondifferentiable nonconvex minimization problem

I am interested in first order necessary conditions for the following minimization problem where the function $f$ is continuous, nondecreasing and concave, with $f(0)=0$, but not necessarily ...
0
votes
0answers
5 views

Perturbation of Polyhedral Projection

I am interested in understanding the behavior of the Euclidean projection $\pi_K(x)$ as the polyhedral set $K$ varies. I know there are different approaches to this, but for what I am doing it would ...
0
votes
0answers
21 views

Detecting faces of polytopes

I am working in convex geometry for the summer with little experience beforehand. It's a lot of fun but it does mean I don't know some of the basic things. I'm interested in the orbits of finite ...
2
votes
1answer
29 views

How to prevent a convex optimization from being unbounded?

I'm novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
0
votes
1answer
21 views

What exactly is non-convex optimization

I am coming across the term: non-convex optimization problem. What exactly is this non-convex structure, and how do I know by only looking at the structure of the problem, I could tell it is ...
1
vote
1answer
34 views

Optimization of a convex target function with inequality constraints

I want to solve the following optimization problem: \begin{equation} \begin{split} \text{maximize} &\;\;\; \ln x_1+\ln x_2+\ln x_3+\ln x_4 \\ \text{s.t} &\;\;\; x_4\le4 \\ ...
-2
votes
1answer
89 views

Matlab optimization toolbox vs. CVX solver?

I would like to know what is the difference between the Matlab optimization toolbox and CVX solver which is a convex optimization toolbox? Can a convex optimization be solved in both?
0
votes
1answer
25 views

Is $f(X) = || Y - XX^T ||_F$ convex given fixed $Y$?

In the scene of nonnegative matrix factorization, $f(X_1, X_2) = \| Y - X_1 X_2 \|_F$ is not convex, but both $f(X_1)$ given fixed $X_2$ and $f(X_2)$ given fixed $X_1$ are convex, enabling us to ...
0
votes
2answers
56 views

Regularization vs. Inequality Constraint

For what values of a regularization parameter $\alpha$, there is an equivalent inequality constraint in convex optimization? In particular, in the convex optimization problems below $$ \text{ Problem ...
0
votes
0answers
32 views

Finding a solution using the principle of maximum entropy?

I have set of linear constraints and would like to find an answer to its unknown variables, $p_i$'s. One of my options to find a solution for $p_i$'s using maximum entropy problem, $\max(\sum - p_i ...
1
vote
1answer
34 views

Linear constraint in convex optimization

Is it true that the solution to a linearly constrained convex minimization problem can only be placed on the boundary of the constraint set, for any nonlinear convex objective, e.g. $$ \min_x f(x)$$ ...
0
votes
0answers
93 views

Maximize the maximum Eigenvalue under a diagonally constrained matrix

Suppose we have $N\times N$ Hermitian matrix $\mathbf{A}$ I want to find the real $N\times N$ diagonal matrix $\mathbf{D}$ that maximizes the sum of the maximum Eigenvalues : $\mathbf{D}=\arg\max ...
0
votes
1answer
31 views

Is it possible to convexify this cone constraint?

General question An SOCP constraint is given by: $$ \| A_i \mathbf{x} + b_i\| \leq \mathbf{c}_i^T \mathbf{x} + d_i.$$ I have the following constraint: $$ \| A_i \mathbf{x} \| \geq d_i.$$ Is it ...
2
votes
2answers
84 views

How to maximize an entropy function?

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
1
vote
1answer
31 views

Problem understanding dual optimization problem?

I am reading this paper: http://dl.acm.org/citation.cfm?id=1390696 Following optimization problem is defined in section 2: \begin{align} \max_{\mathbf{X}>0} \log ...
0
votes
1answer
37 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
3
votes
1answer
64 views

Are all non-convex problems created equal?

The distinction between convex and non-convex problems is usually dubbed as the distinction between easy and hard problems. While in the convex case you are golden (local optima are global optima; ...
1
vote
1answer
63 views

Convexity of a rational function

I am attempting to (dis)prove that the function $$\frac{4x+3y+2}{x^2+xy+2x+y}$$ is convex for $x,y>0$. Attempting to differentiate the function does not seem like a good idea (or am I making a ...
0
votes
0answers
26 views

Prove that dual variables become free variables

Let P: $max\ c^T x$ subject to $Ax\leq b $ Say if we replace the latter part by $Ax=b$. Show the effect on dual problem is that the variables of dual become free variables. Can you break Ax=b ...
0
votes
1answer
33 views

regarding the concept of dual cone

When studying the covex analysis, I am not clear about the concept of dual cone. In the following graph, $\mathcal{K}*$ was the dual cone. I marked two points, the ...
0
votes
1answer
78 views

Convex optimization: affine equality constraints into inequality constraints

I have the following problem: \begin{equation} \begin{array}{cll} \displaystyle \min_{ \mathbf{x} } & & \displaystyle f(\mathbf{x}) \\ \mathrm{s.t.} & & \mathbf{x} \in \mathcal{C} \\ ...
2
votes
0answers
26 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
3
votes
1answer
67 views

Rank one plus diagonal matrix approximation

Given $A \in R^{n \times n}$, $A$ symmetric. I'm trying to solve the following minimization problem: $\underset{u \in R^n, d \in R^n} \min \, \frac{1}{2} \|X - A\|_F^2$ subject to $X = u u^T + ...
0
votes
0answers
31 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
0
votes
1answer
26 views

Can $\min f'x$ s.t. $(a'x - b)^2 \le d $ be written as a SOCP?

It does not appear to be significantly different from the form listed here: http://en.wikipedia.org/wiki/Second-order_cone_programming with (in article notation) $i = {1}$, $ A = a$, and $b$, $d$ as ...
0
votes
0answers
29 views

Prove the existing and uniqueness of a solution [duplicate]

Let function $f$ be differentiable and convex in $R^n$ . How can it be proved that $∀λ>0$ solution of system equations $f ′ (x)=−λx$ exists exclusively (∃and! ).
0
votes
2answers
46 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
1
vote
2answers
78 views

Maximization of a log det function

I want to solve the following optimization problem $$ \text{maximize } f(X) = - \log \mathrm{det}(X+Y) - a^T (X+Y)^{-1} a \\ \text{subject to } X \succeq W, $$ where the design variable $X$ is ...
0
votes
1answer
28 views

Is this following SDP problem Convex?

Is the following problem convex function? \begin{eqnarray} \begin{aligned} \underset{\mathbf{X}} {\text{minimize}}\,\,\,\, & \text{Trace}(\mathbf{RX}) \\ \text{subject to} &\\ & ...
0
votes
0answers
24 views

Dual convex pairs

I am currently trying to understand a certain proof. The author uses the term dual convex pair for a pair $(\phi,\psi)$ of convex functions defined on subsets $X,Y$ of $\mathbb R^n$ satisfying: $$ ...
0
votes
0answers
44 views

KKT Conditions and Convexity

min $x^2 -xy +y^2 -5x+6y$ subject to $1 \leq y$, $y^3 \leq 2x$, and $x \leq 8$ Write out the KKT conditions for this problem. Show that $(x,y) = (4,2)$ is a KKT point, and is therefore a global ...
0
votes
1answer
21 views

Deriving projection operator for an affine set

Given an affine set $Ax=b$, the Projection operator to this set is $$P(z) = z - A^{T}(AA^{T})^{-1}(Az-b)$$ which is also affine. How is this derived?
7
votes
3answers
117 views

Is group theory useful in any way to optimization?

For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it. Is group theory useful in any way to ...
0
votes
1answer
76 views

Is there any method that convert a non-convex problem to a convex one?

I have an optimization problem of the form: minimize $\quad f_0(x)$ subject to $\;\;\;f_1(x)\leq0,\quad\quad\quad(C1)$ $\quad\;\quad\;\quad\quad\;f_2(x)\leq0,\quad\quad\quad(C2)$ where ...
0
votes
0answers
20 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
0
votes
0answers
24 views

Log barrier for SDP generalized inequality: positive semidefinite point appears infeasible

Given the optimization problem: minimize $\;\;$ tr$(GX) $ subject to $\;$ tr$(F_i X) = 0 \quad \forall i=1,...,p $ $\quad\quad\quad\quad\;\; X \succcurlyeq 0 $ I know the log barrier ...
1
vote
1answer
70 views

accomodating non-negativity constraint in the dual

Suppose the objective implicitly imposes non-negativity constraint, say, the objective is sum of square roots of the decision variables. Is it necessary to consider the inequality constraints imposing ...
0
votes
1answer
45 views

Homogeneous non-negative least-squares

I would like to least-squares-"solve" a set of linear equations ($\underset{\mathbf{x}}{\mathrm{argmin}}\; \|\mathbf{Ax-b}\|_2$). In my case, $\mathbf{b=0}$, e.g. the system is homogeneous. I also ...
0
votes
1answer
38 views

No free lunch theorems

In James Spall's book, when explaining NFL theorems (http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization}) an example is given. Suppose input space has $3$ elements and output space ...
0
votes
0answers
22 views

dual feasibility question in augmented Lagrangians and the method of multipliers

I am going through Boyd's tutorial on ADMM. My question is basically from Sec 2.3. Consider the optimization problem $$\min.~f(x)~~~~\text{s.t.}~~~Ax = b.$$ Then the Lagrangian is ...
0
votes
0answers
14 views

Linear Programming error bounds question

We have the LP problem: Maximize $P=3x+2y$ subject to $$-x+3y \leq 2+r_1$$ $$x+y \leq 8+r_2$$ $$2x-y \leq 10+r_3$$ What would be the formula for $P(r)$ in terms of $r=(r_1, r_2, r_3)$ for the ...
1
vote
2answers
60 views

Composition of non-monotonic convex function

Given the following composition of functions: $h:\Bbb R^k\rightarrow\Bbb R$ $g:\Bbb R^n\rightarrow\Bbb R$ $f(x)=h(g_1(x),g_2(x),...,g_k(x))$ There are known rules which guarantee ...
0
votes
1answer
27 views

Semi-Infinite Linear Programming: Why is the infimum attained?

I have an optimization problem of the following form: $$\min c^T \lambda\\ \text{s.t. } f(x)^T \lambda \ge g(x) \text{ for all } x \in E,$$ where $E$ is an arbitrary set, $c \in \mathbb{R}^n, f ...
1
vote
1answer
51 views

Projection onto a convex closed set

H, If $K$ is a non-empty convex and closed subset of a uniformly convex Banach space $X$ (Hilbert for example) and $v \notin K$, we know that there exists a unique $k_0\in K$ such that ...
0
votes
1answer
24 views

Decreasing Function Projected onto Simplex

Consider $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$, defined as $f(x) := a x + b$, where $a<0$ and $b \in \mathbb{R}_{\leq 0}^{n}$. Note that $f$ is decreasing: $$ x \geq y \Longrightarrow f(x) ...
0
votes
1answer
55 views

Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?

Consider the assignment problem: $$ Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} $$ s.t. $$ \sum_i x_{ij} = 1 \quad\forall j $$ $$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$ $$ ...