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.

learn more… | top users | synonyms

3
votes
1answer
51 views

Understanding the conditions for which ADMM can be applied

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
5
votes
0answers
51 views

Difference of convex functions optimization problem in R

I am seeking of any already written R package which could help in optimization technique which is called Difference of convex functions. This technique is sketched here and could be very useful for ...
1
vote
1answer
111 views

How to efficently solve: min $\sum_{ij}(a_{ij}x_{ij}^2 + b_{ij}x_{ij})$ s.t

I am trying to solve the following problem, where $a_{ij} \ge 0 \ \forall i,j$: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})\\ \mbox{subject ...
3
votes
2answers
85 views

Second-order derivative condition for convexity

It is written in a book I'm reading that $$\nabla f(x) = \left( \frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2},...,\frac{\partial f(x)}{\partial x_n}\right)$$ and $$\nabla^2 ...
0
votes
0answers
55 views

Iterative optimization problem

There is problem which I am stuck in that for nearly a month. I have encountered a problem which is as follows (equation (1)). \begin{align} &\min_x &f(x) &\quad\implies \text{represents ...
6
votes
1answer
119 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$ ...
0
votes
0answers
62 views

Iterative Optimization [duplicate]

I have encountered a problem which is as follows \begin{align} &\min_x &f(x)\\ &\operatorname{subject to} &h_i(x) =0\\ & &g_i(x) = 0 \end{align} where $f(x)$ is a quadratic ...
0
votes
0answers
30 views

CPLEX: function convex on search space but not on whole R^n

I have an optimization problem where the function i want to minimize is convex; it's of the form $f = \sum_i - x_i y_i$, all variables have a constraint $x_i \geq 0, y_i \geq 0$, and all other ...
0
votes
0answers
23 views

Algorithm for SDP with repeated structure, diagonal blocks

I wish to solve a semidefinite relaxation of the following problem: $$ \begin{array}{rl} \min_{z_1,\ldots,z_k\in\mathbb R^n}\ & z^\top A z\\ \textrm{s.t.} & z_i^\top B_j z_i+c_j^\top z_i=0\ ...
0
votes
1answer
137 views

Storage complexity of SDP solver SCS

This is a follow up question to this question. Consider the following SDP in standard form: \begin{align} &\min_{X\in S^n, X>0} \operatorname{tr}(AX)\\ &\mbox{subject to}\; ...
3
votes
1answer
81 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 ...
3
votes
1answer
55 views

Maximizing a function over a polytope

I have to maximize $$f(x,y)=-\log(xy)$$ However I need it over the polytope $T=\mathrm{conv}\{(1/2,1/2),(1,2),(2,1)\}$ and this gives me problems: Then I get $$f_x(x,y)=1/x=0$$ $$f_y(x,y)=1/y=0 $$ ...
5
votes
1answer
134 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 ...
1
vote
2answers
103 views

Mathematical programming formulation of triangle intersection

Given variables $a_1$, $b_1$, $c_1$ and $a_2$, $b_2$, $c_2$ representing the vertices of two plane triangles, how might one specify the requirement for the two triangles to intersect as an objective ...
1
vote
1answer
55 views

Python package for large absolute value optimisation

I have an absolute value optimisation problem $$\min_x \sum |r-Cx|$$ where $x$ is small around 200 dimension. But $C$ has lots of rows, $C_{30000\times200}$ and $r$ is $30000\times1$. So this will ...
3
votes
1answer
60 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 ...
4
votes
2answers
217 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, ...
0
votes
1answer
41 views

Convex optimization for symmetric (but not positive definite) problems?

Can one employ convex optimization for symmetric but not positive definite problems? I tried using MATLAB's quadprog() function to solve this problem: ...
2
votes
1answer
79 views

Optimization with matrix exponential constraint

Suppose I'm optimizing for an unknown $x\in\mathbb{R}^k.$ I have a linear operator $A(\cdot)$ that maps $x$ to an $n\times n$ symmetric matrix, i.e., $A:\mathbb{R}^k\rightarrow\mathbb{R}^{n\times ...
2
votes
1answer
82 views

How can I solve a nonlinear optimization problem where constraint contains exponential term?

I have the optimization problem as below: $$\begin{align} &\text{maximize } \sum_{k=1}^{M} \alpha_k {R}_k\\ &\text{subject to: } \exp \left[ - (2^{{R}_k } -1) \left(\frac{\tilde{Z} g_{k} ...
2
votes
1answer
148 views

Comparison of convex hulls [closed]

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; ...
2
votes
1answer
128 views

Solve $AX = B$ where $X^T X = C$

Is there a natural way to find the solution to $$AX = B, X^TX = C \enspace \text{?}$$ $X$ is a matrix and has a small number of rows, and $A$ is sparse. An approximate solution would be fine.
4
votes
1answer
49 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 ...
0
votes
1answer
50 views

Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$ We can in theory convert the constraints to the convex hull ...
0
votes
0answers
69 views

Cyclic Coordinate Descent Optimization for Bayes Logistic Regression (Code Problem?)

I am trying to reproduce the CLG algorithm for the Laplace prior given in Genkin et al to find the MAP estimates for a logistic regression model. I am using Python (Anaconda 2.2) with Numpy to ...
0
votes
2answers
114 views

Convex quadratic problem solver gives different answers?

I am pretty sure that the following variance objective function should be a convex quadratic problem. My objective function is as follows: $$ \text{argmin } \text{var }(X*L) \xi \geq 1, \text{ where ...
0
votes
1answer
126 views

Converting smooth $L1$ norm approximation into SOCP

I am approximating the expression $\left\|Ax-b\right\|_1$ by the expression $$\text{minimize}\;\;\sum_i\sqrt{(a_i^Tx-b_i)^2+\varepsilon}$$ where $a_i$ is the $i^{th}$ row of $A$. This function is ...
0
votes
1answer
120 views

What are open source codes for interior point optimization to modify?

I am working on a modified interior point algori thm for semidefinite for my special problem. I don't have enough skills and knowledge about interior point for semidefinite to code it from scratch. ...
1
vote
1answer
88 views

How to nest 2 simple CVX problems? Is it possible at all?

I have the underdetermined outer optimization problem $$\text{min}_{x\geq 0}\quad \|Ax-b_1\|_2^2+\|AT(x)-b_2\|_2^2$$ with $A\in\mathbb{R}^{m\times n}$ and $m<<n=64^2$ or in corresponding CVX ...
0
votes
1answer
57 views

How to write Goemans-Williamson MAX-CUT relaxation as SDP

Let W be a graph Laplacian (symmetric diagonally dominant, and thus PSD), and X the matrix variable. Let $<A,B>=Tr(A^TB)$. $$\text{Maximize}\;\; \displaystyle\sum_{i,j} w_{ij}(x^{(i)}\cdot ...
0
votes
0answers
30 views

comparing different practical convex optimization algorithms

I am trying to implement limited memory bundle method on piece-wise linear convex optimization problem (with dimension=5000) in c++, however, it seems limited memory bundle method code is not ...
0
votes
0answers
17 views

Applying smooth minimization on non smooth problems

Is it possible to apply Nesterov's smooth minimization of non smooth function on a problem of the form $$\mathop {\min }\limits_{\lambda \in {R^m}} \mathop {\max }\limits_{\sigma \in {{\left\{ ...
1
vote
0answers
40 views

Numerical Implementation of “integrates to some values” type constraint in convex solvers?

I am maximizing a linear functional subject to an integrates to one constraint. More explicitly, my problem is $$\begin{align} &\max_{x \in \mathbb{R}^n}\quad c \cdot x\\ &\text{subject to} ...
1
vote
1answer
151 views

Looking for open source numerical solver

I am trying to solve an optimization problem $$\begin{align} &\min f(x)\\ &\text{subject to } Ax\leq b\\ &x \in R^{\sim 10000},\ b \in R^{\sim 10000} \end{align}$$ $A$ is somewhat sparse ...
1
vote
1answer
77 views

beta in Nesterov's first method for piece wise linear convex optimization problem

I am trying to implement Nesterov's first method to solve convex piece-wise linear optimization problem, from this website: ...
0
votes
0answers
32 views

state of art non smooth convex optimization [duplicate]

Basically, I am trying to implement non-smooth convex optimization in c++. I am wondering what is the state of art condition of non-smooth convex optimization. For example, what's the best method ...
0
votes
1answer
68 views

fast gradient method for convex piecewise linear function

What is the state of art gradient based algorithms in convex optimization solving non-smooth piece-wise linear functions? Thank you. EDIT: It is different from one of my previous post in the sense ...
0
votes
1answer
141 views

Doubt regarding stopping criterion for Newton method

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
4
votes
2answers
204 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: $$\text{Minimize}\;\; ||A-S||_2$$ $$\hspace{-5mm}\text{Subject to}\;\; S\geq0$$ $A$ is given and $S$ is the ...
0
votes
1answer
65 views

Finding the minimum of a convex function with noisy evaluation

I want to find the argument of a function for which it is minimal. The function is expected to be convex but I cannot evaluate it exactly so I have to deal with the fact that there's noise on top. The ...
2
votes
1answer
81 views

Generalized linear-fractional program [closed]

Given the generalized linear-fractional program: $$\text{Minimize}\;\; \max_{i}\Big|\frac{c_i^Tx+d_i}{e_i^Tx+f_i}\Big|$$ $$\hspace{-5mm}\text{Subject to}\;\; e_i^Tx+f_i>0$$ I convert this into the ...
0
votes
0answers
111 views

Help with the definition of constraints for a joint optimization problem

A trajectory is piecewise defined by the following polynomial form: $$ f(t) = a + bt+ct^{2}+dt^{3}+et^{4}+ft^{5}+gt^{6}+ht^{7}+it^{8}+jt^{9} $$ for every single segment composing the trajectory (the ...
3
votes
1answer
342 views

Converting quadratic constraint to linear matrix inequality

So I have the quadratic programming problem: (x is the variable) $$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ ...
0
votes
1answer
72 views

Comparing computational complexity of convex optimization and a heuristic algorithm

I am working on a resource allocation problem, which is convex and has several constraints, and I want to compare the computational complexity of the following algorithms. 1) The algorithm that uses ...
0
votes
1answer
139 views

Convex Polygon Intersection

Determining the intersection of two convex polygons is one of the fundamental problems in computational geometry . I'm asking for an algorithm having: INPUT: Given two convex polygons P and Q in 2D ...
1
vote
1answer
111 views

How we can implement the result of maximum principle in our numerical optimization algorithm?

I have an algorithm (in R) that maximizes a convex function on a compact convex set in every iteration. Based on the maximum principle, I know that the maximima are only attained on the boundary. But ...
0
votes
0answers
223 views

Phase retrieval via SDP (semidefinite program) of 2D test image (Matrix completion)

In SDP based phase retrieval we have intensity measurement (abs(FFT2(x))^2) of the form A(xo) = |ak,x|^2 =b^2, phase retrieval is then find x that obeys A(xo)=b The quadratic measurements can be ...
0
votes
1answer
26 views

CVX : Obtaining the minimizing parameter at the optimum

In CVX, how do we return the value of the parameter over which the problem is minimized at the optimal value? By this, I mean, how do we obtain $$x^* = \arg\min_x f(x)$$ when solving the problem ...
2
votes
1answer
92 views

Projecting onto convex shapes - best fit convex polygon

I am interested in studying a problem of the form $\min F(\Omega)$ where $\Omega$ varies in the class of convex, open sets in the plane. An idea is to deform $\Omega$ at each step using a steepest ...
0
votes
0answers
69 views

Coding a convex problem in CVX

I am new to CVX and am trying to simulate this convex problem I found in a paper. $$\min_{\gamma,\mathbf{mu},\mathbf{G},\mathbf{\Omega},t} \text{Tr}(\mathbf{G}\mathbf{C}\mathbf{G}^H)+t \\ s.t. ...