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

**URL:** <https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626>\
**Category:** Optimization (Mathematical)\
**Tags:** convex-optimization, disciplined-convex-p\
**Created:** [December 6, 2021, 1:37am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626 "2021-12-06T01:37:31Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![iHany](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihany/32/18151_2.png) [@iHany](https://discourse.julialang.org/u/iHany)\
**Post date:** [December 6, 2021, 1:37am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/1 "2021-12-06T01:37:31Z")

</div>

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

```julia
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
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!

---

<div class="post-metadata">

**Author:** ![iHany](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihany/32/18151_2.png) [@iHany](https://discourse.julialang.org/u/iHany)\
**Post date:** [December 6, 2021, 1:41am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/2 "2021-12-06T01:41:24Z")

</div>

Modified code and result using `BenchmarkTools.jl`:

- code

```julia
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
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.

```

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [December 6, 2021, 1:54am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/3 "2021-12-06T01:54:08Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![iHany](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihany/32/18151_2.png) [@iHany](https://discourse.julialang.org/u/iHany)\
**Post date:** [December 6, 2021, 1:55am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/4 "2021-12-06T01:55:52Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [December 6, 2021, 1:57am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/5 "2021-12-06T01:57:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![iHany](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihany/32/18151_2.png) [@iHany](https://discourse.julialang.org/u/iHany)\
**Post date:** [December 6, 2021, 1:58am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/6 "2021-12-06T01:58:03Z")

</div>

Thanks for your help, @odow !

---

<div class="post-metadata">

**Author:** ![iHany](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihany/32/18151_2.png) [@iHany](https://discourse.julialang.org/u/iHany)\
**Post date:** [December 6, 2021, 2:33am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/7 "2021-12-06T02:33:37Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [December 6, 2021, 2:37am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/8 "2021-12-06T02:37:24Z")

</div>

Your two formulations are not equivalent.

---

<div class="post-metadata">

**Author:** ![iHany](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihany/32/18151_2.png) [@iHany](https://discourse.julialang.org/u/iHany)\
**Post date:** [December 6, 2021, 2:38am UTC](https://discourse.julialang.org/t/understanding-dcp-in-convex-jl-and-the-difference-of-elapsed-time/72626/9 "2021-12-06T02:38:06Z")

</div>

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