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

learn more… | top users | synonyms

1
vote
0answers
27 views

An Orthogonal Projection with Weighted Norm

In the context of solving a convex program via projected gradient descent i am facing the following problem: $$\min_{x\in\mathbb R^2}\lVert x-y\rVert_M^2,\qquad\lVert x\rVert\le1$$ or written ...
1
vote
2answers
27 views

L1 regularized SVM in Matlab

Minimizing the following SVM formulation \begin{align} \arg\min_{\mathbf{w}}\frac{1}{2}\|\mathbf{w}\|^2_2 \\ \text{subject to } \quad y_i(\mathbf{w}\cdot\mathbf{x_i}) \ge 1 \end{align} can be done ...
0
votes
1answer
37 views

How to show $f(x,y) \leq \theta f(x,y) + (1-\theta)f(x,y)$ for $\theta \in [0,1]$?

Let $\theta \in [0, 1]$. Let $f(x,y)$ be a function. Is there a way I could prove that $f(x,y) \leq \theta f(x,y) + (1-\theta)f(x,y)$? I have tried to start with $f(x,y) = 2f(x,y) - f(x,y)$ or ...
0
votes
1answer
24 views

Reference for gradient descent with unit norm constraint

I faced a non-convex optimization problem with unit norm constraint. I can solve the problem using the gradient descent method and the projection of the gradient onto the tangent plane as in @joriki ...
1
vote
2answers
26 views

multi-objective optimization

I am currently encounterring a optimization problem. The goal is optimize an objective function A and B at the same time. But the problem is that optmizing A will almost always tradoff with B, such ...
2
votes
1answer
35 views

Origin of Slater's condition

I've been looking all over the internet to answer this question: Slater's condition is a commonly used to certify that strong duality holds in a convex optimization problem. Although used in many ...
1
vote
1answer
43 views

Matrix Maximization

I would like to solve the following optimization problem for a matrix $X$ which is symmetric and positive-semidefinite: $$ \mathrm{maximize} \, \, \, f(X) = \log \mathrm{det} X - k_1 \log(k_2 + a^T X ...
0
votes
0answers
30 views

Using l1 magic toolbox for compressive sensing : Positive definite matricies.

I'm trying to use l1 magic to reconstruct an image from a single pixel camera I've developed. The test functions used are random binary patterns projected onto the object scene, so each pattern is ...
3
votes
2answers
87 views

What numerical methods are known to solve $L_1$ regularized quadratic programming problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
0
votes
1answer
33 views

Strong convexity of a function with cases

Given a set $S = \{x_1,\dotsc,x_n\} \subset \mathbb{R}$, is the function \begin{align} f&: (0,\infty) \to \mathbb{R} \\ f&(p) = 2p^2 + \frac{1}{n}\sum_{i=1}^n \max(0, -p^2-x_i) \end{align} ...
0
votes
0answers
23 views

dual value of a linear constraint

Assume a minimization problem. The dual of an inequality '<' constraint is the marginal improvement in the objective function (ie marginal reduction) by marginally increasing the right-hand-side ...
1
vote
0answers
38 views

find the angles of a given vector sum

Assume you have n vectors in 2D space, with different fixed magnitudes $l_i$. The problem is to find the angle of each vector such that vector sum is a specific vector. That is, $\sum l_i \cos ...
0
votes
0answers
16 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
27 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
1answer
50 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 ...
0
votes
1answer
31 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
21 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}): ...
1
vote
0answers
29 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
16 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, ...
1
vote
1answer
32 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?
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 ...
0
votes
0answers
22 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
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
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 ...
0
votes
1answer
32 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$. ...
1
vote
1answer
20 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
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
1answer
25 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? ...
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 $$ ...
1
vote
1answer
43 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}$ : $$ ...
0
votes
1answer
28 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 ...
4
votes
2answers
231 views

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, ...
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
1answer
21 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 ...
1
vote
1answer
22 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
17 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
24 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
24 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} ...
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
18 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
26 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. ...
0
votes
1answer
21 views

What exactly is non-convex optimization

I am coming across the term: non-convex optimization problem. What exactly is this non-convex structure, and how do I know by only looking at the structure of the problem, I could tell it is ...
1
vote
1answer
32 views

Optimization of a convex target function with inequality constraints

I want to solve the following optimization problem: \begin{equation} \begin{split} \text{maximize} &\;\;\; \ln x_1+\ln x_2+\ln x_3+\ln x_4 \\ \text{s.t} &\;\;\; x_4\le4 \\ ...
-2
votes
1answer
48 views

Matlab optimization toolbox vs. CVX solver?

I would like to know what is the difference between the Matlab optimization toolbox and CVX solver which is a convex optimization toolbox? Can a convex optimization be solved in both?
0
votes
1answer
24 views

Is $f(X) = || Y - XX^T ||_F$ convex given fixed $Y$?

In the scene of nonnegative matrix factorization, $f(X_1, X_2) = \| Y - X_1 X_2 \|_F$ is not convex, but both $f(X_1)$ given fixed $X_2$ and $f(X_2)$ given fixed $X_1$ are convex, enabling us to ...
0
votes
2answers
53 views

Regularization vs. Inequality Constraint

For what values of a regularization parameter $\alpha$, there is an equivalent inequality constraint in convex optimization? In particular, in the convex optimization problems below $$ \text{ Problem ...
0
votes
0answers
27 views

Finding a solution using the principle of maximum entropy?

I have set of linear constraints and would like to find an answer to its unknown variables, $p_i$'s. One of my options to find a solution for $p_i$'s using maximum entropy problem, $\max(\sum - p_i ...