KKT conditions using Dualization

[matbesancon]

Specifying KKT conditions of a problem using Dualization could be interesting, we have most of the bricks already in place. Given a primal:

min <c, x>
A x = b
x in K

Yielding a dual:

max <b, y>
A^T y + s = c
s in dual(K)

The KKT can be expressed with primal feasibility, dual feasibility and complementarity. The first two parts can be expressed with standard convex constraints. The last one being less trivial, two options would be:

• Adding complementarity constraints, see discussion https://github.com/JuliaOpt/MathOptInterface.jl/issues/771
• Returning pairs of complementary expressions or variables, with the notation from above [(x_j, s_j), j in 1..n]

[odow]

💯 for this.

The last one being less trivial, two options would be:

Vote for Complementarity constraints.

I talked to M. Ferris about this and we're super keen to be able to solve KKT's with PATH.

But we have to be a little careful about how we do the formulation. Take a read of the pitfalls section.

Essentially, we need to make sure to write

[Ax - b; s] in Complements()

instead of

[b - Ax; s] in Complements()

In addition, while it makes sense to convert to the standard form Ax = b before constructing the KKT's, it might be better to keep as much model structure as possible, and derive the KKT's directly from the user's model without normalizing first. This gives PATH more information since otherwise it has s free which is hard.

[matbesancon]

In some cases (if you know bounds on your primal and dual expression), rewriting using big Ms & binaries can be a decent option, for which having the two expressions can be easier.

for i in eachindex(kkt_results.complementarity_pairs)
    (primal_expr, dual_expr) = kkt_results.complementarity_pairs[i]
    (Mp, Md) = bounds[i]
    z[i] = @variable(m, Bin)
    @constraint(m, 0 <= primal_expr <= Mp * z[i])
    @constraint(m, 0 <= dual_expr <= Md * (1 - z[i]))
end

[joaquimg]

Some of it was done in: https://github.com/joaquimg/BilevelJuMP.jl

[matbesancon]

Considered handled by #67 or do we leave this open?

[guilhermebodin]

Don't know if it is interesting to have a function kkt that receives an MOI problem and returns the kkt conditions as MOI constraints with Complements(). For now BilevelJuMP.jl builds the kkt conditions internally, and the way to define the complementarity depends on the mode chosen by the user.