Continuous optimisation course of the University of Oxford (C6.2, C12.1b)

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.

Original solutions to the paper released at the source request. The complete editable transcription is retained in the private examination archive.

Use $F$ for the maximized objective function, and adopt optimization constraints $g_i\ge 0$ withThe feasible set is nonempty, since it contains $(0,0)$. It is closed as an intersection of inverse images of closed sets under continuous functions. It lies in the disk of radius $\sqrt{20}$, so is bounded and therefore compact by the Heine-Borel theorem. The objective function is a polynomial, hence continuous. The extreme value theorem now guarantees a global maximizer exists.

All three active constraints force $x_1=2$ and $x_2=4$, which also satisfy $x_1^2+x_2^2=20$. For maximization use $\mathcal{L}=F+{\lambda }^{T}g$, $\lambda \ge 0$. At $x^{\ast }=(2,4)$,Stationarity gives the complete familyIn particular $({\lambda }_1,{\lambda }_2,{\lambda }_3)=(2,3/2,2)$ is strictly positive. Three gradients in two dimensions cannot be linearly independent, so the linear independence constraint qualification fails. But $d=(-1,-1)$ gives $\nabla g_i\cdot d=(1,12,3)>0$, so the Mangasarian–Fromovitz constraint qualification holds.

For a nonzero linearized feasible direction $d$, each $\nabla g_i\cdot d\ge 0$, andThe inequality is strict because equality would require all three inner products to vanish, and the first and third gradients already span ${\mathbb{R}}^2$. This proves a strict local maximum: otherwise a sequence of nearby feasible points with no smaller objective would, after normalizing their differences from $x^{\ast }$ and taking a convergent subsequence, give a unit linearized feasible direction with nonnegative objective derivative, contradicting the displayed inequality. Thus

Write $x_1=t$, $x_2=t^2$. The two inactive constraints are strict exactly for $-2<t<2$. Complementary slackness gives ${\lambda }_1={\lambda }_2=0$. The KKT conditions reduce toIf $t=0$ these give ${\lambda }_3=0$. Otherwise ${\lambda }_3=2t$ and $t=-3/2$, which gives a negative multiplier and is inadmissible. Thereforeis the only KKT point with this active set. Its active gradient $(0,1)$ is nonzero, so the linear independence constraint qualification, and hence the Mangasarian–Fromovitz constraint qualification, holds.

It is not a local maximizer: $(0,\epsilon )$ is feasible for small $\epsilon >0$ and has objective ${\epsilon }^2>0=F(0,0)$. The feasible boundary path $(t,t^2)$ for small negative $t$ has objective $2t^3+t^4<0$, so it is not a local minimizer either.

Convert to minimization with $f=-F$ and retain $g\ge 0$. A continuously differentiable inequality augmented Lagrangian method uses the merit functionFor $g_i\le \mu {\lambda }_i$ its contribution is $-{\lambda }_i{g}_i+g_i^2/(2\mu )$; otherwise it is the constant $-\mu {\lambda }_i^2/2$. This shifted truncation permits multipliers to decrease as well as increase while remaining nonnegative.

A useful initial estimate comes from the preceding pure quadratic penalty method at ${\mu }_{-1}$:Here $g(-1,-1)=(3,18,-2)$, so with ${\mu }_{-1}=2$ chooseThen use this estimate and ${\mu }_0=1$ in the first augmented subproblem. Initial estimates are a choice, rather than uniquely specified data; zero multipliers would also define an initialization.

For the convention above, after approximately minimizing $\Phi (\cdot ,{\lambda }^{[k]},{\mu }_k)$, updateThe exact shifted-residual identity isIf the constraint is violated, $g_i(x^{[k+1]})\le 0$, its left side is $\min \{g_i,0\}$, and replacing the new multiplier by its limiting value gives the printed local estimateFor arbitrary iterates, the precise unshifted statement includes the negative part:Thus the printed estimate describes approach from the violated side; it is not a universal signed equality on the feasible side. This qualification follows directly from the projection in the update.

Its numerical significance is that the constraint violation is controlled by ${\mu }_k$ times the multiplier error, rather than by ${\mu }_k$ alone. Once multipliers are accurate, high feasibility accuracy can be obtained with a moderate positive penalty parameter. This avoids forcing $1/{\mu }_k$ to become enormous and reduces the ill-conditioning of the inner minimization. Inactive constraints eventually have zero multiplier and zero violation.

Assume the denominators are defined, so $c,d\ne 0$. For a descent direction $p$, set $\phi (\alpha )=f(x+\alpha p)$. The Wolfe conditions areThe first is sufficient decrease and the second is the curvature condition. Hereis positive definite, with eigenvalues $2/c^2,2/d^2$. The exact step isIt gives ${\phi }^{\prime }({\alpha }_{\ast })=0$, so the curvature condition holds. Its decrease is $\phi ({\alpha }_{\ast })-\phi (0)={\alpha }_{\ast }{\phi }^{\prime }(0)/2$, so sufficient decrease holds for the usual choice $0<\sigma \le 1/2$, $\sigma <\eta <1$. Hence exact searches satisfy Wolfe with an Armijo constant at most one half. If one allowed $\sigma >1/2$, even an exact quadratic minimizer would fail that condition; the parameter range matters.

A standard form of the Zoutendijk theorem assumes that $f$ is continuously differentiable and bounded below on the starting level set, that its gradient is Lipschitz on a neighborhood of that set, and that the steps satisfy fixed Wolfe conditions. For descent directions $p_k$, defineThenIn particular, if $\cos {\theta }_k\ge \delta >0$, then $\nabla f(x_k)\to 0$. This last angle hypothesis is needed to turn the general descent theorem into gradient convergence.

For this quadratic, $f\ge 0$, the Hessian matrix is the constant positive-definite matrix $H$, and the gradient is globally Lipschitz with constant $L=2\max (c^{-2},d^{-2})$. Its level sets are compact. Thus all objective-function hypotheses hold; Wolfe holds for the exact steps with the parameters above. The direction hypothesis will be verified for alternating exact coordinate minimization in the next part.

Use the exact line searches from part (i). After minimizing along one coordinate, the corresponding gradient component is zero. Unless the optimum has been reached, the whole nonzero gradient therefore lies along the other coordinate, which is selected next. The chosen signed coordinate direction then has $\cos {\theta }_k=1$. A selected zero gradient component can be skipped; it already minimizes that coordinate.

The Zoutendijk theorem therefore gives $\nabla f(x_k)\to 0$. The unique point with zero gradient isSince $\nabla f(x)=H(x-x^{\ast })$ and $H$ is invertible, gradient convergence implies $x_k\to x^{\ast }$. Positive definiteness makes this the unique global minimum.

Convergence also holds if “line search” is interpreted as any fixed-parameter Wolfe search. If coordinate $i$ is selected, its signed step $s$ satisfies $s=-\omega g_i/h$, where $h=c^{-2}+d^{-2}$ and $1-\eta \le \omega \le 2(1-\sigma )$. Sufficient decrease gives $f(x_k)-f(x_{k+1})\ge \sigma (1-\eta )g_i(x_k{)}^2/h$. Summation shows that selected gradient components tend to zero and step lengths tend to zero. The other component was selected in the preceding step; Lipschitz continuity then makes it tend to zero as well. Thus the full gradient converges to zero. The simple one-step angle argument and sharp Q-linear factor below use exact coordinate minimization; arbitrary Wolfe choices need not have that same Euclidean one-step factor.

A sequence is Q-linearly convergent to $x^{\ast }$ in a specified norm if $\Vert x_{k+1}-x^{\ast }\Vert \le q\Vert x_k-x^{\ast }\Vert$ for all sufficiently large $k$, with some $q<1$. Its asymptotic factor is the limsup of consecutive error ratios.

Put $h=c^{-2}+d^{-2}$, $b_0=c^{-2}-d^{-2}$ and $t=b_0/h$. For an error $e=x-x^{\ast }$, an exact first-coordinate step sets $e_1=-t{e}_2$, and an exact second-coordinate step sets $e_2=-t{e}_1$. Once the first coordinate step has occurred, errors consequently alternate between the two linesThe next error has its free coordinate multiplied in magnitude by $|t|$, and both lines have the same Euclidean norm factor $\sqrt{1+t^2}$. Therefore, until finite termination,This is a sharp bound, attained after the first step; the objective errors have factor $t^2$ per step. If $c^2=d^2$, the problem separates and at most two exact steps suffice. When the condition number is large, the factor approaches one: the iterates zigzag slowly across a narrow tilted valley.

Take the usual symmetric meaning of positive definite $Q$. To include all data allowed by the source, first check feasibility. PutFull row rank makes $B$ positive definite. Every $x$ satisfying $Ax=b$ is uniquely $x_0+z$ with $Az=0$, and $z^{T}Q{x}_0=0$. ThusIf ${\rho }^2>1$, there is no feasible point. If ${\rho }^2=1$, the only feasible point is $x_0$, and $x_0$ is optimal for every $c$. If ${\rho }^2<1$, the Slater condition holds, and the following KKT conditions are necessary and sufficient:Necessity follows from the constraint qualification proved in (ii). Sufficiency follows from convexity: the stationary optimization Lagrangian $c^{T}x+y^T(b-Ax)+\gamma (x^{T}Qx-1)$ is minimized at $x$, while its feasible values never exceed the objective, and complementary slackness makes its value at $x$ equal the objective.

The singleton case cannot be silently covered by ordinary KKT necessity. For example, let $Q=I$, $A=(10)$, $b=1$, $c=(0,1{)}^T$. The sole feasible point $(1,0)$ is optimal, but stationarity would require $(0,1)$ to lie in the span of $(1,0)$, which is impossible. The feasibility split above supplies genuinely necessary and sufficient conditions without assuming an unprinted regularity hypothesis.

The equality gradients are independent everywhere. At an interior point of the ellipsoid, there is no active inequality, so the Mangasarian–Fromovitz constraint qualification holds. At a boundary point $x=x_0+z$, a qualifying direction must satisfy $Av=0$ and $2x^{T}Qv<0$.

If ${\rho }^2<1$, choose $v=x_0-x=-z$. At a boundary point $z^{T}Qz=1-{\rho }^2>0$, andThus the qualification holds at every feasible point. If ${\rho }^2=1$, the only feasible point is $x_0$; for every $v\in \ker A$, $x_0^{T}Qv=0$, so no strict direction exists. This provesThe equivalence also identifies this case with strict feasibility of the inequality on the affine equality space.