GitHub

Overview

The KKT module provides a modular, customizable interface for developing and selecting various approaches to solve the KKT systems.

KKT backends

KKT systems

All formulations below refer to a linear program in primal-dual standard form

\[ \begin{array}{rl} (P) \ \ \ \displaystyle \min_{x} & c^{\top} x\\ s.t. & A x = b\\ & l \leq x \leq u \end{array} \quad \quad \quad \begin{array}{rl} (D) \ \ \ \displaystyle \max_{y, z} & b^{\top} y + l^{\top}z^{l} - u^{\top}z^{u}\\ s.t. & A^{\top}y + z^{l} - z^{u} = c\\ & z^{l}, z^{u} \geq 0 \end{array}\]

Tulip.KKT.K2 — Type
K2 <: AbstractKKTSystem

Augmented system

\[ \begin{bmatrix} -(\Theta^{-1} + R_{p}) & A^{\top}\\ A & R_{d} \end{bmatrix} \begin{bmatrix} \Delta x\\ \Delta y \end{bmatrix} = \begin{bmatrix} \xi_d\\ \xi_p \end{bmatrix}\]

where

  • $\Theta^{-1} = X^{-l}Z^{l} + X^{-u} Z^{u}$
  • $R_{p}, R_{d}$ are current primal and dual regularizations
  • $\xi_{d}, \xi_{p}$ are given right-hand sides
source
Tulip.KKT.K1 — Type
K1 <: AbstractKKTSystem

Normal equations system

\[ \begin{array}{rl} \left( A (\Theta^{-1} + R_{p})^{-1} A^{\top} + R_{d} \right) \Delta y & = \xi_{p} + A (Θ^{-1} + R_{p})^{-1} \xi_{d}\\ \Delta x &= (Θ^{-1} + R_{p})^{-1} (A^{\top} \Delta y - \xi_{d}) \end{array}\]

where

  • $\Theta^{-1} = X^{-l}Z^{l} + X^{-u} Z^{u}$
  • $R_{p}, R_{d}$ are current primal and dual regularizations
  • $\xi_{d}, \xi_{p}$ are the augmented system's right-hand side
source

KKT solvers

Custom linear solvers should (preferably) inherit from the AbstractKKTSolver class, and extend the following functions:

Tulip.KKT.update! — Function
update!(kkt, θinv, regP, regD)

Update internal data and factorization/pre-conditioner.

After this call, kkt can be used to solve the augmented system

    [-(Θ⁻¹ + Rp)   Aᵀ] [dx] = [ξd]
    [   A          Rd] [dy]   [ξp]

for given right-hand sides ξd and ξp.

Arguments

  • kkt::AbstractKKTSolver{T}: the KKT solver object
  • θinv::AbstractVector{T}: $θ⁻¹$
  • regP::AbstractVector{T}: primal regularizations
  • regD::AbstractVector{T}: dual regularizations
source
Tulip.KKT.solve! — Function
solve!(dx, dy, kkt, ξp, ξd)

Solve the symmetric quasi-definite augmented system

    [-(Θ⁻¹ + Rp)   Aᵀ] [dx] = [ξd]
    [   A          Rd] [dy]   [ξp]

and over-write dx, dy with the result.

Arguments

  • dx, dy: Vectors of unknowns, modified in-place
  • kkt: Linear solver for the augmented system
  • ξp, ξd: Right-hand-side vectors
source