pyproximal.optimization.primal.ProximalGradient#

pyproximal.optimization.primal.ProximalGradient(proxf, proxg, x0, epsg=1.0, tau=None, backtracking=False, beta=0.5, eta=1.0, niter=10, niterback=100, acceleration=None, tol=None, callback=None, show=False)[source]#

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.

Parameters

proxfpyproximal.ProxOperator: Proximal operator of f function (must have grad implemented)
proxgpyproximal.ProxOperator: Proximal operator of g function
x0numpy.ndarray: Initial vector
epsgfloat or np.ndarray, optional: Scaling factor of g function
taufloat or numpy.ndarray, optional: Positive scalar weight, which should satisfy the following condition to guarantees convergence: \(\tau \in (0, 1/L]\) where L is the Lipschitz constant of \(\nabla f\). When tau=None, backtracking is used to adaptively estimate the best tau at each iteration. Finally, note that \(\tau\) can be chosen to be a vector when dealing with problems with multiple right-hand-sides
backtrackingbool, optional: Force backtracking, even if tau is not equal to None. In this case the chosen tau will be used as the initial guess in the first step of backtracking
betafloat, optional: Backtracking parameter (must be between 0 and 1)
etafloat, optional: Relaxation parameter (must be between 0 and 1, 0 excluded).
niterint, optional: Number of iterations of iterative scheme
niterbackint, optional: Max number of iterations of backtracking
accelerationstr, optional: Acceleration (None, vandenberghe or fista)
tolfloat, optional: Tolerance on change of objective function (used as stopping criterion). If tol=None, 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

Notes

The Proximal point 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.