Sqp active set and augmented lagrangian methods — Examples

At $x_0$, $\mathrm{\nabla }f(x_0)=0$ and the linearized inequality is $1-p_1-p_2\le 0$. The unconstrained minimizer $p=0$ is infeasible. On the active face $p_1+p_2=1$, stationarity for $q(p)=\frac{1}{2}\mathrm{\parallel }p{\mathrm{\parallel }}_2^2$ is $p-\lambda (1,1{)}^T=0$; combining with the face equation gives $p_1=p_2=\lambda =1\mathrm{/}2$. This point is feasible with nonnegative multiplier.

The positive-definite QP has a unique minimizer; its feasible KKT tuple passes the active-set acceptance filters in [F2]. By [F3] the returned step is exactly $(1\mathrm{/}2,1\mathrm{/}2)$.

The nonlinear point $x_{\ast }=(1\mathrm{/}2,1\mathrm{/}2)$ is feasible and has $\mathrm{\nabla }f(x_{\ast })=(1\mathrm{/}2,1\mathrm{/}2)$, $\mathrm{\nabla }g(x_{\ast })=(-1,-1)$, and multiplier ${\lambda }_{\ast }=1\mathrm{/}2$. Thus stationarity holds, the multiplier is nonnegative, and complementarity holds with $g(x_{\ast })=0$. Since the objective is convex and the constraint affine, [F4] proves global optimality; strict convexity of the objective makes the minimizer unique.

At $x=(c,s)$, $h(x)=0$, $Dh(x)=2(c,s)$, and $\mathrm{\nabla }f(x)=4(c,s)-(1,0)$. The unit tangent $t=(-s,c)$ satisfies $t^T\mathrm{\nabla }f(x)=s$. The QP constraint gives $p\in \mathrm{span}(t)$; minimizing $\mathrm{\nabla }f(x{)}^{T}p+\frac{1}{2}\mathrm{\parallel }p{\mathrm{\parallel }}_2^2$ on this line gives $p=-st=(s^2,-sc)$. Its QP multiplier is $-(4-c)\mathrm{/}2$, since $p+\mathrm{\nabla }f(x)=(4-c)(c,s)$.

Here $Dh(x)Dh(x{)}^T=4$, so [F3] gives $w=(-c{s}^2\mathrm{/}2,-s^3\mathrm{/}2)$ and $\mathrm{\parallel }w{\mathrm{\parallel }}_2=s^2\mathrm{/}2$. Direct substitution into the quadratic constraint yields $h(x+p+w)=\frac{s^4}{4}\mathrm{.}$ The corrected first coordinate is $c+s^2(1-c\mathrm{/}2)$, so the corrected objective change is $-s^2(1-c\mathrm{/}2)+s^4\mathrm{/}2$. Adding the penalty contribution gives ${\psi }_{\rho }(x+p+w)-{\psi }_{\rho }(x)=-s^2(1-c\mathrm{/}2)+s^4(1\mathrm{/}2+\rho \mathrm{/}4)\mathrm{.}$

Since $x^{T}p=0$ and $\mathrm{\parallel }p{\mathrm{\parallel }}_2^2=s^2$, $h(x+p)=s^2$. Also $\mathrm{\nabla }f(x{)}^{T}p=-s^2$, so [F2] gives $D_{\rho }=s^2$. The objective changes by $s^2$, while the equality violation changes from zero to $s^2$; hence the full-step merit change is $(1+\rho )s^2>0$, which fails the Armijo right side $-\sigma s^2<0$.

Divide the corrected merit change plus $\sigma D_{\rho }$ by $s^2$. With $\sigma =1\mathrm{/}4$, the result is $-1+c\mathrm{/}2+s^2(1\mathrm{/}2+\rho \mathrm{/}4)+1\mathrm{/}4$, which tends to $-1\mathrm{/}4$ as $\theta \to 0$. It is therefore negative for all sufficiently small nonzero $\theta$, proving the SOC Armijo test passes. The explicit $O(s^2)$ correction norm and $O(s^4)$ residual satisfy the quadratic-size and cubic-residual bounds of [F4].

Substitution into [F1] gives ${\mathcal{L}}_{\rho }^E(x,y;\nu )=\frac{1}{2}{x}^2+\frac{1}{2}(1+\rho )y^2+\nu y\mathrm{.}$ Its Hessian is diagonal with eigenvalues $1$ and $1+\rho$, so the Euclidean spectral condition number is $1+\rho$.

The gradient equations are $x=0$ and $(1+\rho )y+\nu =0$; the unique inner minimizer is $(0,-\nu \mathrm{/}(1+\rho ))$. Its constraint value is $-\nu \mathrm{/}(1+\rho )$, so [F1] gives ${\nu }^{+}=\nu -\rho \nu \mathrm{/}(1+\rho )=\nu \mathrm{/}(1+\rho )$. Its absolute contraction factor is $1\mathrm{/}(1+\rho )$, which decreases as $\rho$ increases while the condition number in step 1.1 increases.