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

learn more… | top users | synonyms

0
votes
1answer
24 views

how to differentiate to optimize this function?

I have an optimization function in the following form: $E = \operatorname*{argmin}_{A} \sum_j \| A\bf{x}_j - B \|_2^2 + \mu\sum_i a_{ii}^2$ Where, A is an unknown diagonal matrix with elements ...
0
votes
0answers
56 views

How to derive dual of this L1 norm approximation problem?

I am working through a question in Convex Optimization by Boyd and Vandenberghe. I've made an image with the original question, and the part of the solution I don't understand: how the dual is ...
1
vote
0answers
45 views

Farthest point on a parallelotope from the origin

I have two related questions. First, consider a maximal independent set of vectors $\{v_1,\cdots,v_k\}$ in $k$ dimensional space. The rows of a square matrix $A$ are from those vectors. The origin is ...
0
votes
1answer
114 views

Closed form solution

I have the following optimization problem: $$\min_{\mathbf{G}} \|\mathbf{B(A+G)\|_F^2} \quad{} \\\text{subject to} \quad{} \mathbf{\|C^T(A+G)\|_F^2\leq \gamma \|A^T(A+G)\|_F^2 } \quad{}, \\ ...
0
votes
2answers
20 views

Solving for gradient of Frobenius norm term

Let's first define a couple of variables: $A,B,C \in \mathbb{R}^{m \times n}, D \in \mathbb{R}^{n \times n}$, and $\mu$ is a scalar. Say I have an ADMM sub-problem that looks like this: $\arg ...
5
votes
1answer
165 views

Is this function concave or can it be made concave?

I am working with a point process with an event arrival rate of: $$ \lambda(t) = \mu + \sum\limits_{t_i<t}{\alpha e^{-\beta(t-t_i)}}$$ where $ t_1,..t_n $ are the event arrival times. The log ...
0
votes
0answers
47 views

Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
0
votes
2answers
49 views

$\max \{\sum \limits_{i=1}^n z_i w_i \}$ where $\sum \limits_{j=1}^n |w_j| = 1$

How can we find $\max \{\sum \limits_{i=1}^n z_i w_i \}$ where $\sum \limits_{i=1}^n |w_j| = 1$? $z, w \in \mathbb{R}^n$
0
votes
0answers
22 views

Frobenius norm and Gaussian noise

Why Frobenius norm is considered to a good tool for dealing with Gaussian noise?
0
votes
1answer
35 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
0
votes
0answers
50 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
3
votes
3answers
141 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
0
votes
1answer
33 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$ \min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge b$$ Where Q is square ($n$x$n$), positive semi ...
0
votes
0answers
46 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
30 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
2
votes
2answers
61 views

Augmented Lagrangian

Consider the following equality constraint minimization problem: minimize $\text{ }f(x)$ subject to $Ax=b$ Its Lagrangian is then: $L(x,y) = f(x) + y^T(Ax-b)$ We can use then gradient ascent to ...
0
votes
3answers
66 views

Optimizing an expression containing sum of square roots of squared terms

For optimization problems involving square root, it is common to optimize the squared expression instead of that containing the square root. What if we have sum of squared expressions ? Consider the ...
0
votes
0answers
24 views

Applications of low-rank matrix approximation

There was a similar question here Use of low rank approximation of a matrix that has unfortunately remained unanswered. Although being along the same lines, my question will be formulated in a little ...
6
votes
1answer
163 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
0
votes
0answers
20 views

Convex Inequality describing Functions inside specific area

Let us assume that we have two functions $f_1$, $f_2:[0,1] \rightarrow \mathbb{R}^{2}$, which describe each a point trajectory on the plane. Let us further assume that we parametrize those functions ...
1
vote
2answers
63 views

How to check for convexity of function that is not everywhere differentiable?

I have a question. I have just been introduced to the subject of convex sets and convex functions. I read this in wikipedia that a practical test for convexity is - to check whether the 2nd ...
0
votes
1answer
71 views

Convex optimization approximation

Consider the optimization problem $\mathcal{P}_0$ $$ \min_{x \in \mathbb{R}^2} \left\| x-p \right\|^2 $$ $$ \text{sub. to: } \ A x \leq b, \ \ x_1^2 + x_2^2 = 1 $$ where $p \in \mathbb{R}^2$ is a ...
0
votes
1answer
54 views

Model $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty $ into standard form

I need to solve the following convex optimization problem: $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty$ s.t $x ...
2
votes
3answers
119 views

Is this optimization problem solvable?

I have the following optimization problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~ \|\mathbf{y+Ax}\|_\infty \leq \beta\|\mathbf{y}\|_\infty ~~,~~ \|\mathbf{x}\|^2 \leq \alpha^2$$ where ...
3
votes
1answer
65 views

Generalization of log-convexity (log-concavity): log-log-convexity (log-log-concavity)?

$\underline{\mathrm{Background\; on\; function\; Convexity}}$ A function, $f$, is convex if: $$f( x\theta+y(1-\theta) ) \leq \theta f(x) + (1-\theta)f(y).$$ $f$ is concave if $-f$ is convex, [1]. If ...
0
votes
1answer
21 views

Complexity of convex optimization problem with interior-point

Assume I have a matrix $Q \in \mathbb{R}^{n \times n}$ which is positiv definite and symmetric, and I want to minimize $$ \frac{1}{2} x^T Q x + x^T f $$ on a non-empty convex set $x\in D=\{ v \in ...
0
votes
0answers
17 views

Linearized ADM and matrix adjoints

$\newcommand{\argmin}{\operatorname{argmin}}$ In this question I am referring to this paper ...
1
vote
0answers
22 views

How to convexify (relax) this L0 eigenvalue optimization problem?

Let $C_1,\dots,C_L$ be $N\times N$ hermitian matrices. Let $d<0$ be a given negative constant. Then consider the optimization problem \begin{align} \max_{r\in \mathcal{R}^{L\times 1}} &\mid\mid ...
1
vote
2answers
57 views

How to solve this optimization problem? (may be gradient descent?)

I have the following optimization problem. $$\operatorname*{argmax}_{w} \|(1-w)\boldsymbol{X} -w\boldsymbol{Y}\|^2 \\ s.t. \quad 0<w<1 $$ How can I find the solution of this problem? May be ...
2
votes
0answers
39 views

Solve the linear program

Please help to solve this problem. I am new to this type of problems and any help will be greatly appreciated $$\text{ Minimize } 7x-5y+3z$$ $$\text{ Such that } \ \ \ 0 ≤ x ≤ 6 , -2 ≤ y ≤ 7 , -4 ...
1
vote
0answers
72 views

Alternating Direction Method of Multipliers (ADMM) application

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form: $\min \text{ } f(X) + g(Z)$ $\text{s.t. } AX + BZ = C$ where $X$, $Z$ and $C$ are real ...
0
votes
1answer
29 views

Farkas's Lemma for SDPs

One formulation of Farkas's Lemma for semidefinite programs is the following statement: Let $A_1,\ldots,A_n$ be symmetric $m \times m$ matrices. The system $$ x_1A_1 + \cdots + x_nA_n \succ 0 $$ ...
1
vote
1answer
114 views

Knuth's Sandwich Theorem: requesting proof clarification

The question is about F6 of Section 8 ("Elementary facts about cones") in Donald Knuth's Sandwich Theorem (http://arxiv.org/pdf/math/9312214.pdf). He claims to prove $(A \cap B)^* = A^* + B^*$ when ...
0
votes
1answer
131 views

Gradient descent (with line search) for convex functions viewed as alternation

I have fundamental confusion about gradient descent (with line search) and the reason it works. I try to explain my view here, and please tell me where it goes wrong. Let $f: \mathbb{R}^n \to ...
1
vote
2answers
85 views

Free solvers in C/C++ for convex integer programming

I need to solve the following integer program: $\text{minimize } \sum_{i=1}^n(a_{i0} x_i + \sum_{k=1}^3 a_{ik}w_i^k + \sum_{j=1}^m d_{ij}y_{ij})$ $\text{subject to}$ $$ \sum_{i=1}^n y_{ij}=1, \quad ...
0
votes
1answer
35 views

How to deal with non-existent derivatives in Lagrangian?

I am stucked at a detail in a constrained optimization problem: Question Assume that the objective function is continuous on its domain $D$, but at some points $Z \subseteq D$ it is not ...
0
votes
1answer
60 views

$F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$ Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex ...
0
votes
1answer
45 views

Coordinate descent with constraints

Coordinate descent is a powerful method for solving optimization problems like $$\min_x \tfrac{1}{2}x^T A x + b^T x + \lambda ||x||_1$$ where $A$ is symmetric and positive definite, $\lambda>0$ ...
1
vote
0answers
19 views

Can this type of constraint be recasted to a convex constraint?

I have an optimization problem where all the constraints are linear but some of the type: $$ y_i = \frac{x_i}{\sum_k x_k} $$ It seems that the equality can be relaxed to an inequality adding the ...
0
votes
1answer
17 views

What is a $0$-sublevel set?

I read the notes of S. Boyd, and am confused about the following: $f_0(x)$ is quasiconvex. I am confused about the latter one particularly. What does it mean? Thanks!
1
vote
2answers
31 views

Help needed on convex optimization!!

Can some please help me in solving the below questions. I want to prove the below functions are convex, concave or neither.
1
vote
2answers
34 views

When solving convex problem, why we don't just find the optimal of the cost function and project it back to the feasible set

I know that is wrong, because if it is right people would not develop so many algorithms. But why? Can I ask for some examples illustrating this does not guarantee optimal?
0
votes
1answer
62 views

Sparse representation using overcomplete dictionary - when is L1 norm not good enough?

I am trying to find a sparse representation of a signal consisting of a single sinusoid and a single spike (delta function), via what I think is traditionally called "basis pursuit", using $L_1$ norm ...
1
vote
0answers
34 views

When does l1 regularisation give a sparse solution?

I was maximising a likelihood function, which is convex. I know that the system has a K-sparse solution. I wanted to know the conditions (or some sufficient conditions) on the likelihood function ...
0
votes
3answers
169 views

How exactly do I prove that I find the maximum of the function

I am currently trying to maximize an objective function $f(a,b,c,d,e)$ over the variable $b$ only. By taking the derviative of f over b, setting it to zero, I can solve b in terms of the other 4 ...
0
votes
1answer
44 views

Proximal operator fixed point property for matrices

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\dom}{\operatorname{dom}}$ Recall again that the proximal operator for vectors $\prox_{f}: R^n ...
1
vote
1answer
50 views

Finding analytically proximal operator of $g(P)=\|PX\|_1$ using Moreau decomposition

$\newcommand{\prox}{\operatorname{prox}}$ Consider the function $g(P) = \|PX\|_1$, where $P \in R^m \times R^m$ and $X \in R^m \times R^n$ is a known constant matrix. In the paper by Parikh and Boyd ...
2
votes
1answer
51 views

Proximal operator, scaling by a matrix

Proximal operator is defined for matrices as a map prox$_f:R^m\times R^n \rightarrow R^m\times R^n$: prox$_f$(X) := argmin$_{Y\in R^m\times R^n}$ $ f(Y) + \frac{1}{2}||Y-X||^2$ In case of vectors, ...
3
votes
0answers
45 views

Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$ x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0 $$ which is assumed to have a unique minimizer. The ...
1
vote
0answers
57 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 ...