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

learn more… | top users | synonyms

3
votes
2answers
951 views

Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...
0
votes
1answer
20 views

Hyperplane separating fraction of points

Given a set of points $S$ and a fraction $\alpha$ I would like to find exactly one hyperplane which divides $S$ such that approximately $\alpha$ points lie on one side and $1-\alpha$ points on the ...
0
votes
0answers
11 views

A question Kolmogrov's generalized inequality for projection onto convex sets

Kolmogrov's inequality says that, if $C$ is a convex set, and $P_C(x)$ is an operator for projecting point $x$ into the convex set $C$, if $z = P_C(x)$, then for any $y \in C$ we have $$ (z - y).(x - ...
0
votes
1answer
45 views

New variable in a convex optimization problem

Consider the convex optimization program $$ \min_{x \in X } x^\top P x + p^\top x \quad \text{ sub. to: } Ax = b $$ where $X \subset \mathbb{R}^n$ is compact, $P \succ 0$, $A \in \mathbb{R}^{m \times ...
4
votes
2answers
219 views
+100

Optimization problem using Reproducing Kernel Hilbert Spaces

I am encountering a problem concerning Reproducing Kernel Hilbert Spaces (RKHS) in the context of machine learning using Support Vector Machines (SVMs). With refernce to this paper [Olivier Chapelle, ...
-2
votes
0answers
26 views

Convex Optimization for circular antenna array [on hold]

i want to use convex optimization to solve near field beamformer design problem to find the minimum number of antennas required for a uniform circular array and elliptical array for the wideband case. ...
0
votes
1answer
30 views

Sums of positive and negative distances to the least squares plane

Let $A_{1}, A_{2}, \ldots, A_{n}$ be points in $\mathbb{R}^{3}$ and $\pi_{*}$ be the least squares plane, i. e. $$ \sum \limits_{i = 1}^{n}\rho^{2}(A_{i}, \pi_{*}) = \min_{\pi}\sum \limits_{i = ...
0
votes
1answer
26 views

Convexity of trace for the product of two matrices

I have the following function for two matrices ${\bf A}$ and ${\bf B}$: $f({\bf A}, {\bf B}) = Tr\{({\bf Y - XAB)}^T({\bf Y - XAB)}\}$ where $Tr$ represents the trace function and matrices ${\bf X}$ ...
3
votes
2answers
148 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
1
vote
2answers
268 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
1
vote
1answer
295 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 ...
0
votes
1answer
17 views

Optimality conditions in convex programming

I'm reading about Zero-order conditions in Nonlinear Programming and the following confuses me (my questions are below the theory): Consider the set $\Gamma \subset E^{n+1} = \{(r,\textbf{x}): ...
0
votes
1answer
377 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
0
votes
0answers
17 views

Confusion related to dual averaging method [on hold]

I have been trying to understand about the dual averaging method proposed by Nesterov. I found some slides too http://www.cs.cmu.edu/~ggordon/10725-F12/slides/27-dual-averaging.pdf. But I didn't get ...
1
vote
0answers
28 views

Confusion related to this optimization algorithm [closed]

I was reading this paper http://rain.aa.washington.edu/@api/deki/files/168/=CDC13_0909.pdf. However, in page 3 of the paper, it has something like this It is saying that the standard dual ...
1
vote
1answer
14 views

Can be x_1 * x_2 >= x_3 * x_4 represented as a second order conic (SOCP) constraint?

I'll like to know if the constraint x_1 * x_2 >= x_3 * x_4 can be represented as an SOCP constraint. Note that setting matrix A = [ x_1 x_3 \\ x_4 x_2] the constraint is equivalent to det(A) >= 0, ...
3
votes
2answers
1k views

KKT and Slater's condition

I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following: "For any convex optimization problem with differentiable objective and constraint function, any ...
0
votes
1answer
238 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
0answers
21 views

Primal-dual subgradient method

In these notes, an extension of the subgradient method is presented in Section 8 (page 30). The method is described so quickly and neither convergence analysis (compared to classical subgradient for ...
1
vote
1answer
31 views

Why is $L_0$ norm not convex? [closed]

I have this confusion in understanding the convexity of the $L_0$ norm. Why is $L_0$ norm not convex?
2
votes
1answer
55 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 $$ ...
0
votes
0answers
17 views

closed form solution of a particular convex program

I wish to know if there is a closed form solution of a program of the following form $\max_w x^Tw \text{ such that } \tau_2\| w \|_2 + \tau_1 \| w \|_1 \leq 1, ~\ \tau_1, \tau_2 > 0$ When either ...
1
vote
1answer
317 views

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

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

Formulation and computation of “the” unique median of an even-sized list

Consider an even-sized set of numbers $X = \{x_k\}$, such as $X = \{1, 2, 7, 10\}$. The median $m$ is defined as: $$m = \mathrm{arg \min_x} \sum_k \lvert x_k - x\rvert^1$$ Any $m \in [2, 7]$ is a ...
0
votes
1answer
31 views

Sufficient condition on convex function such that $f(x) > -\infty$ for all $x$.

Let $f : \mathbb R^n \to [-\infty, \infty]$ convex and let $f(\overline x) > -\infty$ for $\overline x \in \mbox{int}(\mbox{dom}(f)$. Show that $f(x) > -\infty$ for all $x \in \mathbb R$. ...
0
votes
1answer
47 views

Why is L21 norm not smooth

I have this confusion. I was reading this paper http://www.cis.temple.edu/~yuhong/research/papers/ijcai13b.pdf. I didn't understand why is L21 norm not smooth?
0
votes
0answers
18 views

Proof of sufficient condition of existence of Lagrange multipliers

Consider the optimization problem $$ (P) \quad \inf\{ f(x) : g_i(x) \le 0, i = 1,\ldots, m, x \in \mathbb R^m \} $$ where $f, g_i : \mathbb R^n \to (-\infty, \infty]$ are convex and $0 \ne ...
1
vote
1answer
19 views

Stochastic convex (conave) functions vs. convex (concave) function

Can someone help me understand the difference beween stochastic convex (conave) functions and convex (concave) function
0
votes
1answer
21 views

Hessian of non-differentiable function

Given a function $f = \max\{f_1,f_2\}$ with $f_1,f_2$ convex and differentiable, I know I can calculate the subgradient of $f$. Is there also an equivalent of the subgradient for the (sub)Hessian? ...
1
vote
1answer
38 views

Proximal Mapping for maximum of linear and quadratic function

I was wondering if there is an efficient way of calculating the proximal mapping of the following function $f : \mathbb{R}^3 \rightarrow \mathbb{R}$, $b_i \in \mathbb{R}^3$, $c_i \in \mathbb{R}$ : $$ ...
1
vote
1answer
232 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
0
votes
1answer
506 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
137 views

formulate this scheduling problem as linear programming problem

Sorry if this very silly, but i am something new to optimization theory: We have $m$ identical Machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. ...
0
votes
1answer
27 views

Dual norm equivalence?

$\|\|$ is a norm in $R^n$, its dual norm is defined as $\|s\|^*=max_{\|x\|=1}s^Tx$. We denote $s^\#$ as any vector in the following set: [Arg $max_x: \ \ s^Tx-\frac{1}{2}\|x\|^2$] How to verify ...
0
votes
1answer
10 views

Confusion related to proximal mapping [duplicate]

I was reading this paper http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf and I came across this part I didn't get how the third line came from the second line. Any ...
1
vote
0answers
21 views

Confusion related to proximal newton method

I was reading this method related to proximal newton methods http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf. I came across this page I didn't get what this part means $ ...
0
votes
0answers
18 views

show f has aminimum on S where S is …

consider the problem to minimize $f(x+ad)$ subject to $x+ad \in\ $S and $a\geq0 $ where $S$ is a compact convex set and $f$ is a convex function. Furthermore, suppose that $d$ is an improving ...
0
votes
1answer
19 views

How to solve the dual problem of SVM

By solving the primal form of SVM (support vector machine), we can get the dual form of this problem. The more details are shown in wiki of SVM. Given this dual problem, how can I solve the ...
2
votes
4answers
339 views

definition of strongly convex

There are several equivalent definitions for strongly convex. For example, some literature said: A function $f$ is strongly convex with modulus $c$ if either of the following holds $$f(\alpha ...
1
vote
1answer
20 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 ...
0
votes
0answers
15 views

Laplacian Regularization with Sparse group Lasso

I have an optimization problem that is of the form: $\{\textbf{A}\} = argmin \{tr(\textbf{A}^\top L \textbf{A}) + \lambda_1||\textbf{A}||_1 + \lambda_2||\textbf{A}||_{2,1}\}$ where $\textbf{A}$ is a ...
1
vote
3answers
23 views

Constraint to unconstraint optimization problem by subsitution

Given the following convex optimization problem $\min_{x,p} ||x|| - p$ subject to $p > 0$ Can I change the above to an unconstrained convex optimization problem by substituting $c = ...
1
vote
1answer
22 views

Could I get the explicit solution to the following problem relate to generalized rayleigh quotient?

$\bf x$ and $\bf a$ are complex vectors, $\bf C$ is positive definite complex matrix, $\bf B$ is positive-semidefinite complex matrix. What's the objective value? Thanks! $$\max_{\bf x} ...
3
votes
1answer
276 views

Solving Linearly Constrained Quadratic Programming with Coordinate Descent

Does anybody have any idea about how to solve the following problem with Coordinate Descent? \begin{align} \min &\quad \mathbf{x}^{\top}P\mathbf{x} + b^{\top}\mathbf{x}\\ \text{Subject to}& ...
0
votes
1answer
220 views

How do I prove that the composition of an affine function preserves convexity?

What would be the formal proof that $ f(Ax + b) $ given $ f(x) $ is a convex function ? I got to the point where I expanded $$ f(\lambda(Ax+b) + (1- \lambda)(Ay+b)) = f(A(\lambda x + (1 - \lambda)y) + ...
1
vote
1answer
48 views

A particular quadratic minimization problem

Given $n^2$ constants $a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{nn}$ and $n^2$ non-negative variables $x_{11},x_{12},\ldots,x_{1n},x_{21},\ldots,x_{nn}$. Find the minimum value of $$\sum_{i=1}^n ...
1
vote
0answers
16 views

First order necessary conditions for nondifferentiable nonconvex minimization problem

I am interested in first order necessary conditions for the following minimization problem where the function $f$ is continuous, nondecreasing and concave, with $f(0)=0$, but not necessarily ...
0
votes
0answers
5 views

Perturbation of Polyhedral Projection

I am interested in understanding the behavior of the Euclidean projection $\pi_K(x)$ as the polyhedral set $K$ varies. I know there are different approaches to this, but for what I am doing it would ...
0
votes
0answers
21 views

Detecting faces of polytopes

I am working in convex geometry for the summer with little experience beforehand. It's a lot of fun but it does mean I don't know some of the basic things. I'm interested in the orbits of finite ...
2
votes
1answer
24 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. ...