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

learn more… | top users | synonyms

2
votes
1answer
59 views

Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
2
votes
1answer
149 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq f(\bar{x})\...
2
votes
0answers
40 views

Solve the linear program

Please help to solve this problem. I am new to this type of problems and any help will be greatly appreciated $$\text{ Minimize } 7x-5y+3z$$ $$\text{ Such that } \ \ \ 0 ≤ x ≤ 6 , -2 ≤ y ≤ 7 , -4 ...
2
votes
1answer
66 views

Solving $ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$

Let $\phi \in \mathcal ( [0,1]^2)$ symetric , can we find a solution to the following minimisation problem? $$ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$$ with $$ F[\...
2
votes
1answer
90 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. p_{k,...
2
votes
1answer
117 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 ...
2
votes
0answers
154 views

How to prove the convexity of the logrithmic gamma function?

Here's what I did: $$\Gamma'(z)=\int_0^\infty \log(t)e^{-t}t^{z-1}dt$$ $$\Gamma''(z)=\int_0^\infty \log^2(t)e^{-t}t^{z-1}dt$$$$\frac{d^2}{dz^2}\log\Gamma(z)=\frac{\Gamma''(z)\Gamma(z)-(\Gamma'(z))^2}...
2
votes
0answers
77 views

Strictly convex self-concordant function

Some definitions: A function $f:R^n\rightarrow R$ is convex[strictly convex] if for every $\lambda\in[0,1]$ [$\lambda\in(0,1)$] and for every $x,y$ [$x\neq y$] in $R^n$ we have $f(\lambda x+(1-\...
2
votes
0answers
129 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book "...
2
votes
1answer
139 views

Convexity of a region on probability simplex

Exercise 2.15 g of Boyd et al Convex Optimization book : On the probability simplex in $\mathbb{R}^n$ where each point $p = (p_1,p_2,p_3,\ldots,p_n)$ corresponds to a distribution for random variable $...
2
votes
0answers
52 views

Semidefinite Program formulation

I have the following problem and would like to formulate that as an SDP. I am not sure how to approach this : A set $S$ is given such that : $$ S = \{P \in R^{n \times m} : ||p_i - c_i|| \leq d_i \}$$...
2
votes
0answers
401 views

Uniqueness of the solution

We know that 1) Minimise of a convex function the unique solution exists 2) Maximise of a concave function the unique solution exists How about 1) Minimise of a strictly convex function? 2) ...
2
votes
0answers
85 views

Is the following problem convex , quasiconvex, or nonconvex?

I want to get the optimal matrix $W$. But I am not sure whether it can be resolved. Note that $W,\mu,\lambda_{1},\ldots,\lambda_{K} $ are variables, others are fixed. Is it convex or quasiconvex or ...
2
votes
0answers
103 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ s.t.~&\left(\mathbf{A}_0+\sum_{i=1}^{K}y_i\mathbf{A}_i\...
2
votes
0answers
112 views

the objective function $\|F\|_F^2$ is quasiconvex in the optimization?why?

I have read a paper, but I can not understand one optimization thoroughly.Generally, Frobenius norm of one matrix, $\|F\|_F^2$, as the objective function is convex, so we can resolve it not using the ...
2
votes
0answers
87 views

How to get the minimum and maximum of one convex function?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The Lagrangian function of $Q$ is $\mathcal{L} = h^H(\hat{f} + e)(\hat{f} + e)^Hh + \...
2
votes
0answers
98 views

The most efficient algorithm to solve the following problem

Is there an efficient optimization algorithm to solve the following problem? $(\alpha,\beta,\gamma,\cdots) =$ argmax $\sum_{i}\log(\alpha a_i+\beta b_i+\gamma c_i+\cdots)$, s.t. $\lambda_1\alpha+\...
2
votes
0answers
60 views

Proving an optimization problem has a rational optimum.

Consider the function $$ J_\gamma(X) = \det\left( I - \tfrac{1}{\gamma^2} (A+BXC)^\mathsf{T}(A+BXC)\right) $$ where $A$, $B$, $C$, $X$ are matrices of real numbers. Further suppose that $B^\mathsf{T}B$...
2
votes
1answer
549 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
2
votes
0answers
31 views

Tractability of a cardinality problem

I have this confusion related to the convexity and tractability of a problem. The given problem is maximize $u^TSu$ subject to $||u||_2 = 1$ and card(u) <= r This is a NP hard problem because ...
2
votes
0answers
85 views

Optimization problem in the Von Neumann Entropy

I have a constrainted optimization problem in the Von Neumann Entropy. In a CVX-like syntax the problem goes as follows: given variable $\mathtt{c(n)}$ $$\begin{align} \text{minimize} \qquad & ...
2
votes
1answer
37 views

Confusion related to explanation of convexity of a function

I was reading this paper where the define an optimization problem as where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because ...
2
votes
0answers
58 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
0answers
24 views

Analogue of Helly’s theorem for non-exact interpolation

Let $\overrightarrow{x}=(x_1,x_2, \ldots ,x_n),\overrightarrow{a}=(a_1,a_2, \ldots ,a_n)$ and $\overrightarrow{b}=(b_1,b_2, \ldots ,b_n)$ be vectors in ${\mathbb R}^n$, with $a_k \leq b_k$ for every $...
2
votes
0answers
192 views

$\{x:Ax\leq 0\}$ contains a subset of type $\{x:A'x=0, ax\leq 0\}$

If $C:=\{x:Ax\leq 0\}\neq\{x:Ax=0\}$, an independent set of rows of $A$ can be chosen, one denoted by $a$ and the others put as rows into a matrix $A'$, such that $\{x:A'x=0,ax\leq 0\}\subseteq C$. ...
2
votes
0answers
103 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
2
votes
1answer
78 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 ...
2
votes
1answer
303 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} |...
2
votes
0answers
163 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 $A$,...
2
votes
0answers
45 views

Convex formulation of a nearly convex optimization problem

The following problem has come up in my studies of logarithmic norms. I wish to find $\mu \in \mathbb{R}$ and a positive semidefinite $B$ so as to minimize the convex function $c \mu - \log\det(B)$ ...
2
votes
0answers
117 views

Examples of functions that are Lipschitz w.r.t. Schatten p-norm?

A convex function $f$ is $R$-Lipschitz w.r.t. to a norm $\|\cdot\|$ if for all points $a, b$ we have $|f(a)-f(b)| \leq R\|a-b\|$. For a real symmetric $n\times n$ matrix $A$ with eigenvalues denoted ...
2
votes
0answers
163 views

How to minimize the supremum of two convex functions?

Given $f_1(x)$, $f_2(x)$, $x\in \mathbb{R}^d$, two convex functions, we define the following problem: $\underset{x\in C}{{\rm minimize}}\,{\rm max}\left(f_{1}\left(x\right),f_{2}\left(x\right)\right)$...
2
votes
0answers
171 views

Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables

I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this. Read ...
2
votes
0answers
56 views

convex optimization with inconsistent constraints

If you have a problem in convex optimization where all $N$ constraints ($N >> 0$) yield no possible solution but you are able to rank, or weight the constraint in terms of their importance are ...
2
votes
0answers
84 views

Convexity of a function

Suppose we have $F: R^n \longrightarrow R$ , $P: R^n \longrightarrow R^n$ and $G: R^n \longrightarrow R$ all nice- let's say given by polynomial and $P$ is invertible - such that $F(x) =G( P(x) )$. ...
2
votes
0answers
54 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 b\}...
2
votes
0answers
80 views

Find a vector such that its matrix product is positive in every element

Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick ...
2
votes
0answers
371 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 ...
2
votes
0answers
415 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
2
votes
2answers
67 views

How do I solve the following equality-constrained quadratic program?

I am trying to minimize: $$(x_1-k_1)^2 + (x_2-k_2)^2 + (x_3-k_3)^2 +\ldots+ (x_n-k_n)^2$$ subject to following equality: $$B = 1 + x_1 + x_2 + x_3 + x_4+\ldots+x_n.$$ Is there a closed form ...
1
vote
1answer
1k views

is nonlinear least square a non convex optimization?

linear least-squares are convex optimization. Are nonlinear least squares also convex optimization? Can someone please give some simple examples?
1
vote
2answers
124 views

Legendre transform of a norm

Let $||\cdot||$ be a norm on $\mathbb{R}^n$, with dual norm $||x||_* :=\max_\limits{y:||y||\leq 1}y^T x$. I'd like to show $$\max_{x \in \mathbb{R}^n}(x^T d-||x||)=\begin{cases} 0 & \text{ if } ||...
1
vote
2answers
2k views

How to prove a set of positive semi definite matrices forms a convex set?

Let $C$ be the set of positive semi-definite matrices, how can I prove it is a convex set?
1
vote
3answers
62 views

Inequality involving a convex function

Do the points that satisfy an inequality involving a convex function constitute a convex set? Specifically if $x \in \mathbb R^n$ and I have a function $f(x)$ then is the set $\{x \mid f(x) \le 0\}$ ...
1
vote
2answers
100 views

Why is the constraint $\|w\| = 1$ non-convex?

Related: Why is this function, related to SVM derivation, non-convex? I am studying notes which cover the derivation of SVM. The intuition is the geometric margin should be maximized in order to ...
1
vote
1answer
448 views

What's the difference between interior and relative interior?

As defined in Convex Optimization written by Stephen Boyd, both interior and relative interior seems to describe a same thing: a set that peels away it's boundary points. So what on earth is the ...
1
vote
2answers
41 views

Is f(x)=-log(x) a closed function?

I am reading Convex optimization written by Stephen Boyd. In page 640, there is an example said \begin{equation} f(x)=-log(x) \end{equation} is a closed function. But this function seems does not ...
1
vote
2answers
623 views

When is the difference of two convex functions convex?

Assume that $X$ is a finite dimensional Banach space. I know that in general if two functions $f:X \mapsto \mathbb{R}$, $g:X \mapsto \mathbb{R}$ are convex then the function $(f-g):X \mapsto \mathbb{R}...
1
vote
2answers
97 views

The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$. The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where $D(\alpha)=\frac{...
1
vote
2answers
2k views

Carathéodory's theorem

Carathéodory's theorem says "If $C\subset R^n$, then every point from ${\rm conv}\; C$ can be expressed as a convex combination at the most of $n+1$ elements from $C$" In every proof I found, it ...