pyproximal.optimization.cls_primal.ADMM

class pyproximal.optimization.cls_primal.ADMM(callbacks: Callbacks = None)

Alternating Direction Method of Multipliers

Solves the following minimization problem using Alternating Direction Method of Multipliers:

\[\begin{split}\mathbf{x},\mathbf{z} = \argmin_{\mathbf{x},\mathbf{z}} f(\mathbf{x}) + g(\mathbf{z}) \\ s.t. \; \mathbf{x}=\mathbf{z}\end{split}\]

where \(f(\mathbf{x})\) and \(g(\mathbf{z})\) are any convex function that has a known proximal operator.

ADMM can also solve the problem of the form above with a more general constraint: \(\mathbf{Ax}+\mathbf{Bz}=\mathbf{c}\). This routine implements the special case where \(\mathbf{A}=\mathbf{I}\), \(\mathbf{B}=-\mathbf{I}\), and \(\mathbf{c}=\mathbf{0}\), as a general algorithm can be obtained for any choice of \(f\) and \(g\) provided they have a known proximal operator.

On the other hand, for more general choice of \(\mathbf{A}\), \(\mathbf{B}\), and \(\mathbf{c}\), the iterations are not generalizable, i.e. they depend on the choice of the \(f\) and \(g\) functions. For this reason, we currently only provide an additional solver for the special case where \(f\) is a pyproximal.proximal.L2 operator with a linear operator \(\mathbf{G}\) and data \(\mathbf{y}\), \(\mathbf{B}=-\mathbf{I}\) and \(\mathbf{c}=\mathbf{0}\), called pyproximal.optimization.primal.ADMML2. Note that for the very same choice of \(\mathbf{B}\) and \(\mathbf{c}\), the pyproximal.optimization.primal.LinearizedADMM can also be used (and this does not require a specific choice of \(f\)).

See also

ADMML2

ADMM with L2 misfit function

LinearizedADMM

Linearized ADMM

Notes

The ADMM algorithm can be expressed by the following recursion [1]:

\[\begin{split}\mathbf{x}^{k+1} = \prox_{\tau f}(\mathbf{z}^{k} - \mathbf{u}^{k})\\ \mathbf{z}^{k+1} = \prox_{\tau g}(\mathbf{x}^{k+1} + \mathbf{u}^{k})\\ \mathbf{u}^{k+1} = \mathbf{u}^{k} + \mathbf{x}^{k+1} - \mathbf{z}^{k+1}\end{split}\]

Note that x and z converge to each other, however if iterations are stopped too early x is guaranteed to belong to the domain of f while z is guaranteed to belong to the domain of g. Depending on the problem either of the two may be the best solution.

[1]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3 (1), 1-122. https://doi.org/10.1561/2200000016.

Methods

__init__([callbacks])
callback(x, *args, **kwargs)	Callback routine
finalize([nbar, show])	Finalize solver
memory_usage()	Compute memory usage of the solver
run(x, z[, niter, show, itershow])	Run solver
setup(proxf, proxg, x0, tau[, z0, gfirst, ...])	Setup solver
solve(proxf, proxg, x0, tau[, z0, gfirst, ...])	Run entire solver
step(x, z[, show])	Run one step of solver