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

learn more… | top users | synonyms

1
vote
0answers
123 views

Facets of the convex hull as solution of an optimization problem?

Given $N$ points $x_1, x_2, ..., x_N \in \mathbb{R}^n$, consider their convex hull $$\mathcal{C} = \text{conv}( \{ x_1, ..., x_n \} ) = \bigcap_{j=1}^{J} \{ x \in \mathbb{R}^n : \ A_j x \leq b_j \} ...
1
vote
0answers
82 views

Formulation of a problem as semidefinite programming

I would appreciate some help with this problem: $R$ is a positive semidefinite matrix $\in{R}^{n\times n}$, $A \in{R}^{n\times m}$. I need to formulate this optimization problem as semidefinite ...
1
vote
0answers
143 views

About Schur complement in a non-linear matrix inequality

I have the following matrix inequality which is nonlinear due to $M^TM$. In order to transform into an LMI, I apply the Schur complement, however I am not sure about the result. Can you tell me if ...
1
vote
0answers
52 views

Is it problematic when using Newton Descent with discontinuous Hessian?

Is there any side effect when applying Newton Descent to a convex function whose Hessian is discontinuous?
1
vote
0answers
135 views

Maximizing an inner-product over a convex set.

Let $x \in \mathbb{R}^N$ and let $K$ be a closed convex set in $\mathbb{R}^n$. Let $$ \widehat{y} = \textrm{arg} \, \textrm{max} _{\,\,y \in K} \langle x,y \rangle,$$ where $\langle \cdot, \cdot ...
1
vote
0answers
31 views

Confusion related to convexity and concavity of a problem

I was reading this paper http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf related to adaptive multi-hyperplane machine for non linear classification In that paper, they have mentioned about ...
1
vote
0answers
24 views

Can we express a SPD matrix $S$ in terms of $S^{2}$ in a different manner to solve a convex problem?

I have to find the Symmetric Positive Definite matrix $S\in \mathcal{M}_{m,m}$ that minimizes the function $f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ which has been proven to be convex in the ...
1
vote
0answers
108 views

maximize an objective function with an infinite component

Suppose I have the following maximization problem: $\log\det(\alpha K_p)-c\alpha$ with respect to $\alpha$ with $c$ being a constant and $m$ being the dimension of $K_p$. Here, one of the eigenvalues ...
1
vote
0answers
143 views

K.K.T. conditions, Lagrangian gradient not defined for zero.

When I write the K.K.T. conditions for the problem I have, I get the following expression for the gradient of the Lagrangian: $$\frac{\partial \mathcal{L}}{\partial x} = - \frac{\sqrt{x} + ...
1
vote
0answers
192 views

How to find $\kappa$ to minimize integral $I = \frac{1}{\kappa}\int\limits_{0}^{T} \mathrm{exp}\left(-f(\kappa,x)\right) \mathrm{d}x$

I am trying to find such value $\kappa \in (0,1)$ that would minimize the integral \begin{equation} \begin{aligned} I = \frac{1}{\kappa}\int\limits_{0}^{T} \mathrm{exp}\left(-f(\kappa,x)\right) ...
1
vote
0answers
86 views

Minimize a complex quadratic subject to two convex quadratic constraints

I have the following the optimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~&||\mathbb{x}^H\mathbb{u}||_2^2-2*Real\{ \mathbb{x^Hu}\} \\\ ...
1
vote
0answers
58 views

Parameterized convex optimization

I'm trying to formulate a game so that at Nash equilibrium I achieve supply equales demand. Then I ran into this problem. For all $i,$ $v_{i}\left(x_{i}\right)$ is concave in $x_{i}$. The value ...
1
vote
0answers
58 views

Closed form for Lagrange dual

Can Lagrange dual always be computed in closed form? Can you give me a simple example where the dual is not analytically computable?
1
vote
0answers
49 views

why is it important to have $\max_x \min_y f(x,y)=\min_y \max_x f(x,y)$?

I am currently trying to understand the minimax theorem of Von Neumann and the improved versions of this theorem. At any case we have the property $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} ...
1
vote
0answers
244 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
1
vote
0answers
47 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
0answers
47 views

General properties of an optimal solution of a convex program

How do we seek certain properties for a solution of a convex minimization problem. For example we want to make sure if the below objective has a symmetric optimal solution: \begin{equation} \min_X ...
1
vote
0answers
37 views

using the ellipsoid algorithm to find a poly time algorithm for the optimization problem

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
1
vote
0answers
131 views

Upper bound for L1-L2 optimization problem

I am interested in the following convex optimization problem: \begin{align*} \max & ||x||_1 \\ \text{s.t.} & ||x-a||_1 \le K \\ & ||b\circ x||_2 \le 1\\ & x \in R^n \end{align*} where ...
1
vote
0answers
94 views

minimum of the function over symmetric body

Let $X$ be a normed space. Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$. We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
1
vote
0answers
164 views

Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem: $\underset{p}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2 \;\; ...
1
vote
0answers
234 views

A convex programming problem involving sum of logarithms of linear functions

Here is a convex programming problem I encountered while working on an estimation problem for a mixture of multinomial distributions. We have a matrix $A_{m \times n}$ containing non-negative real ...
1
vote
0answers
125 views

How to calculate the maximal ellipsoid in a given polyhedron

I am faced with the problem of finding the ellipsoid $B$ ($B$ is a symmetric positive definite matrix) of maximal volume within a convex set $C$ given as a set of linear inequalities $C=\{x| a_i^T x ...
1
vote
0answers
160 views

conjugate function for matrix mixed norm

I am familiar with the conjugate function of the vector norm, which uses the concept of dual norm and is defined as follows: ...
1
vote
0answers
279 views

Is conditional entropy a convex function?

A conditional entropy can be expressed in the following way, $H_{V_t}(V_s) = -\sum_{s,t}p(s,t)\log{p_t(s)} = -\sum_{s,t}p(s,t)\log{\frac{p(s,t)}{\sum_{s'}{p(s',t)}}}$ $s$ and $t$ are defined ...
1
vote
0answers
50 views

Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l\rangle - f_1(x) - f_2(x)$ via convex duality?

I am attemping to solve the argument maximization problem $$\arg\sup_x \{\langle x,l\rangle - f_1(x) - f_2(x)\}\qquad\qquad\qquad\qquad (1)$$ where the functions $f_1$ and $f_2$ are concave but ...
1
vote
0answers
164 views

Convexity of a Set

Consider the following function, $$ f(x, y) = e^{m e^{-y}+n e^{-x}-x-y} \left(a x e^y+b e^x y+c x y\right) $$ where $a, b, c, m$ and $n$ are positive constants. I want to show $f(x, y)$ is ...
0
votes
0answers
12 views

Constraint optimization with lagrangian

I am having trouble regarding the general steps one needs to take in order to solve an constraint optimization using Lagrangian. More specifically, I want to maximize objective equation $f(x,y,z,w)$ ...
0
votes
0answers
13 views

optimal basic feasible solution and optimal solution

When studying Linear Program, I once meet the following theorem However, the proof given by the notes was not clear to me. I would really appreciated that if you can share with me the insight of ...
0
votes
0answers
35 views

Using l1 magic toolbox for compressive sensing : Positive definite matricies.

I'm trying to use l1 magic to reconstruct an image from a single pixel camera I've developed. The test functions used are random binary patterns projected onto the object scene, so each pattern is ...
0
votes
0answers
25 views

dual value of a linear constraint

Assume a minimization problem. The dual of an inequality '<' constraint is the marginal improvement in the objective function (ie marginal reduction) by marginally increasing the right-hand-side ...
0
votes
0answers
16 views

A question Kolmogrov's generalized inequality for projection onto convex sets

Kolmogrov's inequality says that, if $C$ is a convex set, and $P_C(x)$ is an operator for projecting point $x$ into the convex set $C$, if $z = P_C(x)$, then for any $y \in C$ we have $$ (z - y).(x - ...
0
votes
0answers
18 views

closed form solution of a particular convex program

I wish to know if there is a closed form solution of a program of the following form $\max_w x^Tw \text{ such that } \tau_2\| w \|_2 + \tau_1 \| w \|_1 \leq 1, ~\ \tau_1, \tau_2 > 0$ When either ...
0
votes
0answers
22 views

Primal-dual subgradient method

In these notes, an extension of the subgradient method is presented in Section 8 (page 30). The method is described so quickly and neither convergence analysis (compared to classical subgradient for ...
0
votes
0answers
19 views

Proof of sufficient condition of existence of Lagrange multipliers

Consider the optimization problem $$ (P) \quad \inf\{ f(x) : g_i(x) \le 0, i = 1,\ldots, m, x \in \mathbb R^m \} $$ where $f, g_i : \mathbb R^n \to (-\infty, \infty]$ are convex and $0 \ne ...
0
votes
0answers
25 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 ...
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 ...
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 ...
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
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
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
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
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 ...
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 ...
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 ...