Questions tagged [convex-optimization]
Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function.
214
questions
15
votes
5answers
14k views
Minimizing the Sum of Absolute Deviation ($ {L}_{1} $ Distance)
I have a data set $x_{1}, x_{2}, \ldots, x_{k}$ and want to find the parameter $m$ such that it minimizes the sum $$\sum_{i=1}^{k}\big|m-x_i\big|.$$
that is
$$\min_{m}\sum_{i=1}^{k}\big|m-x_i\big|.$$...
14
votes
2answers
21k views
What are the advantages/disadvantages of interior point methods over simplex method for linear optimization?
As I understand it, since a solution to a linear program always occurs at a vertex of its polyhedral feasible set (if a solution exists and the optimal objective function value is bounded from below, ...
12
votes
2answers
6k views
Solving a least squares problem with linear constraints in Python
I need to solve
\begin{alignat}{1}
& \min_{x}\|Ax - b\|^2_{2}, \\
\mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\
& \quad x_{i} \geq 0, \quad \forall{i}.
\end{alignat}
I think it is a ...
11
votes
2answers
7k views
CVXOPT VS. OpenOpt
CVXOPT: http://abel.ee.ucla.edu/cvxopt/index.html
OpenOpt: http://openopt.org/Welcome
What's the relation between them?
What are the advantages/disadvantages of them, respectively?
BTW, is there any ...
10
votes
4answers
4k views
Linear programming with matrix constraints
I have an optimization problem that looks like the following
$$
\begin{array}{rl}
\min_{J,B} & \sum_{ij} |J_{ij}|\\
\textrm{s.t.} & MJ + BY =X
\end{array}
$$
Here, my variables are matrices $...
10
votes
3answers
2k views
Do they use semidefinite programming in industry?
I can't see any mention of it in job listings. I've seen mentioned integer programming, MIP, mixed-integer nonlinear programming, LP, dynamic programming etc., but no SDP.
Is it much trendier in the ...
10
votes
2answers
2k views
How is geometric programming different from convex programming?
How is (generalized) geometric programming different from general convex programming?
A geometric program can be transformed into a convex program, and is typically solved by an interior point method....
9
votes
2answers
324 views
Computation Effort of Algorithms
Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation ...
9
votes
3answers
235 views
How to intellligently attempt to rule out convexity?
I want to minimize a complicated objective function, and I'm not sure if it is convex. Is there a nice algorithm that attempts to prove that it is not convex? Of course the algorithm could fail to ...
8
votes
5answers
4k views
Minimizing $\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ using CVX
In Matlab, I would like to minimize the function
$$f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$$
where $S \in \mathcal{M}_{m,m}$ is symmetric and positive definite, which is definitely a convex ...
8
votes
2answers
1k views
Why are convex problems easy to optimize?
Motivated by this top answer to the question: Why is convexity more important than quasi-convexity in optimization?, I am now hoping to understand why convex problems are easy to optimize (or at least ...
8
votes
2answers
1k views
Max of a convex combination over a convex hull of real variables
I have the following linear program:
$$
\begin{array}{cc}
\text{Maximize} & a^T x \\
\text{Subject to} & x_{\min} \leq x \leq x_{\max} \\
& \mathbf{1}^T x = 1
\end{...
8
votes
2answers
3k views
How to deal with norm inequality constraints
I want to solve the (convex) optimisation task:
$max_{r,z}\quad r$
subject to the following two constraints
$r\|x_i\| - x_i^Tz \leq 0 \qquad \forall i=1,\dots, N $
$\|z\| \leq 1$
$r\geq0$
$r$ is a ...
8
votes
1answer
913 views
How to calculate the maximal ellipsoid in a given polyhedron
I am faced with the problem of finding the ellipsoid $B$ ($B$ is a symmetric positive definite matrix) of maximal volume within a convex set $C$ given as a set of linear inequalities $C=\{x| a_i^T x \...
7
votes
3answers
1k views
Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm
So I have a symmetric matrix $A$ and I would like to solve the optimization problem,
$$\hspace{2.5mm}\text{Minimize}\;\; \|A-S\|_2$$
$$\hspace{-5mm}\text{Subject to}\;\; S\geq0.$$
$A$ is given and $S$ ...
7
votes
2answers
182 views
Why is the Dual problem preferred for Maximal Margin Classification?
The primal problem is
$$\min_{w,b}\frac{1}{2}w^Tw$$
$$s.t. f_i(w)=1-y_i(w\cdot x_i+b)\leq0$$
Where $y_i=\pm1$.
Instead of using Gradient Descent directly, the dual is usually solved:
$$\max_{\...
7
votes
2answers
170 views
Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?
I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise.
The other variables in the linear program,...
7
votes
3answers
477 views
Does there exist an arbitrary-precision convex optimization solver?
I have a relatively simple convex optimization problem that involves less than 100 variables but contains a terribly ill-conditioned matrix. I have tried CVX and CPLEX; even though both can typically ...
7
votes
1answer
1k views
Ways to speed up solving an LP with Google's ortools
I'm having an issue solving an LP of the form:
$$\min z = c^Tx$$
$$\text{s.t.}$$
$$Ax \geq b$$
$$x\geq p$$
$1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$
The specific problems I'm running into ...
7
votes
0answers
259 views
Finding points inside cells of power (generalized Voronoi) diagram
Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by:
$$\...
6
votes
1answer
381 views
What is required of the objective function in order to use Gauss Newton method?
From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.
In addition to that, are the following ...
6
votes
3answers
2k views
What is the most appropriate derivative free optimization algorithm
We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$.
If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
6
votes
1answer
115 views
numerical solution of an under-determined linear equation in high dimensions
I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
6
votes
2answers
427 views
Minimizing 1D convex functions
I have a one dimensional convex function
$$f : [a,b] \to \mathbb{R}$$
and want to find the minimum value
$$\min_{a \le x \le b} f(x)$$
I know all derivatives of $f$, so the problem could easily be ...
6
votes
1answer
307 views
Non-linear optimization using approximate gradient
I'm working with non-linear optimization for imaging, such as MRI and CT.
Our problem is of the form $\|Ax-b \|_2^2+\lambda \|Wx\|_1$. $A$ is never formed explicitly, so we're limited to approaches ...
6
votes
1answer
73 views
Sparsity-Promoting Convex Optimization Over Simplex
Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + ...
6
votes
1answer
473 views
How to minimize ratio of L1 and square root of L2 norms
Here is the function I want to minimize:
$$\sum_i\frac{\rho_{\tau}(1-\alpha-\pmb x_i^{\top}\pmb\beta)}{\sqrt{1+\pmb\beta^{\top}\pmb\beta}}$$
where $\alpha\in\mathbb{R}$, $\pmb\beta\in\mathbb{R}^p$ ...
6
votes
1answer
175 views
Confusion related to convexity and concavity of a function
I was reading this paper http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf related to adaptive multi-hyperplane machine for non linear classification
In that paper, they have mentioned about ...
5
votes
2answers
2k views
How to determine whether two cylinders intersect or not?
Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
5
votes
1answer
145 views
Largest hypercuboid inside a polyhedron
Given a polyhedron $\mathbf{Ax} \leq \mathbf{b}$, how to find the largest hypercuboid, with unknown center $\mathbf{x_{0}}$ and side lengths $2\epsilon_{i}$, which are aligned along the co-ordinate ...
5
votes
1answer
422 views
How to transform such an SDP to standard form
I plans to use CSDP to solve the following semi-definite problem:
$$\min_{B, \beta}\operatorname{trace}(CB) \\
\text{s.t.} \ \operatorname{trace}(AB)=1 \\
\beta\geqslant 0 \\
\begin{bmatrix}
1 & \...
5
votes
1answer
62 views
Minimal point of a intersection of $n$ convex sets is always the minimal point of the intersection of two convex sets?
I have the intuition that the minimal point (in the sense of having the lowest value in one of the Euclidean space dimensions) of a intersection of $n$ convex sets is always the minimal point of the ...
5
votes
1answer
340 views
Solving $ (A^{-1} + D)^{-1} v $ with low rank Cholesky factors of $A$
I have a large matrix $A \in \mathcal{R}^{N\times N}$ which is supposedly positive-definite, but numerically low rank. Instead of $A$, I have its incomplete Cholesky factor $G$, such that $A \simeq GG^...
5
votes
1answer
968 views
Fast projection onto semidefinite cone
Lots of algorithms for semidefinite programming make use of the Frobenius projection onto the cone of semidefinite matrices:
$$\mathcal{P}(A) = \min_{X\succeq0} \|A-X\|_{\mathrm{Fro}}^2.$$
Let's ...
5
votes
1answer
170 views
Matrix completion algorithm
I am trying to implement the algorithm presented in this paper which tries to recover a matrix that represent a less noisier dataset of the intensities of the pixels of a set of images. In this case ...
5
votes
0answers
94 views
Generally quadratic convex problem with one non-convex term
How would you approach a standard convex quadratic problem with convex constraints but one non-convex term ? Say $|x|^{0.4}$.
$$\min_x \frac{1}{2} x^{T}Qx + g^Tx + c^T \mathrm{sign}(x) |x|^{0.4} $$
...
5
votes
0answers
104 views
Minimum of quadratic assignment (QAP) with convex objective
Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem:
$$
\min_{\textrm{permutation matrices }P}
\mathrm{tr}(BP^\top AP+C^\top ...
5
votes
0answers
145 views
Difference of convex functions optimization problem in R
I am seeking of any already written R package which could help in an optimization technique which is called Difference of convex functions. This technique is sketched here and could be very useful ...
4
votes
2answers
8k views
Tikhonov regularization in the non-negative least square - NNLS (python:scipy)
I am working on a project that I need to add a regularization into the NNLS algorithm. Is there a way to add the Tikhonov regularization into the NNLS implementation of scipy [1]?
[2] talks about it, ...
4
votes
1answer
323 views
Imposing special structure on Positive Semi-Definite matrix
I am trying to implement the algorithm described in reference 1 using cvxpy. However I am struggling to constrain the matrix $Z_j$ as described in equations (33-35)....
4
votes
1answer
2k views
Biconvex optimization problems
Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?
4
votes
2answers
830 views
Quadratic programs with rank deficient positive semidefinite matrices
Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
4
votes
1answer
1k views
Converting convex quadratic constraint to linear matrix inequality (LMI)
I have the quadratic programming problem in $x$
$$\text{Minimize}\;\; x^T\Sigma x$$
$$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$
$$\hspace{25mm}\boldsymbol{1}^Tx=1$$
...
4
votes
1answer
60 views
SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)
Can someone explain me at a high level the difference between an SCP and an SQP to solve a nonlinear (nonconvex) program?
Assume my problem is something like
$$\min\limits_x. \quad f(x)$$
$$s.t. \...
4
votes
1answer
53 views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
4
votes
3answers
535 views
How can I use Projected Gradient Descent for this optimization problem with constraint?
Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that
$$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
4
votes
1answer
75 views
LP and SDP nomenclature
A canonical form of primal linear program is
$$
\text{minimize } c^T \cdot x \\
\text{subject to } Ax = b, x \geq 0
$$
The dual is
$$
\text{maximize } b^T \cdot y \\
\text{subject to }...
4
votes
2answers
164 views
Non-linear root finding with positive definite Jacobian
I am dealing with a system of non-linear equations:
$$
f(\boldsymbol{x}) = \boldsymbol{y}, \;\;\; \boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^d.
$$
And I know that the Jacobian $J(\boldsymbol{x})$ ...
4
votes
1answer
84 views
Geometric Programming - symbolic version
I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
4
votes
1answer
391 views
Best platform for complex SDPs with n and m around 5-15K?
I am looking to solve a class of SDPs with complex entries, with the semi-definite cone $S^n$, $n$ around 5000 to 15000. Also, $m$, the number of equality/inequality constraints is close to $n$.
I ...
