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
11 views

What is a composition of two binary relations geometrically? [migrated]

the composition was defined as follow: (a,b) \in (R;S) <=> there is c | (a,c) \in R and (c,b) \in S . If our two relations R and S are two convex polygon ...
0
votes
1answer
94 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
111 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
35 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
70 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
65 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
111 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
42 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
85 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
102 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
68 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
21 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
36 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
49 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
63 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
38 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
96 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
85 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
91 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
95 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
212 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
76 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
151 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
240 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
118 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
158 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
165 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
446 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
89 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
207 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
51 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
71 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
226 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
449 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
60 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
343 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 ...