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.

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.

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.

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.