pyproximal.optimization.cls_primal.PPXA

class pyproximal.optimization.cls_primal.PPXA(callbacks: Callbacks = None)[source]

Parallel Proximal Algorithm (PPXA)

Solves the following minimization problem using Parallel Proximal Algorithm (PPXA):

\[\mathbf{x} = \argmin_\mathbf{x} \sum_{i=1}^m f_i(\mathbf{x})\]

where \(f_i(\mathbf{x})\) are any convex functions that has known proximal operators.

See also

ConsensusADMM

Consensus ADMM

Notes

The Parallel Proximal Algorithm (PPXA) can be expressed by the following recursion [1], [2], [3], [4]:

  • \(\mathbf{y}_{i}^{0} = \mathbf{x}\) or \(\mathbf{y}_{i}^{0} = \mathbf{x}_{i}\) for \(i=1,\ldots,m\)

  • \(\mathbf{x}^{0} = \sum_{i=1}^m w_i \mathbf{y}_{i}^{0}\)

  • for \(k = 1, \ldots\)

    • for \(i = 1, \ldots, m\)

      • \(\mathbf{p}_{i}^{k} = \prox_{\frac{\tau}{w_i} f_i} (\mathbf{y}_{i}^{k})\)

    • \(\mathbf{p}^{k} = \sum_{i=1}^{m} w_i \mathbf{p}_{i}^{k}\)

    • for \(i = 1, \ldots, m\)

      • \(\mathbf{y}_{i}^{k+1} = \mathbf{y}_{i}^{k} + \eta (2 \mathbf{p}^{k} - \mathbf{x}^{k} - \mathbf{p}_i^{k})\)

    • \(\mathbf{x}^{k+1} = \mathbf{x}^{k} + \eta (\mathbf{p}^{k} - \mathbf{x}^{k})\)

where \(0 < \eta < 2\) and \(\sum_{i=1}^m w_i = 1, \ 0 < w_i < 1\). In the current implementation, \(w_i = 1 / m\) when not provided.

References

[1]

Combettes, P.L., Pesquet, J.-C., 2008. A proximal decomposition method for solving convex variational inverse problems. Inverse Problems 24, 065014. Algorithm 3.1. https://doi.org/10.1088/0266-5611/24/6/065014 https://arxiv.org/abs/0807.2617

[2]

Combettes, P.L., Pesquet, J.-C., 2011. Proximal Splitting Methods in Signal Processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, pp. 185-212. Algorithm 10.27. https://doi.org/10.1007/978-1-4419-9569-8_10

[3]

Bauschke, H.H., Combettes, P.L., 2011. Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 1st ed, CMS Books in Mathematics. Springer, New York, NY. Proposition 27.8. https://doi.org/10.1007/978-1-4419-9467-7

[4]

Ryu, E.K., Yin, W., 2022. Large-Scale Convex Optimization: Algorithms & Analyses via Monotone Operators. Cambridge University Press, Cambridge. Exercise 2.38 https://doi.org/10.1017/9781009160865 https://large-scale-book.mathopt.com/

Methods

__init__([callbacks])

callback(x, *args, **kwargs)

Callback routine

finalize([nbar, show])

Finalize solver

memory_usage()

Compute memory usage of the solver

run(x, y[, niter, show, itershow])

Run solver

setup(proxfs, x0, tau[, eta, weights, ...])

Setup solver

solve(proxfs, x0, tau[, eta, weights, ...])

Run entire solver

step(x, y[, show])

Run one step of solver