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

learn more… | top users | synonyms

1
vote
1answer
42 views

Optimization of several cost functions together

Say I want to minimize several functions together: $$\min \lVert f_1\rVert, \min \lVert f_2\rVert, \min \lVert f_1-f_2\rVert$$ where $\lVert f\rVert$ is the $L_2$ norm of $f$. I am wondering can I ...
0
votes
0answers
52 views

Approximation of largest eigenvalue

What is an approximation for the largest eigenvalue of a matrix $A $? I mean, I am looking for some expressions that can be used as approximation for largest eigenvalue
1
vote
1answer
46 views

Convex Function Help and Counterxample

Given $g: \mathbb{R}^n \to \mathbb{R}$ is convex and $f:\mathbb{R} \to \mathbb{R}$ is convex and increasing. Show that $(f \circ g): \mathbb{R}^n \to \mathbb{R}$ is convex. I had no problem proving ...
2
votes
0answers
75 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 ...
1
vote
1answer
35 views

Approximate an exponential function

I have an optimization problem, where I would like to minimize $$F=\exp(\mathrm{trace}(A)+\frac{1}{2}\mathrm{trace}(A^2)-\lambda)$$ where $A$ is a non-negative matrix. Is it possible to replace $F$ ...
0
votes
1answer
226 views

Composition of convex function and affine function

Let $g: E^{m} \rightarrow E^{1}$ be a convex function, and let $h: E^{n} \rightarrow E^{m} $ be an affine function of the form $h(x)=Ax+b$, where $A$ is an $m \times n$ matrix and $b$ is an $m \times ...
-1
votes
1answer
84 views

Prove or disprove the concavity of the function [closed]

Prove or disprove the concavity of $f$ over the following two domains. $$f(x_1,x_2)=10-2(x_2-x^{2}_{1})^{2}$$ defined either over $$S_1=\{(x_1,x_2) : -1\leq x_1 \leq 1, -1 \leq x_2 \leq ...
-1
votes
2answers
39 views

Constraints in optimization; redundant hardness?

This is not an accurate mathematical problem, and rather a philosophical and ambitious question. As far as I know, unconstrained problems are easier than constrained problems; right? This is mostly ...
1
vote
1answer
229 views

convexity of matrix “soft-max” (log trace of matrix exponential)

In convex optimization it is often convenient to use the following smooth approximation to $\max\{x_1, \ldots, x_n\}$: $$ f_\lambda(x_1, \ldots, x_n) = \frac{1}{\lambda}\log \sum_{i = 1}^n{e^{\lambda ...
2
votes
1answer
656 views

How to find closest positive definite matrix of non-symmetric matrix

I have a matrix A given and I want to find the matrix B which is closest to A in the frobenius norm and is positiv definite. B does not need to be symmetric. I found a lot of solutions if the input ...
1
vote
0answers
20 views

Uniqueness of the solution to a quadratic opt problem

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
8
votes
1answer
270 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
0
votes
2answers
44 views

Show that the set of points that are nearer $a$ than $b$ with respect to $\lVert \cdot \rVert_2$ is convex

I am trying to show the above statement: Show that the set of points that are nearer $a$ than $b$ in the sense of Euclidean $\lVert\cdot\rVert_2$ are convex. My attempt This follows from the ...
2
votes
1answer
127 views

The convex conjugate of a quadratic form with positive semi definite matrix

I want to find the convex conjugate (Legendre transform) of a quadratic for $1/2x^{t}Qx$ when $Q$ is positive semi-definite. If Q is non-singular, the solution is easy - the gradient is $y-Qx=0$ so ...
2
votes
2answers
214 views

What change of variables, if any, transforms this nonconvex problem into a convex one?

I'm looking for a convex reformulation, if any exists, of the following minimisation problem: Let $A$ be a symmetric, positive definite $n \times n$ matrix, and $b \in \mathbb{R}^n$. Minimise ...
0
votes
1answer
72 views

Cyclic monotonicity of sub-differential domain and convex property

I am looking for hints/proof's overview/reference about this proposition : Let $S\subset \mathbb{R}^d\times\mathbb{R}^d$. There exist a convex function $\phi$ such that $S\subset \partial\phi$ ...
2
votes
3answers
101 views

Is this set convex ?2

Is this set convex for every arbitrary $\alpha\in \mathbb R$? $$\Big\{(x_1,x_2)\in \mathbb R^2_{++} \,\Big|\, x_1x_2\geq \alpha\Big\}$$ Where $\mathbb R^2_{++}=[0,+\infty)\times [0,+\infty)$.
2
votes
0answers
48 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 ...
1
vote
0answers
223 views

Minimum L1 norm may not obtain the sparsest solution?

Here is a paper called For Most Large Underdetermined Systems of Equations, the Minimal L1-norm Near-Solution Approximates the Sparsest Near-Solution. However, I did not quite get its definition of ...
1
vote
0answers
76 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 ...
1
vote
1answer
109 views

minimum trace norm on the set of matrices with fixed diagonal entries

What is the min nuclear norm (sum of singular values) on all $n \times n$ matrices$A$ whose diagonal is fixed. i.e. $diag(A) = v$ Is it true that the diagonal matrix is a minimizer?
1
vote
1answer
44 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
2
votes
2answers
98 views

Verifying the convexity of some function

Convex function: We will say that $f:X\rightarrow R$ is convex function if for every $\lambda\in [0,1]$ and for every $x,y\in X$ ($X$ is convex space) $f(\lambda x+(1-\lambda)y)\leq\lambda ...
0
votes
1answer
45 views

Proximal mapping scaling property

According to this presentation it holds that for $h(x) = f(\lambda x)$ it holds that $prox_h(x) = \frac{1}{\lambda} prox_{\lambda^2 f}(\lambda x)$ where the proximal operator is defined as ...
0
votes
1answer
74 views

Strictly positive solution of linear equations

Suppose $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$, and $b\in \mathcal{R}(A)$. Show that there exists an $x$ satisfying $x \succcurlyeq 0$, $Ax = b$ if and only if there exists no ...
1
vote
1answer
130 views

Free software or algorithm for Second-Order Cone Program

I need to solve the following optimization problem: $$ \mathbf{x}^\ast = \operatorname{argmin}_{\mathbf{x}} \Vert \mathbf{Rx} \Vert_2^2 \;\;\; \mathrm{s.t.} \;\;\; \mathbf{s}^\mathrm{H} \mathbf{x} = ...
3
votes
1answer
145 views

Lagrange dual of a sum of convex functions

Given a set of convex functions $f_i(x)$ and convex sets $X_i$ in $\mathbb R^n$ I need to find the Lagrange dual problem for the problem $\min \sum{f_i(x)} , x \in X_i \forall i$. There is of course ...
1
vote
2answers
255 views

Why the unit circle in $\mathbf{R^2}$ has one dimension?

When I was reading 'Convex Optimization, Stephen Boyd', I was wondering of following steps Consider the unit circle in $\mathbf{R^2}$, $i.e.$, $\{x\in\mathbf{R^2}|x^2_1+x^2_2=1\}$. Its affine hull ...
0
votes
1answer
88 views

Lagrangian dual for the sum of norms

I would like some help in deriving the Lagrangian dual function of a sum-of-norms minimization problem : $\sum{||A_{i}x-b_{i}||}$ when $A_{i}$ are matrices, and $b_{i},x$ vectors. I understand I can ...
0
votes
2answers
88 views

machine learning optimization

I was studying SVM and I am having problems in the conversion of this optimization problem into another : and gamma_hat is defined by I had to paste the images because I was having troubles with ...
3
votes
2answers
305 views

Recovering the solution of optimization problem from the dual problem

In the context of (most of the times convex) optimization problems - I understand that I can build a Lagrange dual problem and assuming I know there is strong duality (no gap) I can find the optimum ...
0
votes
1answer
51 views

Finding the Expansion of a Separable Convex Optimization Problem

Hi there is a convex optimization problem in this paper which I am trying to implement in mosek. The author specifies that they also implement it using the separable optimization method. Specifically ...
0
votes
1answer
58 views

SOCP formulation: wrong inequality direction in constraints

The problem is constrained by a set of inequalities in the form of $$ \| A_i\mathbf{x}\|\geq \mathbf{y_i^Tx} $$ where x is a n-vector of unknowns, $A_i$ are matrices and $y_i$ vectors. Is it possible ...
0
votes
1answer
59 views

Probability that a $n$-dimensional Gaussian falls into a half-space

For $a \in \mathbb{R}_{\ge 0}^d$ and $b \in \mathbb{R}_{\ge 0}$, we can define a half-space as the set of points $x \in \mathbb{R}^d$ such that $a \cdot x \le b$, namely, $$\mathcal{H}(a,b) = \{x \in ...
1
vote
2answers
74 views

Trace of quadratic function with 2 PSD matrices - convex?

If A & B are positive semi-definite, is this always convex: $$ trace(XAX^TB) $$ There was a similar question asked here: Trace of a quadratic function, Convexity and here: Confusion related to ...
2
votes
1answer
89 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 ...
1
vote
1answer
118 views

how to construct the Lagrangian dual problem?

The primal optimization problem is, \begin{align*}\min_x\;&f_0(x)\\ \text{s.t.}\;&f_i(x)\le0\\ &h_j(x)=0\end{align*}, to construct the dual problem, I form the Lagrangian, ...
2
votes
1answer
49 views

What is the name of this object?

Suppose I have a convex set $K\subset X$, where $X$ is say a real Hilbert space (for simplicity). Then, given some $a\in \Bbb{R}$, let $$ \hat{K}=\{x:\langle x,y\rangle \leq a \;\forall y\in K\} $$ ...
1
vote
2answers
96 views

What is the motivation behind strong convexity

Definition : A function is said to be $\beta$-strongly convex if, $f(\theta w + (1-\theta) w') \le \theta f(w) + (1-\theta) f(w') - \frac{\beta}{2}\theta(1-\theta)(w-w')^2$ What is the motivation ...
4
votes
3answers
220 views

Newton's method intuition

In optimisation the Newton step is $-\nabla^2f(x)^{-1}\nabla f(x)$. Could someone offer an intuitive explanation of why the Newton direction is a good search direction? For example I can think of ...
4
votes
1answer
405 views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
0
votes
1answer
50 views

Prove that proximal function is convex

How to prove that the proximal function $$ \Phi (y) \equiv \min_x \left(f(x)+\frac{1}{2} ||x-y||_2^2\right) $$ is a convex function of $y$ if $f(x)$ is a convex function of $x\in \mathbb{R}^n $? ...
1
vote
2answers
131 views

Application of Fenchel Young- Inequality

i'm stuck on the weak duality ineqiality. For $X,Y$ euclidean spaces: $f: X\rightarrow (-\infty,\infty]$, $g: Y\rightarrow (-\infty,\infty]$ and $A:X\rightarrow Y$ linear bounded mapping. I want to ...
2
votes
1answer
56 views

How to prove a set is convex

Let $E = \{x\mid (x - c)^{T} P^{-1} (x-c) \le 1 \}$, where $P$ is symmetric positive definite. Show that $E$ is convex. Here is what I did. It seems like $E$ is an ellipsoid. We want to show that ...
1
vote
1answer
199 views

Sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
1
vote
1answer
93 views

Property for the subdifferential and duality mapping in context of the Moreau-Yosida regularization

I have a question arising from the Moreau-Yosida regularization in Banach spaces. The real Banach space $X$ and its dual $X^*$ are both reflexive strictly convex, $f:X \rightarrow \mathbb{R} \cup ...
0
votes
1answer
55 views

Convexity of a second order cone

Does the following set define a second order cone? Anyway, is it a convex set? $(x,t)$ so that $\lVert(Ax+b)\rVert^{2} \le t(c^{t}x+d)$ $x \in R^{n}$ (A being a matrix, b,c vectors of the ...
1
vote
0answers
39 views

Is $A^TP+PA<0$, $P>0$ and $A^TP+PA\leq-I$, $P\geq I$ equivalent?

Consider the LMI, where $A$ is a Hurwitz matrix: $A^TP+PA<0$, $P>0$, minimize trace(P) According to Stephen Boyd's book, the inequalities are homogeneous in P and hence can by replaced with ...
1
vote
1answer
44 views

Is $|| AXB-C ||_F$ convex?

Let $A \in \mathbb R^{n\times n}$, $B \in \mathbb R^{n\times n}$, $C \in \mathbb R^{n\times n}$ be constant matrices. Is the following convex? minimize $|| AXB-C ||_F$ for $X>0$, where $|| \dots ...
0
votes
1answer
211 views

Gradient of a norm with a linear operator

In mathematical image processing many algorithms are stated as an optimization problem, where we have an observation $f$ and want recover an image $u$ that minimizes a objective function. Further, to ...