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
2answers
137 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
20 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: ...
1
vote
0answers
32 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
70 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
132 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
112 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
41 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
35 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
32 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
104 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
64 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
48 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
44 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
37 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
24 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
23 views

What is state of art bundle methods?

What is the most widely applied bundle method currently available? I am trying to solve a large convex optimization as accurate as possible with dimension being roughly 5000+.... Thank you.
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
37 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
144 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
71 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
31 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
56 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
115 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
169 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
49 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
76 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
90 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 ...
0
votes
0answers
29 views

quick projection

I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ): http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf ...
3
votes
1answer
215 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
56 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
106 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
109 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
153 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
24 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 ...
0
votes
0answers
54 views

solving non smooth convex (piecewise linear) optimization using bundle methods in c++

What is the state of art c++ solvers for non-smooth (piecewise linear) convex optimizations (based on bundle method)? I know that piecewise linear objective can be converted to LP combined with ...
2
votes
1answer
67 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
56 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. ...
2
votes
1answer
109 views

non-smooth convex c++ solver

I happened to know that there are advanced established techniques for non-smooth convex optimization in research. For example, these two papers: Nesterov, "Smooth minimization of non-smooth ...
0
votes
0answers
44 views

Checking if convex polytope is nonempty

I am currently running a linear program with MATLAB to determine, by the exitflag of linprog, if two rotated and shifted hypercubes have nonempty intersection. I wondered if this is a waste of time, ...
1
vote
2answers
104 views

convex optimization with objective function given by oracles

Is there any solver for convex optimization in C++ (or some dedicated scheme while no solver is yet available) that could solve a convex optimization problem with objective function value given by an ...
6
votes
3answers
1k 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 ...
1
vote
1answer
47 views

How to find max and min bounds of a uncertain function

First I would like to say that I have searched the for uncertain fitting, robust fitting, linear optimization, convex optimization, etc. But I'm lacking the knowledge to solve this problem, and I need ...
0
votes
2answers
94 views

Numerical minimization of scalar-valued function in 3d

I am finding minimum of the potential function $f=f_1+f_2$, where $f_i: \mathbb{R}^3\to\mathbb{R}$. I was about to use Levenberg-Marquardt as the quick starting point, since it is already implemented ...
2
votes
1answer
61 views

How can I convert this SDP constraint?

I have the following SDP problem: max: $Tr(CX)$ subject to: $X \geq 0, I - X \geq 0$. I want to convert it into the standard form specified by CSDP (I'm using the callable C interface), which is: ...
3
votes
2answers
95 views

A separable nonnegative quadratic program

I have spent quite some time trying to solve the following quadratic program: $$\min \sum_{i=1}^n (\frac{1}{2}x_i^TQx_i+c_i^Tx_i), \quad \mathrm{s.t. } \quad x_i\ge 0 \quad \forall i,$$ where $n$ is ...
3
votes
2answers
103 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})$ ...
0
votes
2answers
287 views

Matlab fmincon with zero user-supplied hessian

I have to solve the problem $$\min_x 1^Tx+\frac{\lambda}{2}\|\Omega\mu-x\|_2^2+\frac{\beta}{2}\|x-\bar{\gamma}\|_2^2\quad\text{w.r.t.}\quad Px-c=0,\ \ x\geq0$$ and in order to do that with Matlab I ...
2
votes
0answers
78 views

About Convex Geometry

A consistency notion in constraint programming: Let $P = (X, D, C)$ be a CSP. Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is ...
5
votes
1answer
154 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 ...
0
votes
1answer
367 views

CPLEX claims to have solved QP minimisation but solution is not optimal

I am trying to solve a small QP problem in CPLEX. The problem has several linear constraints. The optimiser runs and finds a solution which satisfies these constraints and CPLEX returns a success ...