douglas_rachford_pd

odl.solvers.nonsmooth.douglas_rachford.douglas_rachford_pd(x, f, g, L, niter, tau=None, sigma=None, callback=None, **kwargs)[source]

Douglas-Rachford primal-dual splitting algorithm.

Minimizes the sum of several convex functions composed with linear operators:

min_x f(x) + sum_i g_i(L_i x)

where f, g_i are convex functions, L_i are linear Operator's.

Can also be used to solve the more general problem:

min_x f(x) + sum_i (g_i @ l_i)(L_i x)

where l_i are convex functions and @ is the infimal convolution:

(g @ l)(x) = inf_y g(y) + l(x - y)

For references on the algorithm, see algorithm 3.1 in [BH2013].

Parameters:
xLinearSpaceElement

Initial point, updated in-place.

fFunctional

proximal factory for the function f.

gsequence of Functional's

Sequence of of the functions g_i. Needs to have g[i].convex_conj.proximal.

Lsequence of Operator's

Sequence of Operator's with as many elements as g.

niterint

Number of iterations.

taufloat, optional

Step size parameter for f. Default: Sufficient for convergence, see douglas_rachford_pd_stepsize.

sigmasequence of floats, optional

Step size parameters for the g_i's. Default: Sufficient for convergence, see douglas_rachford_pd_stepsize.

callbackcallable, optional

Function called with the current iterate after each iteration.

Other Parameters:
lsequence of Functional's, optional

Sequence of of the functions l_i. Needs to have l[i].convex_conj.proximal. If omitted, the simpler problem without l_i will be considered.

lamfloat or callable, optional

Overrelaxation step size. If callable, it should take an index (starting at zero) and return the corresponding step size.

See also

odl.solvers.nonsmooth.primal_dual_hybrid_gradient.pdhg

Solver for similar problems.

odl.solvers.nonsmooth.forward_backward.forward_backward_pd

Solver for similar problems which can additionaly handle a differentiable term.

Notes

The mathematical problem to solve is

\min_x f(x) + \sum_{i=0}^n (g_i \Box l_i)(L_i x),

where f, g_i, l_i are proper, convex and lower semicontinuous and L_i are linear operators. The infimal convolution g \Box l is defined by

(g \Box l)(x) = \inf_y g(y) + l(x - y).

The simplified problem,

\min_x f(x) + \sum_{i=0}^n g_i(L_i x),

can be obtained by setting

l(x) = 0 \text{ if } x = 0, \infty \text{ else.}

To guarantee convergence, the parameters \tau, \sigma_i and L_i need to satisfy

\tau \sum_{i=1}^n \sigma_i \|L_i\|^2 < 4

The parameter \lambda needs to satisfy 0 < \lambda < 2 and if it is given as a function it needs to satisfy

\sum_{n=1}^\infty \lambda_n (2 - \lambda_n) = +\infty.

References

[BH2013] Bot, R I, and Hendrich, C. A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators. SIAM Journal on Optimization, 23.4 (2013), pp 2541--2565.