pyproximal.optimization.cls_primal.ProximalGradient

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

Proximal gradient (optionally accelerated)

Solves the following minimization problem using (Accelerated) Proximal gradient algorithm:

\[\mathbf{x} = \argmin_\mathbf{x} f(\mathbf{x}) + \epsilon g(\mathbf{x})\]

where \(f(\mathbf{x})\) is a smooth convex function with a uniquely defined gradient and \(g(\mathbf{x})\) is any convex function that has a known proximal operator.

Notes

The Proximal gradient algorithm can be expressed by the following recursion:

\[\begin{split}\mathbf{x}^{k+1} = \mathbf{y}^k + \eta (\prox_{\tau^k \epsilon g}(\mathbf{y}^k - \tau^k \nabla f(\mathbf{y}^k)) - \mathbf{y}^k) \\ \mathbf{y}^{k+1} = \mathbf{x}^k + \omega^k (\mathbf{x}^k - \mathbf{x}^{k-1})\end{split}\]

where at each iteration \(\tau^k\) can be estimated by back-tracking as follows:

\[\begin{split}\begin{aligned} &\tau = \tau^{k-1} &\\ &repeat \; \mathbf{z} = \prox_{\tau \epsilon g}(\mathbf{x}^k - \tau \nabla f(\mathbf{x}^k)), \tau = \beta \tau \quad if \; f(\mathbf{z}) \leq \tilde{f}_\tau(\mathbf{z}, \mathbf{x}^k) \\ &\tau^k = \tau, \quad \mathbf{x}^{k+1} = \mathbf{z} &\\ \end{aligned}\end{split}\]

where \(\tilde{f}_\tau(\mathbf{x}, \mathbf{y}) = f(\mathbf{y}) + \nabla f(\mathbf{y})^T (\mathbf{x} - \mathbf{y}) + 1/(2\tau)||\mathbf{x} - \mathbf{y}||_2^2\).

Different accelerations are provided:

• acceleration=None: \(\omega^k = 0\);

• acceleration=vandenberghe [1]: \(\omega^k = k / (k + 3)\) for `

• acceleration=fista: \(\omega^k = (t_{k-1}-1)/t_k\) where \(t_k = (1 + \sqrt{1+4t_{k-1}^{2}}) / 2\) [2]

[1]

Vandenberghe, L., “Fast proximal gradient methods”, 2010.

[2]

Beck, A., and Teboulle, M. “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems”, SIAM Journal on Imaging Sciences, vol. 2, pp. 183-202. 2009.

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(proxf, proxg, x0[, epsg, tau, ...])	Setup solver
solve(proxf, proxg, x0[, epsg, tau, ...])	Run entire solver
step(x, y[, show])	Run one step of solver