ADMM

The alternating direction method of multipliers (ADMM) minimises a sum of two terms that are easy to handle separately:

$$\underset{x}{\min }F(x)+G(x)⟶\underset{x,z}{\min }F(x)+G(z)\text{s.t.}x=z.$$

With penalty parameter $\rho >0$ and the scaled dual variable $u$, the iteration is

$$\begin{array}{rl}{x}^{k+1}& ={\mathrm{prox}}_{F/\rho }(z^k-u^k)=\arg \underset{x}{\min }F(x)+\frac{\rho }{2}\Vert x-z^k+u^k{\Vert }^2,\\ z^{k+1}& ={\mathrm{prox}}_{G/\rho }(x^{k+1}+u^k)=\arg \underset{z}{\min }G(z)+\frac{\rho }{2}\Vert x^{k+1}-z+u^k{\Vert }^2,\\ u^{k+1}& =u^k+x^{k+1}-z^{k+1},\end{array}$$

initialised for example with $z^0=x^0$ and $u^0=0$ (see Proximal Operator). The same $\rho$ appears in both proximal steps; it is the penalty of the augmented Lagrangian $F(x)+G(z)+\frac{\rho }{2}\Vert x-z+u{\Vert }^2$.

Convergence. For closed, proper, convex $F,G$, the residuals $x^k-z^k\to 0$, the objective converges to the optimum, and $\rho u^k$ converges to a dual solution, for any $\rho >0$. The choice of $\rho$ affects speed. Residual balancing adapts it: increase $\rho$ if the primal residual $\Vert x-z\Vert$ dominates, and decrease it if the dual residual $\rho \Vert z^{k+1}-z^k\Vert$ dominates. For nonconvex $F$, such as the EIT misfit, convergence is only guaranteed under extra assumptions, but ADMM often works well in practice.

Stopping. Stop when both the primal residual $\Vert x^k-z^k\Vert$ and the dual residual $\rho \Vert z^k-z^{k-1}\Vert$ are small.

In EIT. $F$ is the data misfit, whose prox is computed iteratively, and $G=\beta \mathcal{R}$ is a regulariser with a cheap prox (Total Variation, Tikhonov Regularization, box constraints) or a learned denoiser (Plug-and-Play Priors, Diffusion Proximal Operator). See Nested ADMM Reconstruction.

In ModularEIT.jl: ADMM.

References

1. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein (2011). Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Found. Trends Mach. Learn. 3(1), 1–122. doi:10.1561/2200000016
2. Y. Wang (2022). Anisotropic TV Regularization in Electrical Impedance Tomography: An Experimental Study. Engineering 14(3), 138–146. doi:10.4236/eng.2022.143013
3. C. Park, S. Shoushtari, W. Gan, U. S. Kamilov (2023). Convergence of Nonconvex PnP-ADMM with MMSE Denoisers. IEEE CAMSAP 2023, 511–515. doi:10.1109/CAMSAP58249.2023.10403463