Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / B / 6 / iii / Solution

Stationarity of the equality-constrained quadratic subproblem gives $B_k{s}_k+g_k-A_k^T{y}_{k+1}=0$. Together with feasibility, this isMultiplying the bottom block row by $-1$ gives a symmetric indefinite saddle-point matrix, with right side $(-g_k,c_k{)}^T$.

One solution strategy uses the Schur complement. From $s_k=B_k^{-1}(A_k^T{y}_{k+1}-g_k)$ obtainThis is an $m\times m$ positive-definite system when $A_k$ has full row rank; factor $B_k$ and solve with it rather than forming its inverse.

A second strategy uses a nullspace basis $Z$ for $\ker A_k$. Choose one particular $s_p$ with $A_k{s}_p=-c_k$, write $s_k=s_p+Zz$, and solve the reduced systemThe reduced Hessian is positive definite. These range-space and nullspace reductions exploit different relative sizes of $m$ and $n-m$.