The Riemannian Chambolle-Pock algorithm

The Riemannian Chambolle—Pock is a generalization of the Chambolle—Pock algorithm Chambolle and Pock [CP11] It is also known as primal-dual hybrid gradient (PDHG) or primal-dual proximal splitting (PDPS) algorithm.

In order to minimize over $p∈\mathcal M$ the cost function consisting of In order to minimize a cost function consisting of

\[F(p) + G(Λ(p)),\]

over $p∈\mathcal M$

where $F:\mathcal M → \overline{ℝ}$, $G:\mathcal N → \overline{ℝ}$, and $Λ:\mathcal M →\mathcal N$. If the manifolds $\mathcal M$ or $\mathcal N$ are not Hadamard, it has to be considered locally only, that is on geodesically convex sets $\mathcal C \subset \mathcal M$ and $\mathcal D \subset\mathcal N$ such that $Λ(\mathcal C) \subset \mathcal D$.

The algorithm is available in four variants: exact versus linearized (see variant) as well as with primal versus dual relaxation (see relax). For more details, see Bergmann, Herzog, Silva Louzeiro, Tenbrinck and Vidal-Núñez [BHS+21]. In the following description is the case of the exact, primal relaxed Riemannian Chambolle—Pock algorithm.

Given base points $m∈\mathcal C$, $n=Λ(m)∈\mathcal D$, initial primal and dual values $p^{(0)} ∈\mathcal C$, $ξ_n^{(0)} ∈T_n^*\mathcal N$, and primal and dual step sizes $\sigma_0$, $\tau_0$, relaxation $\theta_0$, as well as acceleration $\gamma$.

As an initialization, perform $\bar p^{(0)} \gets p^{(0)}$.

The algorithms performs the steps $k=1,…,$ (until a StoppingCriterion is fulfilled with)

\[ξ^{(k+1)}_n = \operatorname{prox}_{\tau_k G_n^*}\Bigl(ξ_n^{(k)} + \tau_k \bigl(\log_n Λ (\bar p^{(k)})\bigr)^\flat\Bigr)\]
\[p^{(k+1)} = \operatorname{prox}_{\sigma_k F}\biggl(\exp_{p^{(k)}}\Bigl( \operatorname{PT}_{p^{(k)}\gets m}\bigl(-\sigma_k DΛ(m)^*[ξ_n^{(k+1)}]\bigr)^\sharp\Bigr)\biggr)\]
Update
- $\theta_k = (1+2\gamma\sigma_k)^{-\frac{1}{2}}$
- $\sigma_{k+1} = \sigma_k\theta_k$
- $\tau_{k+1} = \frac{\tau_k}{\theta_k}$
\[\bar p^{(k+1)} = \exp_{p^{(k+1)}}\bigl(-\theta_k \log_{p^{(k+1)}} p^{(k)}\bigr)\]

Furthermore you can exchange the exponential map, the logarithmic map, and the parallel transport by a retraction, an inverse retraction, and a vector transport.

Finally you can also update the base points $m$ and $n$ during the iterations. This introduces a few additional vector transports. The same holds for the case $Λ(m^{(k)})\neq n^{(k)}$ at some point. All these cases are covered in the algorithm.

Manopt.ChambollePock — Function

ChambollePock(
    M, N, cost, x0, ξ0, m, n, prox_F, prox_G_dual, adjoint_linear_operator;
    forward_operator=missing,
    linearized_forward_operator=missing,
    evaluation=AllocatingEvaluation()
)

Perform the Riemannian Chambolle—Pock algorithm.

Given a cost function $\mathcal E:\mathcal M → ℝ$ of the form

\[\mathcal E(p) = F(p) + G( Λ(p) ),\]

where $F:\mathcal M → ℝ$, $G:\mathcal N → ℝ$, and $Λ:\mathcal M → \mathcal N$. The remaining input parameters are

p, X: primal and dual start points $x∈\mathcal M$ and $ξ∈T_n\mathcal N$
m,n: base points on $\mathcal M$ and $\mathcal N$, respectively.
adjoint_linearized_operator: the adjoint $DΛ^*$ of the linearized operator $DΛ(m): T_{m}\mathcal M → T_{Λ(m)}\mathcal N$
prox_F, prox_G_Dual: the proximal maps of $F$ and $G^\ast_n$

note that depending on the AbstractEvaluationType evaluation the last three parameters as well as the forward operator Λ and the linearized_forward_operator can be given as allocating functions (Manifolds, parameters) -> result or as mutating functions (Manifold, result, parameters) -> result` to spare allocations.

By default, this performs the exact Riemannian Chambolle Pock algorithm, see the optional parameter DΛ for their linearized variant.

For more details on the algorithm, see [BHS+21].

Optional parameters

acceleration: (0.05)
dual_stepsize: (1/sqrt(8)) proximal parameter of the primal prox
evaluation: (AllocatingEvaluation()) specify whether the proximal maps and operators are allocating functions(Manifolds, parameters) -> resultor given as mutating functions(Manifold, result, parameters)-> result
Λ: (missing) the (forward) operator $Λ(⋅)$ (required for the :exact variant)
linearized_forward_operator: (missing) its linearization $DΛ(⋅)[⋅]$ (required for the :linearized variant)
primal_stepsize: (1/sqrt(8)) proximal parameter of the dual prox
relaxation: (1.) the relaxation parameter $γ$
relax: (:primal) whether to relax the primal or dual
variant: (:exact if Λ is missing, otherwise :linearized) variant to use. Note that this changes the arguments the forward_operator is called with.
stopping_criterion: ([StopAfterIteration](@ref)(100)) a StoppingCriterion
update_primal_base: (missing) function to update m (identity by default/missing)
update_dual_base: (missing) function to update n (identity by default/missing)
retraction_method: (default_retraction_method(M, typeof(p))) the retraction to use
inverse_retraction_method (default_inverse_retraction_method(M, typeof(p))) an inverse retraction to use.
vector_transport_method (default_vector_transport_method(M, typeof(p))) a vector transport to use

Output

the obtained (approximate) minimizer $p^*$, see get_solver_return for details.