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

learn more… | top users | synonyms

2
votes
0answers
33 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)$ ...
0
votes
0answers
33 views

How can I reformulate my problem to make it convex?

I would like to find the symmetric positive definite matrix $S\in \mathcal{M}_{m,m}$ that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex ...
2
votes
0answers
67 views

the dual of the dual is the primal?

Consider a convex optimization problem (call it $P$). Consider its dual (call it $D$). Is it true that the dual of $D$ is $P$? For linear programming, it is true. I'd just like to know under which ...
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 ...
0
votes
0answers
240 views

Gradient Descent with nonlinear constraint on Symmetric positive definite matrix space

I would like to find the stationary point $S_*$ (global minimum) that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex in Convexity of ...
1
vote
1answer
52 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
2
votes
2answers
59 views

What are the relations between these two minimizations

What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$ and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$ ?
1
vote
2answers
265 views

Maximize the product of linear functions

Suppose $f(x,y) = \prod_{i=1}^n (a_ix+b_iy)$ where $n$ is a constant larger than 500, and $a_i>0$, $b_i>0$ are known coefficient. There is only one global maximum. What's the most efficient ...
0
votes
2answers
93 views

An eigen problem

$K$ is a symmetric positive semidefefinit matrix. $K1 = 0$ (i.e. The sum of elements in each row is $0$. Or in other words matrix $K$ is centered. From this we conclude the smallest eigenvalue of $K$ ...
1
vote
2answers
486 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?
3
votes
1answer
759 views

Why is this composition of concave and convex functions concave?

Please forgive my ignorance. I have a quick silly question about a statement given without proof in Convex Optimization by Boyd and Vandenberghe (page 87). Suppose $\mathbb{R}_+^n$ is the set of ...
1
vote
1answer
58 views

linear equivalent min{} constraint

Activities are assigned to venues. Each activity $a_i$ has maximum size $b_i$ and demand $c_i$. Each venue $v_j$ has maximum size $d_j$. An activity can be assigned to multiple venues, and we need to ...
2
votes
2answers
120 views

straightforward way to determine if this set is convex?

straightforward way to determine if this set is convex? $Z=\left\{x\in\mathbb{R}^2:3x_1^4-x_1x_2+x_2^4\le x_2,x_1>2,x_2>2\right\}$ I know I can try by manipulation of linear combination of two ...
0
votes
1answer
22 views

Is the weighted graph matching problem a convex problem?

According to Umeyama, the weighted graph matching problem can be formulated as $min_P || PA_GP^T - A_H ||$ s.t. $P$ is a doubly stochastic matrix where $A_G$ and $A_H$ are n-by-n matrices How can ...
0
votes
1answer
327 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
2
votes
2answers
431 views

Linear optimization problem: Minimizing a linear function over an affine set.

The problem is as follows: Give an explicit solution of the linear optimization problem below. $$ \text{minimize}\ c^Tx \\ \text{subject to}\ Ax\ =\ b $$ No other information is given. My ...
3
votes
2answers
83 views

About the convexity of Ky Fan's norm

As we know, the Ky Fan norm is convex, and so is the Ky Fan k-norm. My question is, does this imply that the difference between them is a non-convex function, since it results from "difference between ...
2
votes
0answers
83 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 ...
5
votes
0answers
155 views

Need advice: what should be my next step?

I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
9
votes
2answers
340 views

On the convexity of element-wise norm 1 of the inverse

Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$ \|A\|_1= \sum_{i,j} |A_{i,j}|. $$ Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
1
vote
2answers
82 views

computational strategy for solving convex-concave minmax problem

Assume f(x,y) is convex in $x$ and concave in $y$. Then \begin{equation}\min_x \max_y f(x,y)\end{equation} is globally solvable, because f is convex in x (max of convex is convex.) But can we find a ...
2
votes
1answer
2k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
2
votes
1answer
65 views

Convex relaxation for the complement of Lorentz cone

Is it possible to obtain a convex relaxation for $$ \{ (x,t): t \le \|x\|_2\} \in \mathbb{R}^{d+1} $$ where $x \in \mathbb{R}^d$ and $\|x\|_2$ is the usual Euclidean norm, by moving to higher ...
2
votes
1answer
242 views

Maximizing the number of non-crossing lines between a number of points

Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross. Hoping for a polynomial time algorithm, I ...
1
vote
1answer
74 views

Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex?

Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$ However I don't know if it is possible to find ...
0
votes
2answers
70 views

Any idea which matrix theorem this is?

I came across a theorem that boyd uses to convert the simplex to the form of a polyhedra. I don't know anything about this theorem. Theorem states: If $B$ has rank $k$, then we can find two matrices ...
0
votes
1answer
35 views

Is $\{x\in\mathbb{R}^4: x\ge 0, \, x_1x_2+x_3x_4\ge\alpha\}$ convex?

Is $\{x\in\mathbb{R}^4: x\ge 0\, \mbox{ and }\, x_1x_2+x_3x_4\ge\alpha\}$, for $\alpha>0$, a convex set? A related question is this one: Is $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \in \mathbb{R}_+$, a ...
3
votes
2answers
171 views

How many points to find a polynomial?

I would like to fit a formula $ax^b + cx^d+ e$ to a set of points. I have two questions. If my data were perfect, how many points do I need in the worst case to get $a,b,c,d,e$ exactly? If my data ...
0
votes
1answer
53 views

non convex optimisation

\begin{eqnarray} {\textbf{maximise}} \hspace{2mm} Ar^{-(a+b)} + Br^{-(a+b+c)}-C \nonumber \end{eqnarray} such that, \begin{eqnarray} c= l(h-m_{0}) \nonumber\\ m_{1} \leq h \leq m_{2} \nonumber\\ ...
1
vote
0answers
112 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 ...
0
votes
1answer
290 views

Convex Functions: Property Proof

Let $f\colon S\to \mathbb R$ be a $C^1$ function on a convex domain $S \subseteq \mathbb R^n$. Show that if $f$ is convex then $(\nabla f(x) - \nabla f(y)) \cdot (x-y) \ge 0$ for all $x,y \in S$. ...
0
votes
0answers
98 views

Maximizing a set of function

Consider a utility function $U_i$, for every individual $i=1,...,n$. $U_i(c_i) = \left\{ \begin{array}{l l} d_i & \quad \text{if $c_i$ < $c_i^{low}$}\\ m_i(c_i - a_i + b_i) & ...
0
votes
1answer
338 views

Maximization of sum of two functions

Is there any relationship similar to the following. Let $X$ be the maximum of functions $f_1(x)+f_2(x)$. Let $X_1$ be a maximum of $f_1(x)$ and let $X_2$ be a maximum of $f_2(x)$. Is there any ...
1
vote
2answers
461 views

A question dealing with the convexity of functions involving the absolute value

Just beginning to learn convex analysis and optimization, I have some inquiries to make with regard to the absolute value function $f(x)= |x|$. This function is clearly convex, but since we know that ...
1
vote
0answers
150 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
1answer
207 views

Convex Functions: Proofs

Let $f$ be a monotone nondecreasing function of a single variable which is also convex. Let $g$ be a convex function defined on a convex set $G$. Is it true that the composition of these functions ...
1
vote
1answer
126 views

Unboundedness of Quadratic Function

I was reading about Trust Region Methods for solving Nonlinear Optimization problems are came across this statement in my notes: If the quadratic approximation to the function $f(x)$ which is given ...
1
vote
1answer
137 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, ...
2
votes
2answers
210 views

maximize log determinant subject to a linear constraint

Does anyone know any efficient method to solve the following problem? $ (\alpha,\beta) = \text{argmax} \log \det (\alpha K_1 + \beta K_2)$ s.t. $c_1 \alpha + c_2 \beta = c_3, \alpha\geq0, \beta\geq ...
0
votes
1answer
242 views

Convex function necessary condition

For a function to be convex it should have a convex domain besides the first-order, second-order conditions. Why do we need that the domain of the function should also be convex? Edit: What I am ...
1
vote
4answers
208 views

Bounded linear function implication

In Stephen Boyd's book boyd uses the theorem that a linear function is bounded below on $R^m$ only when it is zero. I can't really digest this. Csn someone tell me why this holds? I mean if I take a ...
1
vote
2answers
236 views

Affine dimension of a simplex

In Stephen Boyd's book on Convex optimization he points out that k+1 affinely independent points form a simplex with affine dimension k. My understanding of affinely independent points is that no 3 ...
1
vote
1answer
609 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?
5
votes
1answer
515 views

Minimizing l-infinity norm of complex vector

I have an $n$-dimensional complex vector space, and I want to minimize the $L_\infty$ norm of a point that is constrained to an $m$-dimensional affine subspace. That is, Given $\mathbf{z} \in ...
1
vote
1answer
120 views

directional derivative sublinear of a convex function sublinearity problem to show

How to show the following: If $f:\mathbb R^d \rightarrow \mathbb R$ is convex then its directional derivative is sublinear? Thank you...
2
votes
1answer
60 views

Possibility of Unboundedness in Least Squares Minimization

Suppose we have the quadratic minimization problem \begin{equation} \min_x \frac{1}{2} x^TPx + q^Tx +r \end{equation} We know that when $P$ is symmetric positive semi-definite, but the optimality ...
2
votes
2answers
115 views

Constrained maximization problem

I need help with the following optimization problem $$ \max\;\alpha\ln(x(1-y^2))+(1-\alpha)\ln(z) $$ where the maximization is with respect to $x,y,z$, subject to \begin{align} \alpha ...
2
votes
2answers
76 views

Geometric difference between $x^TAx$ and $x^TAx + b^Tx + c$

What is the difference between $x^TAx$ and $x^TAx + b^Tx + c$ geometrically? Some analogous examples from quadriatic equations would be great.
0
votes
1answer
77 views

convex conjugate $f^*$ is proper if both $f$ and $f^{**}$ are

If $f$ and $f^{**}$ on $\mathbb R^d$ are proper functions where $f^*$ stands for the convex conjugate of $f$ why does that follow that $f^*$ is proper, too? Thanks a lot...
1
vote
2answers
238 views

Positive Second derivative and convexity

Let $f:\mathbb R\to\mathbb R$, maps a point $x \in \mathbb R$. $f$ is twice differentiable. Show that if second derivative is positive for all $x$ then $f$ is convex Is there anyway to prove this ...