Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2010 / B / 5

Use the optimization Lagrangian $\mathcal{L}(x,y)=f(x)-y^{T}c(x)$, with $A(x)=Dc(x)$ and $H(x,y)={\nabla }_{xx}^2\mathcal{L}(x,y)$. Under the usual linear independence constraint qualification, a local minimizer has multipliers $y_{\ast }$ satisfying the equality-constrained Karush-Kuhn-Tucker conditionsThe second-order necessary condition isOnly feasible tangent directions enter this last test; the Hessian matrix need not be positive semidefinite on the entire ambient space.

With $y=-c/\mu$, differentiation of the quadratic penalty method objective givesThe primal Newton system is thereforeFor bounded multipliers and regular derivatives, $H$ remains of ordinary size while ${\mu }^{-1}{A}^{T}A$ becomes large in directions normal to the constraints. If the feasible tangent space is nontrivial and retains ordinary-size curvature, this produces a large condition number as $\mu \downarrow 0$.

Introduce $w=Ap/\mu$. The same step is obtained from the symmetric augmented systemEliminating $w$ recovers the primal system exactly. This matrix contains no explicit ${\mu }^{-1}$ entries and tends to a saddle-point matrix. Under full row rank of the limiting constraint Jacobian matrix and nonsingularity of the limiting reduced Hessian, that limiting matrix is nonsingular, so this formulation avoids the artificial penalty-induced separation of scales.

These conditioning statements require regularity beyond bounded $y$ alone. A rank-deficient constraint Jacobian matrix or singular reduced Hessian can still make the augmented system ill-conditioned. If $m=n$ and $A$ is nonsingular, all directions may scale together in the primal system, so a large condition number is not automatic there either.

Complete the square in the augmented Lagrangian method objective:For fixed $u,\mu$, the last term is constant in $x$. Thus its minimization is the quadratic penalty method applied to the shifted constraint $c(x)=\mu u$.

Its practical advantage is that multiplier updates, typically $u^{+}=u-c(x)/\mu$, can drive the original constraint residual to zero while $\mu$ stays moderately sized. The plain quadratic penalty method generally needs $\mu$ very small to produce the same feasibility accuracy, exposing the conditioning problem in part (ii).

The linearized constraints may be inconsistent, for example when $-c(x_k)$ is not in the image of a linear map defined by $A(x_k)$. Even if feasible, the quadratic objective may have negative curvature along its feasible tangent space, making it unbounded below and leaving no local minimizer.

Fletcher's Sℓ1QP replaces the hard linearized constraints by an L1 exact penalty and bounds the step inside a trust region. One usual form isThe zero step is always admissible. The trust region is compact, so a minimum exists even when the model Hessian matrix is indefinite; the constraint penalty measures infeasibility rather than making the subproblem impossible to solve. Adjusting its weight promotes feasibility, while the radius keeps the local model within a controlled neighbourhood. Introducing nonnegative positive- and negative-part slack variables converts the absolute values to an equivalent smooth quadratic program with box constraints.^[ref]

Stationarity of the equality-constrained quadratic model gives $g_k+H_k{s}_k-A_k^T{y}_{k+1}=0$, while feasibility gives $A_k{s}_k=-c_k$. A symmetric system linking the step and new multiplier isLet $Z$ have columns forming a basis of $\ker A_k$. The saddle-point matrix is nonsingular exactly when $A_k$ has full row rank and $Z^T{H}_{k}Z$ is nonsingular. Full row rank is necessary because a nonzero vector in $\ker A_k^T$ would give a null vector of the block matrix. Under full row rank, solving a homogeneous system forces $s=Zq$ and then $Z^T{H}_{k}Zq=0$; this proves sufficiency and the converse. Positive definiteness of the reduced Hessian is sufficient for a constrained minimum but is stronger than the nonsingularity condition asked here.

A null-space method first finds $s_p$ with $A_k{s}_p=-c_k$, then solvesand recovers $y_{k+1}$ from $A_k^T{y}_{k+1}=g_k+H_k{s}_k$. It needs the stated full row rank and nonsingular reduced matrix; Cholesky decomposition is available when the latter is positive definite.

A range-space method additionally assumes $H_k$ is invertible. It solves the Schur complement equationsIf $H_k$ is positive definite and $A_k$ has full row rank, the Schur matrix is positive definite and both solves can use Cholesky decomposition. An indefinite but invertible $H_k$ instead requires a suitable indefinite factorization; the Schur matrix must remain nonsingular.