View on GitHub

memo

Chapter16-02. Direct Solution of the KKT System

16.2 Direct Solution of the KKT System

Theorem 16.3

Then

\[\mathrm{inertia}(K) = \mathrm{inertia}(Z^{\mathrm{T}}GZ) + (m, m, 0) .\]

If $Z^{\mathrm{T}}GZ$ is positive definite, $\mathrm{inertia}(K) = (n, m, 0)$.

proof

$\Box$
\[\begin{eqnarray} x^{*} & := & Yx_{Y} + Z x_{Z} \nonumber \\ Z & \in & \mathrm{Null}(A) \nonumber \\ Y & \in & \mathbb{R}^{n - m} \nonumber \end{eqnarray}\]

By substituting this into the equality constraints,

\[\begin{eqnarray} & & Ax = b \nonumber \\ & \Leftrightarrow & A Y x_{Y} + A Z x_{Z} = b \nonumber \\ & \Leftrightarrow & A Y x_{Y} = b . \nonumber \end{eqnarray}\] \[\begin{eqnarray} q(x) & = & \frac{1}{2} x^{\mathrm{T}} G x + c^{\mathrm{T}} x \nonumber \\ & = & \frac{1}{2} (Yx_{Y})^{\mathrm{T}} G x + c^{\mathrm{T}} x \end{eqnarray}\]

TODO.

$\Box$

Factoring The Full KKT System

For (2), $K$ is decomposed as follows

\[\begin{eqnarray} P^{\mathrm{T}}KP = LBL^{\mathrm{T}} \label{equation_16_12} \end{eqnarray}\]

where $P$ is permutation matrix, $L$ is unit lower triangular, and $B$ is block-diagonal with either $1 \times 1$ or $2 \times 2$ blocks. By substituting the decomposition, we obtain

\[\begin{eqnarray} & & K \left( \begin{array}{c} -p \\ \lambda^{*} \end{array} \right) = \left( \begin{array}{c} g \\ h \end{array} \right) \nonumber \\ & \Leftrightarrow & PLBL^{\mathrm{T}}P^{\mathrm{T}} \left( \begin{array}{c} -p \\ \lambda^{*} \end{array} \right) = \left( \begin{array}{c} g \\ h \end{array} \right) \nonumber \\ & \Leftrightarrow & LBL^{\mathrm{T}}P^{\mathrm{T}} \left( \begin{array}{c} -p \\ \lambda^{*} \end{array} \right) = P^{\mathrm{T}} \left( \begin{array}{c} g \\ h \end{array} \right) . \nonumber \end{eqnarray}\]

To solve the equation,

\[\begin{eqnarray} \text{solve }_{z} L z & = & P^{\mathrm{T}} \left( \begin{array}{c} g \\ h \end{array} \right) \nonumber \\ \text{solve }_{\hat{z}} B \hat{z} & = & z \nonumber \\ \text{solve }_{\bar{z}} L^{\mathrm{T}} \bar{z} & = & \hat{z} \nonumber \\ \left( \begin{array}{c} - p \\ \lambda^{*} \end{array} \right) & \leftarrow & P \bar{z} \nonumber \end{eqnarray}\]

Schur-complement Method

From KKT condition,

\[\begin{eqnarray} -Gp + A^{\mathrm{T}}\lambda^{*} & = & g \nonumber \\ -Ap & = & h . \nonumber \end{eqnarray}\] \[\begin{eqnarray} & & -Gp + A^{\mathrm{T}}\lambda^{*} = g \nonumber \\ & \Leftrightarrow & -Ap + AG^{-1}A^{\mathrm{T}}\lambda^{*} = AG^{-1}g \nonumber \\ & \Leftrightarrow & h + AG^{-1}A^{\mathrm{T}}\lambda^{*} = AG^{-1}g \nonumber \\ & \Leftrightarrow & AG^{-1}A^{\mathrm{T}}\lambda^{*} = AG^{-1}g - h . \label{equation_16_13} \end{eqnarray}\]

We can solve the equation with respect to $\lambda^{*}$.

\[\begin{eqnarray} & & -Gp + A^{\mathrm{T}}\lambda^{*} = g \nonumber \\ & \Leftrightarrow & Gp = A^{\mathrm{T}}\lambda^{*} - g . \label{equation_16_14} \end{eqnarray}\] \[\begin{eqnarray} \left( \begin{array}{cc} G & A^{\mathrm{T}} \\ 0 & - AG^{-1}A^{\mathrm{T}} \end{array} \right) \label{equation_16_15} \end{eqnarray}\]

$AG^{-1}A^{\mathrm{T}}$ is the Schur complenet of $G$ in $K$.

\[\begin{eqnarray} \left( \begin{array}{cc} G & A^{\mathrm{T}} \\ A & 0 \end{array} \right)^{-1} & = & \left( \begin{array}{cc} C & E \\ E^{\mathrm{T}} & F \end{array} \right) \nonumber \\ C & := & G^{-1} - G^{-1}A^{\mathrm{T}}(AG^{-1}A^{\mathrm{T}})^{-1}AG^{-1} \nonumber \\ E & := & G^{-1}A^{\mathrm{T}}(AG^{-1}A^{\mathrm{T}})^{-1} \nonumber \\ F & := & -(AG^{-1}A^{\mathrm{T}})^{-1} . \nonumber \end{eqnarray}\]

Null-space method

\[\begin{eqnarray} p = Y p_{Y} + Z p_{Z} \label{equation_16_17} \end{eqnarray}\]

where $Z \in \mathbb{R}^{n \times (n - m)}$ null-space matrix, and $Y \in \mathbb{R}^{n \times m}$ such that $[Y \mid Z]$ is nonsingular. By substituting $p$ into the second equation, we obtain

\[\begin{eqnarray} & & -A p = h \nonumber \\ & \Leftrightarrow & -A \left( Y p_{Y} + Z p_{Z} \right) = h \nonumber \\ & \Leftrightarrow & -A Y p_{Y} = h . \label{equation_16_18} \end{eqnarray}\] \[\begin{eqnarray} & & -G p + A^{\mathrm{T}}\lambda^{*} = g \nonumber \\ & \Leftrightarrow & - GYp_{Y} - G Z p_{Z} + A^{\mathrm{T}}\lambda^{*} = g \nonumber \\ & \Leftrightarrow & - Z^{\mathrm{T}}GYp_{Y} - Z^{\mathrm{T}} G Z p_{Z} = Z^{\mathrm{T}} g \nonumber \\ & \Leftrightarrow & Z^{\mathrm{T}}GYp_{Y} = - Z^{\mathrm{T}} g - Z^{\mathrm{T}} G Z p_{Z} . \label{equation_16_19} \end{eqnarray}\]

Lagrange multiplier is obtaiined by

\[\begin{eqnarray} & & -Gp + A^{\mathrm{T}}\lambda^{*} = g & \Leftrightarrow & A^{\mathrm{T}}\lambda^{*} = g + Gp \nonumber \\ & \Leftrightarrow & (AY)^{\mathrm{T}}\lambda^{*} = Y^{\mathrm{T}} \left( g + Gp \right) \label{equation_16_20} \end{eqnarray}\]