Usage from MATLAB

How to call ECOS from MATLAB

To solve the convex second-order cone problem

$\begin{matrix} {\text{minimize}\ \ } & {c^{T}x} \\ {\text{subject\ to}\ \ } & {Ax = b} \\ & {Gx \preceq_{K}h} \\ \end{matrix}$

You can directly call ECOS from MATLAB® using its native interface:

[x,y,info,s,z] = ecos(c,G,h,dims,A,b,opts)

It takes the problem data c,G,h,A,b and the necessary information on the dimension of the cones that is given in the struct dims. Note that A and G have to be given in sparse format. The equality constraints defined by A and b are optional and can be omitted. The dims structure has the following fields:

dims.l - scalar, dimension of positive orthant (LP-cone) $R_{+}$
dims.q - vector with dimensions of second order cones $Q^{n} = \{(t,x) \in R_{+} \times R^{n - 1}\ |\ t \geq \| x\|_{2}\}$
dims.e - scalar, number of exponential cones $K_{e} = closure\{(x,y,z) \in R^{3}\ |\ exp(x/z) \leq y/z,z > 0\}$

The length of dims.q determines the number of second order cones. Use the empty matrix [] to indicate that a cone is not present, for example dims.q = [] if there are no second-order cones in your problem instance. Auxiliary settings can be passed to the solver by means of the struct opts, which is explained in detail here.

Return values

After a solve, ECOS returns the following variables:

ID	Description
`x`	Primal variables
`y`	Dual variables for equality constraints
`s`	Slack variables for inequality $Gx \preceq_{K}h\Leftrightarrow s = h - Gx$
`z`	Dual variables associated to $s \in K$
`info`	Struct with detailed information on solve status

Information on Solve Status - the "info" Struct

The struct info contains the following fields:

Field	Description
`exitflag`	Numerical value for status of the solve (details see below)
`infostring`	Information for humans on what the exitflag means
`pcost`	Primal objective value $c^{T}x$
`dcost`	Dual objective value $- b^{T}y - h^{T}z$
`pres`	Normalized primal residual $\text{max}\left( {\| Ax - b\|_{2}/\text{max}(1,\| b\|_{2}),\| Gx + s - h\|_{2}/\text{max}(1,\| h\|_{2})} \right)$
`dres`	Normalized dual residual $\| A^{T}y + G^{T}z + c\|_{2}/\text{max}(1,\| c\|_{2})$
`pinfres`	Primal infeasibility measure $\| A^{T}y + G^{T}z\|_{2}/\text{max}(1,\| c\|_{2})$
`dinfres`	Dual infeasibility measure $\text{max}\left( {\| Ax\|_{2}/\text{max}(1,\| b\|_{2}),\| Gz + s\|_{2}/\text{max}(1,\| h\|_{2})} \right)$
`pinf`	Indicates primal infeasibility if $h^{T}z + b^{T}y < 0$
`dinf`	Indicates dual infeasibility if $c^{T}x < 0$
`gap`	Complementarity gap $s^{T}z$
`relgap`	Normalized complementarity gap $s^{T}z/( - pcost)$
`iter`	Number of iterations performed
`timing`	Struct with timing information

Note these values refer to the last iterate before ECOS exited because of an exit criterion. See the exitcodes below for more details.

Example: L1 minimization (Linear Programming)

In the following, we show how to solve a L1 minimization problem, which arises for example in sparse signal reconstruction problems (compressed sensing):

$\begin{matrix} {\text{minimize}\ \ } & {\| x\|_{1}} \\ {\text{subject\ to}\ \ } & {Ax = b} \\ \end{matrix}$

where $x \in R^{n}$ , $A \in R^{mxn}$ with $m \ll n$ . We use the epigraph reformulation to express the L1-norm of ,

$\begin{matrix} x & {\leq u} \\ {- x} & {\leq u} \\ \end{matrix}$

where $u \in R_{+}^{n}$ and we minimize $\sum\limits_{i = 1}^{n}u_{i}$ . Hence the optimization variables are stacked as follows:

z = [x; u]

With this reformulation, the sparse reconstruction problem can be written as the linear program (LP)

$\begin{matrix} {\text{minimize}\ \ } & {c^{T}z} \\ {\text{subject\ to}\ \ } & {\overset{\sim}{A}z = b} \\ & {Gx \leq h} \\ \end{matrix}$

where the inequality is w.r.t. the positive orthant. The following MATLAB® code generates a random instance of this problem, and calls ECOS to compute a solution:

% set dimensions and sparsity of
A
n = 1000; m = 10; density = 0.01;  
  
% linear term
c = [zeros(n,1); ones(n,1)];  
  
% equality constraints
A = sprandn(m,n,density);  
Atilde = [A, zeros(m,n)];  
b = randn(m,1);  
  
% linear inequality constraints
I = speye(n);  
G = [  I -I;  
      -I -I];  
h = zeros(2*n,1);  
  
% cone dimensions (LP cone only)
dims.l = 2*n; dims.q = [];  
  
% call solver
z = ecos(c,G,h,dims,Atilde,b);  
x = z(1:n);  
nnzx = sum(abs(x) > 1e-8);  
  
% print sparsity info
fprintf('Optimal x has %d/%d (%4.2f%%) non-zero entries.\n', nnzx , n,  nnzx/n*100);

Quadratic Programming with ECOS

The MATLAB® package of ECOS comes with a quadratic programming interface that mimics the standard MATLAB® QP solver interface by quadprog. It supports QPs of the form

$\begin{matrix} {\text{minimize}\ \ } & {\frac{1}{2}x^{T}Hx + f^{T}x} \\ {\text{subject\ to}\ \ } & {Gx \leq h} \\ & {Ax = b} \\ & {lb \leq x \leq ub} \\ \end{matrix}$

where we assume that is positive definite. This is the standard formulation that also MATLAB®'s built-in solver quadprog uses. To deal with the quadratic objective, we have to reformulate it into a second-order cone constraint to directly call ECOS. This conversion is done within a MATLAB® interface called ecosqp. Hence you can simply use

[x,fval,exitflag,output,lambda,t] = ecosqp(H,f,G,h,A,b,lb,ub,opts)

to solve the quadratic program. See help ecosqp for more details. The last output argument indicates the solution time required by the ECOS solver (without the conversion into an SOCP).

Provide feedback

Saved searches