KKT systems

MadNLP manipulates KKT systems using two abstractions: an AbstractKKTSystem storing the KKT system' matrix and an AbstractKKTVector storing the KKT system's right-hand-side.

AbstractKKTSystem

MadNLP implements three different types of AbstractKKTSystem, depending how far we reduce the KKT system.

MadNLP.AbstractUnreducedKKTSystem — Type
AbstractUnreducedKKTSystem{T, MT} <: AbstractKKTSystem{T, MT}

Augmented KKT system associated to the linearization of the KKT conditions at the current primal-dual iterate $(x, s, y, z, ν, w)$.

The associated matrix is

[Wₓₓ  0  Aₑ'  Aᵢ'  -I   0 ]  [Δx]
[ 0   0   0   -I    0  -I ]  [Δs]
[Aₑ   0   0    0    0   0 ]  [Δy]
[Aᵢ  -I   0    0    0   0 ]  [Δz]
[V    0   0    0    X   0 ]  [Δν]
[0    W   0    0    0   S ]  [Δw]

with

  • $Wₓₓ$: Hessian of the Lagrangian.
  • $Aₑ$: Jacobian of the equality constraints
  • $Aᵢ$: Jacobian of the inequality constraints
  • $X = diag(x)$
  • $S = diag(s)$
  • $V = diag(ν)$
  • $W = diag(w)$
MadNLP.AbstractReducedKKTSystem — Type
AbstractReducedKKTSystem{T, MT} <: AbstractKKTSystem{T, MT}

The reduced KKT system is a simplification of the original Augmented KKT system. Comparing to AbstractUnreducedKKTSystem), AbstractReducedKKTSystem removes the two last rows associated to the bounds' duals $(ν, w)$.

At a primal-dual iterate $(x, s, y, z)$, the matrix writes

[Wₓₓ + Σₓ   0    Aₑ'   Aᵢ']  [Δx]
[ 0         Σₛ    0    -I ]  [Δs]
[Aₑ         0     0     0 ]  [Δy]
[Aᵢ        -I     0     0 ]  [Δz]

with

  • $Wₓₓ$: Hessian of the Lagrangian.
  • $Aₑ$: Jacobian of the equality constraints
  • $Aᵢ$: Jacobian of the inequality constraints
  • $Σₓ = X⁻¹ V$
  • $Σₛ = S⁻¹ W$
MadNLP.AbstractCondensedKKTSystem — Type
AbstractCondensedKKTSystem{T, MT} <: AbstractKKTSystem{T, MT}

The condensed KKT system simplifies further the AbstractReducedKKTSystem by removing the rows associated to the slack variables $s$ and the inequalities.

At the primal-dual iterate $(x, y)$, the matrix writes

[Wₓₓ + Σₓ + Aᵢ' Σₛ Aᵢ    Aₑ']  [Δx]
[         Aₑ              0 ]  [Δy]

with

  • $Wₓₓ$: Hessian of the Lagrangian.
  • $Aₑ$: Jacobian of the equality constraints
  • $Aᵢ$: Jacobian of the inequality constraints
  • $Σₓ = X⁻¹ V$
  • $Σₛ = S⁻¹ W$

Each AbstractKKTSystem follows the interface described below:

MadNLP.get_kkt — Function
get_kkt(kkt::AbstractKKTSystem)::AbstractMatrix

Return a pointer to the KKT matrix implemented in kkt. The pointer is passed afterward to a linear solver.

MadNLP.initialize! — Function
initialize!(kkt::AbstractKKTSystem)

Initialize KKT system with default values. Called when we initialize the InteriorPointSolver storing the current KKT system kkt.

MadNLP.build_kkt! — Function
build_kkt!(kkt::AbstractKKTSystem)

Assemble the KKT matrix before calling the factorization routine.

MadNLP.compress_hessian! — Function
compress_hessian!(kkt::AbstractKKTSystem)

Compress the Hessian inside kkt's internals. This function is called every time a new Hessian is evaluated.

Default implementation do nothing.

MadNLP.compress_jacobian! — Function
compress_jacobian!(kkt::AbstractKKTSystem)

Compress the Jacobian inside kkt's internals. This function is called every time a new Jacobian is evaluated.

By default, the function updates in the Jacobian the coefficients associated to the slack variables.

MadNLP.jtprod! — Function
jtprod!(y::AbstractVector, kkt::AbstractKKTSystem, x::AbstractVector)

Multiply with transpose of Jacobian and store the result in y, such that $y = A' x$ (with $A$ current Jacobian).

MadNLP.regularize_diagonal! — Function
regularize_diagonal!(kkt::AbstractKKTSystem, primal_values::AbstractVector, dual_values::AbstractVector)

Regularize the values in the diagonal of the KKT system. Called internally inside the interior-point routine.

MadNLP.set_jacobian_scaling! — Function
set_jacobian_scaling!(kkt::AbstractKKTSystem, scaling::AbstractVector)

Set the scaling of the Jacobian with the vector scaling storing the scaling for all the constraints in the problem.

MadNLP.is_inertia_correct — Function
is_inertia_correct(kkt::AbstractKKTSystem, n::Int, m::Int, p::Int)

Check if the inertia $(n, m, p)$ returned by the linear solver is adapted to the KKT system implemented in kkt.

By default, MadNLP stores a AbstractReducedKKTSystem in sparse format, as implemented by SparseKKTSystem:

The user has the choice to store the KKT system as a sparse AbstractUnreducedKKTSystem:

MadNLP provides also two structures to store the KKT system in a dense matrix. Although less efficient than their sparse counterparts, these two structures allow to store the KKT system efficiently when the problem is instantiated on the GPU.

MadNLP.DenseKKTSystem — Type
DenseKKTSystem{T, VT, MT} <: AbstractReducedKKTSystem{T, MT}

Implement AbstractReducedKKTSystem with dense matrices.

Requires a dense linear solver to be factorized (otherwise an error is returned).

AbstractKKTVector

Each instance of AbstractKKTVector implements the following interface.

MadNLP.AbstractKKTVector — Type
AbstractKKTVector{T, VT}

Supertype for KKT's right-hand-side vectors $(x, s, y, z, ν, w)$.

MadNLP.number_primal — Function
number_primal(X::AbstractKKTVector)

Get total number of primal values $(x, s)$ in KKT vector X.

MadNLP.number_dual — Function
number_dual(X::AbstractKKTVector)

Get total number of dual values $(y, z)$ in KKT vector X.

MadNLP.full — Function
full(X::AbstractKKTVector)

Return the all the values stored inside the KKT vector X.

MadNLP.primal — Function
primal(X::AbstractKKTVector)

Return the primal values $(x, s)$ stored in the KKT vector X.

MadNLP.dual — Function
dual(X::AbstractKKTVector)

Return the dual values $(y, z)$ stored in the KKT vector X.

MadNLP.primal_dual — Function
primal_dual(X::AbstractKKTVector)

Return both the primal and the dual values $(x, s, y, z)$ stored in the KKT vector X.

MadNLP.dual_lb — Function
dual_lb(X::AbstractKKTVector)

Return the dual values $ν$ associated to the lower-bound stored in the KKT vector X.

MadNLP.dual_ub — Function
dual_ub(X::AbstractKKTVector)

Return the dual values $w$ associated to the upper-bound stored in the KKT vector X.

By default, MadNLP provides two different AbstractKKTVector.