Manual

Dualize a JuMP model

Use dualize to formulate the dual of a JuMP model.

For example, consider this problem:

julia> using JuMP, Dualization
julia> begin
           model = Model()
           @variable(model, x)
           @variable(model, y >= 0)
           @variable(model, z)
           @constraint(model, soccon, [1.0 * x + 2.0, y, z] in SecondOrderCone())
           @constraint(model, eqcon, x == 1)
           @constraint(model, con_le, x + y >= 1)
           @objective(model, Min, y + z)
       end;
julia> print(model)Min y + z
Subject to
 eqcon : x = 1
 con_le : x + y ≥ 1
 soccon : [x + 2, y, z] ∈ MathOptInterface.SecondOrderCone(3)
 y ≥ 0
julia> dual_model = dualize(model)A JuMP Model
├ solver: none
├ objective_sense: MAX_SENSE
│ └ objective_function_type: JuMP.AffExpr
├ num_variables: 5
├ num_constraints: 5
│ ├ JuMP.AffExpr in MOI.EqualTo{Float64}: 2
│ ├ JuMP.AffExpr in MOI.GreaterThan{Float64}: 1
│ ├ Vector{JuMP.VariableRef} in MOI.SecondOrderCone: 1
│ └ JuMP.VariableRef in MOI.GreaterThan{Float64}: 1
└ Names registered in the model: none
julia> print(dual_model)Max _[2] - 2 _[3] + _[1]
Subject to
 _[1] + _[2] + _[3] = 0
 _[5] = 1
 -_[2] - _[4] ≥ -1
 [_[3], _[4], _[5]] ∈ MathOptInterface.SecondOrderCone(3)
 _[2] ≥ 0

Name the dual variables and dual constraints

Provide prefixes for the names of the variables and constraints using DualNames.

julia> dual_model = dualize(model; dual_names = DualNames("dual_var_", "dual_con_"))A JuMP Model
├ solver: none
├ objective_sense: MAX_SENSE
│ └ objective_function_type: JuMP.AffExpr
├ num_variables: 5
├ num_constraints: 5
│ ├ JuMP.AffExpr in MOI.EqualTo{Float64}: 2
│ ├ JuMP.AffExpr in MOI.GreaterThan{Float64}: 1
│ ├ Vector{JuMP.VariableRef} in MOI.SecondOrderCone: 1
│ └ JuMP.VariableRef in MOI.GreaterThan{Float64}: 1
└ Names registered in the model
  └ :dual_con_x, :dual_con_y, :dual_con_z, :dual_var_con_le, :dual_var_eqcon, :dual_var_soccon_1, :dual_var_soccon_2, :dual_var_soccon_3
julia> print(dual_model)Max dual_var_con_le - 2 dual_var_soccon_1 + dual_var_eqcon
Subject to
 dual_con_x : dual_var_eqcon + dual_var_con_le + dual_var_soccon_1 = 0
 dual_con_z : dual_var_soccon_3 = 1
 dual_con_y : -dual_var_con_le - dual_var_soccon_2 ≥ -1
 [dual_var_soccon_1, dual_var_soccon_2, dual_var_soccon_3] ∈ MathOptInterface.SecondOrderCone(3)
 dual_var_con_le ≥ 0

Pass a new optimizer

If the primal model has an optimizer attached you will lose the optimizer during the dualization. To dualize the model and attach the optimizer to the dual model you should do dualize(model, optimizer):

julia> import ECOS
julia> dual_model = dualize(model, ECOS.Optimizer)A JuMP Model
├ solver: ECOS
├ objective_sense: MAX_SENSE
│ └ objective_function_type: JuMP.AffExpr
├ num_variables: 5
├ num_constraints: 5
│ ├ JuMP.AffExpr in MOI.EqualTo{Float64}: 2
│ ├ JuMP.AffExpr in MOI.GreaterThan{Float64}: 1
│ ├ Vector{JuMP.VariableRef} in MOI.SecondOrderCone: 1
│ └ JuMP.VariableRef in MOI.GreaterThan{Float64}: 1
└ Names registered in the model: none

Solve a problem using its dual formulation

Wrap an optimizer with dual_optimizer to solve the dual of the problem instead of the primal:

julia> using JuMP, Dualization, ECOS
julia> model = Model(dual_optimizer(ECOS.Optimizer))A JuMP Model
├ solver: Dual model with ECOS attached
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

You can also set the optimizer after the model is created:

julia> using JuMP, Dualization, ECOS
julia> model = Model()A JuMP Model
├ solver: none
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none
julia> set_optimizer(model, dual_optimizer(ECOS.Optimizer))

Pass arguments to the solver by attaching them to the solver constructor:

julia> using JuMP, Dualization, ECOS
julia> model = Model(dual_optimizer(optimizer_with_attributes(ECOS.Optimizer, "maxit" => 5)))A JuMP Model
├ solver: Dual model with ECOS attached
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

or by using JuMP.set_attribute:

julia> using JuMP, Dualization, ECOS
julia> model = Model(dual_optimizer(ECOS.Optimizer))A JuMP Model
├ solver: Dual model with ECOS attached
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none
julia> set_attribute(model, "maxit", 5)

The benefit of solving the dual formulation

Solving an optimization problem via its dual representation can be useful because some conic solvers assume the model is in the standard form and others use the geometric form.

The geometric conic form has affine expressions in cones:

\[\begin{align} & \min_{x \in \mathbb{R}^n} & c^T x \\ & \;\;\text{s.t.} & A_i x + b_i & \in \mathcal{C}_i & i = 1 \ldots m \end{align}\]

The standard form has variables in cones:

\[\begin{align} & \min_{x \in \mathbb{R}^n} & c^T x \\ & \;\;\text{s.t.} & A x + s & = b \\ & & s & \in \mathcal{C} \end{align}\]

Solvers which use the geometric conic form include CDCS, SCS, ECOS, and SeDuMi. Solvers which use the standard conic form include SDPT3, SDPNAL, CSDP, and SDPA. Mosek v10 supports both affine constraints in cones and variables in cones, hence both the standard and geometric form at the same time.

Supported problem types

Dualization.jl works only for optimization models that can be written in conic form, and that are composed of the following constraints and objectives.

If you try to dualize an unsupported model, and error will be thrown.

Constraints

Note that some of MOI constraints can be bridged, see Bridges, to constraints in this list.

Objective functions

Advanced: add support for new sets

Dualization.jl can automatically dualize models with custom sets.

To do this, the user needs to define the set and its dual set and provide the functions:

• Dualization.supported_constraint
• MathOptInterface.dual_set

If the custom set has some special scalar product (see the link), the user also needs to provide the MathOptInterface.Utilities.set_dot function.

For example, let us define a fake cone and its dual, the fake dual cone. We will write a JuMP model with the fake cone and dualize it.

julia> using Dualization, JuMP
julia> struct FakeCone <: MOI.AbstractVectorSet
           dimension::Int
       end
julia> struct FakeDualCone <: MOI.AbstractVectorSet
           dimension::Int
       end
julia> model = Model();
julia> @variable(model, x[1:3] >= 0)3-element Vector{JuMP.VariableRef}:
 x[1]
 x[2]
 x[3]
julia> @constraint(model, con, 1.0 * x in FakeCone(3))con : [x[1], x[2], x[3]] ∈ Main.FakeCone(3)
julia> @objective(model, Min, sum(x))x[1] + x[2] + x[3]
julia> print(model)Min x[1] + x[2] + x[3]
Subject to
 x[1] ≥ 0
 x[2] ≥ 0
 x[3] ≥ 0
 con : [x[1], x[2], x[3]] ∈ Main.FakeCone(3)

Now in order to dualize we must overload the methods as described above.

julia> MOI.dual_set(s::FakeCone) = FakeDualCone(MOI.dimension(s))
julia> function Dualization.supported_constraint(
           ::Type{MOI.VectorOfVariables},
           ::Type{FakeCone},
       )
           return true
       end
julia> function Dualization.supported_constraint(
           ::Type{<:MOI.VectorAffineFunction},
           ::Type{FakeCone},
       )
           return true
       end

If your set has some specific scalar product you also need to define a new set_dot function. Assume that our FakeCone has this weird scalar product:

julia> import LinearAlgebra
julia> function MOI.Utilities.set_dot(x::Vector, y::Vector, ::FakeCone)
           return 2 * LinearAlgebra.dot(x, y)
       end

Dualize the model

julia> dual_model = dualize(model)A JuMP Model
├ solver: none
├ objective_sense: MAX_SENSE
│ └ objective_function_type: JuMP.AffExpr
├ num_variables: 3
├ num_constraints: 4
│ ├ JuMP.AffExpr in MOI.GreaterThan{Float64}: 3
│ └ Vector{JuMP.VariableRef} in Main.FakeDualCone: 1
└ Names registered in the model: none
julia> print(dual_model)Max 0
Subject to
 -_[3] ≥ -1
 -_[2] ≥ -1
 -_[1] ≥ -1
 [_[1], _[2], _[3]] ∈ Main.FakeDualCone(3)