Past exam of the continuous optimisation course of the University of Oxford / 2011 (C12.1b, DMAC 2B88, DMSU 2B88)

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.

For $y\in {\mathbb{R}}^m$ and $\gamma \ge 0$, define the optimization LagrangianThe Lagrangian primal isFor feasible $x$, the supremum is $c^{T}x$: equality terms vanish and the nonpositive inequality term has maximum zero at $\gamma =0$. If $Ax\ne b$, scale $y$ in the direction $b-Ax$ to make the supremum infinite. If the inequality fails, send $\gamma \to \infty$. Thus the inner supremum is exactly the objective extended to $+\infty$ off the feasible set. This proves equivalence with the original problem, including its infeasible case.

Reverse the order of the two optimizations to obtain the Lagrangian dualPut $s=c-A^{T}y$ and $r=\sqrt{s^T{Q}^{-1}s}$. For $\gamma >0$, completing the square givesAt $\gamma =0$ the infimum is finite precisely if $s=0$, when it equals $b^{T}y$. For $r>0$, the expression $\gamma +r^2/(4\gamma )$ is minimized at $\gamma =r/2$, with value $r$. The same optimized value holds when $r=0$, choosing $\gamma =0$. Eliminating $\gamma$ therefore gives ${\sup }_y\{b^{T}y-\sqrt{s^T{Q}^{-1}s}\}$. Introducing $\theta =r$ yieldsThe nonnegative square root is enforced by $\theta \ge 0$. Optimizers correspond by $\gamma =\theta /2$, including the zero case.

For fixed $y$, $s=c-A^{T}y$ is fixed. The relaxed inequality and $\theta \ge 0$ say preciselyThe objective $b^{T}y-\theta$ strictly decreases with $\theta$, so its best choice is always equality. Replacing any feasible relaxed point by that choice preserves feasibility and improves or leaves unchanged the objective. Conversely every point satisfying equality is feasible for the relaxed problem. Thus the two dual formulations have the same optimal value and the same optimal $y,s$, with equality at any optimizer.

This algebraic equivalence in fact does not require Slater's condition. Under the stipulated condition, strong duality additionally identifies their attained optimum with the primal optimum. With $Q^{-1/2}s$ as a linear coordinate, the relaxed constraint is $\Vert Q^{-1/2}s{\Vert }_2\le \theta$, so the relaxed formulation is a second-order cone program.