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

Use the optimization Lagrangian $L(x,y)=f(x)-y^{T}c(x)$ and let $A=Dc$ be the $m\times n$ constraint Jacobian matrix. Under the standard regularity hypothesis $\mathrm{rank}A(x_{\ast })=m$, a local constrained minimizer satisfies, for some multiplier $y_{\ast }$,The second-order necessary condition isRegularity makes each such tangent vector the velocity of a feasible smooth curve. Twice differentiating the objective along that curve and using stationarity and the differentiated constraints gives the displayed nonnegative second derivative.

The regularity hypothesis is needed for these multiplier conditions to be necessary in this form. For example minimizing $f(x)=x$ subject to $c(x)=x^2=0$ has the unique feasible minimizer zero, but $f^{\prime }(0)-y{c}^{\prime }(0)=1$ for every $y$. The question does not explicitly state the qualification, so it must be supplied when using the usual KKT conditions.

The sequential quadratic programming step minimizes a quadratic local objective model while enforcing the first-order constraint expansion $c(x_k+s)\approx c_k+A_{k}s=0$. When the iterate and multipliers are close to a regular solution and $B_k$ approximates the Lagrangian Hessian, the resulting correction approximates a Newton step for the nonlinear KKT conditions.

Full row rank of $A_k$ ensures that $A_{k}s=-c_k$ is solvable for every $c_k$ and that the multiplier of the quadratic subproblem is unique. A positive-definite $B_k$ makes the objective strictly convex and coercive on the affine feasible set, giving a unique global subproblem minimizer. In fact positivity on $\ker A_k$, rather than on every vector, is enough for uniqueness and boundedness on that set; full positive definiteness is a convenient stronger assumption.

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$.

Since $p$ is even, differentiating $c_i^p$ givesAt a stationary point define $y_i=-c_i(x{)}^{p-1}/\mu$. Then $\nabla f(x)-Dc(x{)}^{T}y=0$, precisely the stationarity equation for the optimization Lagrangian. Bounded multipliers giveThus along any subsequence of stationary points with $x_{\mu }\to x_{\ast }$, a further subsequence of bounded multipliers converges to $y_{\ast }$, and continuity yields $c(x_{\ast })=0$ and $\nabla f(x_{\ast })-Dc(x_{\ast }{)}^T{y}_{\ast }=0$. These are the equality-constrained first-order conditions. Bounded multipliers alone do not establish convergence of the primal points; the precise conclusion concerns their finite cluster points. This is the power penalty multiplier limit.

Suppress the iteration subscript. From the quadratic subproblem, $As=-c$ and $g=-Bs+A^{T}y$. ThereforeWhen $|c^{T}y|>0$, the stated bound on $\mu$ makes ${\mu }^{-1}\Vert c{\Vert }_p^p\ge |c^{T}y|$. Consequentlyusing positive definiteness of $B$. Thus every nonzero such SQP step is a descent direction for the penalty function. If $c^{T}y=0$, the quotient bound is unnecessary and the same conclusion follows for every $\mu >0$. A zero step has zero directional derivative and is not a strict descent direction; it corresponds to an already feasible stationary point. This nonzero-step qualification is implicit in the requested conclusion.