Manual

Conic Duality

Conic duality is the starting point for MOI's duality conventions. When all functions are affine (or coordinate projections), and all constraint sets are closed convex cones, the model may be called a conic optimization problem. For conic-form minimization problems, the primal is:

and the dual is:

where each $\mathcal{C}_i$ is a closed convex cone and $\mathcal{C}_i^*$ is its dual cone.

For conic-form maximization problems, the primal is:

and the dual is:

A linear inequality constraint $a^T x + b \ge c$ should be interpreted as $a^T x + b - c \in \mathbb{R}_+$, and similarly $a^T x + b \le c$ should be interpreted as $a^T x + b - c \in \mathbb{R}_-$. Variable-wise constraints should be interpreted as affine constraints with the appropriate identity mapping in place of $A_i$.

For the special case of minimization LPs, the MOI primal form can be stated as

By applying the stated transformations to conic form, taking the dual, and transforming back into linear inequality form, one obtains the following dual:

For maximization LPs, the MOI primal form can be stated as:

and similarly, the dual is:

Supported constraints

This is the list of supported Function-in-Set constraints of the package. If you try to dualize a constraint not listed here, it will return an unsupported error.

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

Supported objective functions

Dualize a model

dualize(args...; kwargs...)

DualOptimizer

You can solve a primal problem by using its dual formulation using the DualOptimizer.

DualOptimizer(dual_optimizer::OT) where {OT <: MOI.ModelLike}

julia> using Dualization, JuMP, GLPK

julia> model = Model(dual_optimizer(GLPK.Optimizer))
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Dual model with GLPK attached

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.

Geometric form has affine expressions in cones

Standard form has variables in cones

Adding 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:

• supported_constraint
• dual_set

If the custom set has some special scalar product (see the link), the user also needs to provide a 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.

using Dualization, JuMP, MathOptInterface, LinearAlgebra

# Rename MathOptInterface to simplify the code
const MOI = MathOptInterface

# Define the custom cone and its dual
struct FakeCone <: MOI.AbstractVectorSet
    dimension::Int
end

struct FakeDualCone <: MOI.AbstractVectorSet
    dimension::Int
end

# Define a model with your FakeCone
model = Model()
@variable(model, x[1:3])
@constraint(model, con, x in FakeCone(3)) # Note that the constraint name is "con"
@objective(model, Min, sum(x))

The resulting JuMP model is

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

# Overload the methods dual_set and supported_constraints
Dualization.dual_set(s::FakeCone) = FakeDualCone(MOI.dimension(s))
Dualization.supported_constraint(::Type{MOI.VectorOfVariables}, ::Type{<:FakeCone}) = true

# If your set has some specific scalar product you also need to define a new set_dot function
# Our FakeCone has this weird scalar product
MOI.Utilities.set_dot(x::Vector, y::Vector, set::FakeCone) = 2dot(x, y)

# Dualize the model
dual_model = dualize(model)

The resulting dual model is

If the model has constraints that are MOI.VectorAffineFunction

model = Model()
@variable(model, x[1:3])
@constraint(model, con, x + 3 in FakeCone(3))
@objective(model, Min, sum(x))

the user only needs to extend the supported_constraints function.

# Overload the supported_constraints for VectorAffineFunction
Dualization.supported_constraint(::Type{<:MOI.VectorAffineFunction}, ::Type{<:FakeCone}) = true

# Dualize the model
dual_model = dualize(model)

The resulting dual model is

Advanced

KKT Conditions

The KKT conditions are a set of inequalities for which the feasible solution is equivalent to the optimal solution of an optimization problem, as long as strong duality holds and constraint qualification rules such as Slater's are valid. The KKT is used in many branches of optimization and it might be interesting to write them programatically.

The KKT conditions of the minimization problem of the first section are the following:

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Note that "Dual Feasibility" and "Stationarity" correspond to the two constraints of the dual problem. Therefore, after writing the primal problem, Dualization.jl can obtain the dual problem automatically and then we simply have to write the "Complementary slackness" to complete the KKT conditions.

One important use case is Bilevel optimization, see BilevelJuMP.jl. In this case, variables of an upstream model are considered as parameters in a lower level model. One classical solution method for bilevel programs is to write the KKT conditions of the lower (or inner) problem and consider them as (non-linear) constraints of the upper (or outer) problem. Dualization can be used to derive parts of KKT conditions.

Parametric problems

It is also possible to deal with parametric models. In regular optimization problems we only have a single (vector) variable represented by $x$ in the duality section, there are many use cases in which we can represent parameters that will not be considered in the optimization, these are treated as constants and, hence, not "dualized".

In the following, we will use $x$ to denote primal optimization variables, $y$ for dual optimization variables and $z$ for parameters.

and the dual is:

and the KKT conditions are:

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Quadratic problems

Optimization problems with conic constraints and quadratic objective are a straightforward extensions to the conic problem with linear constraints usually defined in MOI. More information here.

A primal minimization problem can be standardized as:

Where P is a positive semidefinite matrix.

A compact formulation for the dual problem requires pseudo-inverses, however, we can add an extra slack variable w to the dual problem and obtain the following dual problem:

note that the sign in front of the P matrix can be changed because w is free and the only other term depending in w is quadratic and symmetric. The sign choice is interesting to keep the dual problem closer to the KKT conditions that reads as follows:

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Parametric quadratic problems

Just like the linear problems, these quadratic programs can be parametric. The Primal minimization form is:

The Dual is:

and the KKT conditions are:

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity: