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

For $\mathcal{L}=f-y^{T}c$, the inequality-constrained Karush-Kuhn-Tucker conditions areUnder an appropriate constraint qualification, the second-order necessary condition is $d^{T}H(x_{\ast },y_{\ast })d\ge 0$ on the critical coneEquivalently active constraints with positive multiplier require $A_{i}d=0$, while active zero-multiplier constraints retain $A_{i}d\ge 0$. Inactive constraints impose no first-order tangent restriction. This distinction is why the relevant cone need not be the nullspace of every active row.

On the strictly feasible region $c_i(x)>0$, the logarithmic barrier objective isWith $y_i(x)=\mu /c_i(x)$, its gradient isThe positive coefficients $y_i$ are the barrier's multiplier estimates.

The equation $F_{\mu }(x,y)=0$, together with $c(x)>0$ and $y>0$, is the perturbed Karush-Kuhn-Tucker conditions: stationarity is unchanged, while exact complementary slackness becomes $c_i(x)y_i=\mu$ for each $i$. A finite limit of such points as $\mu \downarrow 0$ satisfies the original conditions by continuity.

For a strictly feasible $x$, the second block uniquely specifies $y_i=\mu /c_i(x)$. Substitution into the first block gives precisely $\nabla B_{\mu }(x)=0$. Thuswithin the stated strictly positive domain. These are stationary barrier points; they need not all be local minimizers in a nonconvex problem.

The Jacobian matrix of $F_{\mu }$ in $(x,y)$ isThe top-left block is the Hessian matrix of $f-y^{T}c$ with $y$ held fixed. In the second block, differentiating $C(x)y$ in $x$ gives $YA$ and in $y$ gives $C$. The explicit derivative with respect to $\mu$ is $(0,-e{)}^T$. Differentiate $F_{\mu }(v(\mu ))=0$ by the chain rule:All blocks are evaluated on the current central path point.

At the current exact path point $v(\mu )$, stationarity is already zero and $Cy=\mu e$. Therefore $F_{\bar{\mu }}(v(\mu ))=(0,(\mu -\bar{\mu })e{)}^T$. Its Newton correction solvesThe matrix has no explicit dependence on the barrier parameter, so comparison with part (iv) giveswhen $J$ is nonsingular. If it is singular, the displayed vector is still a solution of the correction equations, but uniqueness of the correction cannot be inferred from differentiability of the path alone.

This step is exactly the tangent predictor in the stated first-order Taylor expansion. For nearby positive $\bar{\mu }$, it approximates the new path point with error $o(|\bar{\mu }-\mu |)$; a bounded second path derivative improves this to $O((\bar{\mu }-\mu {)}^2)$. Continuity also preserves strict positivity for sufficiently small parameter changes. Larger changes may require damping to keep both the constraint values and multiplier estimates positive.