Naive sequential three-block ADMM

For proper closed convex $f_i:{\mathbb{R}}^{n_i}\to (-\mathrm{\infty },+\mathrm{\infty }]$, linear $A_i:{\mathbb{R}}^{n_i}\to {\mathbb{R}}^p$, data $b\in {\mathbb{R}}^p$, penalty $\rho >0$, and scaled multiplier $u^k$, the naive sequential three-block ADMM sweep is $x_1^{k+1}\in \arg {\min }_{x_1}{f}_1(x_1)+\frac{\rho }{2}\mathrm{\parallel }{A}_1{x}_1+A_2{x}_2^k+A_3{x}_3^k-b+u^k{\mathrm{\parallel }}^2,$ then $x_2^{k+1}$ minimizes the same augmented residual with $x_1^{k+1}$, $x_2$ variable and $x_3^k$ fixed; then $x_3^{k+1}$ minimizes it with the first two new blocks; finally $u^{k+1}=u^k+A_1{x}_1^{k+1}+A_2{x}_2^{k+1}+A_3{x}_3^{k+1}-b\mathrm{.}$ These formulas specify the exact recurrence conditional on attained block minima; proper closed convexity alone does not ensure attainment.

The executable procedure takes the data above, a current state $(x_1^k,x_2^k,x_3^k,u^k)$, three positive integer caps $C_i$, and, for each block, a supplied deterministic solver program $S_i$ and Boolean certificate checker $V_i$. Their complete instructions and data representations are part of the input. Each program uses discrete steps that terminate; the checker is also such a program. A solver takes its displayed block objective and may halt with failed or a candidate-certificate pair $(v,e)$. Admissibility requires that $V_i(H,v,e)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ implies $H(v)<+\mathrm{\infty }$ and $H(v)\le H(w)$ for every block vector $w$. This is a soundness requirement on supplied checkers, not a claim that such certificates can always be found or that arbitrary function descriptions can be checked automatically.

Execute one sweep as follows. Return invalid-input for mismatched dimensions, nonpositive $\rho$, or caps that are not positive integers. Keep the old state and store tentative blocks separately. For $i=1,2,3$ in that order, form its block objective using the already computed new blocks and the remaining old blocks. Run $S_i$ on that objective, then, if it returns $(v,e)$, run $V_i$ on this triple, allowing at most $C_i$ program steps in total for this solver-checker pair. After each step inspect for termination: an explicit failure, malformed output, or a false checker result returns block-$i$-solve-failed; a true result stores $v$ as the tentative block. If the budget is used without such a result or failure, return block-$i$-cap-exhausted. A true result on the last allowed step is accepted. Any failure returns the unchanged old state. Only after all three blocks are accepted, perform the displayed multiplier update, commit the four new vectors, and return success with that state. A requested finite run repeats this sweep for an input nonnegative integer number of sweeps and stops at its first nonsuccess status. No convergence is asserted.