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

learn more… | top users | synonyms

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
26 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
33 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
49 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
24 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
53 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
28 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
29 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
83 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
23 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
77 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
25 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
33 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
54 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
59 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
25 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
29 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 ...
1
vote
1answer
66 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
22 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
57 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
27 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
25 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
45 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
70 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
23 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
38 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
20 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
115 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
53 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
18 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
21 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
64 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
44 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
0answers
30 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
12 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
54 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
26 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
48 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
46 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 $$ $$ ...
1
vote
2answers
51 views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the ...
1
vote
0answers
28 views

Infinity norm minimization

I am wondering how to minimize an objective function of the following form: $$\min_{\mathbf{x}\in\mathcal{R}^{MN}} \|\mathbf{x}-\mathbf{y}\|_\infty + \lambda\mathrm{TV}(\mathbf{x})$$ Here, ...
1
vote
1answer
62 views

Showing a function is concave

Given $F(\underline{x}) = Ax_1 + Bx_2 + \ln(a^2-(x_1^2+x^2_2))$ on $S=\{\underline{x}\in\mathbb{R}\mid x_1^2+x_2^2<a^2\}$ with $A,B,a\in\mathbb{R}$, show that $F$ is concave on $S$. Since we have ...
1
vote
3answers
45 views

How to find a counter example for non convexity?

Consider a simple function $f(x) = \frac{x}{y}, x,y \in (0,1]$, the Hessian is not positive semi definite and hence it is a non convex function. However, when we plot the function using Matlab/Maxima, ...
0
votes
0answers
48 views

Lagrange dual method and KKT condition

Consider the following optimization problem \begin{equation}\notag \begin{split} \max & x^2+y^2 \\ \mathrm{s.t.} & x^2 \leq 1 \\ & 0\leq y\leq 2 \end{split} \end{equation} Obviously, the ...