Examples in CVX MATLAB

Table of Contents

• LASSO problem
• Semidefinite Programming
• Logistic Regression
• Minimization of p-norm
• Norm-constrained minimum-norm problem
• Regularized matrix completion problem
• Portfolio selection
• Principal component analysis
• Easy configuration

In what follows we give a few code snippets in MATLAB and compare SuperSCS with SCS.

This is a preliminary study to show that SuperSCS outperforms SCS, but a more thorough analysis is necessary.

In what follows we compare the two algorithms using five different types of problems: (i) a LASSO problem ( \(\ell_1\)-regularized least squares), (ii) a semidefinite program (SDP) and, in particular, a minimum-norm problem and an LMI-constrained problem, (iii) a logistic regression problem, (iv) a minimum \(p\)-norm problem, (v) a 2-norm-constrained minimum-norm problem and, last , (vi) a matrix completion problem involving the nuclear norm.

Note

The following benchmarks are available in /tests/matlab/.

Reported runtimes were recorded on an Intel® Core™ i5-6200U CPU @ 2.30GHz × 4 machine with 11.6 GiB RAM running 64-bit Ubuntu 14.04.

Both SuperSCS and SCS were compiled using gcc v4.8.5 and accessed via MATLAB® using a MEX interface.

Remarks

For the sake of reproducibility, we use

rng('default');
rng(1);

LASSO problem

We solve a simple LASSO problem of the form

\[ \mathrm{Minimize}_x\ \textstyle\frac{1}{2} \|Ax-b\|^2 + \mu \|x\|_1, \]

with \(x\in\mathbb{R}^n\), \(A\in\mathbb{R}^{m\times n}\).

Here \(n=10000\), \(m=2000\).

We define the problem data as follows:

s = ceil(n/10);
x_true=[randn(s,1);zeros(n-s,1)];
x_true = x_true(randperm(n));

density = 0.1;
rcA = .1;
A=sprandn(m,n,density,rcA);

b = A*x_true + 0.1*randn(m,1);
mu = 1;

Note that \(A\) is a sparse matrix with density \(10\%\) and reciprocal condition number \(0.1\).

We then formulate the problem in CVX with accuracy \(\epsilon=10^{-4}\).

We solve it using SuperSCS with restarted Broyden directions with memory \(100\) and using \(k_0=0\):

do_super_scs = 0;

tic;
cvx_begin
    cvx_solver scs
    cvx_solver_settings('eps', 1e-4,...
        'do_super_scs',do_super_scs,...
        'direction', 100,...
        'memory', 100)
    variable x_c(n)
    minimize(0.5*sum_square(A*x_c - b) + mu*norm(x_c,1))
cvx_end
toc

Notice that we may pass any parameters to SCS using CVX's cvx_solver_settings.

SuperSCS with the above options terminates after \(169\) iterations and \(85.1\) s.

Instead, SCS requires \(3243\) iterations which corresponds to \(802\) s.

SuperSCS exhibits a speed-up of \(\times 9.4\).

Note

Any values that are not overridden using cvx_solver_settings are set to their default values.

Semidefinite Programming

Here we solve the problem

\begin{eqnarray*} &&\mathrm{Minimize}_{Z}\ \|Z-P\|_{\mathrm{fro}}\\ &&Z\geq 0\\ &&Z: \mathrm{Hermitian},\ \mathrm{Toeplitz} \end{eqnarray*}

n=800;
P = randn(n,n);
cvx_begin sdp
cvx_solver scs
cvx_solver_settings('eps', 1e-4,...
        'do_super_scs',1,...
        'memory', 50)
    variable Z(n,n) hermitian toeplitz
    dual variable Q
    minimize( norm( Z - P, 'fro' ) )
    Z >= 0 : Q;
cvx_end

SuperSCS solves this problem in \(218\)s ( \(103\) iterations), whereas SCS requires \(500\)s to terminate ( \(392\) iterations).

Another interesting SDP problem is that of determining a symmetric positive definite matrix \(P\) which solves

\begin{eqnarray*} &&\mathrm{Minimize}_{P}\ \mathrm{trace}(P)\\ &&P=P'\\ &&P \geq I\\ &&A'P + PA \leq -I \end{eqnarray*}

For this example we chose a (stable) matrix \(A\) with its eigenvalues uniformly logarithmically spaced between \(-10^{-1}\) and \(-10^{1}\).

n=100;
A = diag(-logspace(-0.5, 1, n));
U = orth(randn(n,n));
A = U'*A*U;

tic
cvx_begin sdp
    cvx_solver scs
    cvx_solver_settings('eps', 1e-3,...
        'do_super_scs', 1, ...
        'memory', 100);
    variable P(n,n) symmetric
    minimize(trace(P))
    A'*P + P*A <= -eye(n)
    P >= eye(n)
cvx_end    
toc    

SuperSCS converges after \(40.7\)s ( \(314\) iterations), whereas SCS converges after \(415\)s ( \(4748\) iterations)

Logistic Regression

Here we solve the following \(\ell_1\)-regularized logistic regression problem:

\[ \mathrm{Minimize}_w\ \lambda \|w\|_1 - \sum_{i}\log(1+\exp(a' w_i + b)) \]

density = 0.1;
p = 1000;   % features
q = 10*p;   % total samples
w_true = sprandn(p,1,0.2);
X_tmp = 3*sprandn(p, q, density);
ips = -w_true'*X_tmp;
ps = (exp(ips)./(1 + exp(ips)))';
labels = 2*(rand(q,1) < ps) - 1;
X_pos = X_tmp(:,labels==1);
X_neg = X_tmp(:,labels==-1);
X = [X_pos -X_neg]; % include labels with data
lam = 2; 

We formulate the problem as follows:

tolerance = 1e-3;
cvx_begin
   cvx_solver scs
   cvx_solver_settings('eps', tolerance,...
     'do_super_scs', 1,...
     'ls', 5,...
     'memory', 50)
   variable w(p)
   minimize(sum(log_sum_exp([sparse(1,q);w'*X])) + lam * norm(w,1))       
cvx_end

For \(\epsilon=10^{-3}\), SuperSCS terminates after \(131\)s ( \(134\) iterations), while SCS requires \(329\)s ( \(675\) iterations).

For \(\epsilon=10^{-4}\), SuperSCS requires \(179\)s ( \(183\) iterations), whereas SCS still requires as much as \(497\)s ( \(983\) iterations).

In both cases, SuperSCS is about \(2.5\) times faster.

Minimization of p-norm

Consider the problem

\begin{eqnarray*} &&\mathrm{Minimize}_x\ \|x\|_p\\ &&Gx = f \end{eqnarray*}

This is the problem formulation in CVX

n = 2000;
m = ceil(n/4);

density = 0.1;
G = sprandn(m,n,density);
f = randn(m,1) * n * density;
pow = 1.5;

tic
cvx_begin
    cvx_solver scs
    cvx_solver_settings('eps', 1e-4,...
        'do_super_scs', 0, ...
        'memory', 50,...
        'use_indirect', 0);
    variable x(n)
    minimize(norm(x, pow))
    subject to
      G*x == f
    cvx_end
toc

For \(\epsilon=10^{-3}\), SuperSCS converged after \(11.3\)s ( \(1355\) iterations) , while SCS required \(39\)s ( \(4911\) iters).

For \(\epsilon=10^{-4}\), SuperSCS terminated after 17s ( \(4909\) iterations), while SCS failed to terminate within \(10^4\) iterations.

Norm-constrained minimum-norm problem

Here we solve a constrained problem of the form

\begin{eqnarray*} &&\mathrm{Minimize}_x\ \|Ax-b\|\\ &&\|Gx\| \leq 1 \end{eqnarray*}

with \(x\in\mathbb{R}^m\), \(A\in\mathbb{R}^{m\times n}\) and \(G\in\mathbb{R}^{2n\times n}\).

The problem data are:

m = 3000; 
n = ceil(m/2);
A = sprandn(m,n,0.5,0.01);
b = 10*randn(m,1);
G = 2*sprandn(2*n, n, 0.1);

And we need to solve it up to an accuracy of \(\epsilon=10^{-3}\).

The problem is formulated in CVX as follows:

tic;
cvx_begin
    cvx_solver scs
    cvx_solver_settings('eps', 1e-3,...
        'do_super_scs', 1, ...
        'memory', 20);
    variable x(n)
    minimize( norm(A*x-b) )
    subject to
        norm(G*x) <= 1
cvx_end
toc

SuperSCS converges after \(37.1\)s ( \(116\) iterations).

On the other hand, SCS did not converge after \(242s\) ( \(5000\) iterations).

Note that SuperSCS can attain much higher precision; for instance, it converges with \(\epsilon=10^{-4}\) in \(41.2\)s ( \(131\) iterations) and with \(\epsilon=10^{-6}\) it converges after \(58\)s ( \(194\) iterations).

Regularized matrix completion problem

Let \(M\) be a given matrix whose elements \(\{(i,j)\}_{i\in I, j\in J}\) are missing.

Here, we formulate the matrix completion problem as a nuclear norm minimization problem.

\begin{eqnarray*} &&\mathrm{Minimize}_{X}\ \|X-M\|_{\mathrm{fro}}^2 + \lambda \|X\|_{*}\\ &&X_{i',j'} = M_{i',j'},\ \forall i'\notin I,\ j'\notin J \end{eqnarray*}

Problem formulation:

rng('default');
rng(1);
m = 500;
n = 200;
percentage_missing = 0.9;
n_nan = ceil(percentage_missing*m*n);
M = randn(m, n);
idx = randperm(m*n);
idx_nan = idx(1:n_nan);
idx_not_nan = idx(n_nan+1:end);
M(idx_nan) = nan;
lam = 1e-3;

Problem solution:

scs_options = SuperSCSConfig.andersonConfig('tolerance', 1e-4,...
    'do_record_progress',1,'verbose',1,'memory',5);

cvx_begin sdp
    cvx_solver scs
    scs_set_options(scs_options)
    variable X(m,n)
    minimize (lam * norm_nuc(X) + sum_square(X(idx_not_nan)-M(idx_not_nan)))
    subject to
        X(idx_not_nan)==M(idx_not_nan)
cvx_end

See Also

easy configuration

SuperSCS (with Broyden directions and memory 50) converges in \(22s\) ( \(128\) iterations), whereas SCS takes \(43s\) ( \(677\) iterations).

Portfolio selection

Here we solve the following portfolio selection problem:

\begin{eqnarray*} &&\mathrm{Maximize}_z\ \mu'z - \gamma z'\Sigma z\\ &&1'z = 1\\ &&z \geq 0, \end{eqnarray*}

where \(z\) is the portfolio of assets, \(\mu\) is the vector of expected returns, \(\gamma\) is a risk-aversion parameter and \(\Sigma=F'F+D\) is the asset return covariance matrix with \(F\) being the factor loading matrix and \(D\) is a diagonal matrix called the asset-specific risk.

The problem is generated as follows:

density = 0.1;
rc = 0.5; % estimated reciprocal condition number

n = 100000;
m = 100;

mu = exp(0.01 * randn(n, 1)) - 1; % returns
D = rand(n,1) / 10; % idiosyncratic risk
F = sprandn(n, m, density, rc) / 10; % factor model
gamma = 1;
B = 1;

The problem is solved using CVX as follows:

cvx_begin
    cvx_solver scs
    cvx_solver_settings('eps', 1e-4,...
        'do_super_scs', 1,...
        'direction', 100,...
        'memory', 100)
    variable x(n)
    maximize(mu'*x - gamma*(sum_square(F'*x) + sum_square(D.*x)))r
    sum(x) == B
    x >= 0
cvx_end

The above problem is solved in \(46.7\)s and at \(292\) iterations with SuperSCS running with restarted Broyden directions with memory equal to \(100\).

The respective results for SCS are \(157\)s and \(3050\) iterations (approximately \(3.3\) times slower).

For a lower tolerance of \(\epsilon=10^{-3}\) , SuperSCS with memory equal to \(100\) terminates at \(162\) iterations after \(23.5\)s while SCS converges after \(43.9\)s at \(787\) iterations.

Principal component analysis

Here we solve the following sparse PCA problem (using an \(\ell_1\)-regularization).

The problem has the form

\begin{eqnarray*} &&\mathrm{Maximize}_X\ \mathrm{trace}(SX) - \lambda \|X\|_1\\ && \mathrm{trace}(X) = 1\\ && X = X' \succeq 0 \end{eqnarray*}

d = 200;
p = 10;
A = sprandn(p,d,0.3,0.0001);
S = full(A'*A);
lam = 2;

cvx_begin sdp
    cvx_solver scs
    cvx_solver_settings('eps', 1e-3,...
       'verbose', 1,...
       'do_super_scs', 0, ...
       'direction', 100, ...
       'memory', 100);
    variable X(d,d) symmetric
    minimize(-trace(S*X) + lam*norm(X,1))
    trace(X)==1
    X>=0
cvx_end  

SuperSCS: \(7.6\)s, \(95\) iterations

SCS: \(65\)s, \(2291\) iterations

Speed-up: \(\times 8.6\)

Easy configuration

Instead of using cvx_solver_settings to provide the SuperSCS configuration options, you may use scs_set_options to which you may pass a SuperSCSConfig object which can be constructed from the namesake factory class.

Here is an example:

solver_options = SuperSCSConfig.andersonConfig();
cvx_begin 
cvx_solver scs
scs_set_options(solver_options)
   % describe your problem here
cvx_end

Ready-to-use sets of configuration options are the following

• SuperSCSConfig.andersonConfig() Anderson's acceleration with memory equal to 10
• SuperSCSConfig.broydenConfig() Restarted Broyden method with memory equal to 50
• SuperSCSConfig.fprDirectionConfig()
• SuperSCSConfig.douglasRachfordConfig() simple Douglas-Rachford algorithm
• SuperSCSConfig.scsConfig() original SCS implementation

You may use SuperSCSConfig and override some of the default parameters as follows

solver_options = SuperSCSConfig.andersonConfig('memory', 12, 'tolerance', 1e-4);

See Also

SuperSCS: first steps

SuperSCS in C: examples