Solving large(?) problem with Convex.jl and SCS

Specific Domains Optimization (Mathematical)
,
1

Hello!

I am trying to port some MATLAB code (which uses YALMIP to call into
SCS) over to Julia (using Convex.jl and SCS.jl for the purpose).

The code builds sparse matrices A, C, D, sparse vector b and
tries to solve for vector variable x:

using Convex: Variable, minimize, solve!, norm;
using SCS: SCSSolver;

# ... build A, b, C, D, then:

@info "Creating convex optimization problem ..." size(A) size(x) size(b) size(C) size(D)
problem = minimize(
    # objective function: min L1-norm(x)
    norm(x, 1),
    # constraint (A): be eps-close to low res data
    norm(A*x-b, 2) <= ϵ,
    # constraint (B): pixel intensities are non-negative
    x >= 0,
    # constraint (C):
    C*x <= 0,
    # constraint (D):
    D*x >= 0,
);
@debug "Done at $(now()) ..."

@info "Solving optimization problem ..."
solver = SCSSolver(
    # see: https://github.com/cvxgrp/scs/blob/58e9af926fabc6674a9f488d4e9761a4f0fc451c/include/scs.h#L43
    verbose=1,
    normalize=0,        # boolean, heuristic data rescaling: 1
    scale=1.0,          # if normalized, rescales by this factor: 5
    #rho_x=1e-3,        # x equality constraint scaling: 1e-3
    max_iters=600,      # maximum iterations to take: 2500
    eps=1e-4,           # convergence tolerance: 1e-3
    #alpha=1.8,         # relaxation parameter: 1.8
    cg_rate=1,          # for indirect, tolerance goes down like (1/iter)^cg_rate: 2
);
solve!(problem, solver);

When I try to run this code, it runs for several hours (well over one full day) and then it crashes:

 Info: Creating convex optimization problem ...
│   size(A) = (130050, 520200)
│   size(x) = (520200, 1)
│   size(b) = (130050,)
│   size(C) = (520200, 520200)
â””   size(D) = (520200, 520200)
┌ Debug: Done at 2019-10-19T16:08:38.268 ...
â”” @ BEAM .../src/BEAM.jl:594
[ Info: Solving optimization problem ...
alpha must be in (0,2)
ERROR: Validation returned failure

signal (11): Segmentation fault
in expression starting at REPL[17]:1
scs_solve at /.../BEAM.jl/deps/scs/src/scs.c:838
SCS_solve at /.../.julia/packages/SCS/Y9wx3/src/c_wrapper.jl:95
macro expansion at /.../.julia/packages/SCS/Y9wx3/src/c_wrapper.jl:63 [inlined]
macro expansion at ./gcutils.jl:87 [inlined]
#SCS_solve#5 at /.../.julia/packages/SCS/Y9wx3/src/c_wrapper.jl:61
#SCS_solve at ./none:0
unknown function (ip: 0x7f8c11befecc)
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2197
optimize! at /.../.julia/packages/SCS/Y9wx3/src/MPB_wrapper.jl:107
#solve!#4 at /.../.julia/packages/Convex/6NNC8/src/solution.jl:45
solve! at /.../.julia/packages/Convex/6NNC8/src/solution.jl:21 [inlined]
#solve!#3 at /.../.julia/packages/Convex/6NNC8/src/solution.jl:13 [inlined]
solve! at /.../.julia/packages/Convex/6NNC8/src/solution.jl:12 [inlined]
beam at /net/nfs4/pelkmanslab-fileserver-common/.../BEAM.jl/src/BEAM.jl:608
beam at /net/nfs4/pelkmanslab-fileserver-common/.../BEAM.jl/src/BEAM.jl:238
unknown function (ip: 0x7f8c53fe2ed7)
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2197
do_call at /buildworker/worker/package_linux64/build/src/interpreter.c:323
eval_value at /buildworker/worker/package_linux64/build/src/interpreter.c:411
eval_stmt_value at /buildworker/worker/package_linux64/build/src/interpreter.c:362 [inlined]
eval_body at /buildworker/worker/package_linux64/build/src/interpreter.c:772
jl_interpret_toplevel_thunk_callback at /buildworker/worker/package_linux64/build/src/interpreter.c:884
unknown function (ip: 0xfffffffffffffffe)
unknown function (ip: 0x7f8c7adefa0f)
unknown function (ip: 0x1)
jl_interpret_toplevel_thunk at /buildworker/worker/package_linux64/build/src/interpreter.c:893
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:815
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:764
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:764
jl_toplevel_eval_in at /buildworker/worker/package_linux64/build/src/toplevel.c:844
eval at ./boot.jl:330
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2191
eval_user_input at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.2/REPL/src/REPL.jl:86
macro expansion at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.2/REPL/src/REPL.jl:118 [inlined]
#26 at ./task.jl:268
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2191
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1614 [inlined]
start_task at /buildworker/worker/package_linux64/build/src/task.c:596
unknown function (ip: 0xffffffffffffffff)
Allocations: 219070439 (Pool: 219026780; Big: 43659); GC: 621
Segmentation fault (core dumped)

However:

  1. The error message complains that alpha must be in (0,2) but I did not change its default value which seems to be 1.8 according to the SCS header files…

  2. I guess the “Segmentation fault” is due to some failing memory allocation – how could I check that?

In addition:

  1. Despite having compiled SCS with OpenMP and BLAS/LAPACK support, I only see 1 CPU being used - no parallel computing seems to happen. (OMP_NUM_THREADS and JULIA_NUM_THREADS are both set to 8.)

  2. No output from SCS is printed to the console – so perhaps the Julia code is running some sort of preparation before entering SCS and the crash already happens at this stage?

  3. The problem is too large to be solved with dense matrices so if Convex.jl is converting the constraints to dense form it will always fail. Could this be the case?

I am rather new to Julia and convex optimization in general, so I hope what I’ve just written makes sense…

Thanks for any suggestion or explanation!

Riccardo

2

That looks like a bug in SCS.jl to me. One way to check if it’s during Convex’s model formulation or at a later step is to write

c, A, b, cones, var_to_ranges, vartypes, conic_constraints = Convex.conic_problem(problem)

This is the command that is called before Convex.jl uses MathProgBase (MPB) to pass the problem to the solver, and Convex.jl’s model formulation occurs during this step. A, b, and c, correspond to the elements of the MPB standard conic form (Conic models — MathProgBase.jl 0.0 documentation). These should be sparse, and in general I think Convex does try to keep everything sparse. However, I think Convex definitely has areas to improve in terms of memory use, and there’s already one issue on the tracker about it: https://github.com/JuliaOpt/Convex.jl/issues/254.

Note that this command (Convex.conic_problem) will be removed in a future release when we transition to MathOptInterface (MOI); with that, there isn’t a separate formulation step really, which may end up being more performant. You can try the MOI version of Convex here: https://github.com/JuliaOpt/Convex.jl/pull/330. Also, SCS.jl has both a MPB wrapper and a MOI wrapper, so if there is a bug in the MPB wrapper, going through MOI could avoid it.

I ran your code successfully with random sparse matrices whose size is scaled down by a factor of 100 in each dimension, for whatever that’s worth:

scale = 100
sz1 = 130050 Ă· scale
sz2 = 520200 Ă· scale
A = sprandn(sz1, sz2, 1/(sz1*sz2)^2)
x = Variable(sz2)
b = sprandn(sz1, 1/sz1^2)
C = sprandn(sz2, sz2, 1/sz2^4)
D = sprandn(sz2, sz2, 1/sz2^4)
ϵ = 0.1

If you do track down memory problems to Convex, please do file an issue or comment on https://github.com/JuliaOpt/Convex.jl/issues/254!

You might want to try JuMP. I think you need to do some reformulations by hand (which Convex does automatically) in order to input the problem. JuMP is based on MOI which recently got a 1-norm cone (https://github.com/JuliaOpt/MathOptInterface.jl/pull/818) so that might be easier to do now (but I’m not sure how to use that from the JuMP interface). My impression is that JuMP is well optimized and doesn’t have much (if any) unnecessary copying etc.

1 Like
3

what is your version of SCS? how did you install it?

4

Hello Eric,

many thanks for your explanation! and sorry for the late reply – an
urgent task distracted me from this issue.

I have added this line:

and it executes in 14 seconds. Then the code enters solve!() and stays there for ~34 hours…

How can use a patched version of Convex.jl? I’m not yet sure how to
do that with Pkg.add() and Project.toml… (Is this perhaps a
question for the “first steps” section of this forum?)

Thanks for the suggestion – will try starting from there and
increasing the matrix size to see at what point SCS breaks (if it
breaks).

Riccardo

5

Hello Abulak,

I’m currently running SCS 2.0.2, which I compiled myself from the Git sources. I had tried to compile 2.1.1 and “master” but SCS.jl complained it requires SCS 2.0.*.

After compiling it, I set JULIA_LIBRARY_PATH and ran Pkg.add("SCS") as suggested at: GitHub - jump-dev/SCS.jl: Julia Wrapper for SCS (https://github.com/cvxgrp/scs)

Thanks,
Riccardo

6

ok, to isolate this one factor could you please try the “stock” scs? (unset JULIA_LINBRARY_PATH and run Pkg.build("SCS")).

If it doesn’t help please file a bug at SCS.jl;

I’m actually not sure if the instructions on SCS README are correct. Could you try this:

make purge
JULIA_HOME="/opt/julia-1.2.0/lib/julia"

make -j4 CFLAGS="-march=native" DLONG=1 USE_OPENMP=1 BLASLDFLAGS="-L$JULIA_HOME -lopenblas64_" BLAS64=1 BLASSUFFIX=_64_

LD_LIBRARY_PATH=$JULIA_HOME:$LD_LIBRARY_PATH ./out/demo_socp_direct 1000 0.5 0.5 1
LD_LIBRARY_PATH=$JULIA_HOME:$LD_LIBRARY_PATH ./out/demo_socp_indirect 1000 0.5 0.5 1
7

Hi Riccardo,

The fact that Convex.conic_problem runs quickly and without exceptions makes me think that the model formulation step is not a problem. Convex.jl pretty much just immediately passes off that data to MathProgBase which hands it to SCS.

To use that patched version of Convex with MOI, type ] to enter the package mode in the REPL and enter

add https://github.com/ericphanson/Convex.jl#MathOptInterface

Or you can do by running the Julia code

Pkg.add(PackageSpec(name="Convex", url="https://github.com/ericphanson/Convex.jl", rev="MathOptInterface"))

Either way will update your manifest to point towards this version of Convex. If Convex.jl is already loaded in your session, you need to restart Julia to use it (it won’t load two versions of the same package in the same Julia session).

The syntax for solving on this branch is just a bit different. Instead of solve!(problem, SCSSolver()), the syntax is solve!(problem, SCS.Optimizer()).

If you do try it out, let me know if you run into any problems!

8

I had tried this first, same behavior. (Actually, I compiled SCS
myself because I thought the “stock” version might not be
well-optimized for my computer since it was taking so long.)

Here: (I changed your instructions a bit: JULIA_HOME points to the
root dir of the Julia install, so libraries are in
$JULIA_HOME/lib/julia and I used make OPT_FLAGS=... instead of
make CFLAGS=... otherwise location of include files etc. were being
wiped away)

$ which julia
/opt/easybuild/software/Julia/1.2.0-linux-x86_64/bin/julia

$ export JULIA_HOME=/opt/easybuild/software/Julia/1.2.0-linux-x86_64

$ cd deps/scs/
$ make clean
$ make -j8 OPT_FLAGS="-march=native" DLONG=1 USE_OPENMP=1 BLASLDFLAGS="-L$JULIA_HOME/lib/julia -lopenblas64_" BLAS64=1 BLASSUFFIX=_64_
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/scs.o src/scs.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/util.o src/util.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/cones.o src/cones.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/accel.o src/accel.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/cs.o src/cs.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/linalg.o src/linalg.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/ctrlc.o src/ctrlc.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/scs_version.o src/scs_version.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o src/normalize.o src/normalize.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/indirect/private.o linsys/indirect/private.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/common.o linsys/common.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/private.o linsys/direct/private.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/ldl.o linsys/direct/external/ldl.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_1.o linsys/direct/external/amd_1.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_valid.o linsys/direct/external/amd_valid.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_2.o linsys/direct/external/amd_2.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_postorder.o linsys/direct/external/amd_postorder.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_control.o linsys/direct/external/amd_control.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_post_tree.o linsys/direct/external/amd_post_tree.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_preprocess.o linsys/direct/external/amd_preprocess.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_aat.o linsys/direct/external/amd_aat.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_info.o linsys/direct/external/amd_info.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_global.o linsys/direct/external/amd_global.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_defaults.o linsys/direct/external/amd_defaults.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_order.o linsys/direct/external/amd_order.c
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native   -c -o linsys/direct/external/amd_dump.o linsys/direct/external/amd_dump.c
mkdir -p out
mkdir -p out
ar rv out/libscsindir.a src/scs.o src/util.o src/cones.o src/accel.o src/cs.o src/linalg.o src/ctrlc.o src/scs_version.o src/normalize.o linsys/indirect/private.o linsys/common.o
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native -shared -Wl,-soname,libscsindir.so -o out/libscsindir.so src/scs.o src/util.o src/cones.o src/accel.o src/cs.o src/linalg.o src/ctrlc.o src/scs_version.o src/normalize.o linsys/indirect/private.o linsys/common.o -lm -lrt -lgomp -L/opt/easybuild/software/Julia/1.2.0-linux-x86_64/lib/julia -lopenblas64_
r - src/scs.o
r - src/util.o
r - src/cones.o
r - src/accel.o
r - src/cs.o
r - src/linalg.o
r - src/ctrlc.o
r - src/scs_version.o
r - src/normalize.o
r - linsys/indirect/private.o
r - linsys/common.o
ranlib out/libscsindir.a
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native -o out/demo_socp_indirect test/random_socp_prob.c out/libscsindir.a -lm -lrt -lgomp -L/opt/easybuild/software/Julia/1.2.0-linux-x86_64/lib/julia -lopenblas64_
mkdir -p out
mkdir -p out
ar rv out/libscsdir.a src/scs.o src/util.o src/cones.o src/accel.o src/cs.o src/linalg.o src/ctrlc.o src/scs_version.o src/normalize.o linsys/direct/private.o linsys/direct/external/ldl.o linsys/direct/external/amd_1.o linsys/direct/external/amd_valid.o linsys/direct/external/amd_2.o linsys/direct/external/amd_postorder.o linsys/direct/external/amd_control.o linsys/direct/external/amd_post_tree.o linsys/direct/external/amd_preprocess.o linsys/direct/external/amd_aat.o linsys/direct/external/amd_info.o linsys/direct/external/amd_global.o linsys/direct/external/amd_defaults.o linsys/direct/external/amd_order.o linsys/direct/external/amd_dump.o linsys/common.o
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native -shared -Wl,-soname,libscsdir.so -o out/libscsdir.so src/scs.o src/util.o src/cones.o src/accel.o src/cs.o src/linalg.o src/ctrlc.o src/scs_version.o src/normalize.o linsys/direct/private.o linsys/direct/external/ldl.o linsys/direct/external/amd_1.o linsys/direct/external/amd_valid.o linsys/direct/external/amd_2.o linsys/direct/external/amd_postorder.o linsys/direct/external/amd_control.o linsys/direct/external/amd_post_tree.o linsys/direct/external/amd_preprocess.o linsys/direct/external/amd_aat.o linsys/direct/external/amd_info.o linsys/direct/external/amd_global.o linsys/direct/external/amd_defaults.o linsys/direct/external/amd_order.o linsys/direct/external/amd_dump.o linsys/common.o -lm -lrt -lgomp -L/opt/easybuild/software/Julia/1.2.0-linux-x86_64/lib/julia -lopenblas64_
r - src/scs.o
r - src/util.o
r - src/cones.o
r - src/accel.o
r - src/cs.o
r - src/linalg.o
r - src/ctrlc.o
r - src/scs_version.o
r - src/normalize.o
r - linsys/direct/private.o
r - linsys/direct/external/ldl.o
r - linsys/direct/external/amd_1.o
r - linsys/direct/external/amd_valid.o
r - linsys/direct/external/amd_2.o
r - linsys/direct/external/amd_postorder.o
r - linsys/direct/external/amd_control.o
r - linsys/direct/external/amd_post_tree.o
r - linsys/direct/external/amd_preprocess.o
r - linsys/direct/external/amd_aat.o
r - linsys/direct/external/amd_info.o
r - linsys/direct/external/amd_global.o
r - linsys/direct/external/amd_defaults.o
r - linsys/direct/external/amd_order.o
r - linsys/direct/external/amd_dump.o
r - linsys/common.o
ranlib out/libscsdir.a
gcc -g -Wall -Wwrite-strings -pedantic -O3 -funroll-loops -Wstrict-prototypes -I. -Iinclude -Ilinsys -fPIC -fopenmp -march=native -o out/demo_socp_direct test/random_socp_prob.c out/libscsdir.a -lm -lrt -lgomp -L/opt/easybuild/software/Julia/1.2.0-linux-x86_64/lib/julia -lopenblas64_
****************************************************************************************
Successfully compiled scs, copyright Brendan O'Donoghue 2012.
To test, type 'out/demo_socp_indirect' to solve a random SOCP.
**********************************************************************************
Compiled with blas and lapack, can solve LPs, SOCPs, SDPs, ECPs, and PCPs
****************************************************************************************

$ LD_LIBRARY_PATH=$JULIA_HOME/lib/julia:$LD_LIBRARY_PATH ./out/demo_socp_direct 1000 0.5 0.5 1
seed : 1

_a is 3000 by 1000, with 32 nonzeros per column.
A has 32000 nonzeros (1.066667% dense).
Nonzeros of A take 0.000238 GB of storage.
Row idxs of A take 0.000119 GB of storage.
Col ptrs of A take 0.000004 GB of storage.

ScsCone information:
Zero cone rows: 1500
LP cone rows: 1500
Number of second-order cones: 0, covering 0 rows, with sizes
[]
Number of rows covered is 3000 out of 3000.

Generating random matrix:
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
done
true pri opt = 8.857986
true dua opt = 8.857986
----------------------------------------------------------------------------
        SCS v2.0.2 - Splitting Conic Solver
        (c) Brendan O'Donoghue, Stanford University, 2012-2017
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 32000
eps = 1.00e-05, alpha = 1.50, max_iters = 5000, normalize = 1, scale = 1.00
acceleration_lookback = -1, rho_x = 1.00e-03
Variables n = 1000, constraints m = 3000
Cones:  primal zero / dual free vars: 1500
        linear vars: 1500
Setup time: 2.88e-01s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0| 1.73e+00  1.94e+00  9.99e-01 -1.19e+03  1.16e+01  0.00e+00  3.17e-02
   100| 2.71e-04  3.08e-05  4.65e-04  8.84e+00  8.85e+00  8.57e-14  2.76e-01
   200| 4.80e-05  3.18e-06  6.24e-05  8.86e+00  8.86e+00  8.57e-14  4.78e-01
   300| 4.80e-05  1.28e-07  4.48e-05  8.86e+00  8.86e+00  3.59e-14  6.73e-01
   400| 1.77e-06  1.76e-06  6.48e-06  8.86e+00  8.86e+00  3.59e-14  8.10e-01
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 8.10e-01s
        Lin-sys: nnz in L factor: 518233, avg solve time: 1.72e-03s
        Cones: avg projection time: 1.14e-06s
        Acceleration: avg step time: 0.00e+00s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 5.9495e-16, dist(y, K*) = 0.0000e+00, s'y/|s||y| = -2.7643e-18
primal res: |Ax + s - b|_2 / (1 + |b|_2) = 1.7734e-06
dual res:   |A'y + c|_2 / (1 + |c|_2) = 1.7572e-06
rel gap:    |c'x + b'y| / (1 + |c'x| + |b'y|) = 6.4848e-06
----------------------------------------------------------------------------
c'x = 8.8580, -b'y = 8.8579
============================================================================
true pri opt = 8.857986
true dua opt = 8.857986
scs pri obj= 8.858026
scs dua obj = 8.857905

$ LD_LIBRARY_PATH=$JULIA_HOME/lib/julia:$LD_LIBRARY_PATH ./out/demo_socp_indirect 1000 0.5 0.5 1
seed : 1

_a is 3000 by 1000, with 32 nonzeros per column.
A has 32000 nonzeros (1.066667% dense).
Nonzeros of A take 0.000238 GB of storage.
Row idxs of A take 0.000119 GB of storage.
Col ptrs of A take 0.000004 GB of storage.

ScsCone information:
Zero cone rows: 1500
LP cone rows: 1500
Number of second-order cones: 0, covering 0 rows, with sizes
[]
Number of rows covered is 3000 out of 3000.

Generating random matrix:
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
done
true pri opt = 8.857986
true dua opt = 8.857986
----------------------------------------------------------------------------
        SCS v2.0.2 - Splitting Conic Solver
        (c) Brendan O'Donoghue, Stanford University, 2012-2017
----------------------------------------------------------------------------
Lin-sys: sparse-indirect, nnz in A = 32000, CG tol ~ 1/iter^(2.00)
eps = 1.00e-05, alpha = 1.50, max_iters = 5000, normalize = 1, scale = 1.00
acceleration_lookback = -1, rho_x = 1.00e-03
Variables n = 1000, constraints m = 3000
Cones:  primal zero / dual free vars: 1500
        linear vars: 1500
Setup time: 2.16e-03s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0| 1.74e+00  1.96e+00  9.99e-01 -1.19e+03  1.68e+01  0.00e+00  2.05e-01
   100| 2.89e-04  1.03e-05  4.36e-04  8.84e+00  8.85e+00  1.16e-13  2.56e-01
   200| 4.81e-05  4.63e-06  1.00e-04  8.86e+00  8.86e+00  1.16e-13  2.95e-01
   300| 4.80e-05  1.12e-06  3.89e-05  8.86e+00  8.86e+00  1.27e-13  3.19e-01
   400| 2.06e-05  7.59e-07  9.35e-06  8.86e+00  8.86e+00  2.38e-13  3.48e-01
   480| 1.54e-06  1.70e-06  2.27e-06  8.86e+00  8.86e+00  5.55e-15  3.72e-01
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 3.72e-01s
        Lin-sys: avg # CG iterations: 2.78, avg solve time: 6.91e-04s
        Cones: avg projection time: 4.23e-07s
        Acceleration: avg step time: 0.00e+00s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 5.0589e-16, dist(y, K*) = 0.0000e+00, s'y/|s||y| = 8.4916e-18
primal res: |Ax + s - b|_2 / (1 + |b|_2) = 1.5373e-06
dual res:   |A'y + c|_2 / (1 + |c|_2) = 1.7024e-06
rel gap:    |c'x + b'y| / (1 + |c'x| + |b'y|) = 2.2741e-06
----------------------------------------------------------------------------
c'x = 8.8580, -b'y = 8.8580
============================================================================
true pri opt = 8.857986
true dua opt = 8.857986
scs pri obj= 8.857998
scs dua obj = 8.857955

I can see from inspecting /proc/$(pgrep julia)/maps that the libscs*.so files just compiled have been loaded; still, I do not get any output from the solver to the console which I find puzzling…

Thanks,
Riccardo

9

Hi Eric,

many thanks for the setp-by-step instructions; I’m trying your branch
of Convex.jl out now, will let you know what the results are.

Thanks,
R

1 Like
10

With the MOI branch, the code crashes rather quickly (which is already
an improvement over crashing after 36 hours :-)):

┌ Info: Creating convex optimization problem ...
│   size(A) = (130050, 520200)
│   size(x) = (520200, 1)
│   size(b) = (130050,)
│   size(C) = (520200, 520200)
â””   size(D) = (520200, 520200)
┌ Debug: Done at 2019-10-24T19:29:27.488 ...
â”” @ BEAM /.../BEAM.jl/src/BEAM.jl:595
[ Info: Solving optimization problem ...

signal (11): Segmentation fault
in expression starting at REPL[16]:1
jl_gc_pool_alloc at /buildworker/worker/package_linux64/build/src/gc.c:1128
jl_gc_alloc_ at /buildworker/worker/package_linux64/build/src/julia_internal.h:274 [inlined]
jl_gc_alloc at /buildworker/worker/package_linux64/build/src/gc.c:2949
_new_array_ at /buildworker/worker/package_linux64/build/src/array.c:100 [inlined]
_new_array at /buildworker/worker/package_linux64/build/src/array.c:160 [inlined]
jl_alloc_array_1d at /buildworker/worker/package_linux64/build/src/array.c:420
ml_matches_visitor at /buildworker/worker/package_linux64/build/src/gf.c:2502
jl_typemap_intersection_node_visitor at /buildworker/worker/package_linux64/build/src/typemap.c:472
jl_typemap_intersection_visitor at /buildworker/worker/package_linux64/build/src/typemap.c:567
ml_matches at /buildworker/worker/package_linux64/build/src/gf.c:2547
cache_method at /buildworker/worker/package_linux64/build/src/gf.c:946
cache_method at /buildworker/worker/package_linux64/build/src/gf.c:1045 [inlined]
jl_mt_assoc_by_type at /buildworker/worker/package_linux64/build/src/gf.c:1045
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2153
_ntuple at ./ntuple.jl:36
ntuple at ./ntuple.jl:18 [inlined]
Type at /.../.julia/packages/SCS/Y9wx3/src/types.jl:117
#SCS_solve#5 at /.../.julia/packages/SCS/Y9wx3/src/c_wrapper.jl:46
#SCS_solve at ./none:0
unknown function (ip: 0x7f39e7065dac)
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2197
optimize! at /.../.julia/packages/SCS/Y9wx3/src/MOI_wrapper.jl:431
optimize! at /.../.julia/packages/MathOptInterface/XE04a/src/Utilities/cachingoptimizer.jl:189
optimize! at /.../.julia/packages/MathOptInterface/XE04a/src/Bridges/bridge_optimizer.jl:199
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2197
optimize! at /.../.julia/packages/MathOptInterface/XE04a/src/Utilities/cachingoptimizer.jl:189
#solve!#16 at /.../.julia/packages/Convex/ezsVS/src/MOI_solve.jl:192
solve! at /.../.julia/packages/Convex/ezsVS/src/MOI_solve.jl:179
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2197
beam at /.../BEAM.jl/src/BEAM.jl:610
beam at /.../BEAM.jl/src/BEAM.jl:239
unknown function (ip: 0x7f3a280f7277)
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2197
do_call at /buildworker/worker/package_linux64/build/src/interpreter.c:323
eval_value at /buildworker/worker/package_linux64/build/src/interpreter.c:411
eval_stmt_value at /buildworker/worker/package_linux64/build/src/interpreter.c:362 [inlined]
eval_body at /buildworker/worker/package_linux64/build/src/interpreter.c:772
jl_interpret_toplevel_thunk_callback at /buildworker/worker/package_linux64/build/src/interpreter.c:884
unknown function (ip: 0xfffffffffffffffe)
unknown function (ip: 0x7f39ee2c160f)
unknown function (ip: 0x1)
jl_interpret_toplevel_thunk at /buildworker/worker/package_linux64/build/src/interpreter.c:893
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:815
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:764
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:764
jl_toplevel_eval_in at /buildworker/worker/package_linux64/build/src/toplevel.c:844
eval at ./boot.jl:330
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2191
eval_user_input at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.2/REPL/src/REPL.jl:86
macro expansion at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.2/REPL/src/REPL.jl:118 [inlined]
#26 at ./task.jl:268
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2191
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1614 [inlined]
start_task at /buildworker/worker/package_linux64/build/src/task.c:596
unknown function (ip: 0xffffffffffffffff)
Allocations: 276536732 (Pool: 276486409; Big: 50323); GC: 847
Segmentation fault (core dumped)

I guess I should follow @abulak’s advice and report this as a bug in SCS.jl ?

1 Like
11

Ok, this seems to be a bug in SCS.jl. Could you check if using Pkg; Pkg.test("SCS") runs without errors?

Did you managed to solve a scaled-down version of the problem? If so, please consider filing a but for SCS.jl

(set also max_iters=1 and see what happens; depending on the system there might be some buffering involved, e.g. I see the first output only after ~ 4000 iterations has passed)

the alpha must be in (0,2) + segmentation fault might suggest that our SCSsettings was GCd…

12

I did some more tests, using sparse random matrices in a variant of Eric’s code above.
My modified code just tries different downscaling factors starting with scale=128 down to scale=1.

  • when using “stock” SCS, small test sizes run fine until scale=8, at which point I get an ArgumentError – I reported this as issue #162 in SCS.jl. The same error happens with the stock Convex.jl and with the MOI-based branch of Convex.jl.

  • when using custom-built SCS (exactly like above), I get an instant “Segmentation fault” already at scale=128. I reported this separately as issue #163 in SCS.jl.

Riccardo

13

The problem works fine in the original with Eric’s MOI branch of Convex.jl and the ECOS solver. Memory usage seems to be double that of SCS, though.

Anyway, it looks like the problem with the large dataset is an issue with SCS.

14

This was eventually solved in issue #163 on SCS.jl’s GitHub; I am summarizing the solution in case someone lands here by an Internet search. Many thanks to anyone involved for helping me debug it (it turned out most of the problems were self-inflicted).

  • I had to use @ericphanson’s version of Convex.jl that uses MathOptInterface (see comment #6 in this thread)

  • likewise, I had to use SCS.jl from the master branch, to use SCS 2.1 (this might be supported by the released SCS.jl by now)

  • I had to compile SCS myself, using the following command line (note that other mentions of make in this thread may have the error that actually originated issue #163):

      make OPT="-O3 -march=native" DLONG=1 USE_OPENMP=1 BLASLDFLAGS="-L$JULIA_HOME/lib/julia -lopenblas64_" BLAS64=1 BLASSUFFIX=_64_ LD_LIBRARY_PATH="$JULIA_HOME/lib/julia"
1 Like