Finite-budget augmented-Lagrangian multiplier method

Fix a $C^2$ program as in Equality and inequality augmented Lagrangians and multiplier updates, a penalty $\rho >0$, finite positive integer outer cap $K$, finite positive integer per-call inner cap $M$, tolerances ${ϵ}_k\ge 0$, and KKT tolerance $\tau \ge 0$. A supplied finite-budget inner procedure receives $(x_k,{\nu }_k,{\lambda }_k,\rho ,{ϵ}_k,M)$, performs at most $M$ inner iterations, and returns one of: success(x_k^+,\widehat\epsilon_k) with $x_k^{+}\in U$ and ${\widehat{ϵ}}_k=\mathrm{\parallel }{\mathrm{\nabla }}_x{\mathcal{L}}_{\rho }(x_k^{+},{\nu }_k,{\lambda }_k){\mathrm{\parallel }}_2\le {ϵ}_k$; budget-exhausted(x_{\rm last},\widehat\epsilon_{\rm last}) with $x_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\in U$ and ${\widehat{ϵ}}_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}=\mathrm{\parallel }{\mathrm{\nabla }}_x{\mathcal{L}}_{\rho }(x_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},{\nu }_k,{\lambda }_k){\mathrm{\parallel }}_2$; or failure(data) when it cannot continue or report a residual. Each inner iteration and report computation is finite, and the procedure returns by its cap.

Initialize $x_0\in U$, ${\nu }_0\in {\mathbb{R}}^p$, and ${\lambda }_0\in {\mathbb{R}}_{+}^m$. For $k=0,\dots ,K-1$:

1. Call the inner procedure with cap $M$. On budget-exhausted(x_{\rm last},\widehat\epsilon_{\rm last}), return inner-budget-exhausted with current $(x_k,{\nu }_k,{\lambda }_k)$, that point, and residual. On failure(data), return inner-failure with the data. If a purported success reports a residual exceeding ${ϵ}_k$, return inner-failure with the reported data. Otherwise store its reported inner residual ${\widehat{ϵ}}_k$.
2. Set ${\nu }_{k+1}={\nu }_k+\rho h(x_k^{+}),{\lambda }_{k+1}=[{\lambda }_k+\rho g(x_k^{+}){]}_{+}\mathrm{.}$
3. Set $r_k=r_{\mathrm{K}\mathrm{K}\mathrm{T}}(x_k^{+},{\nu }_{k+1},{\lambda }_{k+1})$. If $r_k\le \tau$, return kkt-tolerance-reached with $x_k^{+}$, $({\nu }_{k+1},{\lambda }_{k+1})$, $r_k$, and ${\widehat{ϵ}}_k$; otherwise set $x_{k+1}=x_k^{+}$ and continue.

If all $K$ outer iterations finish without that test passing, return outer-budget-exhausted with $x_K$, $({\nu }_K,{\lambda }_K)$, the last KKT residual $r_{K-1}$, and inner residual ${\widehat{ϵ}}_{K-1}$. The routine claims neither convergence nor that the inner procedure succeeds within its cap.

Domain preservation, finite-cap termination and reported-residual guarantees are proved in The augmented-Lagrangian multiplier procedure preserves its domain and returns within its caps ↗.