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

learn more… | top users | synonyms

0
votes
0answers
65 views

Calculation of the set for the polar tangent cone?

I have the following theorem in my book. Assume that $\tilde{x}$ is a local minimum from a minimization problem and that f(.) is differentible at $\tilde{x}$ Let $T_X(\tilde{x})$ be the tangent cone ...
0
votes
2answers
50 views

Is the geometric-to-arithmetic function convex or concave?

Consider a vector $\mathbf{x} \in \mathbb{R}_{++}^N$. Also consider two functions, $g(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, and $a(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, ...
0
votes
3answers
68 views

Concave function divided by a convex function. What is the result?

Let us say that I have a function $f(x)$ that we know is a concave. And let us also say that we have another function $g(x)$ that is a convex. If I make a new function, $h(x) = \frac{f(x)}{g(x)}$, ...
1
vote
1answer
31 views

How to verify correctness of a Fenchel conjugate derivation

Suppose I derived Fenchel conjugate of a function. My goal is to check if my solution is right. Suppose the steps are not available any more and only the final solution is present. Is there any ...
0
votes
0answers
21 views

Show that the Rosenbrock function is strictly convex for a specific region

So we know that the Rosenbrock function is a test function of sorts, but can anyone prove that a specific region is strictly convex? Rosenbrock eqn: $ f(x_{1},x_{2}) = 100(x_{2} - x_{1}^{2})^{2} + ...
1
vote
1answer
75 views

Tangent Cone is a cone?

I first give two definitions. Def1: A set $S$ is a cone if $x \in S, \lambda \geq 0 \implies \lambda x \in S$. Def2: Let $S$ be any set (we may assume $\mathbb{R}^n$ with the usual Euclidean ...
0
votes
2answers
29 views

is convex hull of intersection equal to intersection of convex hull

is $convexhull(S_1\cap S_2)=convexhull(S_1)\cap convexhull(S_2)$ where $S_1$ and $S_2$ are finite sets.
0
votes
0answers
26 views

Isomorphisms of Convex Cones

A convex cone $C$ is a subsets $C \subseteq V$ of a vector space which is closed under positive linear combinations, i.e. for $\lambda, \mu > 0$ and $u,v \in C$ it is $\lambda u + \mu v \in C$. An ...
1
vote
0answers
47 views

Until now, what is the fastest optimization algorithm of non-smooth convex functions

I am wondering if I minimize a non-smooth convex function, which solver should I choose. I think I should choose a fastest one with a big convergence rate. Subgradient descent is always on the ...
1
vote
1answer
62 views

How to show this algorithm on positive semidefinite matrices converges to a global maximum determinant

I'm dealing with an algorithm which is supposed to converge to the maximum determinant of certain positive semidefinite matrices. The problem is that we have such a matrix, and we vary certain ...
0
votes
1answer
79 views

Can a Lipschitz continuous function be strictly convex?

Let $\varphi:\mathbb R^n\to\mathbb R$, and suppose for all $x,y\in\mathbb R^n$, $$\|\varphi(x)-\varphi(y)\|\leq L\|x-y\|$$ for Lipschitz constant $L$. Is it possible for such a function to satisfy ...
1
vote
2answers
85 views

formulating the dual for an instance of a SOCP with linear constraints

I have an optimization problem with second-order cone constraints and linear inequalities and inequalities (shown below). I want to formulate the dual, but have been having trouble. ...
0
votes
0answers
18 views

Quadratic programming problem - SVM with L2 loss

So, I have the following problem: $$\min \frac12 \|w\|^2 + C/2 \cdot \sum_i e_i^2$$ $$\text{s.t. }y^{(i)}[\langle w,x^{(i)}\rangle+b]-1+e_i\ge0 $$ where $y^{(i)}\in\{-1,1\},x^{(i)},C$ are known ...
0
votes
2answers
55 views

Symmetric Positive Definite and Gradient Proof

I have the function $f(x)=\frac {1}{2} \mathbf x^T Q \mathbf x - \mathbf b^T \mathbf x$ where $Q$ is symmetric. I'm trying to show that solving $\nabla f(\mathbf x) = 0$ is equivalent to solving $Q ...
1
vote
0answers
20 views

Dual of the mixed $\ell_1/\ell_2$ norm?

The mixed $\ell_1/\ell_2$ norm $\Omega_{12} $ is defined as $\Omega_{12}(x) = \sum_g ||x_g||_2$ where $x_g$ are disjoint subsets of the elements of the vector $x$. This is used in machine learning ...
0
votes
0answers
56 views

Quadratic Symmetric Positive Definite Function Implies Convex

Consider the function $f$(x)=$\frac {1}{2}$*x*$^T$Q x. Show that if Q is symmetric positive definite, then $f$ is a convex function. Show that $\nabla f$(x) = Q x (provided Q is symmetric). I ...
1
vote
0answers
23 views

can we prove that a certain supremum of affine functions is frechet differentiable or at least continuous?

Let $X$ be a Hilbert space. Let $A\colon \operatorname{dom} A\to X$ be linear operator with closed graph (not necessarily bounded). Define $$ g\colon \operatorname{dom}A\to \mathbb{R}:x\mapsto ...
3
votes
2answers
216 views

Adding Elements to Diagonal of Symmetric Matrix to Ensure Positive Definiteness.

I have a symmetric matrix $A$, which has zeroes all along the diagonal i.e. $A_{ii}=0$. I cannot change the off diagonal elements of this matrix, I can only change the diagonal elements. I need this ...
0
votes
0answers
19 views

Constrained optimization with complex variables

Is there a theory of constrained optimization with complex variables, do you know any textbook on that topic? The typical textbooks on constrained optimization deal with real variables. I actually ...
1
vote
2answers
54 views

Hessian matrix and epigraphs

I'm working on a homework assignment concerning convex optimization and I came across a problem involving the convexity of the function and the convexity of the domain of the function. Consider the ...
1
vote
1answer
38 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
34 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
44 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
54 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
32 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
74 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
72 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
36 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 ...
0
votes
1answer
66 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
136 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 ...
0
votes
0answers
13 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
155 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
32 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 ...
1
vote
1answer
66 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
100 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
57 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$ ...
1
vote
3answers
58 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)$.
1
vote
0answers
23 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
107 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
50 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
70 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
34 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 ...
1
vote
2answers
66 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
22 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
45 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
106 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
70 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
127 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
44 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
76 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 ...