Augmented-Lagrangian multipliers converge locally with summable inner residuals

Write $A=A_{\ast }$, $H=H_{\ast }$ and $r=\dim c$. Strict complementarity and continuity give a neighborhood in which every active inequality satisfies ${\lambda }_i+\rho g_i(x)>0$ and every inactive inequality, whose multiplier is initialized at zero, satisfies ${\lambda }_j+\rho g_j(x)<0$. On this branch, [F2] reduces the $x$-dependent augmented Lagrangian to ${\mathrm{\Phi }}_{\rho }(x,\mu )=f(x)+{\mu }^{T}c(x)+\frac{\rho }{2}\mathrm{\parallel }c(x){\mathrm{\parallel }}_2^2,$ where $\mu =(\nu ,{\lambda }_I)$. Its gradient vanishes at $(x_{\ast },{\mu }_{\ast })$.

The $x$-Hessian at the base point is $W_{\rho }=H+\rho A^{T}A$. If $r=0$, the assumed condition says $H\succ 0$. For $r>0$, choose orthonormal matrices $Z,Y$ spanning $\ker A$ and its orthogonal complement, respectively; then $C_0=AY$ is invertible. In this basis the tangent block is $H_T=Z^{T}HZ\succ 0$ when its dimension is positive, the cross blocks are those of $H$, and the normal block is $Y^{T}HY+\rho C_0^T{C}_0$. Its Schur complement over the tangent block is $D+\rho C_0^T{C}_0$, where $D=Y^{T}HY-Y^{T}HZ{H}_T^{-1}{Z}^{T}HY$; if the tangent block is empty, take $D=Y^{T}HY$. Since $C_0^T{C}_0\succ 0$, this Schur complement is positive definite for sufficiently large $\rho$. Hence $W_{\rho }\succ 0$.

If $r>0$, apply [F3] to $G(x,\mu )={\mathrm{\nabla }}_x{\mathrm{\Phi }}_{\rho }(x,\mu )=0$. Its $x$ derivative is $W_{\rho }$, which is invertible by step 1.2, and its $\mu$ derivative is $A^T$. Therefore there is a local $C^1$ branch $x(\mu )$ with $x({\mu }_{\ast })=x_{\ast }$ and $Dx({\mu }_{\ast })=-W_{\rho }^{-1}{A}^T\mathrm{.}$ If $r=0$, the empty-multiplier branch consists of the local minimizer $x_{\ast }$. By continuity of the Hessian, after shrinking to a convex neighborhood ${\mathrm{\Phi }}_{\rho }(\cdot ,\mu )$ is uniformly strongly convex there; its stationary branch point is its unique local minimizer.

For $r>0$, the exact multiplier map is $T(\mu )=\mu +\rho c(x(\mu ))$, so $DT({\mu }_{\ast })=I-\rho A{W}_{\rho }^{-1}{A}^T\mathrm{.}$ In the orthonormal coordinates of step 1.2, block elimination gives $A{W}_{\rho }^{-1}{A}^T=C_0(D+\rho C_0^T{C}_0{)}^{-1}{C}_0^T$ $=(\rho I+E{)}^{-1}$, where $E=C_0^{-T}D{C}_0^{-1}$ is symmetric. Thus $DT({\mu }_{\ast })=E(\rho I+E{)}^{-1}$. Its eigenvalues are $e_i\mathrm{/}(\rho +e_i)$, which have absolute value less than $1$ for all sufficiently large $\rho$. Continuity of $DT$ then gives a closed multiplier ball on which $T$ is a contraction with some factor $q<1$. For $r=0$ the multiplier update is absent.

Let ${\widehat{x}}_k$ be an inner point in the selected branch with residual at most ${ϵ}_k$, and let $x({\mu }_k)$ be the exact branch minimizer. Strong convexity with constant $\alpha$ gives $\alpha \mathrm{\parallel }{\widehat{x}}_k-x({\mu }_k){\mathrm{\parallel }}_2^2\le ⟨\mathrm{\nabla }{\mathrm{\Phi }}_{\rho }({\widehat{x}}_k,{\mu }_k)-\mathrm{\nabla }{\mathrm{\Phi }}_{\rho }(x({\mu }_k),{\mu }_k),{\widehat{x}}_k-x({\mu }_k)⟩\le {ϵ}_k\mathrm{\parallel }{\widehat{x}}_k-x({\mu }_k){\mathrm{\parallel }}_2\mathrm{.}$ After cancellation (with the zero-distance case immediate), $\mathrm{\parallel }{\widehat{x}}_k-x({\mu }_k){\mathrm{\parallel }}_2\le {ϵ}_k\mathrm{/}\alpha$. The multiplier update is on the same PHR branch, so its difference from $T({\mu }_k)$ has norm at most $\rho L_c{ϵ}_k\mathrm{/}\alpha =C{ϵ}_k$. Hence $\mathrm{\parallel }{\mu }_{k+1}-{\mu }_{\ast }{\mathrm{\parallel }}_2\le q\mathrm{\parallel }{\mu }_k-{\mu }_{\ast }{\mathrm{\parallel }}_2+C{ϵ}_k\mathrm{.}$ The stated sum bound keeps this recurrence inside the multiplier ball and keeps every inner point within the primal branch tube.

Iterating the inequality gives $\mathrm{\parallel }{\mu }_k-{\mu }_{\ast }{\mathrm{\parallel }}_2\le q^k\mathrm{\parallel }{\mu }_0-{\mu }_{\ast }{\mathrm{\parallel }}_2+C{\sum }_{j=0}^{k-1}{q}^{k-1-j}{ϵ}_j\mathrm{.}$ The first term tends to zero. For the sum, any fixed finite prefix tends to zero as $k\to \mathrm{\infty }$, while the remaining tail is bounded by $C{\sum }_{j\ge J}{ϵ}_j$, which tends to zero as $J\to \mathrm{\infty }$. Therefore ${\mu }_k\to {\mu }_{\ast }$. Also ${ϵ}_k\to 0$ because it is summable, so step 4.1 gives ${\widehat{x}}_k-x({\mu }_k)\to 0$ and continuity gives ${\widehat{x}}_k\to x_{\ast }$. When $r=0$, step 1.2 gives a strongly convex local objective and the same residual estimate directly yields ${\widehat{x}}_k\to x_{\ast }$.

The hypotheses and local restrictions used above are exactly the regularity, branch, residual, and successful-inner-call conditions in the Statement and [A2]. This proves the limit claim for the successful update sequence; a finite dispatch may return a cap or failure status first and no global convergence is asserted.