Manual

Conic Duality

MOI standard form and 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.

The following formulations follow strictly MOI´s definition of duality we shall refer to them as MOI standard form.

For 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 maximization problems, the primal is:

and the dual is:

Note that the equality constraints have minus signs that could be flipped for simplicity. However, for generality, we keep the minus signs so that the models displayed here precisely match the outputs of the package.

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$.

We will always present the maximization forms after the minimization form for completeness. However, it is possible to obtain the maximizatio dual by flipping the objective signs of a maximization problem, converting it in a minimization problem, then apply minimization duality and flip the signs again to obtain the dual as a minimization problem.

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:

MOI compact form and duality

An equivalent formulation for conic duality explicitly constrains variables into cones. The implicit version can be achieved with the above formulation (MOI standard form) by considering the A_i that are projections onto some of the canonical axis.

The explicit constraints on variables convey additional structural information that can be exploited by some solver. Therefore, MOI includes the method add_constrained_variables for such purpose. These constraints are special because they are created together with the corresponding constrained variables. Hence, each variable can only belong to one of such.

Next, we precisely define the MOI compact form and present their respective dual problems. The reader will notice that the models are more verbose than the MOI standard form, but actually the solvers receives fewer constraints and slack variables are avoided. Consequently, the dual will have fewer variables and fewer constraints.

Minimization problem in MOI compact form

The primal is:

and the dual is:

where each $\mathcal{C}_i$ and $\mathcal{V}_j$ are closed convex cones and $\mathcal{C}_i^*$ and $\mathcal{V}_j^*$ the respective dual cones.

Maximization problem in MOI compact form

The primal is:

and the dual is:

Note that signs changed in the constraints of the dual compared to the standard form. This is because the standard form would have negative signs in all terms in a equality constraint, which were inverted for simplicity. However, in the compact form, this operation is not allowed because it would change a nontrivial cone $\mathcal{C}_i$.

Linear Programming

Minimization

Primal

Dual

Maximization

Primal

Dual

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, HiGHS

julia> model = Model(dual_optimizer(HiGHS.Optimizer))
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Dual model with HiGHS 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 programmatically.

MOI standard form

Minimization

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.

Maximization

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

MOI compact form

Minimization

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

We keep the $u_j$ variable explicit to make Dual Feasibility and Complementary Slackness very clear. However, in the final model it is possible to replace the latter using the stationarity constraint.

Maximization

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

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.

MOI standard form

Minimization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Maximization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

MOI compact form

Minimization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Maximization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Quadratic problems

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

MOI standard form

Minimization

Primal

Where P is a positive semidefinite matrix.

Dual

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, in the constraint, 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.

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Maximization

Primal

Where N is negative semidefinite, i.e., -N is a positive semidefinite matrix.

Dual

Just like in the minimization case we can add an extra slack variable w to the dual problem and obtain the following dual problem:

note that, in the constraint, the sign in front of the N 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.

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

MOI compact form

Minimization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Maximization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Parametric quadratic problems

Just like the conic linear problems, these quadratic programs can be parametric.

MOI standard form

Minimization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Maximization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

MOI compact form

Minimization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity:

Maximization

Primal

Dual

KKT

• Primal Feasibility:

• Dual Feasibility:

• Complementary slackness:

• Stationarity: