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

learn more… | top users | synonyms

0
votes
1answer
19 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 0$$ Where Q is square ($n$x$n$), positive semi ...
-2
votes
0answers
17 views

Quadratic programming with linear equality constraints in Matlab [on hold]

I have to identify an ARX under some linear constraints, this means that I have a quadratic programming with linear equality constraints problem. One way is to use the following equations in the ...
0
votes
0answers
10 views

Convex Quadratic Programming - solution always exists?

Assume I want to minimize $$ f(x) = x^T Q x + c^T x $$ $$ Ax \leq 0 , Bx = d$$ where $Q$ is symmetric and positive definite. This implies that f is strictly convex and has at most one minimum. How ...
0
votes
0answers
14 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
14 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
38 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
42 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
22 views

How to write a matlab code to get the convex weights? [on hold]

Given the value $P_1,P_2, P_3$, how to write a matlab code to calculate the optimization weights $\omega_i$ in the following equation, $$ P_{new}^{-1} = \omega_1 P_1^{-1} + \omega_2 ...
0
votes
0answers
29 views

No element in the convex hull of other elements [on hold]

Consider a set $A$. If there is no element $a_i \in A$ lies in the convex hull of the other elements $\text{conv}(A\backslash \{a_i\})$.... Could anyone give me an simple example for this ...
0
votes
0answers
14 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
0answers
93 views
+50

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
18 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
51 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
0answers
45 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
45 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
95 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
38 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
16 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
14 views

Linearized ADM and matrix adjoints

$\newcommand{\argmin}{\operatorname{argmin}}$ In this question I am referring to this paper ...
1
vote
0answers
16 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
46 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
37 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
37 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
21 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
103 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 ...
1
vote
1answer
40 views

Optimization problems on the circle

Consider the optimization problem $$ \min_{x \in \mathbb{R}^2} x^{\top} P x + q^{\top} x$$ subject to: $$ A x = b, \ x \in X, \ x_1^2 + x_2^2 = 1$$ where $X$ is compact and convex. Then ...
0
votes
1answer
98 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
58 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
25 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
55 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
25 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
14 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
27 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
votes
0answers
32 views

Constraint optimization with lagrangian

I am having trouble regarding the general steps one needs to take in order to solve an constraint optimization using Lagrangian. More specifically, I want to maximize objective equation $f(x,y,z,w)$ ...
1
vote
2answers
29 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
32 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
23 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
160 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
21 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
47 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
28 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
38 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
41 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
44 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
41 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
34 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
33 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
42 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
52 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 ...