16.1 Equality-constrained quadratic programs

Definition

• $A \in \mathbb{R}^{m \times n}$,
  • $m \le n$,
  • rank $m$
• $G \in \mathbb{R}^{n \times n}$,

\[\begin{align} \min_{x} & & & q(x) := \frac{1}{2} x^{\mathrm{T}}Gx + x^{\mathrm{T}}c \label{equation_16_03_a} \\ \mathrm{subject\ to} & & & Ax = b \label{equation_16_03_b} \end{align}\]

■

The first order necessary conditions for $x^{*}$ to be a solution of the above euqation

\[\begin{eqnarray} & & \left( \begin{array}{cc} G & -A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{c} x^{*} \\ \lambda \end{array} \right) = \left( \begin{array}{c} -c \\ b \end{array} \right) \nonumber \\ & \Leftrightarrow & \left( \begin{array}{cc} Gx^{*} - A^{\mathrm{T}} \lambda^{*} \\ Ax^{*} + 0 \end{array} \right) = \left( \begin{array}{c} -c \\ b \end{array} \right) \label{equation_16_04} \end{eqnarray}\]

where \(\lambda^{*}\) is lagrange multiplier. Let $x^{*} - x =: p$. Then we

\[\begin{eqnarray} & & \left( \begin{array}{cc} G & -A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{c} x^{*} \\ \lambda \end{array} \right) = \left( \begin{array}{c} -c \\ b \end{array} \right) \nonumber \\ & \Leftrightarrow & \left( \begin{array}{cc} Gx + Gp - A^{\mathrm{T}} \lambda^{*} \\ Ax + Ap \end{array} \right) = \left( \begin{array}{c} -c \\ b \end{array} \right) \nonumber \\ & \Leftrightarrow & \left( \begin{array}{cc} - Gx - Gp + A^{\mathrm{T}} \lambda^{*} \\ Ap \end{array} \right) = \left( \begin{array}{c} c \\ b - Ax \end{array} \right) \nonumber \\ & \Leftrightarrow & \left( \begin{array}{cc} - Gp + A^{\mathrm{T}} \lambda^{*} \\ -Ap \end{array} \right) = \left( \begin{array}{c} c + Gx \\ -b + Ax \end{array} \right) \nonumber \\ & \Leftrightarrow & \left( \begin{array}{cc} G & A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{cc} -p \\ \lambda^{*} \end{array} \right) = \left( \begin{array}{c} g \\ h \end{array} \right) \label{equation_16_05_kkt_matrix} \end{eqnarray}\]

where

\[\begin{eqnarray} g & := & c + Gx \nonumber \\ h & := & Ax - b \nonumber \end{eqnarray}\]

Lemma 16.1

• $A \in \mathbb{R}^{m \times n}$,
  • rank $m$
• $Z \in \mathbb{R}^{n \times (n - m)}$,
  • rank $n - m$
  • columns are a basis of null space of $A$,
    • $AZ = 0$,

If

\[Z^{\mathrm{T}}GZ\]

is positive definite, the KKT matrix

\[\begin{eqnarray} K := \left( \begin{array}{cc} G & A^{\mathrm{T}} \\ A & 0 \end{array} \right) \nonumber \end{eqnarray}\]

is nonsingular. There is a unique vector pair \((x^{*}, \lambda^{*})\) satisfying.

proof

Supposer that $w \in \mathbb{R}^{n}$ and $v \in \mathbb{R}^{n}$ satisfy

\[\begin{equation} \left( \begin{array}{cc} G & A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{c} w \\ v \end{array} \right) = 0 \label{equation_16_08} \end{equation} .\]

Since $A w = 0$,

\[\begin{eqnarray} \left( \begin{array}{c} w \\ v \end{array} \right)^{\mathrm{T}} \left( \begin{array}{cc} G & A^{\mathrm{T}} \\ A & 0 \end{array} \right) \left( \begin{array}{c} w \\ v \end{array} \right) & = & \left( \begin{array}{c} w \\ v \end{array} \right)^{\mathrm{T}} \left( \begin{array}{cc} Gw & A^{\mathrm{T}}v \\ 0 \end{array} \right) \nonumber \\ & = & w^{\mathrm{T}}Gw & A^{\mathrm{T}}v \nonumber \\ & = & 0 \quad (\because \eqref{equation_16_08}) . \nonumber \end{eqnarray}\]

Hence $w$ in null space of $A$, it can be written as $w = Zu$ for some $u \in \mathbb{R}^{n - m}$. Therefore,

\[\begin{eqnarray} & & w^{\mathrm{T}}Gw = 0 \nonumber \\ & & u^{\mathrm{T}}Z^{\mathrm{T}} G Zu = 0 . \nonumber \end{eqnarray}\]

Since $Z^{\mathrm{T}}GZ$ is positive definite, $u = 0$. Therefore, $w = 0$. By \(\eqref{equation_16_08}\),

\[\begin{equation} Gw + A^{\mathrm{T}}v = 0 \end{equation}\]

implies $v = 0$. The equation has solution if and only if $v = 0$ and $w = 0$. Hence the KKT matrix is nonsingular.

$\Box$

Theorem 16.2

• $A$,
  • full row rank
• $Z^{\mathrm{T}}GZ$,
  • is positive definite

Then the $x^{*}$ satisfying \(\eqref{equation_16_04}\) is the unique global solution of \(\eqref{equation_16_03_a}\).

proof

Let $x$ be any point satisfing

\[Ax = b.\]

Let $p := x^{*} - x$. We have that

\[Ap = 0.\]

By substituing the objective functin,

\[\begin{eqnarray} q(x) & = & \frac{1}{2} (x^{*} - p)^{\mathrm{T}}G(x^{*} - p) + c^{\mathrm{T}}(x^{*} - p) \nonumber \\ & = & \frac{1}{2} (x^{*})^{\mathrm{T}} G x^{*} - (x^{*})^{\mathrm{T}}Gp + \frac{1}{2} p^{\mathrm{T}}Gp + c^{\mathrm{T}}(x^{*} - p) \nonumber \\ & = & q(x^{*}) - (x^{*})^{\mathrm{T}}Gp + \frac{1}{2} p^{\mathrm{T}}Gp - c^{\mathrm{T}}p . \end{eqnarray}\]

From the first oder condition \(\eqref{equation_16_04}\),

\[Gx^{*} - A^{\mathrm{T}}\lambda = -c .\]

Hence

\[\begin{eqnarray} q(x) & = & q(x^{*}) - p^{\mathrm{T}}(A^{\mathrm{T}} \lambda - c) + \frac{1}{2} p^{\mathrm{T}}Gp - c^{\mathrm{T}}p \nonumber \\ & = & q(x^{*}) - p^{\mathrm{T}}A^{\mathrm{T}} \lambda + \frac{1}{2} p^{\mathrm{T}}Gp \nonumber \\ & = & q(x^{*}) + \frac{1}{2} p^{\mathrm{T}}Gp \nonumber \end{eqnarray}\]

Since $p \in \mathrm{null}A$, we can write $p = Zu$ for some $u \in \mathbb{R}^{n - m}$. Thus,

\[q(x) = q(x^{*}) + \frac{1}{2} u^{\mathrm{T}}Z^{\mathrm{T}}GZu .\]

By positive definiteness of $Z^{\mathrm{T}}GZ$,

\[q(x) - q(x^{*}) = u^{\mathrm{T}}Z^{\mathrm{T}}GZu \ge 0 .\]

The equality holds if and only if $x = x^{*}$.

$\Box$

Theorem 16.3

• $K$
• $A \in \mathbb{R}^{m \times n}$,
  • rank $m$

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

\[\begin{eqnarray} w = \end{eqnarray}\]

$\Box$

Schur-complement method

• $G$,
  • positive definite

First of all, from \(\eqref{equation_16_05_kkt_matrix}\),

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

The Schur-complement algorithm is described as follows;

• Step1. Solve \(\eqref{equation_16_13}\) with respect to $\lambda^{*}$.
• Step2. Solve \(\eqref{equation_16_14}\) with respect to $p$.
  • From the equation \(\eqref{equation_16_05_kkt_matrix}\), we have

\[\begin{eqnarray} Gp = A^{\mathrm{T}}\lambda^{*} - g \label{equation_16_14} . \end{eqnarray}\]

The Schur-complement algorithm is useful when

• $G$ is well conditioned
• $G^{-1}$ is known explicitly thorugh a quasi-Newton updating formula
• The number of equality constraints $m$ is small

\[\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)^{-1} \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 methods

• Null space methods does not require non-singularity of $G$.
• Lemma 16.1 must hold

Suppose that $p_{Y}$ and $p_{Z}$ satify

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

where

• $Z \in \mathbb{R}^{n - m}$ null-space matrix of $A$,
• $Y \in \mathbb{R}^{n \times m}$ matrix such that $[ Y \mid Z ]$ is nonsingular.
• $p_{Y} \in \mathbb{R}^{m}$,
• $p_{Y} \in \mathbb{R}^{n-m}$,

By substituting \(\eqref{equation_16_17}\) into \(\eqref{equation_16_05_kkt_matrix}\), we obtain

\[\begin{eqnarray} & & -Ap = h \nonumber \\ & \Leftrightarrow & AYp_{Y} + AZp_{Z} = -h \nonumber \\ & \Leftrightarrow & AYp_{Y} = -h \nonumber \\ & \Leftrightarrow & p_{Y} = -(AY)^{-1})h . \label{equation_16_18} \end{eqnarray}\]

To obtain $p_{Z}$,

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

By multiplying the first row in \(\eqref{equation_16_05_kkt_matrix}\) by $Y$,

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

The null space methods is as follows

• Step1. Determine $Z$ for given $A$,
• Step2. Determine $Y$ from $Z$
• Step3. Solve \(\eqref{equation_16_18}\) w.r.t. $p_{Y}$,
• Step4. Solve \(\eqref{equation_16_19}\) w.r.t. $p_{Z}$,
  • The equation can be solved by Cholesky factorization
• Step5. Solve \(\eqref{equation_16_19}\) w.r.t. $p_{Z}$,