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

learn more… | top users | synonyms

2
votes
1answer
46 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 ...
0
votes
0answers
12 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 ...
0
votes
0answers
6 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 $\...
0
votes
0answers
21 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
0answers
16 views

Approximation of non-differentiable optimization problems with max function

The book by D. Bertsekas "Constrained optimization and Lagrange multiplier methods", Ch. 5.1.3 describes at p. 312 a method that is used to solve non-differentiable optimization problems by ...
3
votes
1answer
25 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
14 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
14 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 ...
1
vote
2answers
27 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
40 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} ...
0
votes
0answers
24 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 ...
-5
votes
0answers
23 views

product of two convex function is convex or not? [on hold]

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
36 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

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
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
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} \...
1
vote
0answers
48 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\...
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, ...
0
votes
2answers
73 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{...
1
vote
2answers
15 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\|^...
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
1answer
63 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)=\...
3
votes
1answer
39 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\}\...
1
vote
1answer
23 views

How can I calculate the Lipschitz constant with a matrix function?

How to calculate the Lipschitz constant of a matrix function $\mathbf{F(X)} : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$ defined by $$\mathbf{F(X) = AX + B \odot X + XC}$$ where $\mathbf{A}...
0
votes
0answers
14 views

Minimization problem not convex

From Stephen Boyd's lecture series on Convex Optimization, he provides an example of why a minimization problem is not convex: ...
0
votes
0answers
7 views

To show total total dual integrality

Let P be the unit cube with, $P=conv\{\left(\begin{array}{c} 1/2 \\ 1/2\\1/2 \end{array}\right),\left(\begin{array}{c} -1/2 \\ 1/2\\1/2 \end{array}\right),\left(\begin{array}{c} 1/2 \\ -1/2\\1/2 \end{...
2
votes
0answers
31 views

Sup of a linear function

Let $X$ be a banach space or simply a normed space and $C$ a convex (closed) subset of $X$. It is true that if $x \in C$ is such that $f(x)=\sup f(C)$, (in other words $x$ is a supporting point for $C$...
0
votes
1answer
14 views

KKT condition of linearly inseparable Support Vector Machine (SVM)

In the paper Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines, the optimization problem for linearly inseparable SVM is \begin{align} \min\limits_{\boldsymbol{w},...
0
votes
0answers
27 views

Concave optimization on closed unit ball, using penalty function

Background: I want to solve an optimization problem like $$\begin{align*}\text{minimize }&f(x)\\ \text{subject to }&\|x\| \le 1.\end{align*}$$ where $x \in \mathbb{R}^d$, $\|\cdot\|$ is the $...
0
votes
0answers
9 views

How to put constraint on the rank of a matrix to be completed using CVX toolbox [migrated]

I would like to complete a matrix using cvx toolbox in MATLAB. For example: ...
1
vote
0answers
32 views

Maximize $\gamma$ such that $A+\lambda B-\gamma C\succeq 0$

This question follows this previous one: Maximize $\gamma$ such that $A+\gamma B\succeq 0$ This time, $A\succ 0$, $B$ is indefinite and $C = \begin{bmatrix} 0 & \dots & 0 \\ \vdots & \...
0
votes
2answers
43 views

Poof- A function is convex iff it is convex when restricted to a any line that intersects its domain.

When I read the Convex Optimization, Boyd I noticed a statement about determining a function to be convex or not. It is: "A function is convex iff it is convex when restricted to a any line that ...
1
vote
1answer
61 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 ...
1
vote
0answers
21 views

proximal operator to sum of norm functions

The proximal operator is defined by: $$ prox_{\tau f} = \arg\min_u \frac 1 {2\tau} \|u-u^k\|^2 + f(u) $$ I know the solution when $$ f(u) = \|Au+b\|_1 $$ But I wonder how to derive the solution of ...
0
votes
1answer
48 views

Finding the inverse image of a function

While I was reading a Convex Optimization book, I found an example, which is attached below. What is confused me is that how the authors derived/concluded that the hyperbolic cone is the image inverse ...
0
votes
0answers
14 views

Finding Dual of non-standart programming problem

I am working in optimization field. My programming problem is not of the standart form, however it is convex. Objective is nonlinear but concave (log of product). I do maximization. Constaints: ...
0
votes
0answers
20 views

The convex (bi)conjugate and the Fourier transform

In the context of convex optimization, I am looking to find a formula for the convex biconjugate of a function $f: X \rightarrow \mathbb{R}$ where $X$ is a real normed vector space, in terms of its ...
0
votes
0answers
24 views

Sequential versus simultaneous optimization of multivariate problems

Suppose we have the bivariate function $f(x,y)$. I want to solve the following problem: \begin{equation} \min\limits_{(x,y)} \; \; f(x,y) \end{equation} I want to prove theoretically that ...
0
votes
1answer
25 views

Find minimal point of convex set

I'm having some convex set $P \subset \mathbb{R}^n_+$ and a linear-time indicator procedure $I_P(x)$ that allows for each given point $x \in \mathbb{R}^n_+$ to say whether it lies inside $P$ or not. ...
1
vote
0answers
33 views

A set is affine if and only if its intersection with any line is affine. [duplicate]

How can we prove that the a set is affine if and only if its intersection with any line is affine? In fact, I want to know if there is such theorem that the intersection of two affine set is affine?
2
votes
0answers
41 views

Optimizing potential

Let $X$ be a vector field on a Riemmanian manfiold $M$. I recently read that solving: \begin{equation} \operatorname{argmin}_{\phi}\int_M (\nabla \phi - X)^2 d\mu, \end{equation} where $\mu$ is ...
0
votes
1answer
56 views

When is minimizing the sum of images of $f$ equivalent to minimizing the sum of independent variables? [closed]

I have to admit I am not good at math, but this is a problem I am having trouble with. What kind of function $f$ can guarantee that $$\arg\min\sum_{i=1}^Kf(x_i) = \arg\min\sum_{i=1}^Kx_i$$ ...
4
votes
1answer
111 views

Find closest point, subject to linear inequality constraints

Given a point $p\in \mathcal{R}^2$, I want to compute the closest point $x \in \mathcal{R}^2$, subject to linear inequality constraints $Ax \leq b$. That is, $$\begin{array}{ll} \text{minimize} & ...
0
votes
2answers
56 views

Is Frank Wolfe a descent algorithm?

A colleague was explaining to me that the Frank-Wolfe algorithm is a descent algorithm (i.e. its objective value decreases monotonically at each iteration). However, when I tried simulating it, my ...
0
votes
0answers
19 views

Impact of convexity under different changes of variables for different parts of optimization

Let $$ \min_x f(x)$$ such that $$ C(x) \le 0$$ where $C$, and $f$ each are convex under respective changes of variables. How does that impact the optimization? If standard algorithms are sensitive ...
0
votes
2answers
29 views

Optimization of the function of two variables

I have two functions $f(x,y)$ and $g(x,y)$. I want to minimize the sum of these functions w.r.t $x,y \in (0,1)$. I know that for fixed values of $x$, $f(.,y)$ is a decreasing function while $g(.,y)$ ...