16.3 Iterative solution of the KKT System

• Assume $Z^{\mathrm{T}}GZ$ is positive definite

CG Applied to the reduced system

Let $x^{*}$ be an optimal solution. By null-space method, the optimal solution can be decomposed as

\[\begin{eqnarray} x^{*} & = & Y x_{Y} + Z x_{Z} \label{equation_16_21} \end{eqnarray}\]

where

• $x_{Z} \in \mathbb{R}^{n-m}$,
  • $AZ = 0$
• $x_{Y} \in \mathbb{R}^{m}$,

By substituting the linear constraint, we obtain

\[\begin{eqnarray} & & Ax^{*} = b \\ & \Leftrightarrow & A Y x_{Y} = b. \label{equation_16_22} \end{eqnarray}\]

Hence $x_{Y}$ can be obtained by the above equation.

\[\begin{eqnarray} & & \min_{x} \frac{1}{2} x^{\mathrm{T}}Gx + x^{\mathrm{T}}c \nonumber \\ & \Leftrightarrow & \min_{x} \frac{1}{2} (Yx_{Y} + Z x_{Z})^{\mathrm{T}}G(Yx_{Y} + Z x_{Z}) + (Yx_{Y} + Z x_{Z})^{\mathrm{T}}c \nonumber \\ & \Leftrightarrow & \min_{x} \frac{1}{2} (Yx_{Y} + Z x_{Z})^{\mathrm{T}}G(Yx_{Y} + Z x_{Z}) + (Yx_{Y} + Z x_{Z})^{\mathrm{T}}c \end{eqnarray}\]

Algorithm 16.1

Preconditioned CG for Reduced Systems.

• $x_{Z} \in \mathbb{R}^{n - m}$,
  • initial point

Step (1)

\[\begin{eqnarray} r_{Z} & := & Z ^{\mathrm{T}} GZ x_{Z} + c_{Z}, \nonumber \\ g_{Z} & := & W_{ZZ}^{-1} r_{Z}, \nonumber \\ d_{Z} & := & - g_{Z}, \nonumber \end{eqnarray}\]

Step (2)

\[\begin{eqnarray} \alpha & \leftarrow & \frac{ r_{Z}^{\mathrm{T}} g_{Z} }{ d_{Z}^{\mathrm{T}} Z^{\mathrm{T}} GZd_{Z} } \label{equation_16_25_a} \\ x_{Z} & \leftarrow & x_{Z} + \alpha d_{Z} \label{equation_16_25_b} \\ r_{Z}^{+} & \leftarrow & r_{Z} + \alpha Z^{\mathrm{T}} G Z d_{Z} \label{equation_16_25_c} \\ g_{Z}^{+} & \leftarrow & W_{ZZ}^{-1}r_{Z}^{+} \label{equation_16_25_e} \\ \beta & \leftarrow & \frac{ (r_{Z}^{+})^{\mathrm{T}} g_{Z}^{+} }{ r_{Z}^{\mathrm{T}}g_{Z} } \label{equation_16_25_f} \\ d_{Z} & \leftarrow & - g_{Z}^{+} + \beta d_{Z} \label{equation_16_25_g} \\ g_{Z} & \leftarrow & g_{Z}^{+} . \label{equation_16_25_h} \end{eqnarray}\]

Step(3) Stop if a termination test is satisfied.

■

Projected CG Method

• Avoids operating with the null-space basis $Z$,

Algorithm 16.2

• Initial point $x$ satysfying $Ax = b$,

Step (1)

• $P := Z(Z^{\mathrm{T}}HZ)^{-1}Z^{\mathrm{T}}$
  • where $H$ is precoditioned matrix in \(\eqref{equation_16_26}\)
• $r := Gx + c$,
• $g = Pr$,
• $d = -g$,

Step (2)

\[\begin{eqnarray} \alpha & \leftarrow & \frac{ r g }{ d^{\mathrm{T}} Gd } \label{equation_16_28_a} \\ x & \leftarrow & x + \alpha d \label{equation_16_28_b} \\ r^{+} & \leftarrow & r + \alpha G d \label{equation_16_28_c} \\ g^{+} & \leftarrow & P r^{+} \label{equation_16_28_e} \\ \beta & \leftarrow & \frac{ (r^{+})^{\mathrm{T}} g^{+} }{ r^{\mathrm{T}}g } \label{equation_16_28_f} \\ d & \leftarrow & - g^{+} + \beta d \label{equation_16_28_g} \\ g & \leftarrow & g^{+} . \label{equation_16_28_h} \end{eqnarray}\]

Step (3) Exist if the test is satisfied. Example of stop test

\[\begin{eqnarray} \abs{ r^{\mathrm{T}}g - r^{\mathrm{T}}Pr } < \epsilon_{\text{tor}} . \en{eqnarray}\]

■

Remark

• $g^{+}$ in the Algorithm is called preconditioned residual, which is defined in the null space of $A$,
• All the search direction $d$ lie in the null space of $A$,
• All $x$ satisfy $Ax = b$,
• Iteration is well-defined if $Z^{\mathrm{T}}GZ$ and $Z^{\mathrm{T}}HZ$ are positive definite
• Choice of $H$
  • $H = \mathrm{diag}(\abs{G{ii}})$,
  • $H = I$,
    • $P$ is the orthogonal projection operator onto the null space of $A$,
  • $H$ as a block diagonal submatrix of $G$,

■

$P_{I}$ is the orothogonal projection operator onto the null space of $A$, that is,

\[\begin{equation} P_{I} := Z(Z^{\mathrm{T}}Z)^{-1}Z^{\mathrm{T}} . \label{equation_16_29} \end{equation}\]

Calculation of the preconditioned residual $g^{+} = P_{I}r^{*}$

There are two ways to calcualte $g^{+1} = P_{I}r^{+}$.

(1) normal euqations approache.

$P_{I}$ have the form

\[\begin{eqnarray} P_{I} = I - A^{\mathrm{T}}(AA^{\mathrm{T}})^{-1}A . \label{equation_16_30} \end{eqnarray}\]

Then $g^{+} = r^{+} - A^{\mathrm{T}}v^{+}$ where $v^{+}$ is the solution of the system

\[\begin{equation} AA^{\mathrm{T}} v^{+} = A r^{+} . \label{equation_16_31} \end{equation}\]

(2) The augmented system approach

\(\begin{eqnarray} \left( \begin{array}{cc} I & A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{c} g^{+} \\ v^{+} \end{array} \right) = \left( \begin{array}{c} r^{+} \\ 0 \end{array} \right) . \label{equation_16_32} \end{eqnarray}\) .

We suppose that $H$ is nonsingular.

(1)

\[\begin{eqnarray} g^{+} & = & P r^{+} \nonumber \\ P & = & H^{-1} ( I - A^{\mathrm{T}}(AH^{-1}A^{\mathrm{T}})^{-1}AH^{-1} ) . \label{equation_16_33} \end{eqnarray}\]

(2) Let us assume that $z^{\mathrm{T}}Hz \neq 0$ for all $z \neq 0$ with $Az = 0$.

\[\begin{eqnarray} \left( \begin{array}{cc} H & A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{c} g^{+} \\ v^{+} \end{array} \right) = \left( \begin{array}{c} r^{+} \\ 0 \end{array} \right) . \label{equation_16_34} \end{eqnarray}\]