Past exam of the continuous optimisation course of the University of Oxford / 2025 / 3 / d

Choose a strictly feasible point, an initial barrier parameter ${\mu }_0>0$, and $0<\theta <1$. At outer iteration $k$, approximately minimize the logarithmic barrier objective $f_{{\mu }_k}$ over its strictly feasible domain of a function. For example, use damped Newton methods, choosing an inner step size by backtracking line search so that every $c_i$ stays positive and the barrier objective function decreases. Solve to a tolerance $\Vert \nabla f_{{\mu }_k}(x^k)\Vert \le {\epsilon }_k$, where ${\epsilon }_k\to 0$. Set ${\mu }_{k+1}=\theta {\mu }_k$ and use $x^k$ as the next starting point.

The associated Lagrange multiplier estimates areReducing ${\mu }_k$ makes these perturbed complementary slackness equations approach the KKT conditions. This describes the generic interior-point method; existence of a solution to every inner minimization needs appropriate additional attainment assumptions and does not follow from strict feasibility alone.

A precise conditional convergence statement is: with the smoothness and convexity assumptions of the question, a strict feasible point, ${\mu }_k\downarrow 0$, and barrier stationarity residualsevery convergent sequence of strictly feasible points $x^k\to x_{\ast }$ has a global minimizer as its limit. The Lagrange multiplier estimates are bounded and have a subsequence converging to multipliers satisfying the KKT conditions. The theorem does not assert convergence of the primal sequence without further assumptions.

First, continuity gives $c_i(x_{\ast })\ge 0$. For an inactive optimization constraint, $c_i(x_{\ast })>0$, soFor the active constraints, the hint permits assuming ${\lambda }_i^k\to {\lambda }_i^{\ast }$. Combining this with the inactive limits gives ${\lambda }_{\ast }\ge 0$, and passage to the limit in the residual equation proves stationarity. Since ${\lambda }_i^k{c}_i(x^k)={\mu }_k\to 0$, complementary slackness also holds. All KKT conditions follow, and part (b) proves global optimality.

The hint's multiplier assumption can in fact be weakened to selecting a subsequence. To see why the estimates are bounded, choose a strict feasible point $z$ and put $\delta ={\min }_i{c}_i(z)>0$. Concavity givesThe right side is bounded because $x^k\to x_{\ast }$ and $r_k\to 0$. This is the bounded barrier multipliers under Slater's condition argument. A convergent multiplier subsequence then gives the same KKT point, which suffices to prove that the assumed primal limit is globally optimal.

For an active constraint with ${\lambda }_i^{\ast }>0$, the perturbed complementary slackness equation gives $c_i(x^k)\sim {\mu }_k/{\lambda }_i^{\ast }$. The Hessian matrix from part (c) therefore includesIf $\nabla c_i(x_{\ast })\ne 0$, curvature normal to that boundary grows like $1/{\mu }_k$. By contrast, a direction tangent to every active constraint annihilates these large normal outer products at the limiting point, and its curvature may remain of order one. A large spread of eigenvalues then makes the Newton linear system poorly conditioned. Under bounded remaining curvature and a positive bounded tangential curvature, the condition number typically grows like $1/{\mu }_k$; this is the usual ill-conditioning of a logarithmic barrier.

It is not a universal rate: there may be no nonzero common tangent direction, some limiting Lagrange multipliers may vanish, or all curvatures may grow together. The Hessian formula identifies the source of the difficulty without assuming these extra nondegeneracy conditions.