Douglas—Rachford algorithm

DouglasRachford(M, f, proxes_f, p)
DouglasRachford(M, mpo, p)
DouglasRachford!(M, f, proxes_f, p)
DouglasRachford!(M, mpo, p)

Compute the Douglas-Rachford algorithm on the manifold $\mathcal M$, starting from pgiven the (two) proximal mapsproxes_f`, see [BPS16].

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, that is, component wise in a vector.

The parallel Douglas Rachford does not work in-place for now, since while creating the new staring point p' on the power manifold, a copy of p Is created

If you provide a ManifoldProximalMapObjective mpo instead, the proximal maps are kept unchanged.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> v
• proxes_f: functions of the form (M, λ, p)-> q 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) -> q computing in place of q.
• p: a point on the manifold $\mathcal M$

Keyword arguments

• α= k -> 0.9: relaxation of the step from old to new iterate, to be precise $p^{(k+1)} = g(α_k; p^{(k)}, q^{(k)})$, where $q^{(k)}$ is the result of the double reflection involved in the DR algorithm and $g$ is a curve induced by the retraction and its inverse.
• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses This is used both in the relaxation step as well as in the reflection, unless you set R yourself.
• λ= k -> 1.0: function to provide the value for the proximal parameter $λ_k$
• R=reflect(!): method employed in the iteration to perform the reflection of p at the prox of p. This uses by default reflect or reflect! depending on reflection_evaluation and the retraction and inverse retraction specified by retraction_method and inverse_retraction_method, respectively.
• reflection_evaluation: (AllocatingEvaluation whether R works in-place or allocating
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions This is used both in the relaxation step as well as in the reflection, unless you set R yourself.
• stopping_criterion=StopAfterIteration(200)|StopWhenChangeLess(1e-5): a functor indicating that the stopping criterion is fulfilled
• parallel=false: indicate whether to use a parallel Douglas-Rachford or not.

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

DouglasRachford(M, f, proxes_f, p; kwargs...)

a doc string with some math $t_{k+1} = g(α_k; t_k, s_k)$

DouglasRachford(M, f, proxes_f, p)
DouglasRachford(M, mpo, p)
DouglasRachford!(M, f, proxes_f, p)
DouglasRachford!(M, mpo, p)

Compute the Douglas-Rachford algorithm on the manifold $\mathcal M$, starting from pgiven the (two) proximal mapsproxes_f`, see [BPS16].

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, that is, component wise in a vector.

The parallel Douglas Rachford does not work in-place for now, since while creating the new staring point p' on the power manifold, a copy of p Is created

If you provide a ManifoldProximalMapObjective mpo instead, the proximal maps are kept unchanged.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> v
• proxes_f: functions of the form (M, λ, p)-> q 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) -> q computing in place of q.
• p: a point on the manifold $\mathcal M$

Keyword arguments

• α= k -> 0.9: relaxation of the step from old to new iterate, to be precise $p^{(k+1)} = g(α_k; p^{(k)}, q^{(k)})$, where $q^{(k)}$ is the result of the double reflection involved in the DR algorithm and $g$ is a curve induced by the retraction and its inverse.
• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses This is used both in the relaxation step as well as in the reflection, unless you set R yourself.
• λ= k -> 1.0: function to provide the value for the proximal parameter $λ_k$
• R=reflect(!): method employed in the iteration to perform the reflection of p at the prox of p. This uses by default reflect or reflect! depending on reflection_evaluation and the retraction and inverse retraction specified by retraction_method and inverse_retraction_method, respectively.
• reflection_evaluation: (AllocatingEvaluation whether R works in-place or allocating
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions This is used both in the relaxation step as well as in the reflection, unless you set R yourself.
• stopping_criterion=StopAfterIteration(200)|StopWhenChangeLess(1e-5): a functor indicating that the stopping criterion is fulfilled
• parallel=false: indicate whether to use a parallel Douglas-Rachford or not.

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

DouglasRachfordState <: AbstractManoptSolverState

Store all options required for the DouglasRachford algorithm,

Fields

• α: relaxation of the step from old to new iterate, to be precise $x^{(k+1)} = g(α(k); x^{(k)}, t^{(k)})$, where $t^{(k)}$ is the result of the double reflection involved in the DR algorithm
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• λ: function to provide the value for the proximal parameter during the calls
• parallel: indicate whether to use a parallel Douglas-Rachford or not.
• R: method employed in the iteration to perform the reflection of x at the prox p.
• p::P: a point on the manifold $\mathcal M$storing the current iterate For the parallel Douglas-Rachford, this is not a value from the PowerManifold manifold but the mean.
• reflection_evaluation: whether R works in-place or allocating
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• s: the last result of the double reflection at the proximal maps relaxed by α.
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled

Constructor

DouglasRachfordState(M::AbstractManifold; kwargs...)

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$

Keyword arguments

• α= k -> 0.9: relaxation of the step from old to new iterate, to be precise $x^{(k+1)} = g(α(k); x^{(k)}, t^{(k)})$, where $t^{(k)}$ is the result of the double reflection involved in the DR algorithm
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• λ= k -> 1.0: function to provide the value for the proximal parameter during the calls
• p=rand(M): a point on the manifold $\mathcal M$to specify the initial value
• R=reflect(!): method employed in the iteration to perform the reflection of p at the prox of p, which function is used depends on reflection_evaluation.
• reflection_evaluation=AllocatingEvaluation()) specify whether the reflection works in-place or allocating (default)
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion=StopAfterIteration(300): a functor indicating that the stopping criterion is fulfilled
• parallel=false: indicate whether to use a parallel Douglas-Rachford or not.

reflect(M, f, x; kwargs...)
reflect!(M, q, f, x; kwargs...)

reflect the point x from the manifold M at the point f(x) of the function $f: \mathcal M → \mathcal M$, given by

\[ \operatorname{refl}_f(x) = \operatorname{refl}_{f(x)}(x),\]

Compute the result in q.

see also reflect(M,p,x), to which the keywords are also passed to.

reflect(M, p, x, kwargs...)
reflect!(M, q, p, x, kwargs...)

Reflect the point x from the manifold M at point p, given by

\[\operatorname{refl}\]

where $\operatorname{retr}$ and $\operatorname{retr}^{-1}$ denote a retraction and an inverse retraction, respectively. This can also be done in place of q.

Keyword arguments

• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses

and for the reflect! additionally

• X=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$ as temporary memory to compute the inverse retraction in place. otherwise this is the memory that would be allocated anyways.

reflect(M, f, x; kwargs...)
reflect!(M, q, f, x; kwargs...)

reflect the point x from the manifold M at the point f(x) of the function $f: \mathcal M → \mathcal M$, given by

\[ \operatorname{refl}_f(x) = \operatorname{refl}_{f(x)}(x),\]

Compute the result in q.

see also reflect(M,p,x), to which the keywords are also passed to.

reflect(M, p, x, kwargs...)
reflect!(M, q, p, x, kwargs...)

Reflect the point x from the manifold M at point p, given by

\[\operatorname{refl}_p(q) = \operatorname{retr}_p(-\operatorname{retr}^{-1}_p q),\]

where $\operatorname{retr}$ and $\operatorname{retr}^{-1}$ denote a retraction and an inverse retraction, respectively.

This can also be done in place of q.

Keyword arguments

• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses

and for the reflect! additionally

• X=zero_vector(M,p): a temporary memory to compute the inverse retraction in place. otherwise this is the memory that would be allocated anyways.