pyproximal.optimization.primal.PPXA

pyproximal.optimization.primal.PPXA(proxfs: list[ProxOperator], x0: ndarray[tuple[Any, ...], dtype[_ScalarT]] | list[ndarray[tuple[Any, ...], dtype[_ScalarT]]], tau: float, eta: float = 1.0, weights: ndarray[tuple[Any, ...], dtype[_ScalarT]] | list[float] | None = None, niter: int = 1000, tol: float | None = 1e-07, callback: Callable[[...], None] | None = None, show: bool = False) → ndarray[tuple[Any, ...], dtype[_ScalarT]]

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.

Parameters:

proxfslist

A list of proximable functions \(f_1, \ldots, f_m\).

x0numpy.ndarray or list

Initial vector \(\mathbf{x}\) for all \(f_i\) if 1-dimensional array is provided, or initial vectors \(\mathbf{x}_{i}\) for each \(f_i\) for \(i=1,\ldots,m\) if a list of 1-dimensional arrays or a 2-dimensional array of size (m, d) is provided, where d is the dimension of \(\mathbf{x}_{i}\).

taufloat

Positive scalar weight

etafloat, optional

Relaxation parameter (must be between 0 and 2, 0 excluded).

weightsnumpy.ndarray or list or None, optional

Weights \(\sum_{i=1}^m w_i = 1, \ 0 < w_i < 1\), Defaults to None, which means \(w_1 = \cdots = w_m = \frac{1}{m}.\)

niterint, optional

Number of iterations of iterative scheme.

tolfloat, optional

Tolerance on change of the solution (used as stopping criterion). If tol=0, run until niter is reached.

callbackcallable, optional

Function with signature (callback(x)) to call after each iteration where x is the current model vector

showbool, optional

Display iterations log

Returns:

xnumpy.ndarray

Inverted model

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/