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

learn more… | top users | synonyms

0
votes
0answers
5 views

Optimization problem shortest path distance and critical node detection problem (interdiction).

I am trying to formulate this optimization problem, max $d_{ij}$ where $d_{ij}$ is the shortest distance between active nodes i and j. However my problem is connecting my decision variable with the ...
3
votes
1answer
25 views

Are the stationary points of a strongly convex function unique in each dimension?

Consider a strongly convex function $~f: \mathbb{R}^n \rightarrow \mathbb{R^+}~$ with a unique minimum at the point $x^* \in \mathbb{R}^n$. I am wondering: if I have another point $y \in ...
0
votes
0answers
9 views

The Dual of a Dual problem for Convex Optimization Problem [on hold]

Assume we have a convex optimization problem, and its dual, and there is strong duality between the primal and the dual problem. My question is if we take the dual of the dual problem, how the dual ...
0
votes
0answers
46 views

Is the ratio trace problem convex?

I have a ratio trace problem described as follows: $\arg\max_{w} \text{trace}((w^tAw)\cdot \text{inv}(w^tBw))$, where A and B are full rank matrices. This problem can be solved via generalized ...
1
vote
1answer
10 views

Fenchel duality in conic program

The question is from the textbook Convex Optimization Algorithms, prof. Bertsekas, p.511 A special case of Fenchel duality is the following: \begin{equation} ...
1
vote
2answers
44 views

Gradient mapping minimization problem

I am trying to solve this particular problem which can be found in this paper: $$\underset{y\in\Delta_n}{\text{argmin}}\{\langle\nabla f(x),y-x\rangle+\dfrac{1}{2}L\|y-x\|_1^2\}$$ I tried formulating ...
0
votes
1answer
47 views
+50

What's wrong in this dual derivation?

I have a function in the form \begin{align} f(q,M)=\sup_{0\leq \alpha \leq 1} -\alpha^T (R\odot M)\alpha+\alpha^Tq \end{align} which is a dual of a minimization problem, where $R$ and $M$ are ...
2
votes
0answers
57 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq ...
6
votes
2answers
273 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
8 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix ...
0
votes
0answers
12 views

The Dual Problem

I have a question related to the dual problem of a maximization primal problem with norm inequalities constraints. I want to find the dual problem for the following primal optimization problem: ...
2
votes
1answer
31 views

How to solve the convex combination problem of matrix?

Let $A \succeq B$ denote matrix $A-B$ is positive semidefinite, and here is the definition of redundant(all the matrix dimensions are $N\times N$ ): Given a set of matrix $\{B_i\}_{i=1}^{l}$, if ...
0
votes
0answers
13 views

Augmented Lagrangian method for nonsmooth problem

Given the problem $\min \sum_i f_i(x_i) \ \ ; \ Ax = b, x_i \in [\ell_i,u_i] $, we can construct the augmented Lagrangian as $$L_\rho(x,\lambda) = \sum_i f_i(x_i) + \lambda'(Ax-b) + ...
0
votes
0answers
10 views

Monotropic polyhedrally constrained programming, implementations

I'm looking for algorithm implementations that can solve problems of the type $$\min \sum_i f_i(x_i) \\ s.t. Ax \leq b \\ Cx = d \\ x_i \in [\ell_i,u_i]$$ I.e. polyhedrally constrained optimization ...
0
votes
0answers
20 views

KKT system with rank-deficient constraints

I have an optimization problem of the following form: $$ \begin{aligned} \operatorname*{minimize}_x & \quad \frac{1}{2}||x - a||^2 \\ \operatorname{subject~to} & \quad ...
2
votes
2answers
105 views

Boundedness of sublevel sets of convex function (Boyd VandenBerghe)

(This is from the book Convex Optimization on p.474 on algorithms for unconstrained minimization) Assumptions The function $f : \mathbb{R}^N \mapsto \mathbb{R}$ is convex and twice-differentiable ...
0
votes
1answer
29 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 , ...
0
votes
1answer
14 views

Linear objective with quadratic constraints

I have the problem $$ \text{maximize } f= c^Tx \\ \text{subject to } x^T Q x \leq 1 \\ x,c \in \mathbb{R}^n \text{ , } Q \in \mathbb{R}^{n \times n} $$ and $ Q $ is additionally symmetric positive ...
0
votes
1answer
25 views

how to calculate the projection of a vector onto a closed convex set? [duplicate]

suppose we have a vector $x \in \mathbb{R}^{n}$, and a closed convex set $C \in \mathbb{R}^{n}$. $C =\{x|Ax=b\}$ how to calculate the vector $y \in \mathbb{R}^{n}$, which is the projection of $x$ ...
1
vote
0answers
23 views

Regression linearization to apply Gauss-Newton

I want to try and use Gauss-Newton in order to estimate a solution to the regression problem with normalizing factor $$\min_{x \in \mathbb{R}^n}: \|y - Ax\|_2^2 + \lambda\|x\|_1.$$ To do this, I have ...
0
votes
1answer
28 views

A small but quite general question about the optimization

If I have a minimization problem in which both the objective function and constraint are nonconvex. I use gradient projection method to solve the problem iteratively. If we relax the constraint and ...
0
votes
2answers
43 views

Is the projection function convex?

Define the following function $f:\mathbb{R}^n\rightarrow \mathbb{R}^n$ to be the projection function onto a convex and a closed set C $f(x)=\arg\min_{y\in C} ||x-y||_2^2 $ Denote $f_i(x)$ ...
0
votes
1answer
101 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
1answer
40 views

Compressive sensing for complex matrix

I'm fairly new to compressive sensing, and I have been looking for a MATLAB implementation of the problem $$ A x = b $$ where $A$ is non square, $x$ is kind of sparse and all the numbers involved are ...
-2
votes
0answers
24 views

This fractional quadratic optimization problem is non-Convex, why?

Why is the following function $f(x)$ non-convex? $$ f(x)=\min\frac{x^TQx}{x^TPx+1} $$ where $Q$ and $P$ are positive semi-definite matrices.
1
vote
1answer
28 views

Is this function composition convex?

Say we have two functions $f:R^n\rightarrow R$ , $g:R^m\rightarrow R^n$. Given that $f$ is convex, under what conditions on $f$ and $g$ we will be able to say that the composition function ...
0
votes
1answer
27 views

Failing To Frame Convex Non-Linear Problem as SOCP

I'm trying to reproduce an equation from equation 5 in the paper here: https://web.stanford.edu/~boyd/papers/pdf/rob_downlink_bf.pdf The equation is an SOCP of the form: ...
1
vote
1answer
9 views

Interior of polar cone and self-concordant function

Suppose $f$ is a self-concordant(see 9.6.2) barrier of a proper cone $K$ ( solid,convex, closed and pointed) in $\mathbb{R}^n$. It looks like the value of all $\nabla f$ is just the interior of the ...
0
votes
1answer
25 views

Prove if C is midpoint convex and closed then its a convex set [duplicate]

Midpoint convexity. A set C is midpoint convex if whenever two points a,b are in C, the average or midpoint (a + b)/2 is in C.Prove that if C is closed and midpoint convex, then C is convex. ...
1
vote
1answer
18 views

Can I write $\mathbb{S}_+^3$ as a norm cone?

Let $\mathbb{S}^3_+$ be the set of $3\times 3$ symmetric semi-definite positive matrix. I wonder whether I can write $\mathbb{S}^3_+$ as a norm cone, i.e., $$\exists A\in \mathbb{R}^{m\times 9}, C, ...
1
vote
0answers
34 views

Unique solution of LP

Hi I am working on the following question: If $c \in int(N_P(x))$, then $x$ is a unique solution. I have proven that this is true if $x$ is a vertex. Well I am wondering if the following is a ...
0
votes
0answers
21 views

Multivariable gradient descent with approximation of gradinet

This is not a statistics problem I have a vector $$X=[x_1,...,x_{10}]$$ and a cost function $$y=F(X)$$ and my aim in to find the best $X$ to minimize the cost function. It is impossible to ...
1
vote
1answer
22 views

Can I write $\mathbb{R}^n_+$ as a norm cone?

Let $\mathbb{R}^n_+=\{x=(x_1,\dots,x_n):x_i\geq 0,\forall i \},n\geq 2$. I wonder whether I can write $\mathbb{R}^n_+$ as a norm cone, i.e., $$\exists A, c, \|\cdot\|, s.t. x \in \mathbb{R}^n_+ \iff ...
0
votes
0answers
22 views

What is the right isomorphism for convex set in $\mathbb{R}^n$

Like we have linear transformation for vector space, I wonder what kind of 'transformation' or 'homomorphism' or 'isomorphism'( when the map is bijective) to look at for convex set in $\mathbb{R}^n$. ...
2
votes
1answer
63 views

Proof of convergence for the proximal point algorithm

I'm trying to come up with a super simple proof of convergence on the proximal point algorithm, which uses the iteration scheme $x^{i+1} = \mathbf{prox}_{tf}(x^i)$ where $f$ is a closed, convex ...
0
votes
1answer
43 views

What is a proximity operator? why do we need it?

I am going to deal with convex optimization problems and I am not a math student so I may have some problems in understanding some topics. As you know, many of the optimization problems lead to a cost ...
1
vote
2answers
440 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
0answers
26 views

Strong convexity of quadratic function

Assume that $Q$ is a positive definite matrix, is it true to say that the function $f(v)=v^TQv$ is strongly convex with respect to the norm $||u||=\sqrt{u^TQu}$? Thanks
0
votes
2answers
41 views

Calculation of minimum infinity norm subject to L1 norm

Can somebody tell me how to evaluate the following in MATLAB or any other programming language? \begin{equation} \min_{x \in \partial \|w\|_1} \| x+y\|_\infty \end{equation} $x,w,y \in R^n$. $w,y$ ...
0
votes
0answers
17 views

Notion of outer normal cone and supporting cone if $x \in$ relint($C$)

In my lecture we defined the outer normal cone $ N_c(x^*)= \{ c\ \in \mathbb{R^n} : \max\limits_{x \in C} \ \ c^Tx = c^Tx^* \}$ and the supporting cone $S_C(x^*)= \bigcap\limits_{c \in N_c(x^*)} ...
-1
votes
1answer
39 views

Image restoration in matlab via PDE toolbox

I want to remove a noise for an image using matlab, when the observed image is $$f=u+v$$ where $u$ is the restored image (is the image i want recovered) and $v$ is the gaussian noise. To restore $u$, ...
1
vote
1answer
445 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
40 views

On a modified least square.

Given a vector $y \in \mathbb R^n$ and real constants $x_{ij}$ ($i=1,\dots,n$, $j=1,\dots,p$), we consider a vector $\beta = (\beta_0,\dots,\beta_p)$ which minimize ...
0
votes
1answer
428 views

relation between size of matrix and condition number

I have a matrix A of size NxM. Is there any relationship between size of a matrix A with the condition number ? I am computing the pseudo inverse (pinv in matlab ) ...
0
votes
0answers
44 views

Computational complexity of the following quadratic program (QP)

Let $A^TA$ be a $n \times n$ matrix. I have the following quadratic program to solve: \begin{array}{rl} \min \limits_{x} & x^T A^T A x \\ \mbox{subject to} & \sum_{i=1}^{r} x_i =1, ...
1
vote
3answers
277 views

How to solve $\min \limits_{\mathbf{x}} \| \mathbf{Ax}-\mathbf{b} \|^2$?

Let $\mathbf{x}=[x_1,\ldots,x_K]$. I have the following optimization problem: \begin{array}{rl} \min \limits_{\mathbf{x}} & \| \mathbf{Ax}-\mathbf{b} \|^2 \\ \mbox{s.t.} & x_k\ge 0, \forall ...
0
votes
0answers
26 views

Hölder's inequality/Cauchy-Schwarz for Bregman Divergence?

Consider the Bregman divergence. $$ D_F(p, q) = F(p)-F(q)-\langle \nabla F(q), p-q\rangle. $$ And its dual norm: $D_{F*}(p, q) $ where $ F^*(y) = \arg\min_x \left\{ \langle x, y\rangle - F(x) ...
0
votes
0answers
21 views

How to judge the convexity of this function?

$ f(X) = -\log \det(X^TX+I)$, $X \in \mathbb{R}^{n \times n}$, is this function convex or not? Does anybody have an idea about this problem? Thanks.
0
votes
1answer
467 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
6
votes
3answers
2k views

KKT and Slater's condition

I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following: "For any convex optimization problem with differentiable objective and constraint function, any ...