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

learn more… | top users | synonyms

1
vote
3answers
181 views

What is the dual of this optimization problem?

Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am looking for the dual of the following optimization ...
1
vote
0answers
155 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 \} ...
0
votes
1answer
25 views

Coding Distributions as a Convex Constraint

In convex optimization, how can we impose a constraint that a variable has certain distribution? e.g. elements of vector $v$ have power law distribution?
1
vote
0answers
90 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 ...
2
votes
0answers
323 views

SDP relaxation of non-convex QCQP and duality gap

Short version Is there a duality gap between a QCQP problem and the SDP problem obtained through lagrangian relaxation? A paper I'm studying is using this fact, but I cannot achieve the authors' ...
3
votes
1answer
148 views

minimization problem on differential equations - optimal control

I am trying to minimize an time-integral of a linear function with respect to differential equations. The problem is formally defined as follows: Given $\lambda< \mu_1, \mu_2$ fixed ...
1
vote
1answer
184 views

Are these convex optimization problems equivalent?

Consider the optimization problem $$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$ where $c \in \mathbb{R}^n$, and ...
0
votes
1answer
71 views

A property of the minima of a sum of convex functions, take 2

This is a follow-up to my previous question. Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is ...
2
votes
1answer
482 views

A property of the minimum of a sum of convex functions

Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is achieved, denoting $$x_i = \arg \min_{x \in ...
0
votes
1answer
702 views

generalized inequalities defined by proper cones

The generalized inequality defined by a proper cone $K$ is that $x \ge_{K} y$ if $x-y \in K$ for $x,y \in K$. Does this means that for any $x \in K$, we have $x \ge_{K} 0$ since $x - 0 = x \in K$ ? ...
1
vote
1answer
85 views

Convergence rate when solving L1 regularized optimization via coordinate descent with tiny step?

Wondering if there is an established result for the convergence rate when solving L1 regularized optimization via coordinate descent with tiny step? By "tiny step" I mean the step is always set to a ...
1
vote
1answer
216 views

Strongly convex function

There is a $\sigma$-strongly convex function, $f(x')\ge f(x)+ \langle x'-x,\mu\rangle +\frac{\sigma}{2}\left|x'-x\right|^2$ where $\mu \in \partial f(x)$, $\mu ' \in \partial f(x')$. How could I get ...
1
vote
1answer
251 views

Closed form solution of a convex optimization problem

Suppose we want to solve the following optimization problem: \begin{equation*} \begin{aligned} & \underset{x,y,z}{\text{minimize}} && x(a-y) \\ & \text{subject to} && ...
0
votes
2answers
81 views

Is it a convex function?

Let $f(.)$ be a function. If $f(X)$ is a convex function of $X$, where $X$ is a matrix. Is $f(AXB)$ also a convex function of $X$? ($A$ and $B$ are fixed matrices).
1
vote
1answer
92 views

Convexity of product of elements from two convex set

Given two convex set $X\subseteq \mathbb{R}^N$,$Y\subseteq \mathbb{R}^{N\times N}$ Given a $x\in X$, is the set $\{z|z=yx,\forall y \in Y\}$ convex? If no, by adding what can force it to be convex? ...
3
votes
3answers
1k views

Deriving the sub-differential of the nuclear norm

Let $f(K)=||K||_*$, the nuclear norm (sum of the singular values) of $K=U\Sigma V^T$. How can one compute the subdifferential $\partial F$. This may be a basic question, I'm trying to work my way ...
0
votes
1answer
440 views

optimal solution

Consider the standard form polyhedron $P = \{x | Ax = b, x ≥ O \}$. Suppose that the matrix $A$ has dimensions $m \times n$ and that its rows are linearly independent. For each one of the following ...
3
votes
1answer
111 views

Alternative representation for Perron Frobenius Eigenvalue

While explaining the application of Geometric programming to Minimizing Spectral radius Boyd says that $\lambda_{pf}$ can also be characterized as: $\operatorname{inf}\{\lambda|\exists{v}>0, ...
3
votes
1answer
210 views

Hessian of a function that takes matrix arguments

I have a function that that takes a matrix and returns a scalar, $f : \mathbb{R}^{m\times n} \rightarrow \mathbb{R}$. I know how to calculate the derivative of this function with respect to the matrix ...
0
votes
1answer
41 views

Prove a set in $\mathbb{R}^2$ is convex.

Let $$\Omega = \{(x_1,x_2)\in\mathbb{R}^2:x_1^2-x_2\leq 6\}$$ Prove that $\Omega$ is a convex set from first principles using the convex combination. edit: Thanks Ewan for that, but I am trying ...
0
votes
0answers
75 views

Is the correlation function convex or not?

Suppose the function for statistical correlation is a non linear constraint in a non linear programming model: $$ \frac{\sum_{t=1}^T (p_t - \bar{p})(R_t - \bar{R})}{\sqrt{\sum_{t=1}^T (p_t - ...
0
votes
2answers
78 views

Anyone saw this interesting function before?

Say $\theta\in\Re^n$ and $\theta_i\in(0,1)$ for all $i$. Define $$ f(\theta) = \frac{1}{n}\sum_i^n\{(1-\theta_i)\log(1-\theta_i)+\theta_i\log\theta_i\} $$ It is easy to see the minimizer of ...
0
votes
1answer
79 views

Rewriting a quadratic Matrix equation as a quadratic vector equation

Consider the set of $N \times N$ matrices $\{W_i\}_{i=1}^{i=L}$, set of $N \times 1$vectors $\{g_i\}_{i=1}^{i=L}$ and $\{h_i\}_{i=1}^{i=L}$. Now consider the following sum \begin{align} ...
0
votes
1answer
301 views

relation between size of matrix and condition number

I have a matrix A of size NxM. Is there any relationship between size of a matrix A with the condition number ? I am computing the pseudo inverse (pinv in matlab ) ...
0
votes
1answer
233 views

Is this sum of convex and concave functions a convex function?

Is this a convex function in $X$, where all the entries are real and $Y,\beta$ are constants where $X,Y$ are rectangular matrices and $\beta$ is a constant vector and $A,B$ are constant p.s.d ...
3
votes
1answer
156 views

Strictly Convex Function and Well-Separated Minimum

Suppose $\Theta \subset \mathbb{R}^d$ is a convex set, and $f:\Theta \rightarrow \mathbb{R}$ is a strictly convex function that has a minimum at $\theta_0\in\Theta$. Is it true then that $\forall ...
3
votes
2answers
980 views

What is an example of non-convex cone

I was studying Stephen Boyd's textbook on convex optimization. It says "A set C is called a cone or nonnegative homogeneous, if for every x $\in$ C, we have $\theta x \in $ C. A set C is a convex cone ...
1
vote
0answers
162 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
1answer
78 views

Distance between a point to a $2d$ ellipse in $3d$ ambient space

Suppose we are working in the 3D Euclidean space. We are given an arbitrary point $p$ and a 2d ellipse: $$E=\{x:x^TQx\leq1,x^Tq=0\},$$ where $Q$ is a positive definite matrix and $q$ is an ...
10
votes
2answers
2k views

What is the difference between minimum and infimum?

What is the difference between minimum and infimum? I have a great confusion about this.
2
votes
1answer
75 views

Proof for certain matrix results?

There are certain results of matrices that Stephen Boyd uses often in his book on Convex optimization. Can someone provide me proof for the results I have enumerated below: If $B \in S^n$ and $A \in ...
0
votes
2answers
264 views
0
votes
1answer
74 views

Quasi-Convexity

Can I get the conclusion that the function of matrix $P$ and $Q$ \begin{equation} \mathrm{tr}\left( PQ\right) \end{equation} is a quasi-concave function for $P>0$, and $Q>0$? It is true for ...
6
votes
0answers
291 views

Is this question solvable? $2$ non-linear equations and the proof that the solution is unique (with asymmetric bounty option)

As mentioned in the title I want to show the uniqueness of the solution to $2$ non-linear equations. However, it seems that I can not solve this question with my current mathematical knowledge. More ...
0
votes
1answer
273 views

Lipschitz constant for optimization of multivariate function

I intend to implement an optimization algorithm which requires the computation of the Lipschitz constant. My function is a multivariate function with more than 50 variables. I am wondering whether ...
3
votes
2answers
494 views

When finding root, does Newton's method fail if the function is non-differentiable?

According to wikipedia's description, the Newton's method finding a root presumes a differentiable function. Then, will it fail when encountering non-differentiable function? For example, can it find ...
1
vote
0answers
54 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?
0
votes
1answer
227 views

Fenchel conjugate of non smooth function

Is it valid to derive Fenchel conjugate for a non-smooth function? Checking its definition $f^*(y) = sup_{x \in \mathsf{dom}f} (y^Tx - f(x))$, I think this would be OK, but I'm not sure about that. ...
3
votes
1answer
107 views

decomposing PSD block matrix into two PSD block matrices

Given $Q = \left( \begin{array}{ccc} A + B & C \\ C^T & D\end{array} \right) $, where we know that $Q, A, B, D$ are all positive semi-definite, square, but not necessarily equally sized ...
1
vote
1answer
494 views

How to prove this function is quasi-convex/concave?

this is the function: $$\displaystyle f(a,b) = \frac{b^2}{4(1+a)}$$
2
votes
1answer
178 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
1
vote
1answer
105 views

Some convex optimization questions

Is minimizing number of $\{{i : x_i \ne 0}\}$ subject to $Ax=b$ a convex problem? Why is it computationally hard? What is polar cone of $\{x \in \mathbb{R}^2:0\le x_1 \le x_2\}$? Are ...
2
votes
1answer
153 views

Prove or disprove that the given expression is “always” positive

I have previously asked a question and I tried to solve it by my own and it led to the question below: Prove or disprove that ...
1
vote
0answers
152 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 ...
0
votes
1answer
66 views

Projection: two closed convex sets

I am really struggling with this problem: $C$ and $D$ are closed, convex subsets of ${R}^n$ with non-empty intersection, i.e. $C \cap D \neq \emptyset $ . Is it true that projection $p_{C\cap ...
2
votes
0answers
157 views

Optimization problem about large matrices

I'd like to solve the following optimization problem: Find non-negative scalar $a$, $b$, $c$ to minimize $\| (D-(aA+bB+cC+D^{-1})^{-1})y\|^2+2\operatorname{trace}((aA+bB+cC+D^{-1})^{-1})$ where ...
3
votes
2answers
143 views

Convexity of Quadratic equation Inequality?

Solving an inequality of the form $x^TAx\geq0$ or $x^TAx\leq0$ is straightforward. I mean we have to check if A is positive semidefinite or negative semidefinite. But what would be the solution to the ...
7
votes
1answer
242 views

How to understand convex duality intuitively

Is there an intuitive way to understand the convex duality? If the primal problem is minimization, the dual is maximization over another set of variables - but I would love to have a geometric ...
2
votes
1answer
234 views

Simple resource for Lagrangian constrained optimization?

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
2
votes
1answer
291 views

Is this function quasi convex

I have a function $f(x,y) = y(k_1x^2 + k_2x + k_3)$ which describes chemical potential of a species ($y$ is mole fraction and $x$ is temperature) I only want to check quasi convexity over a limited ...