Dualization

Sometimes it can be much faster to solve the dual problem than the primal problem. Some solvers will automatically dualize the problem when heuristics deem it beneficial, and alternative DCP modeling languages like CVX will also automatically dualize the problem in some cases. Convex.jl does not automatically dualize any problem, but it is easy to manually do so with Dualization.jl. Here, we will solve a simple semidefinite program (from issue #492) to show how easy it is to dualize the problem, and that it can potentially provide speed ups.

First we load our packages:

using LinearAlgebra
using Convex
using SCS
using Random
using Dualization

Then we setup some test data.

Random.seed!(2022)
p = 50
Σ = Symmetric(randn(p, p))
Σ = Σ * Σ'

50×50 Matrix{Float64}:
  38.5491      -9.19434   -3.35362   …    7.51269   -0.782174    0.492346
  -9.19434     46.2082     3.26346       -8.45905    1.75253    -3.20636
  -3.35362      3.26346   33.9143        -5.48804   -1.74758    -0.448776
   1.90123      1.10823   -0.658593      -0.708771  -4.96303    13.2111
  -0.158679     5.1113     1.48752       -7.48692   11.2294    -15.8021
   4.1403      -0.880331  -9.98876   …    2.51248    4.70591    -4.44428
  -0.402594    -8.29294   -1.58844      -18.6578    -3.31759   -16.3024
 -11.304       10.2001     2.74323      -15.9419     5.75689     8.9036
  -0.0870085   -2.24014    4.96537      -11.4286     1.07291    -4.92868
   0.91165      1.99918   -2.81873       -6.38792    2.71753     6.62308
   ⋮                                 ⋱                         
   3.0628      -8.9038    -4.89449       22.4662     0.405483   -0.622388
  -2.46038     -0.809097   0.981026      13.9882    10.532      -0.436251
   9.00452      4.00894   -9.72641       16.9225     3.16809   -11.0192
  -0.915969    10.8618     1.36586      -17.3174    -4.8303      2.44034
  -0.102041   -10.8846    -2.18525   …   -6.03156    8.08281     1.16781
   3.09663     -0.860589  10.1752        -2.85544   -5.69597    -4.61083
   7.51269     -8.45905   -5.48804       53.7031     2.99391     6.01758
  -0.782174     1.75253   -1.74758        2.99391   41.273      -2.77065
   0.492346    -3.20636   -0.448776       6.01758   -2.77065    47.6351

Now we formulate and solve our primal problem:

d = Variable(p)
problem = maximize(sum(d), 0 ≤ d, d ≤ 1, Σ ⪰ Diagonal(d))
@time solve!(problem, SCS.Optimizer; silent = true)

Problem statistics
  problem is DCP         : true
  number of variables    : 1 (50 scalar elements)
  number of constraints  : 3 (2_600 scalar elements)
  number of coefficients : 2_602
  number of atoms        : 10

Solution summary
  termination status : OPTIMAL
  primal status      : FEASIBLE_POINT
  dual status        : FEASIBLE_POINT
  objective value    : 11.5088

Expression graph
  maximize
   └─ sum (affine; real)
      └─ 50-element real variable (id: 771…872)
  subject to
   ├─ ≤ constraint (affine)
   │  └─ + (affine; real)
   │     ├─ * (constant; positive)
   │     │  ├─ …
   │     │  └─ …
   │     └─ Convex.NegateAtom (affine; real)
   │        └─ …
   ├─ ≤ constraint (affine)
   │  └─ + (affine; real)
   │     ├─ 50-element real variable (id: 771…872)
   │     └─ Convex.NegateAtom (constant; negative)
   │        └─ …
   └─ PSD constraint (convex)
      └─ + (affine; real)
         ├─ 50×50 Matrix{Float64}
         └─ Convex.NegateAtom (affine; real)
            └─ …

To solve the dual problem instead, we simply call dual_optimizer on our optimizer function:

@time solve!(problem, dual_optimizer(SCS.Optimizer); silent = true)

Problem statistics
  problem is DCP         : true
  number of variables    : 1 (50 scalar elements)
  number of constraints  : 3 (2_600 scalar elements)
  number of coefficients : 2_602
  number of atoms        : 10

Solution summary
  termination status : OPTIMAL
  primal status      : FEASIBLE_POINT
  dual status        : FEASIBLE_POINT
  objective value    : 11.5279

Expression graph
  maximize
   └─ sum (affine; real)
      └─ 50-element real variable (id: 771…872)
  subject to
   ├─ ≤ constraint (affine)
   │  └─ + (affine; real)
   │     ├─ * (constant; positive)
   │     │  ├─ …
   │     │  └─ …
   │     └─ Convex.NegateAtom (affine; real)
   │        └─ …
   ├─ ≤ constraint (affine)
   │  └─ + (affine; real)
   │     ├─ 50-element real variable (id: 771…872)
   │     └─ Convex.NegateAtom (constant; negative)
   │        └─ …
   └─ PSD constraint (convex)
      └─ + (affine; real)
         ├─ 50×50 Matrix{Float64}
         └─ Convex.NegateAtom (affine; real)
            └─ …

This page was generated using Literate.jl.