Extended formulations and the DCP ruleset
Convex.jl works by transforming the problem (which possibly has nonsmooth, nonlinear constructions like the nuclear norm, the log determinant, and so forth—into) a linear optimization problem subject to conic constraints.
The transformed problem often involves adding auxiliary variables, and it is called an "extended formulation," since the original problem has been extended with additional variables.
Creating an extended formulation relies on the problem being modeled by combining Convex.jl's "atoms" or primitives according to certain rules which ensure convexity, called the disciplined convex programming (DCP) ruleset. If these atoms are combined in a way that does not ensure convexity, the extended formulations are often invalid.
A valid formulation
As a simple example, consider the problem:
julia> using Convex, SCS
julia> x = Variable();
julia> model_min = minimize(abs(x), [x >= 1, x <= 2]);
julia> solve!(model_min, SCS.Optimizer; silent = true)
Problem statistics problem is DCP : true number of variables : 1 (1 scalar elements) number of constraints : 2 (2 scalar elements) number of coefficients : 2 number of atoms : 3 Solution summary termination status : OPTIMAL primal status : FEASIBLE_POINT dual status : FEASIBLE_POINT objective value : 1.0 Expression graph minimize └─ abs (convex; positive) └─ real variable (id: 149…174) subject to ├─ ≥ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 149…174) │ └─ [-1;;] └─ ≤ constraint (affine) └─ + (affine; real) ├─ real variable (id: 149…174) └─ [-2;;]
julia> x.value
0.999999999998428
The optimum occurs at x = 1
, but let us imagine we want to solve this problem via Convex.jl using a linear programming (LP) solver.
Since abs
is a nonlinear function, we need to reformulate the problem to pass it to the LP solver. We do this by introducing an auxiliary variable t
and instead solving:
julia> using Convex, SCS
julia> x = Variable();
julia> t = Variable();
julia> model_min_extended = minimize(t, [x >= 1, x <= 2, t >= x, t >= -x]);
julia> solve!(model_min_extended, SCS.Optimizer; silent = true)
Problem statistics problem is DCP : true number of variables : 2 (2 scalar elements) number of constraints : 4 (4 scalar elements) number of coefficients : 2 number of atoms : 7 Solution summary termination status : OPTIMAL primal status : FEASIBLE_POINT dual status : FEASIBLE_POINT objective value : 1.0 Expression graph minimize └─ real variable (id: 139…972) subject to ├─ ≥ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 676…714) │ └─ [-1;;] ├─ ≤ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 676…714) │ └─ [-2;;] ├─ ≥ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 139…972) │ └─ Convex.NegateAtom (affine; real) │ └─ … ⋮
julia> x.value
0.999999999998428
That is, we add the constraints t >= x
and t >= -x
, and replace abs(x)
by t
. Since we are minimizing over t
and the smallest possible t
satisfying these constraints is the absolute value of x
, we get the right answer. This reformulation worked because we were minimizing abs(x)
, and that is a valid way to use the primitive abs
.
An invalid formulation
The reformulation of abx(x)
works only if we are minimizing t
.
Why? Well, let us consider the same reformulation for a maximization problem. The original problem is:
julia> using Convex
julia> x = Variable();
julia> model_max = maximize(abs(x), [x >= 1, x <= 2])
Problem statistics problem is DCP : false number of variables : 1 (1 scalar elements) number of constraints : 2 (2 scalar elements) number of coefficients : 2 number of atoms : 3 Solution summary termination status : OPTIMIZE_NOT_CALLED primal status : NO_SOLUTION dual status : NO_SOLUTION Expression graph maximize └─ abs (convex; positive) └─ real variable (id: 765…242) subject to ├─ ≥ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 765…242) │ └─ [-1;;] └─ ≤ constraint (affine) └─ + (affine; real) ├─ real variable (id: 765…242) └─ [-2;;]
This time, problem is DCP
reports false
. If we attempt to solve the problem, an error is thrown:
julia> solve!(model_max, SCS.Optimizer; silent = true)
┌ Warning: Problem not DCP compliant: objective is not DCP
└ @ Convex ~/.julia/dev/Convex/src/problems.jl:73
ERROR: DCPViolationError: Expression not DCP compliant. This either means that your problem is not convex, or that we could not prove it was convex using the rules of disciplined convex programming. For a list of supported operations, see https://jump.dev/Convex.jl/stable/operations/. For help writing your problem as a disciplined convex program, please post a reproducible example on https://jump.dev/forum.
Stacktrace:
[...]
The error is thrown because, if we do the same reformulation as before, we arrive at the problem:
julia> using Convex, SCS
julia> x = Variable();
julia> t = Variable();
julia> model_max_extended = maximize(t, [x >= 1, x <= 2, t >= x, t >= -x]);
julia> solve!(model_max_extended, SCS.Optimizer; silent = true)
Problem statistics problem is DCP : true number of variables : 2 (2 scalar elements) number of constraints : 4 (4 scalar elements) number of coefficients : 2 number of atoms : 7 Solution summary termination status : DUAL_INFEASIBLE primal status : INFEASIBILITY_CERTIFICATE dual status : INFEASIBLE_POINT Expression graph maximize └─ real variable (id: 955…969) subject to ├─ ≥ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 187…646) │ └─ [-1;;] ├─ ≤ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 187…646) │ └─ [-2;;] ├─ ≥ constraint (affine) │ └─ + (affine; real) │ ├─ real variable (id: 955…969) │ └─ Convex.NegateAtom (affine; real) │ └─ … ⋮
whose solution is unbounded.
In other words, we can get the wrong answer by using the extended reformulation, because the extended formulation was only valid for a minimization problem.
Convex.jl always creates the extended reformulation, but because they are only guaranteed to be valid when the DCP ruleset is followed, Convex.jl will programmatically check the whether or not these DCP rules were satisfied and error if they were not.