Douglas–Rachford Algorithm

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

 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.

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.

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.