pyproximal.optimization.cls_primaldual.PrimalDual

class pyproximal.optimization.cls_primaldual.PrimalDual(callbacks: Callbacks = None)

Primal-dual algorithm

Solves the following (possibly) nonlinear minimization problem using the general version of the first-order primal-dual algorithm of [1]:

\[\min_{\mathbf{x} \in X} g(\mathbf{Ax}) + f(\mathbf{x}) + \mathbf{z}^T \mathbf{x}\]

where \(\mathbf{A}\) is a linear operator, \(f\) and \(g\) can be any convex functions that have a known proximal operator.

This functional is effectively minimized by solving its equivalent primal-dual problem (primal in \(f\), dual in \(g\)):

\[\min_{\mathbf{x} \in X} \max_{\mathbf{y} \in Y} \mathbf{y}^T(\mathbf{Ax}) + \mathbf{z}^T \mathbf{x} + f(\mathbf{x}) - g^*(\mathbf{y})\]

where \(\mathbf{y}\) is the so-called dual variable.

Notes

The Primal-dual algorithm can be expressed by the following recursion (gfirst=True):

\[\begin{split}\mathbf{y}^{k+1} = \prox_{\mu g^*}(\mathbf{y}^{k} + \mu \mathbf{A}\bar{\mathbf{x}}^{k})\\ \mathbf{x}^{k+1} = \prox_{\tau f}(\mathbf{x}^{k} - \tau (\mathbf{A}^H \mathbf{y}^{k+1} + \mathbf{z})) \\ \bar{\mathbf{x}}^{k+1} = \mathbf{x}^{k+1} + \theta (\mathbf{x}^{k+1} - \mathbf{x}^k)\end{split}\]

where \(\tau \mu \lambda_{max}(\mathbf{A}^H\mathbf{A}) < 1\).

Alternatively for gfirst=False the scheme becomes:

\[\begin{split}\mathbf{x}^{k+1} = \prox_{\tau f}(\mathbf{x}^{k} - \tau (\mathbf{A}^H \mathbf{y}^{k} + \mathbf{z})) \\ \bar{\mathbf{x}}^{k+1} = \mathbf{x}^{k+1} + \theta (\mathbf{x}^{k+1} - \mathbf{x}^k) \\ \mathbf{y}^{k+1} = \prox_{\mu g^*}(\mathbf{y}^{k} + \mu \mathbf{A}\bar{\mathbf{x}}^{k+1})\end{split}\]

[1]

A., Chambolle, and T., Pock, “A first-order primal-dual algorithm for convex problems with applications to imaging”, Journal of Mathematical Imaging and Vision, 40, 8pp. 120-145. 2011.

Methods

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