search

jump-dev / SCS.jl

A Julia interface for the SCS conic programming solver
https://github.com/cvxgrp/scs
Other
81 stars 27 forks source link

Test with new symmetric SDP format #14

Closed bodono closed 9 years ago

bodono commented 9 years ago

SCS branch symmetric_sdp accepts semidefinite variables of size n * (n+1)/2, instead of n^2 (see discussion here cvxgrp/scs#31). This is quite likely to merge into master eventually, dropping support entirely for SD variables of size n^2. I already made the change, in that branch, for the python and matlab interfaces (very little needed to change). Are any changes required here?

mlubin commented 9 years ago

Besides any changes to the SCS C wrapper, we also should revise the standard conic input format (JuliaOpt/MathProgBase.jl#51).

joehuchette commented 9 years ago

@bodono are these changes available on the latest release version of SCS (https://github.com/cvxgrp/scs/releases/tag/v1.1.0)? If so, we should probably go about making the changes to the lower-triangular interface in this repo.

bodono commented 9 years ago

Yes, v1.1.0 contains the change to the SDP input format.

madeleineudell commented 9 years ago

The current way to match the SCS MathProgBase wrapper to the standard form is extremely slow. See this issue on Convex.jl. It seems like most of the "model generation" time is spent adding the symmetry constraints.

bodono commented 9 years ago

It seems that both SCS and MOSEK now expect the lower triangular input format for SDPs, and making that transition should remove the requirement to make additional symmetry constraints (which was required for the old SCS SDP format). Once those constraints are eliminated it will likely speed up dramatically.

madeleineudell commented 9 years ago

There are still a couple of SDP tests failing with the new conic interface on SCS + Convex (on Julia v0.3.8). (They work on Mosek + Convex.) @bodono , would you be able to take a look? You can run them with julia test/test_sdp.jl in the Convex.jl repo.

Running tests with SCSSolver({(:verbose,false)}):
SCSSolver({(:verbose,false)})
SDP Atoms
     - sdp variables
     - sdp constraints
WARNING: Problem status UnknownError; solution may be inaccurate.
     - nuclear norm atom
  Failure   :: (line:366) :: nuclear norm atom :: got 1.7838063039116236
    p.optval => roughly(3,TOL)
     - operator norm atom
     - sigma max atom
     - lambda max atom
     - lambda min atom
     - matrix frac atom
     - matrix frac atom both arguments variable
  Failure   :: (line:366) :: matrix frac atom both arguments variable :: got 1.0000031305994155
    p.optval => roughly(0.5,TOL)
Out of 27 total facts:
  Verified: 25
  Failed:   2
bodono commented 9 years ago

It's looking like an issue in the conversion to conic form, at least that's my best guess. I wrote up the exact same examples in CVX, with the same settings, and it get's the right answer. Here is the code and output:

cvx_begin
cvx_solver 'scs'
cvx_solver_settings('eps',1e-4, 'scale', 5, 'alpha', 1.8)
variable y(3,3) symmetric
minimize(norm_nuc(y))
y(2,1)<=4
y(2,2)>=3
y(3,3)<=2
y == semidefinite(3)
cvx_end

%%
cvx_begin
cvx_solver 'scs'
cvx_solver_settings('eps',1e-4, 'scale', 5, 'alpha', 1.8)
variable x(2,2) symmetric
maximize(log_det(x))
x(1,1)==1
x(2,2)==1
x == semidefinite(2)
cvx_end

output

----------------------------------------------------------------------------
    SCS v1.1.4 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 24
eps = 1.00e-04, alpha = 1.80, max_iters = 2500, normalize = 1, scale = 5.00
Variables n = 12, constraints m = 30
Cones:  linear vars: 3
    sd vars: 27, sd blks: 2
Setup time: 8.17e-03s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf       nan      -inf       nan       inf  2.39e-02 
   100| 1.09e-05  5.65e-05  4.96e-05 -3.00e+00 -3.00e+00  0.00e+00  6.29e-02 
----------------------------------------------------------------------------
Status: Solved
Timing: Total solve time: 9.31e-02s
    Lin-sys: nnz in L factor: 66, avg solve time: 3.71e-07s
    Cones: avg projection time: 9.75e-06s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 2.2426e-09, dist(y, K*) = 1.6051e-09, s'y/m = -3.1704e-11
|Ax + s - b|_2 / (1 + |b|_2) = 1.0924e-05
|A'y + c|_2 / (1 + |c|_2) = 5.6501e-05
|c'x + b'y| / (1 + |c'x| + |b'y|) = 4.9636e-05
----------------------------------------------------------------------------
c'x = -3.0000, -b'y = -2.9997
============================================================================
------------------------------------------------------------
Status: Inaccurate/Solved
Optimal value (cvx_optval): +2.99966

Calling SCS 1.1.1: 21 variables, 8 equality constraints
   For improved efficiency, SCS is solving the dual problem.
------------------------------------------------------------
NOTE: custom settings have been set for this solver.
------------------------------------------------------------
----------------------------------------------------------------------------
    SCS v1.1.4 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 16
eps = 1.00e-04, alpha = 1.80, max_iters = 2500, normalize = 1, scale = 5.00
Variables n = 8, constraints m = 21
Cones:  linear vars: 2
    sd vars: 16, sd blks: 3
    exp vars: 0, dual exp vars: 3
Setup time: 1.89e-02s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf       nan      -inf       inf       inf  1.99e-02 
   100| 9.47e-06  4.43e-05  2.03e-04 -2.14e-05  1.81e-04  1.35e-16  3.92e-02 
   120| 1.34e-06  1.42e-06  1.18e-06  1.92e-06  3.10e-06  1.35e-16  1.47e-01 
----------------------------------------------------------------------------
Status: Solved
Timing: Total solve time: 1.75e-01s
    Lin-sys: nnz in L factor: 45, avg solve time: 2.86e-07s
    Cones: avg projection time: 2.39e-05s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 1.3878e-09, dist(y, K*) = 2.3195e-09, s'y/m = 5.0364e-11
|Ax + s - b|_2 / (1 + |b|_2) = 1.3373e-06
|A'y + c|_2 / (1 + |c|_2) = 1.4157e-06
|c'x + b'y| / (1 + |c'x| + |b'y|) = 1.1831e-06
----------------------------------------------------------------------------
c'x = 0.0000, -b'y = 0.0000
============================================================================
------------------------------------------------------------
Status: Inaccurate/Solved
Optimal value (cvx_optval): -1.91923e-06

but here is the output for Convex.jl

Running tests:
INFO:  Test: test_sdp.jl
SDP Atoms
     - nuclear norm atom
----------------------------------------------------------------------------
    SCS v1.1.4 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 55
eps = 1.00e-04, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
Variables n = 28, constraints m = 49
Cones:  primal zero / dual free vars: 19
    linear vars: 3
    sd vars: 27, sd blks: 2
Setup time: 1.57e-04s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf       nan      -inf       inf       inf  1.10e-04
    80| 5.62e-06  5.06e-05  3.17e-05  1.78e+00  1.78e+00  0.00e+00  1.94e-03
----------------------------------------------------------------------------
Status: Solved
Timing: Total solve time: 1.95e-03s
    Lin-sys: nnz in L factor: 132, avg solve time: 7.68e-07s
    Cones: avg projection time: 2.13e-05s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 2.0848e-09, dist(y, K*) = 1.9133e-09, s'y/m = 8.6413e-12
|Ax + s - b|_2 / (1 + |b|_2) = 5.6217e-06
|A'y + c|_2 / (1 + |c|_2) = 5.0629e-05
|c'x + b'y| / (1 + |c'x| + |b'y|) = 3.1720e-05
----------------------------------------------------------------------------
c'x = 1.7838, -b'y = 1.7840
============================================================================
  Failure   :: (line:366) :: nuclear norm atom :: got 1.7838063039116236
    p.optval => roughly(3,TOL)
Out of 3 total facts:
  Verified: 2
  Failed:   1
INFO:  Test: test_exp_and_sdp.jl
SDP and Exp Atoms
     - log det atom
----------------------------------------------------------------------------
    SCS v1.1.4 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 35
eps = 1.00e-04, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
Variables n = 15, constraints m = 34
Cones:  primal zero / dual free vars: 15
    sd vars: 13, sd blks: 2
    exp vars: 6, dual exp vars: 0
Setup time: 8.45e-05s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0|      inf       inf       nan      -inf       inf       inf  8.26e-05
   100| 5.11e-03  9.37e-03  2.07e-03 -1.03e+00 -1.04e+00  0.00e+00  2.86e-03
   200| 7.76e-04  6.48e-03  2.56e-05 -1.04e+00 -1.04e+00  3.16e-16  5.65e-03
   300| 1.08e-04  1.82e-03  2.45e-05 -1.04e+00 -1.04e+00  0.00e+00  8.51e-03
   340| 8.82e-05  3.84e-05  9.18e-06 -1.04e+00 -1.04e+00  1.58e-16  9.76e-03
----------------------------------------------------------------------------
Status: Solved
Timing: Total solve time: 9.77e-03s
    Lin-sys: nnz in L factor: 85, avg solve time: 4.82e-07s
    Cones: avg projection time: 2.68e-05s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 3.4397e-17, dist(y, K*) = 2.6157e-09, s'y/m = 1.0074e-10
|Ax + s - b|_2 / (1 + |b|_2) = 8.8216e-05
|A'y + c|_2 / (1 + |c|_2) = 3.8405e-05
|c'x + b'y| / (1 + |c'x| + |b'y|) = 9.1750e-06
----------------------------------------------------------------------------
c'x = -1.0396, -b'y = -1.0396
============================================================================
  Failure   :: (line:366) :: log det atom :: got 1.0395875608531742
    p.optval => roughly(0,TOL)
Out of 3 total facts:
  Verified: 2
  Failed:   1

The problem could be in SCS.jl, but that's less likely since it's quite a thin wrapper. You can compile SCS with EXTRAVERBOSE=1 to see if the data that SCS is getting is what you expect, given the conic form transformations.