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: 112…737)
subject to
├─ ≤ constraint (affine)
│ └─ + (affine; real)
│ ├─ * (constant; positive)
│ │ ├─ …
│ │ └─ …
│ └─ Convex.NegateAtom (affine; real)
│ └─ …
├─ ≤ constraint (affine)
│ └─ + (affine; real)
│ ├─ 50-element real variable (id: 112…737)
│ └─ 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: 112…737)
subject to
├─ ≤ constraint (affine)
│ └─ + (affine; real)
│ ├─ * (constant; positive)
│ │ ├─ …
│ │ └─ …
│ └─ Convex.NegateAtom (affine; real)
│ └─ …
├─ ≤ constraint (affine)
│ └─ + (affine; real)
│ ├─ 50-element real variable (id: 112…737)
│ └─ Convex.NegateAtom (constant; negative)
│ └─ …
└─ PSD constraint (convex)
└─ + (affine; real)
├─ 50×50 Matrix{Float64}
└─ Convex.NegateAtom (affine; real)
└─ …
This page was generated using Literate.jl.