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

learn more… | top users | synonyms

0
votes
1answer
41 views

Find the minimum of a function for only positive values of the vector variable

Let variable vector $\vec{q}$ of size $m\times1$, and its diagonal counterpart $m\times m$ matrix $Q=diag(\vec{q})$, for some $m\in\mathbb{N}$. Define fixed parameter $n\times1$ vectors $\vec{p}, ...
1
vote
0answers
9 views

Least expensive way to “walk” with a convex potential

Let $V(x)$ be a non-decreasing, convex function on $\mathbb{R}^+$ such that $V(0)=0$, $V(1)=1$. Let $A_{L,k}$ be the space whose elements are sequences of positive integers $r= (r_i)_{i=1}^{N}$ such ...
1
vote
1answer
28 views

How can a second-order cone problem be expressed as a conic problem?

I realize that a second-order cone is a cone, and thus an SOCP is a type of conic problem. However, to me it doesn't seem so apparent, looking at their equations. Could someone explain how one could ...
0
votes
0answers
16 views

Nonsmooth Gauss-Seidel minimization (coordinate descent)

I have attempted to implement the coordinate descent algorithm for a separably convex problem of the form $$\min \sum f_i(x_i) \\ \text{s.t.} \ Ax = b $$ using the augmented Lagrangian ...
1
vote
2answers
114 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
0answers
22 views

Optimization problem involving semidefinite matrix variable that is constrained to be a tensor product

I would like to solve the following optimization problem. With scalar $R$ and nine (mutually orthogonal) $9$-dimensional column vectors $\vec v_i$ all given ($\vec v_i\!'$ is the row vector Hermitian ...
0
votes
1answer
29 views

L1 norm differentiablility

I am trying to understand the Least Absolute Deviation algorithm, which basically is min l1-norm(z) subject to z=Ax-b I want to understand how is the l1-norm ...
4
votes
1answer
312 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
-1
votes
1answer
16 views

How is a positive semidefinite cone a convexcone [on hold]

Defining a positive semidefinite $n \times n$ matrices as $Z^T XZ\geqslant 0$ for all $Z$ how can this be convex cone?
1
vote
1answer
14 views

Minimum of biconjugate of a nonconvex $f(x)$ is the minimum of $f(x)$ also?

In Fazel (2002) Matrix rank minimization with applications, Ch. 5.1.4-5.1.5, the author finds an analytic expression for the convex biconjugate of their nonconvex function; however, they state that ...
0
votes
0answers
15 views

Solving a semidefinite program with CVXOPT in python [on hold]

I have a simple $M \times M$ linear matrix inequality that I would like to solve (or fail if it's not solvable). The inequality is: $$ 0 \succeq \left[ \begin{array}{ll} A^T P A & A^T P B \\ B^T ...
3
votes
2answers
1k views

How to find closest positive definite matrix of non-symmetric matrix

I have a matrix A given and I want to find the matrix B which is closest to A in the frobenius norm and is positiv definite. B does not need to be symmetric. I found a lot of solutions if the input ...
-1
votes
1answer
47 views

How can a Euclidean ball is a convex set

A convex set is one which has line segment between two points from the set and the line is subset of the set, How to prove Euclidean ball and ellipsoids are convex set ?
2
votes
1answer
37 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 ...
1
vote
0answers
35 views

Can this be expressed in terms of linear constraints?

I'm attempting to find a matrix $X$ that minimizes some function $f(X)$ subject to the constraint that $$ X=W A Z $$ where $A$ is a given non-negative matrix with rows that sum to 1, and $W$ and $Z$ ...
0
votes
1answer
23 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: ...
0
votes
0answers
16 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
34 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
14 views

The Dual of a Dual problem for Convex Optimization Problem [closed]

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
47 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
17 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} ...
0
votes
1answer
64 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 ...
3
votes
0answers
66 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
276 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
13 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
15 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
11 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
21 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
106 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
26 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
44 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
102 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
25 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
35 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
44 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 ...