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
21 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
52 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
31 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
86 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 ...
0
votes
0answers
12 views

About Intersection of two convex polytope? [migrated]

the intersection of two convex hull of two polytope P and Q , is it the convex hull of the intersection of P&Q ? Conv(P) ∩ Conv(Q) = conv(P∩Q) ???.
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
76 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
53 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
87 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
89 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
136 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
66 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
149 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
176 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
53 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
102 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
91 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
141 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
147 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
411 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
79 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
163 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
94 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
970 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
88 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
49 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
68 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
213 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
365 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
57 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
308 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
198 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
119 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
139 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
235 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
417 views

Biconvex optimization problems

Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?
3
votes
3answers
242 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
83 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 - ...
3
votes
2answers
306 views

Finding A and X such that AX = 0, X is positive non-zero, and A is sparse

I apologize if this is a naive question. I'm trying to create some boostrap data for a system of linear, ordinary differential equations at steady state. Since the equations represent the ...
7
votes
2answers
114 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: ...
1
vote
1answer
94 views

Confusion related to convexity of 0-1 loss function

I am a bit confused why the 0-1 loss function is not convex. What's wrong with it?
4
votes
5answers
1k views

MATLAB's CVX Package to minimize $\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$

I would like to minimize in matlab the function $f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ where $S\in \mathcal{M}_{m,m}$ symmetric positive definite which is definitely convex function. So I ...
1
vote
1answer
54 views

Confusion related to interior point method for optimization

I have this little confusion related to interior point method. In this method we use the log barrier function to approximate the real barrier which is not differential Now when we find the optimal ...
2
votes
1answer
56 views

Confusion while proving logdet function to be concave

I was going through this lecture related to convex optimization. It was proved that logdet function is concave. However, I didn't get the derivation at a part I didn't get how the step marked in ...
6
votes
1answer
161 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 ...
1
vote
1answer
157 views

Robust Counterpart of an uncertain LP

Consider the following robust optimization problem: min c'x s.t.: $Ax\geq b \;\;\forall (A,b)\in \mathcal{U}$. Why can the robust counterpart of the problem be written in this form? $min_x{\{ ...