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

learn more… | top users | synonyms

1
vote
0answers
24 views

Practical exercise in SVM

Suppose we have four positive points $\{0,1,2,3\}$ and three negative points $\{-3,-2,-1\}$. We want to learn soft-margin linear SVM $\min_{w}0.5 \left \| w \right \| +C \sum \epsilon_i$ the ...
1
vote
1answer
28 views

Convex Optimization: do Primal Dual methods need to start with strictly feasible point?

I'm learning about Primal-Dual interior point algorithms from Boyd & Vandenberghe Convex Optimization, ch.11.7. Now the text mentions: In a primal-dual interior-point method, the primal and ...
3
votes
2answers
52 views

Fourier coefficient of convex function

On $I = [0, 2π]$ consider the function $f : I → \mathbb{R}$ to be convex. Define: $$a_k\pi := \int_0^{2\pi}f(x) \cos(kx)\,dx$$ Show that the convexity of $f$ implies that $a_k ≥ 0$ when $k ≥ 1$. ...
0
votes
0answers
27 views

Transforming into a convex program

$\max c^Tx$ $s.t. xy = a, \quad x \le b, \quad L \le y \le H$ Is there a way to transform this problem into a convex problem? $a,b,L,H$ are constants. $x,y$ are optimization variables.
0
votes
3answers
54 views

Is exp(-x) convex?

Is $f(x)=e^{-x}$ a convex function? I know that $e^x$ is convex. If I take the second order derivative of $f(x)$: $$f''(x)=e^{-x}$$ Then we can see for all the $x$, $f''(x)>0$. I'm not sure ...
0
votes
0answers
18 views

(Convex) Reformulation of a program

Given $\{(x_i,y_i)\in \mathbb{R}^d\times \mathbb{R}\}_{i=1}^n$, consider the the following program: \begin{eqnarray*} \mathrm{min}_{\{\hat{y}_i \in \mathbb{R}\}_{i=1}^n,\{g_k \in ...
0
votes
1answer
18 views

Optimize probability of success between k different flows

I want to find a set of coefficients ($n \in R$) that solve the following optimization problem, maximize $\prod_{i=1}^k(1-p_i)^{n_i}$ s.t. $\sum_{i=1}^k n_i = N$. The $p$'s are known positive ...
1
vote
0answers
24 views

Estimating parameters of a stochastic matrix

I am stuck with the following problem in research. Let $A_{1}$, $A_{2}$ and $B$ be stochastic matrices. Let $B = f(A_{1},A_{2})$. Let $\pi =[\pi_{1},\pi_{2},\pi_{3}]$ be a vector such that $\sum_{i} ...
0
votes
0answers
57 views

Optimizing concave function over non-convex set

I have the following problem that I am looking advice on. Let $ \mathcal{F}$ be a convex subset of vector space $X$. The goal it to \begin{align*} \max_{x \in \mathcal{F}} f(x)\\ s.t. \ g(x) \le 0 ...
0
votes
0answers
34 views

Difference Convex Programming using Convex-Concave Procedure (CCCP)

Suppose I have this optimization problem: $ min f(X) - g(X), s.t. f(X)-g(X)\le 0, |X|\ge 0$ where $X$ is a square, symmetric, SPD matrix $\in \mathbb{R}^{N\times N}$, $f(X)=\sum_{a\in S} a^TXa$, and ...
0
votes
0answers
19 views

Eigenvectors of a quadratic form and iterative descent

I am interesting in using eigenvectors of a quadratic form to perform iterative steps to get the function value to a certain point. While other methods may be more common, my quadratic form is not ...
0
votes
1answer
24 views

what is the convex hull of the rank k psd matrix

Given the set $\{X|0\preceq X , rank(X)=k\}$. What is the convex hull (convex envelope) of this nonconvex set? If we further require $X=VV^T$, where $V^TV=I$, $V$ has the size $n\times k$. Then the ...
0
votes
2answers
54 views

Explaining the “well-known” optimization of this particularly simple convex, non-differentiable function?

I've been programming algorithms for solving L1-regularized logistic regression with large datasets. As such, I've been delving into the computer science literature, and came across the following ...
0
votes
0answers
25 views

Feasible set for linear system with linear constraints

I have a linear underdetermined system $Ax = b$ with constraints $0 \le x \le 1$. Matrix $A \in \mathbf{R}^{n \times m}$ with $n < m$, elements of which are either $0$ or $1$, and sum of each ...
0
votes
0answers
30 views

Including constraints in objective function

Apologies for the simple question. With $\mathbf{x},\mathbf{v} \in \mathbb{R}^n$, minimize $f(\mathbf{x}): \mathbb {R}^n \rightarrow \mathbb{R}$. \begin{equation}\tag{*} \begin{array}{c} \text{min} ...
1
vote
0answers
26 views

Why use two slack variables in the support vector regression formulation?

I am learning support vector regression but cannot fully understand the rational of the slack variable tricks in its formulation. The original optimization problem for SVR is as follows: ...
0
votes
0answers
43 views

math background for using Total Variation Norm for an L1-regularized optimization problem (Rudin-Osher-Fatemi)

I am working with some geographic data, and I would like to apply total variation denoising in order to sharpen the boundaries of clusters in the data. I also have some C code to run the split bregman ...
0
votes
1answer
24 views

Covariance Selection with specified sparsity pattern

I am new to semi-definite programming and I am trying to follow through the optimization described in http://cvxopt.org/userguide/spsolvers.html#example-covariance-selection The problem is to ...
0
votes
1answer
13 views

Why is $(T + N_X)(x) \subset T(x)$ when $Dom T \subset X$?

I'm trying to show that given a maximal monotone operator $T$ and a closed convex set $X$ with $Dom T \subset X$ then for a given $x \in Dom T$ it holds $(T + N_X)(x) \subset T(x)$ where ...
0
votes
0answers
14 views

Strict convexity of a non-differentiable multivariate function

Suppose $F: \mathbb{R}^N \mapsto \mathbb{R}$ is differentiable. In order to check for the convexity of $F$, we can restrict it to a line. Thus $F$ is convex iff the function $g: \mathbb{R} \mapsto ...
1
vote
1answer
28 views

solution involving inverse of a rank-1 matrix

I am looking for $\mathbf{y} \in \mathbb{R}^n$ that minimizes the following objective function that involves a real matrix $\mathbf{V} \in \mathbb{R}^{n\times n}$ \begin{equation}\tag{*} ...
0
votes
1answer
19 views

Convex Optimization: minimize over unknown convex set starting in center

Essentially I am trying to develop an algorithm to minimize a function over a convex set that I don't know explicitly. However, I have a starting point "deepest in the set" (i.e. with largest norm ...
1
vote
0answers
18 views

Strictly Concave Function over non-convex set

I have to optimize a function $f$ over a set $S \subset X$. We know that $f$ is non-negative, continuos and strictly concave over $X$. We have that $S$ is compact but not convex. By Extreme Value ...
1
vote
1answer
24 views

Augmented Lagrangian with multiple constraints

I would like to minimise a function, with multiple constraints: $$ \frac{1}{2} \|y-Ax\|_2^2 + \beta \|z\|_1 $$ subject to $$ Bx = 0 $$ and $$ x - z = 0 $$ In my case $(B+I)$ is not a valid ...
0
votes
1answer
22 views

Test Convex Hull of Vectors

My mathematical background is generally not so great so please pardon me if my question appears silly. I am trying to test the convex hull of 3 vectors for an intersection with coordinate axes as ...
0
votes
1answer
20 views

show that $a^T\lambda + a_0$ is equivalen to $\lambda^T(1/2(ea^T + ae^T) + a_0 E)\lambda$

Affine function $f(\lambda)=a^T\lambda + a_0$ where $a, \lambda\in \mathbb{R}^n,a_0\in \mathbb{R}$ and $\lambda$ is in a unit simplex,i.e., $\sum\limits_{i=1}^n \lambda =1, \lambda\in \mathbb{R}^n_+$. ...
0
votes
1answer
33 views

Why is any subspace a convex cone?

I am reading Convex Optimization written by Stephen Boyd. In page 27 of chapter 2, there is an example said 'Any subspace is affine, and a convex cone(hence convex).' Can anybody explain to me why ...
1
vote
4answers
64 views

Optimization of a quadratic function with qudratic constraints

I'm a Graduate student of Electrical Engineering. I have some basic knowledge on Convex Optimization. For my research, I cam across the following optimization program. With $\mu > 0$, find $\arg ...
0
votes
0answers
18 views

How to minimize this sparse quadratic function?

There is a problem when I'm reading a paper. Equation: $min_p|p-p^*|^2+\alpha |R(p)|^2 + \beta |D(p)-\delta|^2$, where $p, p^*, R(p), D(p), \delta$ are all $M\times N$ matrices, and $p^*, R(), D(), ...
1
vote
0answers
15 views

Basis pursuit denoising

The Lagrangian form of basis pursuit denoising $\min_{w} ||w||_{\ell_{1}} + \lambda ||Aw-x||_{\ell_{2}}^{2}$ can be solved using proximal gradient descent. Proximal methods also can be used to ...
0
votes
0answers
32 views

Dictionary learning for sparse coding using ADMM

I'm trying to formulate an ADMM for performing dictionary learning (for sparse coding) on a set of data. Let's assume we have a data matrix of $X \in \mathbb{R}^{M \times N}$, a dictionary of $D \in ...
0
votes
0answers
22 views

Convex Constraint on Sine Wave Simularity

So lets say you have a vector X = [x1 x2 x3 ..... xn] You want to optimize a cost function over X. However you want to constrain the vector X to look like a sine wave. Say you can parameterize a ...
2
votes
1answer
47 views

Proximal mapping of $f(U) = -\log \det(U)$

This is an assignment problem which I failed to solve in a couple of days. Denote the set of all $n \times n$ symmetric matrices and the set of all $n \times n$ symmetric positive definite matrices ...
4
votes
1answer
122 views

Closest Matrix with Specific Eigenvector

Consider a vector ${\bf x}$ and a matrix $A_0$ with $A_0(i,j)\ge0$. What is the best way of getting matrix $A$ s.t. $$A = \arg \min |A-A_0|$$ subject to $$A{\bf x} = \lambda {\bf x} \hspace{2mm} ...
0
votes
1answer
35 views

Schatten p norm p>1

The Schatten p norm is differentiable away from the origin for p> 1. Does a stronger condition of Lipschitz continuity of the gradient also hold?
0
votes
0answers
29 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
2
votes
1answer
28 views

A Variant of Gradient Descent

Suppose I have some objective function $f(\beta)$ which I would like to minimize for $\beta$. A standard gradient descent would be $\beta^{(t+1)}=\beta^{(t)}-\alpha \nabla f(\beta^{(t)})$, where ...
1
vote
1answer
20 views

Logistic Regression is convex proof

I am trying to make sense of this paper qwone.com/~jason/writing/convexLR.pdf "Regularized Logistic Regression is Strictly Convex" by Jason D. M. Rennie. I am following the proof and formula (1) is ...
0
votes
1answer
49 views

Show that the dual norm of spectral norm is Nuclear norm.

Could someone help to understand that the dual norm of spectral norm is Nuclear Norm ? We can focus on the real field. Given a matrix $X \in \mathbb{R}^{mn},$ then the spectral norm is defined by: ...
0
votes
1answer
31 views

is this a convex optimization problem?

Can someone clarify is this a convex optimization problem or not. $min \| X-UV\|_{F}\quad $ s.t $ \quad U \geq ,V\geq0$ . If not , what makes the problem non-convex?
3
votes
1answer
88 views

Newton's method vs. gradient descent with exact line search

tl;dr: When is gradient descent with exact line search preferred over Newton's method? I simply don't understand why exact line search is ever useful, and here's my reasoning. Let's say I have a ...
0
votes
0answers
50 views

Nonsmooth optimization

Now I have a chance taking a course in nonsmooth optimization, the course outline writes: convex analysis, subdifferential calculus and proximal mapping. various numerical algorithms to solve ...
1
vote
0answers
29 views

sup is bounded or not?

The sup is as following: $c_f = sup_{x,s\in D} \ f(y) - f(x) - (y-x)^Tb$ where $y=x+\alpha(s-x)$, $\alpha \in (0,1 )$ is constant and $b$ is a constant vector. $D$ is a convex compact set and ...
1
vote
1answer
27 views

Proving a function of matrix is convex

I have a function of a matrix and a vector $f(A,b)=y^\top (I-A)^{-1} b$ and I want to know the conditions under which it is convex. For functions of a vector, the positive definiteness of the Hessian ...
1
vote
1answer
85 views

Sub-gradient of the “$\ell_0$ norm”

I am trying to characterize the sub-gradient of l0-norm ($f(x) = ||x||_0=\sum_{i=1}^n 1\{{x_i \neq 0}\}$). At first, I thought l0-norm is a convex non-smooth function since it satisfies the triangle ...
1
vote
1answer
46 views

How to derive the solution in quadratic optimization

I'm reading the book "Convex Analysis and Optimization" written by Prof. Bertsekas. In Example 2.2.1, there are the following description: I don't know how to ...
0
votes
1answer
33 views

What's the difference between interior and relative interior?

As defined in Convex Optimization written by Stephen Boyd, both interior and relative interior seems to describe a same thing: a set that peels away it's boundary points. So what on earth is the ...
0
votes
1answer
47 views

How to solve this convex resource allocation problem numerically? CVX doesn't work.

I got a resource allocation problem as follows: \begin{eqnarray} \min &\sum_{i=1}^M \frac{1}{1 + \text{exp}(C_i + \frac{r_i}{1+r_i})} ;\\ &\sum_{i=1}^M r_i \le R;\\ &r_i \ge 0 ...
0
votes
1answer
20 views

Projection on Epigraph of a convex function

Given a convex function $h:\mathbb{R}^n \mapsto \mathbb{R}$, and a point $(x,\alpha) \in \mathbb{R}^n \times \mathbb{R}$, how can I find a closed formula to compute the projection of $(x,\alpha)$ in ...
1
vote
0answers
79 views

Linear programming optimization problem formulation

I need help in formulating an optimization problem. I have a system of equations as follows: $c_1x_1+c_2x_2+c_3x_3=1$ $b_1x_1+b_2x_2+b_3x_3=1$ $a_1x_1+a_2x_2+a_3x_3=1$ In my case the ...