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.AbstractKKTSystem — Type
AbstractKKTSystem{T, VT<:AbstractVector{T}, MT<:AbstractMatrix{T}, QN<:AbstractHessian{T}}

Abstract type for KKT system.

source

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

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

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ᵢ' V½  0  ]  [Δx]
[0    0   0   -I   0   W½ ]  [Δ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  ]  [Δρ]

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)$
  • $Δτ = -W^{-½}Δν$
  • $Δρ = -W^{-½}Δw$
source
MadNLP.AbstractReducedKKTSystem — Type
AbstractReducedKKTSystem{T, VT, MT, QN} <: AbstractKKTSystem{T, VT, MT, QN}

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$
source
MadNLP.AbstractCondensedKKTSystem — Type
AbstractCondensedKKTSystem{T, VT, MT, QN} <: AbstractKKTSystem{T, VT, MT, QN}

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

Each AbstractKKTSystem follows the interface described below:

MadNLP.create_kkt_system — Function
create_kkt_system(
    ::Type{KKT},
    cb::AbstractCallback,
    ind_cons::NamedTuple,
    linear_solver::Type{LinSol};
    opt_linear_solver=default_options(linear_solver),
    hessian_approximation=ExactHessian,
) where {KKT<:AbstractKKTSystem, LinSol<:AbstractLinearSolver}

Instantiate a new KKT system with type KKT, associated to the the nonlinear program encoded inside the callback cb. The NamedTuple ind_cons stores the indexes of all the variables and constraints in the callback cb. In addition, the user should pass the linear solver linear_solver that will be used to solve the KKT system after it has been assembled.

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

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

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

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

Assemble the KKT matrix before calling the factorization routine.

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

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

source
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).

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

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

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

source

Sparse KKT systems

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

Alternatively, the user has the choice to store the KKT system as a SparseUnreducedKKTSystem or as a SparseCondensedKKTSystem:

Dense KKT systems

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.

AbstractKKTVector

Each instance of AbstractKKTVector implements the following interface.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

source

By default, MadNLP provides one implementation of an AbstractKKTVector.