Past exam of the continuous optimisation course of the University of Oxford / 2011 / 1

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.