Scaled two-block ADMM with explicit capped-solve statuses

Let $f:{\mathbb{R}}^n\to (-\mathrm{\infty },+\mathrm{\infty }]$ and $g:{\mathbb{R}}^m\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper closed convex, let $K:{\mathbb{R}}^n\to {\mathbb{R}}^p$ and $L:{\mathbb{R}}^m\to {\mathbb{R}}^p$ be linear, let $c\in {\mathbb{R}}^p$, and let $\rho >0$. The primal problem is ${\min }_{x,z}f(x)+g(z)\text{subject to }Kx+Lz=c,$ and its Lagrangian is $\mathcal{L}((x,z),y)=f(x)+g(z)+⟨y,Kx+Lz-c⟩$. A saddle point means a saddle pair in the sense of Saddle points of extended-real Lagrangians.

Conditional on both block minima being attained, an exact outer sweep with scaled dual $u^k$ computes, in order, $x^{k+1}\in \arg {\min }_x(f(x)+\frac{\rho }{2}\mathrm{\parallel }Kx+L{z}^k-c+u^k{\mathrm{\parallel }}_2^2),$ $z^{k+1}\in \arg {\min }_z(g(z)+\frac{\rho }{2}\mathrm{\parallel }K{x}^{k+1}+Lz-c+u^k{\mathrm{\parallel }}_2^2),$ then set $r^{k+1}=K{x}^{k+1}+L{z}^{k+1}-c$ and $u^{k+1}=u^k+r^{k+1}$. Report also the unscaled dual $y^k=\rho u^k$, objective $p_k=f(x^k)+g(z^k)$, and primal residual $r^k$. If an exact subproblem has multiple minimizers, choose the unique minimum-norm member of its nonempty closed convex minimizer set; existence and uniqueness of that tie-break follow from Every point has a unique nearest point in a nonempty closed Euclidean convex set.

The finite procedure takes the problem data, a current state $(x^k,z^k,u^k)$, positive integer caps $C_x,C_z$, and deterministic solver programs $S_x,S_z$ and Boolean certificate-checker programs $V_x,V_z$ with their complete instructions and data representations. Each program uses discrete steps that terminate. A solver takes its block objective $H$ and may halt with failed or a candidate-certificate pair $(v,e)$. The supplied checkers must be sound: $V(H,v,e)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ implies $H(v)<+\mathrm{\infty }$, $H(v)\le H(w)$ for every block vector $w$, and $\mathrm{\parallel }v{\mathrm{\parallel }}_2\le \mathrm{\parallel }w{\mathrm{\parallel }}_2$ for every minimizer $w$ of $H$. These are admissibility conditions on the input programs, not an automatic test of arbitrary programs or a promise that an exact certificate is available. In particular, proper closed convexity alone does not imply block attainment.

Return invalid-input for mismatched dimensions, $\rho \le 0$, or caps that are not positive integers. Retain the old state and proceed in order through the $x$ and $z$ objectives above, using the tentative new $x$ for the $z$ objective. For block $b\in \{x,z\}$, start $S_b(H)$ and, if it returns $(v,e)$, run $V_b(H,v,e)$, using at most $C_b$ program steps in total for the solver and checker. After each step inspect for termination. An explicit failure, malformed output, or false checker result returns $b$-solve-failed with the unchanged old state. A true checker result stores $v$ as the tentative block; accept it even on the last allowed step. If the budget is used without a true result or failure, return $b$-cap-exhausted with the old state. Only after both blocks are accepted, perform the residual and dual assignments above, commit the new state, and return success with that state, $y^{k+1}$, $p_{k+1}$ and $r^{k+1}$. A requested finite run repeats this sweep for an input nonnegative integer number of sweeps and stops at its first nonsuccess status. Failure, including on a problem without a block minimizer, never advances the outer state. These statuses give no approximate convergence guarantee.