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

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
84 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
26 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
70 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
97 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
53 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
19 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
31 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
48 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
47 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. ...
1
vote
1answer
57 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
36 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
91 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 ...
0
votes
1answer
42 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
79 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
55 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
88 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
92 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
178 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
74 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
150 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
207 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 ...
0
votes
1answer
54 views

Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
4
votes
3answers
103 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
110 views

Custom CVX Functions - Overriding Errors [closed]

I have constructed a function in Matlab that is convex and increasing (qualitatively similar to an exponential function but I am hoping to avoid the successive approximation requirement of exp). In my ...
6
votes
1answer
150 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 ...
5
votes
2answers
157 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 ...
8
votes
4answers
433 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 ...
1
vote
1answer
82 views

Convex objective function of matrix with prescribed determinant and trace

I have real symmetric positive definite matrix $M = \left(\begin{matrix} a & b \\ b & c \end{matrix}\right)$ where $a,b,c \in R,\ a,c>0,\ \left|b\right|<2\sqrt{a c}$. I want to define ...
2
votes
1answer
176 views

Solve Regularized Least Squares problems using Matlab optimization toolbox

I am trying to solve a least squares problem where the objective function has a least squares term along with L1 and L2 norm regularization. I am unable to find which matlab function provides the ...
0
votes
1answer
97 views

Checking the convexity or the concavity of a function

I have an optimization problem with the following objective function. $\max_{a^{l}_{n,k} b^l_{n,k}} \sum_{n=1}^{\overline{N_l}} b_{k,n} \frac{C_1}{C_2} \log_2 \bigg(1 +\frac{a_{k,n} h_{k,n}} ...
2
votes
2answers
1k 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, ...
0
votes
0answers
49 views

Minimizing a quadratic form

I would like to minimize the following quadratic form: $$ f(\mathbf{\theta}) = (\mathbf{y} - \mathbf{\mu}(\mathbf{\theta}))^T \mathbf{\Sigma}({\mathbf{\theta}})^{-1} (\mathbf{y} - ...
0
votes
2answers
89 views

Nonconvex Optimization

Consider the following optimization problem: $\text{max}_{p} \quad ||p||^2 \\ s.t: x\geq 0\\ p\in D$ where $D$ is a convex set. Is this problem $\mathcal{NP}$-hard?
1
vote
1answer
51 views

Optimal linear transform in a simplex

I'm looking for a simple method to find a linear transform that minimizes $$ \text{argmin}_T F(T): T \in \mathbb{R}^{m \times n} ,\ T \ge 0 ,\ T \mathbb{1} = c \mathbb{1} ,\ \mathbb{1}^T T = ...
2
votes
2answers
70 views

minimize function with convex constraints

I need to solve the following problem: For a given p=(x0,y0,z0,w0) and arbitrary T. For example , let p=(0.8,0.1,0.06,0.04) and T=-1.2. I need to find a vector q=(x,y,z,w) with the minimum ...
9
votes
2answers
221 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 ...
0
votes
1answer
411 views

minimization of a convex piecewise linear function [closed]

Let $$f(x) = \left\{ \begin{array}{l} {a_1}x + {b_1} & if\,0 \le {x_1} \le x \le {x_2}\\ {a_2}x + {b_2} & if\,{x_2} < x \le {x_3}\\ \vdots \\ {a_n}x + {b_n} & if\,{x_{n - 1}} < x ...
0
votes
0answers
58 views

Issues with CVX package for optimization

I am trying to use the cvx package for optimization. However, I am having some issues with it. I have a variable X which is a matrix but I cannot add $X^{-1}$ in the objective function. What should I ...
7
votes
2answers
327 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 ...
1
vote
0answers
17 views

Reduction for NP-hardness [duplicate]

Consider the following optimization problem: \begin{align} \text{Min}_{i\neq j\neq s\neq t} |x_i x_j-x_sx_t|\\ s.t: Ax=b\\ x\geq 0; \end{align} This problem can be seen as an instance of non convex ...
2
votes
2answers
202 views

NP-Completeness

Consider an instance of non-convexoptimization problem: It seems that this problem is NP-complete. How can I find a suitable reduction for this?
0
votes
0answers
53 views

Proper Algorithm for Image Recovery from Compressed Measurements in Office Spaces

Can anyone please suggest a proper algorithm for image reconstruction from undersampled data for office spaces ? Basis Pursuit (BP) works for sparse images which would not be a correct assumption for ...
5
votes
1answer
124 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 & ...
4
votes
2answers
141 views

Optimization algorithm selection for 3 variable integer

I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$ it is very expensive to evaluate $x,y,z \in \mathbb{Z}$ 0 < x < 10 0 < y < 30 0 < z < 100 I thought it was convex, not ...
3
votes
2answers
241 views

Quadratic Programming: Quadprog

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = ||S w||^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
3
votes
1answer
436 views

Biconvex optimization problems

Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?
3
votes
3answers
250 views

How to prove that a function is convex?

I'm calculating the gradient of a function with a symbolic math library called theano. Then I'm using gradient descent to find the minimum of the function. I'd like to prove that the minimum is a ...
0
votes
2answers
86 views

Analytical form of the minimum of a function with absolute values

I would like to find the analytical form of the point which minimizes the following function: $$ f(x_T) = \frac{1}{T} a_1 (x_T-x_0)^2 + a_2 |x_T-x_0| + T a_3 + \sum_{i=1}^M p_i \left[b_{1i} (x_T - ...