Understanding DCP in Convex.jl and the difference of elapsed time

Specific Domains Optimization (Mathematical)
,
1

Hi, there!

I’d like to understand why the following elapsed times to solve the following two problems are significantly different.

Here is my code and the result (to avoid high latency due to JIT compile, the results are from the second run).

  • code
using Convex
using SCS


function main()
    m = 100
    u = Variable(m)
    problem = minimize(sum(u))
    problem.constraints += [u >= -ones(m)]
    problem.constraints += [u <= ones(m)]
    @time solve!(problem, SCS.Optimizer())
end

function main2()
    m = 100
    u = Variable(m)
    problem = minimize(sum(abs.(u)))
    problem.constraints += [u >= -ones(m)]
    problem.constraints += [u <= ones(m)]
    @time solve!(problem, SCS.Optimizer())
end
  • result
julia> main()
----------------------------------------------------------------------------
        SCS v2.1.2 - Splitting Conic Solver
        (c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 301
eps = 1.00e-05, alpha = 1.50, max_iters = 5000, normalize = 1, scale = 1.00
acceleration_lookback = 10, rho_x = 1.00e-03
Variables n = 101, constraints m = 201
Cones:  primal zero / dual free vars: 1
        linear vars: 200
Setup time: 3.74e-04s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0| 1.56e+19  1.95e+19  7.71e-01 -1.80e+21 -2.33e+20  1.40e+21  7.28e-05
    16| 1.20e-10  6.18e-11  4.24e-12 -1.00e+02 -1.00e+02  6.95e-17  1.08e-03
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 1.08e-03s
        Lin-sys: nnz in L factor: 603, avg solve time: 4.80e-06s
        Cones: avg projection time: 3.53e-07s
        Acceleration: avg step time: 4.79e-05s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 7.7311e-17, dist(y, K*) = 0.0000e+00, s'y/|s||y| = 1.4670e-16
primal res: |Ax + s - b|_2 / (1 + |b|_2) = 1.1957e-10
dual res:   |A'y + c|_2 / (1 + |c|_2) = 6.1776e-11
rel gap:    |c'x + b'y| / (1 + |c'x| + |b'y|) = 4.2369e-12
----------------------------------------------------------------------------
c'x = -100.0000, -b'y = -100.0000
============================================================================
  0.005095 seconds (3.30 k allocations: 273.094 KiB)

julia> main2()
----------------------------------------------------------------------------
        SCS v2.1.2 - Splitting Conic Solver
        (c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Lin-sys: sparse-direct, nnz in A = 701
eps = 1.00e-05, alpha = 1.50, max_iters = 5000, normalize = 1, scale = 1.00
acceleration_lookback = 10, rho_x = 1.00e-03
Variables n = 201, constraints m = 401
Cones:  primal zero / dual free vars: 1
        linear vars: 400
Setup time: 5.95e-04s
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
----------------------------------------------------------------------------
     0| 1.97e+19  3.19e+18  1.00e+00 -2.02e+21 -0.00e+00  1.57e+21  9.95e-05
     9| 1.31e-11  6.84e-12  4.47e-11 -4.47e-11 -0.00e+00  2.74e-16  1.25e-03
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 1.26e-03s
        Lin-sys: nnz in L factor: 1404, avg solve time: 1.21e-05s
        Cones: avg projection time: 5.42e-07s
        Acceleration: avg step time: 9.24e-05s
----------------------------------------------------------------------------
Error metrics:
dist(s, K) = 4.8275e-16, dist(y, K*) = 0.0000e+00, s'y/|s||y| = -4.5881e-16
primal res: |Ax + s - b|_2 / (1 + |b|_2) = 1.3110e-11
dual res:   |A'y + c|_2 / (1 + |c|_2) = 6.8377e-12
rel gap:    |c'x + b'y| / (1 + |c'x| + |b'y|) = 4.4708e-11
----------------------------------------------------------------------------
c'x = -0.0000, -b'y = -0.0000
============================================================================
  0.025528 seconds (70.72 k allocations: 5.545 MiB)

As can be seen, the second problem with abs operator took much longer time.
I guess that this is because Convex.jl transforms the problem into a conic problem with many slack variables.
It is just my guess, so I’d like to check whether it’s right, or any other reasons.

Thanks!

2

Modified code and result using BenchmarkTools.jl:

  • code
using Convex
using SCS
using BenchmarkTools


function main()
    m = 100
    # 1
    u = Variable(m)
    problem = minimize(sum(u))
    problem.constraints += [u >= -ones(m)]
    problem.constraints += [u <= ones(m)]
    b1 = @benchmark solve!($problem, SCS.Optimizer(); silent_solver=true)
    # 2
    u2 = Variable(m)
    problem2 = minimize(sum(abs.(u2)))
    problem2.constraints += [u2 >= -ones(m)]
    problem2.constraints += [u2 <= ones(m)]
    b2 = @benchmark solve!($problem2, SCS.Optimizer(); silent_solver=true)
    display(b1)
    display(b2)
end
  • result
julia> main()
BenchmarkTools.Trial: 6326 samples with 1 evaluation.
 Range (min … max):  733.458 ΞΌs …   7.484 ms  β”Š GC (min … max): 0.00% … 84.76%
 Time  (median):     754.250 ΞΌs               β”Š GC (median):    0.00%
 Time  (mean Β± Οƒ):   787.644 ΞΌs Β± 298.844 ΞΌs  β”Š GC (mean Β± Οƒ):  2.56% Β±  5.89%

  β–†β–ˆβ–ˆβ–…β–ƒβ–‚β–‚β–                                                      β–‚
  β–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–‡β–ˆβ–‡β–‡β–†β–‡β–†β–†β–†β–…β–†β–†β–†β–…β–…β–…β–„β–…β–ƒβ–ƒβ–β–„β–„β–ƒβ–„β–…β–β–ƒβ–ƒβ–…β–ƒβ–ƒβ–…β–ƒβ–ƒβ–ƒβ–β–β–β–β–β–ƒβ–β–β–β–β–ƒβ–„β–β–β–β–„ β–ˆ
  733 ΞΌs        Histogram: log(frequency) by time       1.37 ms <

 Memory estimate: 273.44 KiB, allocs estimate: 3309.
BenchmarkTools.Trial: 825 samples with 1 evaluation.
 Range (min … max):  5.248 ms … 24.311 ms  β”Š GC (min … max): 0.00% …  0.00%
 Time  (median):     5.487 ms              β”Š GC (median):    0.00%
 Time  (mean Β± Οƒ):   6.059 ms Β±  1.517 ms  β”Š GC (mean Β± Οƒ):  7.28% Β± 12.28%

  β–…β–ˆβ–†β–†β–„β–ƒβ–ƒ ▁                                     ▁▁▁
  β–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–‡β–ˆβ–†β–„β–†β–…β–…β–β–β–β–β–β–„β–„β–β–„β–„β–β–β–β–β–β–β–β–„β–„β–β–β–β–β–„β–„β–†β–ˆβ–ˆβ–ˆβ–ˆβ–ˆβ–‡β–‡β–‡β–†β–„β–†β–β–„β–„ β–ˆ
  5.25 ms      Histogram: log(frequency) by time       10 ms <

 Memory estimate: 5.55 MiB, allocs estimate: 70725.
1 Like
3

You can see why in the log of SCS

nnz in A = 301
Variables n = 101, constraints m = 201

nnz in A = 701
Variables n = 201, constraints m = 401

So the abs version has twice as may variables, twice as many constraints, and more than twice as many non-zeros in the constraint matrix.

2 Likes
4

Thanks for mentioning the evidence.

Then, I wonder if the difference between the numbers of optimisation variable and constraints are due to slack variable generation.
It’s probably right… isn’t it?

5

Yes, I assume Convex reformulates abs(x) into a new variable y with two constraints y >= x and y >= -x. Since you have 100 variables, that accounts for the 100 new variables and the 200 new constraints.

3 Likes
6

Thanks for your help, @odow !

1 Like
7

Wait, I found something strange.

We may transform the following problem

\text{Minimise} \quad \sum_i |u_i| \\ \text{subsect to} \quad u_{\min} \leq u_i \leq u_{max}

into

\text{Minimise} \quad t \\ \text{subsect to} \quad u_{\min} \leq u_i \leq u_{max} \\ \quad u_i \leq t \\ \quad u_i \leq -t

So why Convex.jl generates 100 slack variables…? I think it needs only one, t.

Well, probably due to that Convex.jl takes different reformulation though.

8

Your two formulations are not equivalent.

2 Likes
9

Oh, got it.
It is a summation. Sorry.

1 Like