# Douglas–Rachford Algorithm

The (Parallel) Douglas–Rachford ((P)DR) Algorithm was generalized to Hadamard manifolds in [Bergmann, Persch, Steidl, 2016].

The aim is to minimize the sum

\[F(x) = f(x) + g(x)\]

on a manifold, where the two summands have proximal maps $\operatorname{prox}_{λ f}, \operatorname{prox}_{λ g}$ that are easy to evaluate (maybe in closed form, or not too costly to approximate). Further, define the reflection operator at the proximal map as

\[\operatorname{refl}_{λ f}(x) = \exp_{\operatorname{prox}_{λ f}(x)} \bigl( -\log_{\operatorname{prox}_{λ f}(x)} x \bigr)\]

.

Let $\alpha_k ∈ [0,1]$ with $\sum_{k ∈ \mathbb N} \alpha_k(1-\alpha_k) = ∈ fty$ and $λ > 0$ which might depend on iteration $k$ as well) be given.

Then the (P)DRA algorithm for initial data $x_0 ∈ \mathcal H$ as

## Initialization

Initialize $t_0 = x_0$ and $k=0$

## Iteration

Repeat until a convergence criterion is reached

- Compute $s_k = \operatorname{refl}_{λ f}\operatorname{refl}_{λ g}(t_k)$
- Within that operation, store $x_{k+1} = \operatorname{prox}_{λ g}(t_k)$ which is the prox the inner reflection reflects at.
- Compute $t_{k+1} = g(\alpha_k; t_k, s_k)$
- Set $k = k+1$

## Result

The result is given by the last computed $x_K$.

For the parallel version, the first proximal map is a vectorial version where in each component one prox is applied to the corresponding copy of $t_k$ and the second proximal map corresponds to the indicator function of the set, where all copies are equal (in $\mathcal H^n$, where $n$ is the number of copies), leading to the second prox being the Riemannian mean.

## Interface

`Manopt.DouglasRachford`

— Function```
DouglasRachford(M, f, proxes_f, p)
DouglasRachford(M, mpo, p)
```

Compute the Douglas-Rachford algorithm on the manifold $\mathcal M$, initial data $p$ and the (two) proximal maps `proxMaps`

.

For $k>2$ proximal maps, the problem is reformulated using the parallel Douglas Rachford: A vectorial proximal map on the power manifold $\mathcal M^k$ is introduced as the first proximal map and the second proximal map of the is set to the `mean`

(Riemannian Center of mass). This hence also boils down to two proximal maps, though each evaluates proximal maps in parallel, i.e. component wise in a vector.

If you provide a `ManifoldProximalMapObjective`

`mpo`

instead, the proximal maps are kept unchanged.

**Input**

`M`

– a Riemannian Manifold $\mathcal M$`F`

– a cost function consisting of a sum of cost functions`proxes_f`

– functions of the form`(M, λ, p)->...`

performing a proximal maps, where`λ`

denotes the proximal parameter, for each of the summands of`F`

. These can also be given in the`InplaceEvaluation`

variants`(M, q, λ p) -> ...`

computing in place of`q`

.`p`

– initial data $p ∈ \mathcal M$

**Optional values**

`evaluation`

– (`AllocatingEvaluation`

) specify whether the proximal maps work by allocation (default) form`prox(M, λ, x)`

or`InplaceEvaluation`

in place, i.e. is of the form`prox!(M, y, λ, x)`

.`λ`

– (`(iter) -> 1.0`

) function to provide the value for the proximal parameter during the calls`α`

– (`(iter) -> 0.9`

) relaxation of the step from old to new iterate, i.e. $t_{k+1} = g(α_k; t_k, s_k)$, where $s_k$ is the result of the double reflection involved in the DR algorithm`R`

– (`reflect`

) method employed in the iteration to perform the reflection of`x`

at the prox`p`

.`stopping_criterion`

– (`StopWhenAny`

`(`

`StopAfterIteration`

`(200),`

`StopWhenChangeLess`

`(10.0^-5))`

) a`StoppingCriterion`

.`parallel`

– (`false`

) clarify that we are doing a parallel DR, i.e. on a`PowerManifold`

manifold with two proxes. This can be used to trigger parallel Douglas–Rachford if you enter with two proxes. Keep in mind, that a parallel Douglas–Rachford implicitly works on a`PowerManifold`

manifold and its first argument is the result then (assuming all are equal after the second prox.

and the ones that are passed to `decorate_state!`

for decorators.

**Output**

the obtained (approximate) minimizer $p^*$, see `get_solver_return`

for details

`Manopt.DouglasRachford!`

— Function```
DouglasRachford!(M, f, proxes_f, p)
DouglasRachford!(M, mpo, p)
```

Compute the Douglas-Rachford algorithm on the manifold $\mathcal M$, initial data $p \in \mathcal M$ and the (two) proximal maps `proxes_f`

in place of `p`

.

For $k>2$ proximal maps, the problem is reformulated using the parallel Douglas Rachford: A vectorial proximal map on the power manifold $\mathcal M^k$ is introduced as the first proximal map and the second proximal map of the is set to the `mean`

(Riemannian Center of mass). This hence also boils down to two proximal maps, though each evaluates proximal maps in parallel, i.e. component wise in a vector.

While creating the new staring point `p'`

on the power manifold, a copy of `p`

Is created, so that the (by k>2 implicitly generated) parallel Douglas Rachford does not work in-place for now.

If you provide a `ManifoldProximalMapObjective`

`mpo`

instead, the proximal maps are kept unchanged.

**Input**

`M`

– a Riemannian Manifold $\mathcal M$`f`

– a cost function consisting of a sum of cost functions`proxes_f`

– functions of the form`(M, λ, p)->q`

or`(M, q, λ, p)->q`

performing a proximal map, where`λ`

denotes the proximal parameter, for each of the summands of`f`

.`p`

– initial point $p ∈ \mathcal M$

For more options, see `DouglasRachford`

.

## State

`Manopt.DouglasRachfordState`

— Type`DouglasRachfordState <: AbstractManoptSolverState`

Store all options required for the DouglasRachford algorithm,

**Fields**

`p`

- the current iterate (result) For the parallel Douglas-Rachford, this is not a value from the`PowerManifold`

manifold but the mean.`s`

– the last result of the double reflection at the proxes relaxed by`α`

.`λ`

– function to provide the value for the proximal parameter during the calls`α`

– relaxation of the step from old to new iterate, i.e. $x^{(k+1)} = g(α(k); x^{(k)}, t^{(k)})$, where $t^{(k)}$ is the result of the double reflection involved in the DR algorithm`R`

– method employed in the iteration to perform the reflection of`x`

at the prox`p`

.`stop`

– a`StoppingCriterion`

`parallel`

– indicate whether we are running a parallel Douglas-Rachford or not.

**Constructor**

`DouglasRachfordState(M, p; kwargs...)`

Generate the options for a Manifold `M`

and an initial point `p`

, where the following keyword arguments can be used

`λ`

– (`(iter)->1.0`

) function to provide the value for the proximal parameter during the calls`α`

– (`(iter)->0.9`

) relaxation of the step from old to new iterate, i.e. $x^{(k+1)} = g(α(k); x^{(k)}, t^{(k)})$, where $t^{(k)}$ is the result of the double reflection involved in the DR algorithm`R`

– (`reflect`

) method employed in the iteration to perform the reflection of`x`

at the prox`p`

.`stopping_criterion`

– (`StopAfterIteration`

`(300)`

) a`StoppingCriterion`

`parallel`

– (`false`

) indicate whether we are running a parallel Douglas-Rachford or not.

For specific `DebugAction`

s and `RecordAction`

s see also Cyclic Proximal Point.

## Literature

- [Bergmann, Persch, Steidl, 2016]
Bergmann, R; Persch, J.; Steidl, G.:
A Parallel Douglas–Rachford Algorithm for Minimizing ROF-like Functionals on Images with Values in Symmetric Hadamard Manifolds. SIAM Journal on Imaging Sciences, Volume 9, Number 3, pp. 901–937, 2016. doi: 10.1137/15M1052858, arXiv: 1512.02814.