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

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.