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

2
votes
0answers
4 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
80 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
83 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
73 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
60 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
145 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
100 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
48 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
96 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
65 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 ...
5
votes
0answers
82 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
120 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
362 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
66 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
136 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
88 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}} ...
1
vote
2answers
591 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
46 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
84 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
48 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
65 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
205 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
244 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
35 views

How to choose the subgradient?

I have a threshold linear function as a part of my convex objective function I want to optimize. $f(x) = 0$ for $x < 0$, and $f(x) = x$ for $x \geq 0$. It's not differentiable at 0, but ...
0
votes
0answers
56 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
253 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
179 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
51 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
106 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
135 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
209 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
362 views

Biconvex optimization problems

Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?
3
votes
3answers
211 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
77 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
255 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
112 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
84 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
896 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
54 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
159 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 ...
0
votes
1answer
140 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{\{ ...
0
votes
1answer
30 views

Polynomial solvability [duplicate]

Consider the following optimization problem: Min$_{x}$ $\qquad \sum_{(i,j,t,s)\in I_r}||x_ix_j-x_tx_s||^2$ S.t.: $\qquad x\in \mathcal{C} ;$ where $x=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; ...
1
vote
1answer
93 views

Feasibility checking

Consider the following optimization problem: $Min\;\;\; CX$ $AX\geq b$ $x_ix_j= x_s x_t\;\;\; i\neq j \neq s\neq t$ $x_j\geq 0;$ Where $A$ is the adjacency matrix and $C$ is a constant vector. ...
2
votes
2answers
112 views

polynomial time solvability

Consider the following optimization problem: $Min \qquad C^TX$ S.t.: $\qquad AX=0;$ $x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$ $X=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; ...
2
votes
1answer
71 views

Nonlinear bad constraints

I have an optimization problem with linear objective function. The constraints are in two different groups. The first set of constraints are linear while the second set is nonlinear. The nonlinear ...
4
votes
1answer
151 views

Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables

I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this. Read ...
2
votes
1answer
110 views

Extreme points from constraint expression of convex space

I'm looking for the extreme points of the convex set $S\subset [-1,1]^{n\times 3}$ with $r\in S$ such that \begin{equation} r_{i} \ge r_{k} \iff i\ge k, \end{equation} where the first inequality ...
7
votes
2answers
230 views

Max of a convex combination over a convex hull of real variables

I have the following linear program: $$ \begin{array}{cc} \text{Maximize} & a^T x \\ \text{Subject to} & x_{\min} \leq x \leq x_{\max} \\ & \mathbf{1}^T x = 1 ...