Continuous optimisation course of the University of Oxford (C6.2)

Source: released examination PDF, pages 4–7. Solutions follow the numbering of the 10 June 2025 paper.

Fix an iteration and abbreviate $x=x^k$, $s=s^k$, $d=\nabla f(x{)}^{T}s$. Since $s$ is a descent direction, $d<0$. The directional derivative givesChoose $\bar{\alpha }>0$ so that $|o(\alpha )|\le \frac{1}{2}(1-{\beta }_1)(-d)\alpha$ for $0<\alpha \le \bar{\alpha }$. ThenThis is the Armijo condition for every such positive step size, and $\alpha =0$ gives equality. In particular, a backtracking line search terminates after finitely many reductions.

Write $\varphi (\alpha )=f(x+\alpha s)$ and $h(\alpha )=\varphi (\alpha )-\varphi (0)-{\beta }_1\alpha d$. Part (a) gives $h(\alpha )<0$ just to the right of zero. If $L$ is a lower bound for $f$, thenbecause $d<0$. By continuity, there is a first positive zero $A$ of $h$, and $h(\alpha )\le 0$ on $[0,A]$. Apply the mean value theorem to $\varphi$ on this interval: for some $t\in (0,A)$,At this same $t$, $h(t)\le 0$ supplies the Armijo condition. Thus $\alpha =t>0$ satisfies both weak Wolfe conditions. The boundedness assumption prevents the objective function from following its initial negative slope forever; this is the mechanism behind Existence of a Wolfe step.

If $g=\nabla f(x)\ne 0$, the positive-definite symmetric matrix $B$ is an invertible matrix and $s=-B^{-1}g\ne 0$. Multiplying $Bs=-g$ by $s^T$ givesHence $s$ is a descent direction. If $g=0$, then $s=0$ and the algorithm has already reached a stationary point; the strict descent assertion applies before termination.

Set $p=x^{k+1}-x^k={\alpha }^k{s}^k$ and $y=\nabla f(x^{k+1})-\nabla f(x^k)$. The Quasi-Newton secant equation is $B^{k+1}p=y$. If $B^{k+1}$ is a positive-definite symmetric matrix and $p\ne 0$, it follows thatThe weak curvature part of the Wolfe conditions ensures precisely this necessary condition:The last product is positive because ${\alpha }^k>0$, ${\beta }_2-1<0$, and $s^k$ is a descent direction. This explains why a Quasi-Newton method often uses the Wolfe conditions rather than only the Armijo condition.

Interpret boundedness above uniformly: there is an $M<\infty$ such that $B^k⪯MI$ for every $k$. Since $B^k$ is a positive-definite symmetric matrix, the spectral theorem implies $(B^k{)}^{-1}⪰M^{-1}I$. ThereforeCombining the Armijo condition with ${\alpha }^k\ge C>0$ yieldsIf $f\ge L$, a telescoping sum givesThe nonnegative series converges, so its terms tend to zero:This proves first-order global convergence in the sense of stationarity from uniformly bounded quasi-Newton matrices. It does not imply that every nonconvex objective function reaches a global minimum, or that the iterates themselves converge. Every finite limit point is a stationary point, by continuity of the gradient.

The Cauchy point minimizes the model along the negative gradient ray inside the trust region. With $q=g^{T}Hg$, writeIf $q\le 0$, this last quadratic function decreases throughout the interval. If $q>0$, its unconstrained minimum occurs at $t=\Vert g{\Vert }^2/q$. ThusThe additive constant $a$ has no effect on the Cauchy point. To obtain the Cauchy decrease bound, first suppose $q>0$. Since $\tau q\le \Vert g{\Vert }^2$,The spectral norm inequality $q\le \Vert H\Vert \Vert g{\Vert }^2$ gives $\tau \ge \min \{\Delta /\Vert g\Vert ,1/\Vert H\Vert \}$. HenceIf $q\le 0$, the decrease is at least $\Delta \Vert g\Vert$, which also implies the displayed bound. When $H=0$, interpret $\Vert g\Vert /\Vert H\Vert =+\infty$. Thus the universal choice is $c=1/2$.

At $x^k$, choose $a=f(x^k)$, $g=\nabla f(x^k)$, $H={\nabla }^{2}f(x^k)$, and the current radius $\Delta ={\Delta }_k>0$. A bounded symmetric matrix approximation to the Hessian matrix can also be used. Stop if the gradient is sufficiently small; otherwise approximately solve the trust-region subproblem to obtain $s_k$ with $\Vert s_k\Vert \le {\Delta }_k$ and at least a fixed Fraction of Cauchy decrease. Its predicted decrease is then positive, so calculate the trust-region acceptance ratioFix $0<{\eta }_1<{\eta }_2<1$, $0<{\gamma }_d<1<{\gamma }_u$, and a maximum radius ${\Delta }_{\max }$. One valid update is:

The trust region controls the reliability of the model; the ratio decides whether that reliability was borne out by the actual objective function.

The Cauchy point provides both an inexpensive fallback step and a standard against which a better step can be judged. Requiring a fixed Fraction of Cauchy decrease givesConsequently an exact global minimum of each trust-region subproblem is unnecessary. A step from any inner solver is adequate if it meets this bound.

The convergence argument combines this decrease with model accuracy. For example, suppose the gradient is uniformly Lipschitz continuous on a neighborhood of the visited level set, the model Hessian matrices are uniformly bounded, and the usual acceptance and radius safeguards are used. If $\Vert \nabla f(x^k)\Vert \ge ϵ>0$, the Taylor expansion gives a model error bounded by $K\Vert s_k{\Vert }^2$. For sufficiently small ${\Delta }_k$, division by the Cauchy decrease bound makes $|1-{\rho }_k|$ small. Such trials are successful and cannot keep shrinking the radius. With the gradient bounded away from zero, the radius therefore has a positive lower bound, and each accepted step decreases $f$ by a fixed positive amount. There must be infinitely many accepted steps, since repeated rejection would force the radius below the small-radius acceptance threshold. This contradicts boundedness below of $f$ and proves ${\mathrm{liminf}}_k\Vert \nabla f(x^k)\Vert =0$.

Stronger standard conclusions can be obtained with further regularity and safeguards. Merely being twice continuously differentiable and bounded below does not supply uniform Hessian bounds on an unbounded level set; those uniform assumptions must be stated when using this argument.

Taking the natural logarithm of the positive product constraint gives $h(x)={\sum }_i{a}_i\log x_i=0$. Its gradient has entries $a_i/x_i>0$, so the equality constraint qualification holds everywhere on the feasible set. Use the optimization LagrangianStationarity requires $a_i-\lambda a_i/x_i=0$, so every $x_i=\lambda$. Substitution into the constraint, using ${\sum }_i{a}_i=1$, gives $\lambda =1$. Thus the only candidate for a local minimum is $x=(1,\dots ,1)$.

To prove global minimality without assuming the inequality to be established, set $u_i=\log x_i$. The constraint becomes the affine hyperplane ${\sum }_i{a}_i{u}_i=0$, and the objective function becomes $F(u)={\sum }_i{a}_i{e}^{u_i}$. Its Hessian matrix $\mathrm{diag}(a_i{e}^{u_i})$ is positive-definite, so $F$ is strictly convex. The elementary tangent inequality $e^t\ge 1+t$, with equality only at zero, givesEquality forces every $u_i=0$. ThereforeThis point is the unique global minimizer and the only local minimizer. The logarithm change of variables also explains why a multiplicative constraint leads to a convex optimization argument.

Let $G={\prod }_i{y}_i^{a_i}>0$ be the weighted geometric mean and set $x_i=y_i/G$. Since the weights sum to one,Part (i) implies ${\sum }_i{a}_i{y}_i/G\ge 1$, proving the weighted arithmetic-geometric mean inequality:Equality holds exactly when $x_i=1$ for every $i$, or equivalently when all the $y_i$ are equal.

If $x,y$ are feasible points and $0\le t\le 1$, concavity givesfor every $i$. Thus the feasible set is a convex set. Since the objective function is convex, this is a convex optimization problem.

With inequalities written as $c_i\ge 0$, use the optimization Lagrangian $L(x,\lambda )=f(x)-{\sum }_i{\lambda }_i{c}_i(x)$. The Karush-Kuhn-Tucker conditions at $(x_{\ast },{\lambda }_{\ast })$ areFor any feasible point $z$, the first-order inequalities for a convex function and a concave function giveThe last equality uses complementary slackness. Thus $x_{\ast }$ is a global minimizer. Slater's condition is useful for necessity and existence of Lagrange multipliers, but is not required for this sufficiency argument once a KKT point is supplied.

For $\mu >0$, the logarithmic barrier objective isThe domain of a function $D$ is a nonempty convex set by the same concavity argument as in part (a), with strict inequalities. Differentiating twice on $D$ givesHere ${\nabla }^{2}f⪰0$ by convexity, $-{\nabla }^2{c}_i⪰0$ by concavity, and each outer product is a positive semidefinite matrix. Hence ${\nabla }^2{f}_{\mu }⪰0$, proving convexity on $D$.

The domain qualification matters: the displayed real-valued logarithm expression is not defined on all of ${\mathbb{R}}^n$. The precise whole-space version is the extended-real convex function equal to $f_{\mu }$ on $D$ and $+\infty$ outside $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.