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

learn more… | top users | synonyms

0
votes
0answers
23 views

Equivalence between standard optimization problem and Langragian form

Given a problem: $$\min_x f(x)$$ subject to $$g(x) \le C$$ In general, when it is equivalent to the problem $$\min_x f(x) + \lambda g(x)$$ for certain $\lambda$? Here my equivalence means : the ...
1
vote
0answers
30 views

maximising sinusoidal functions

I have come across a maximisation problem that I do not know how to handle. I have posted the question here in the past. I have the following function to maximise for $x,y$ $$f(x,y)=a_1 \cos(x) +b_1 ...
1
vote
1answer
27 views

LASSO with equivalent quadratic costs

Is there any fundamental difference between the solutions obtained by minimizing following LASSO cost functions, if any? ( $A_{N \times n }$ and $ N >> n$) $ J=\Vert y-Ax \Vert_{2}^{2} + \...
0
votes
1answer
29 views

Confusion of a formula about Lagrangian

Recently, I am reading a paper about eigenvalue problems. Consider the following problem, which occurs at the first page of the paper. \begin{align} \text{minimize}\quad &x^TAx \\ \text{subject ...
0
votes
0answers
14 views

How to prove a mixed integer function $f(x,n_1,n_2)$ is convex [on hold]

I have a mixed-integer function (with continous and disceret variables); $f(x,n_1,n_2)$ , $x\in[0,a]$ and $n_1,n_2\in N_{0}$. How can I show for a given $x$, $f(x,n_1,n_2)$ is convex with respect to $...
0
votes
0answers
18 views

From constrained to unconstrained optimization

I have the following convex optimization problem: \begin{equation}\label{prob} \begin{aligned} &\underset{{\bf W, \xi}}{\text{min}} & \frac{1}{2} ||{\bf W}||_2^2 + \sum_{i=1}^n C_{y_i}\max(0,...
0
votes
0answers
12 views

Formulation of constraints

I would like to formulate the following constraints in a tractable form so that I can perform an optimization over the decision variables $A,x_i,y_i$: $$ A + \sum_{i=1}^N x_i D_i + \beta \big(\sum_{i=...
3
votes
1answer
27 views

minimum of sum of strictly convex functions

Is the following statement true? If so, how can I find a proof? Suppose that $f_1$ and $f_2$ are strictly convex functions on a convex set $X \subseteq \mathbb{R}^n$. If $f_1$ and $f_2$ have minimum,...
0
votes
0answers
17 views

how to calculate infimum of Augmented Lagrangian?

should any body explain that how do we calculate these step? \begin{align*} L(x,y) &= f(x) + y^T(Ax-b)\\ g(y) &= \inf_x \, L(x,y) \\ &= \inf_x \, f(x) - \langle -A^Ty, x \rangle - \langle ...
3
votes
1answer
66 views

Why is this matrix symmetric?

There is an example in the Convex Optimization lecture notes, Boyd. He just said in the lecture that the matrix which is underlined in red color is symmetric! How can we claim that when there is no ...
1
vote
1answer
96 views

Difference between Gradient Descent method and Steepest Descent

What is the difference between Gradient Descent method and Steepest Descent methods? In this book, they have come under different sections: http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ...
0
votes
1answer
41 views

Gradient descent with linear perturbation

Given a convex, differentiable function $f$ (from a Hilbert space to $\mathbb{R}$) with a minimum (say $x^*$), I know you can find $x^*$ using gradient descent. Suppose now that you apply gradient ...
12
votes
1answer
448 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
2
votes
1answer
66 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 $\...
2
votes
0answers
63 views

Accelerated gradient descent versus nonlinear conjugate gradient descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has $O(1/T^2)...
2
votes
2answers
379 views

Gradient descent vs ternary search

Consider a strictly convex function $f: [0; 1]^n \rightarrow \mathbb{R}$. The question is why people (especially experts in machine learning) use gradient descent in order to find a global minimum of ...
2
votes
1answer
563 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
9 views

Nesterov's bound between quadratic and strongly convex cases?

Are there some examples of simple & strongly convex functions for which the convergence bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s bound for strongly convex case $\...
4
votes
3answers
394 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
0answers
24 views

How to solve an inverse problem $d=Ax_1 + Ax_2$

In the optimization problems, there is an operator, $A$, which transforms the model, $x$, to the data domain, $d$. Generally, we don't know the model and we are trying to find it according to the ...
-1
votes
0answers
14 views

What determines the convergence time of a linear program?

I was wondering what are the properties of an LP problem or its the objective function that determine how fast CPLEX finds an optimum. To be specific, given a classical linear programming problem ...
0
votes
1answer
20 views

Convex set equals convex functions within optimization?

Can optimizing a convex function subject to convex constraints be written as optimizing the function subject to a convex set? Does the intersection of convex nonlinear ineualities necessarily describe ...
0
votes
1answer
44 views

Difference between online optimization and stochastic optimization

I have come across above two terms often together. Some authors have distinguished one from the other. Can somebody give me precise differences/similarities between online optimization and stochastic ...
0
votes
0answers
16 views

Projected gradient descent with momentum

Can we apply momentum to projected gradient descent? If so, how should we do that? In the domain I'm working on, momentum greatly speeds up gradient descent. However, I want to do projected ...
0
votes
1answer
15 views

Solution set of a linear matrix inequality is the inverse image of the positive semidefinite cone under an affine transformation

Consider the following matrix inequality: $A(x) = x_1A_1 + x_2A_2 + \dots + x_nA_n \preceq B$. In Stephen Boyd's book on convex optimization, it is mentioned that the solution set of the above matrix ...
6
votes
1answer
235 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t $\...
1
vote
2answers
28 views

Convexity of Certain Functions

Consider the set of functions: \begin{equation} f_n(t) := t^n e^{(\frac{c}{t^n})}, \end{equation} where $c$ is a non-zero real constant. I know that for $n=1$ $f_1(t)$ is convex on $(0,\infty)$ and ...
2
votes
2answers
41 views

Maximizing a convex quadratic function in CVX and Matlab

I understand that a convex function can not be maximized as there is no such value. However, consider the following function: $$\begin{array}{ll} \text{maximize} & 3x^2 + 5y^2\\ \text{subject to} ...
-2
votes
1answer
634 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?
1
vote
0answers
439 views

Error on optimization problem, maximize log determinant on CVX

$A$ is an $N \times N$ complex matrix $W$ is an $N \times N$ complex matrix $C$ is an $N \times N$ complex diagonal matrix $u$ is a scalar $V$ is an $N \times N$ complex matrix, whose diagonal elects ...
0
votes
0answers
26 views

related to biconcave optimization

I have a bivariate function $f(x,y)$ both $x,y$ can assume values within closed interval i.e. $x_1\leq x\leq x_2$ and similarly $y_1 \leq y \leq y_2$. I know that for a fix value of $x$ the function ...
1
vote
1answer
1k views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
-5
votes
0answers
23 views

product of two convex function is convex or not? [closed]

Help me!!! if f(x) = x'Ax, g(x) = x'Bx where A, B are positive semidefinite matrices and x' is transpose of x, is f(x).g(x) convex or not? Thanks
2
votes
0answers
39 views

Convex optimization with $\ell_0$ “norm”

I have an optimization problem of the form $$\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&||x||_0 \le t,\end{align*}$$ where $t$ is a given constant and $f:\mathbb{R}^d \to \...
0
votes
1answer
20 views

Convexity versus Strict Convexity

Let $u,v,w\in\mathbb{R}^n$ be three points that are not collinear. We define $$ \triangle(u,v,w):=\{\alpha u+\beta v+\gamma w:\alpha+\beta+\gamma=1, \alpha,\beta,\gamma\geq 0\}, $$ $$ [u,v]=:= \{tu+(...
1
vote
0answers
54 views

Analytical, numerical and graphical approaches to solve convex optimization problems?

I'm wondering if there are analytical approaches to solve these problems(I found these problems in a book by Stephen Boyd): minimize $f_0(x_1,x_2)$ subject to $2x_1+x_2\ge1$ $x_1+3x_2\ge1$ $x_1\...
1
vote
1answer
34 views

What is the easiest way to optimize the weighted sum of L2 norms?

I have the following cost function (solving for $M$ - the $x_i$s are known): minimize $\sum_i\sum_j(w_{ij} \cdot (x_i-x_j)^T\cdot M\cdot(x_i-x_j))$ ($w_{ij} \in [-1,1] $) subject to: $M \succeq 0$ (...
1
vote
1answer
15 views

Proof: $\underset{\|q\|=1}{\max} q^TAq = \lambda_{\max}$ with $q$ the corresponding eigenvector ($A$ symmetric)

This problem is quite old and there should be similar problems. I know the following technique: \begin{equation} \begin{aligned} q^TAq=q^TU\Lambda U^Tq=(U^Tq)^T\Lambda (U^Tq) \end{aligned} \...
0
votes
2answers
76 views

Easy interpretation of matrix multiplication with a set

I have just started learning convex optimization. I am having little bit difficulties in some notations. Currently I just encountered the following equation: $$ \boldsymbol{epi}(wf) = \left[ \begin{...
0
votes
0answers
10 views

Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given submodular ...
1
vote
2answers
45 views

Optimization with L_infinity norm regularization

I'm trying to solve an optimization problem of the form $$\text{minimize } \; f(x) + \|x\|_\infty$$ where $x$ ranges over all of $\mathbb{R}^n$ and $f:\mathbb{R}^n \to \mathbb{R}$ is a nice, smooth, ...
1
vote
1answer
66 views

Corollary 2.1 in Ekeland and Temam on lower semicontinuity

Why in Corollary 2.1 on page 10 (see the picture) from Ekeland and Temam book Convex Analysis and Variational Problems there is equality in (2.11), i.e why $$\forall u\in V,\quad \overline F(u)=\...
2
votes
2answers
1k views

proximal operator of infinity norm

What is the proximal operator of $\|x\|_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
1answer
62 views

show the quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$ is quasi-concave

I have a quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$, with $x_i$ nonnegative and $A \in[0,1)$. And w.l.o.g. we can normalize $x_i's$ to between 0 and 1. In ...
2
votes
1answer
57 views

Optimize $\max _{x_1,x_2,…,x_N} N , \text{ s.t.} \sum_{i=1}^N f(x_i) \le a$

$Is there general theory for solving optimization problem of the following kind \begin{align} &\max _{x_1,x_2,...,x_N} N \\ \text{ s.t.}& \sum_{i=1}^N f(x_i) \le a\\ &\sum_{i=1}^N g(x_i) \...
1
vote
2answers
53 views

Optimization with box constraints - via nonlinear function

I have the following convex optimization problem over $\mathbb{R}^n$ with box constraints: $$\begin{align}\text{minimize }&\;f(x)\\ \text{subject to }&\;x \in [-1,1]^n\end{align}$$ I can see ...
1
vote
2answers
16 views

2-normed square meaning

I heard $2$-normed square in a lecture talking about the objective function of least-squares. What does the $2$ mean? I understand we take norm and square it, $2$ doesn't make sense to me. $$\|Ax−B\|^...
0
votes
1answer
39 views

Proximal operators on Balls (Projection)

I was following this tutorial, In section 21 it is given Proximal operator over a ball $B_\epsilon$ of radius $\epsilon$ as $$\text{Proj}_{B_\epsilon(y)}(u) = y + (u-y) \max({1 , \frac{\epsilon}{||{u-...
3
votes
1answer
40 views

Is there a way to measure how (non)convex a function is, maybe analogous to condition number?

Consider the functions $f(x) = \sin x$ and $g(x) = (x+1)^2 (x-1)^2$. We know that $f$ has an infinite number of local minimizers and is nonconvex on a non-compact subset of $R$. We know that $g$ has ...
1
vote
0answers
11 views

Proof of the existence of a rational finitely generated cone

Let $P$ be a rational polyhedron and $F$ be the inclusion-wise minimal face. Then we define: $C_F= \left\{c\in \mathbb{R}^n : F \subseteq \left\{x \in P:c^Tx=\max\left\{ c^Ty:y \in P\right\}\right\}\...