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

learn more… | top users | synonyms

1
vote
0answers
33 views

Tucker's theorem from Farkas lemma

I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me. The proof I am following is in this paper at page 16. What I do not ...
0
votes
0answers
20 views

How can I solve $\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$ in a closed form depending on projection?

I'm trying to solve the minimization problem $$\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$$ where $b \in \mathbb{R}^n$, $X \subset \mathbb{R}^n$ is a convex set. And $A$ is a symmetric ...
3
votes
0answers
31 views

Are these equivalent definitions of faces of convex sets?

I consulted several books and found that the definitions of faces and exposed faces of convex sets are a bit messy. Many books just treat them as the same stuff. In book "foundations of ...
1
vote
1answer
40 views

Are these inconsistent definitions of extreme subset of convex set?

I need some elementary knowledge of polyhedral and I am consulting several books. However, I found the definitions may not be consistent. I am not sure if I understand them right. The question is ...
1
vote
0answers
30 views

Convex Optimization: Advantages of Symmetric Primal-Dual Algorithms?

This is a follow-up to an answer on a previous question on PD algorithms: http://math.stackexchange.com/a/1193928/36257 I have done some research learning the mechanics of how Infeasible PD ...
0
votes
1answer
45 views

Is $\mathbf{y}^*$ a local minimizer of $f(\mathbf{h}(\mathbf{y}))$?

Let $f(\mathbf{x})$ be a twice differentiable function, where $\mathbf{x} \in \mathbb{R}^n$. Let $\mathbf{x}^*$ be a local minimizer of $f(\mathbf{x})$. Consider a differentiable and invertible ...
0
votes
1answer
19 views

How can I solve $y \in (N_X + \nabla f)(x)$ via projection?

I a aware that if I'm trying to solve for $x$ the problem $y \in [\lambda I + N_X](x)$ where $y$ is a known vector, and $N_X$ is the normal cone given by $N_X(x) = \{u : \langle u, x - y\rangle ...
0
votes
0answers
45 views

How to use CVX to solve this problem?

I have a function in the variables $x_{kl};\ k,l=1\ldots,m$, $$\sum_{i=1}^n \sum_{j=1,j<j'}^{N_i}\left( b_{ij} b_{ij'}- \sum_{k,l=1}^{m}x_{kl}f_k(a_{ij})f_l(a_{ij'})\right)^2$$ where ...
0
votes
0answers
21 views

Minimizer of $\frac{\lambda}{2} \| \theta - \theta^{(k)}\| + \text{Loss}_\text{hinge}(y \theta \cdot x)$

How do you find the minimizer of: $$\min_{\theta \in \mathbb{R}^d}\left\{ \frac{\lambda}{2} \| \theta - \theta^{(k)}\|^2 + \text{Loss}_\text{hinge}(y \theta \cdot x)\right\}$$ if $\theta^{(k)} \in ...
0
votes
0answers
14 views

SVM Soft Margin Lagrange form

I study the Lagrange multipliers form of SVM. I am particulary interested in values that $\alpha_i$ can get. The following is the Langange multipliers form of hard margin SVM. $min_{w,b} ...
0
votes
0answers
21 views

Minimization over a symmetric matrix

I'd like to know what are possible methods to minimize over a symetric matrix R. Example: min $||AX -B||_2^2$ The minimization is over A, such that $A^T = A$, $A \in R^{3x3}$, $X \in R^{3x\alpha}$, ...
0
votes
1answer
27 views

Affine hull example

In the textbook "Convex Optimization", S. Boyd says that the affine hull of a set $C\subseteq \mathbb{R}^{^{n}}$ is the smallest affine set that contains C. Moreover, the Ex. 2.2 shows the set $ ...
0
votes
1answer
57 views

Explicit solution for a linear program with two constraints

This is not a homework problem, although it wouldn't surprise me if it happens to exist in a textbook somewhere. Is there an explicit solution for the linear program $$\max_x c^Tx ~~ s.t. \\ d^Tx = q ...
1
vote
0answers
27 views

Transform a nonconvex constraint into a convex one

I am solving an optimization problem and I need to formulate it as a convex optimization problem. Is there any way to write the constraint $$ 1 - e^{z} - \frac{e^{-r}}{1+r} \leq 0 $$ as a convex ...
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
33 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
55 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
58 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
35 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
20 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
25 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
15 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
29 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
21 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
17 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
37 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
59 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
39 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 ...