# The Riemannian Chambolle-Pock Algorithm

The Riemannian Chambolle–Pock is a generalization of the Chambolle–Pock algorithm[ChambollePock2011]. It is also known as primal dual hybrig gradient (PDHG) or primal dual proximal splitting (PDPS) algorithm.

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

$F(p) + G(Λ(p)),$

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, i.e. 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 [BergmannHerzogSilvaLouzeiroTenbrinckVidalNunez2020]. In the following we note 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)

1. $ξ^{(k+1)}_n = \operatorname{prox}_{\tau_k G_n^*}\Bigl(ξ_n^{(k)} + \tau_k \bigl(\log_n Λ (\bar p^{(k)})\bigr)^\flat\Bigr)$
2. $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)$
3. 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}$
4. $\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 in verse 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 that $Λ(m^{(k)})\neq n^{(k)}$ at some point. All these cases are covered in the algorithm.

Manopt.ChambollePockFunction
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(x) = F(x) + G( Λ(x) ),$

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

• 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 forwardoperator Λ and the linearizedforward_operatorcan be given as allocating functions(Manifolds, parameters) -> resultor 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[BergmannHerzogSilvaLouzeiroTenbrinckVidalNunez2020].

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 to spare allocations.
• Λ (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.)
• 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 will be called.
• stopping_criterion – (stopAtIteration(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)) the rectraction to use
• inverse_retraction_method - (default_inverse_retraction_method(M)) an inverse retraction to use.
• vector_transport_method - (default_vector_transport_method(M)) a vector transport to use
source
Manopt.ChambollePock!Function
ChambollePock(M, N, cost, x0, ξ0, m, n, prox_F, prox_G_dual, adjoint_linear_operator)

Perform the Riemannian Chambolle–Pock algorithm in place of x, ξ, and potentially m, n if they are not fixed. See ChambollePock for details and optional parameters.

source

## Problem & Options

Manopt.ChambollePockOptionsType
ChambollePockOptions <: PrimalDualOptions

stores all options and variables within a linearized or exact Chambolle Pock. The following list provides the order for the constructor, where the previous iterates are initialized automatically and values with a default may be left out.

• m - base point on $\mathcal M$
• n - base point on $\mathcal N$
• x - an initial point on $x^{(0)} ∈\mathcal M$ (and its previous iterate)
• ξ - an initial tangent vector $ξ^{(0)}∈T^*\mathcal N$ (and its previous iterate)
• xbar - the relaxed iterate used in the next dual update step (when using :primal relaxation)
• ξbar - the relaxed iterate used in the next primal update step (when using :dual relaxation)
• Θ – factor to damp the helping $\tilde x$
• primal_stepsize – (1/sqrt(8)) proximal parameter of the primal prox
• dual_stepsize – (1/sqrt(8)) proximal parameter of the dual prox
• acceleration – (0.) acceleration factor due to Chambolle & Pock
• relaxation – (1.) relaxation in the primal relaxation step (to compute xbar)
• relax – (_primal) which variable to relax (:primal or :dual)
• stop - a StoppingCriterion
• type – (exact) whether to perform an :exact or :linearized Chambolle-Pock
• update_primal_base ((p,o,i) -> o.m) function to update the primal base
• update_dual_base ((p,o,i) -> o.n) function to update the dual base
• retraction_method – (ExponentialRetraction()) the retraction to use
• inverse_retraction_method - (LogarithmicInverseRetraction()) an inverse retraction to use.
• vector_transport_method - (ParallelTransport()) a vector transport to use

where for the last two the functions a Problemp, Optionso and the current iterate i are the arguments. If you activate these to be different from the default identity, you have to provide p.Λ for the algorithm to work (which might be missing in the linearized case).

Constructor

ChambollePockOptions(m::P, n::Q, x::P, ξ::T, primal_stepsize::Float64, dual_stepsize::Float64;
acceleration::Float64 = 0.0,
relaxation::Float64 = 1.0,
relax::Symbol = :primal,
stopping_criterion::StoppingCriterion = StopAfterIteration(300),
variant::Symbol = :exact,
update_primal_base::Union{Function,Missing} = missing,
update_dual_base::Union{Function,Missing} = missing,
retraction_method = ExponentialRetraction(),
inverse_retraction_method = LogarithmicInverseRetraction(),
vector_transport_method = ParallelTransport(),
)
source

## Useful Terms

Manopt.primal_residualFunction
primal_residual(p, o, x_old, ξ_old, n_old)

Compute the primal residual at current iterate $k$ given the necessary values $x_{k-1}, ξ_{k-1}$, and $n_{k-1}$ from the previous iterate.

$\Bigl\lVert \frac{1}{σ}\operatorname{retr}^{-1}_{x_{k}}x_{k-1} - V_{x_k\gets m_k}\bigl(DΛ^*(m_k)\bigl[V_{n_k\gets n_{k-1}}ξ_{k-1} - ξ_k \bigr] \Bigr\rVert$

where $V_{⋅\gets⋅}$ is the vector transport used in the ChambollePockOptions

source
Manopt.dual_residualFunction
dual_residual(p, o, x_old, ξ_old, n_old)

Compute the dual residual at current iterate $k$ given the necessary values $x_{k-1}, ξ_{k-1}$, and $n_{k-1}$ from the previous iterate. The formula is slightly different depending on the o.variant used:

For the :lineaized it reads

$\Bigl\lVert \frac{1}{τ}\bigl( V_{n_{k}\gets n_{k-1}}(ξ_{k-1}) - ξ_k \bigr) - DΛ(m_k)\bigl[ V_{m_k\gets x_k}\operatorname{retr}^{-1}_{x_{k}}x_{k-1} \bigr] \Bigr\rVert$

and for the :exact variant

$\Bigl\lVert \frac{1}{τ} V_{n_{k}\gets n_{k-1}}(ξ_{k-1}) - \operatorname{retr}^{-1}_{n_{k}}\bigl( Λ(\operatorname{retr}_{m_{k}}(V_{m_k\gets x_k}\operatorname{retr}^{-1}_{x_{k}}x_{k-1})) \bigr) \Bigr\rVert$

where in both cases $V_{⋅\gets⋅}$ is the vector transport used in the ChambollePockOptions.

source

## Debug

Manopt.DebugDualResidualType
DebugDualResidual <: DebugAction

A Debug action to print the dual residual. The constructor accepts a printing function and some (shared) storage, which should at least record :x, :ξ and :n.

source
Manopt.DebugPrimalResidualType
DebugPrimalResidual <: DebugAction

A Debug action to print the primal residual. The constructor accepts a printing function and some (shared) storage, which should at least record :x, :ξ and :n.

source
Manopt.DebugPrimalDualResidualType
DebugPrimalDualResidual <: DebugAction

A Debug action to print the primaldual residual. The constructor accepts a printing function and some (shared) storage, which should at least record :x, :ξ and :n.

source

## Record

Manopt.RecordDualChangeFunction
RecordDualChange()

Create the action either with a given (shared) Storage, which can be set to the values Tuple, if that is provided).

source

## Internals

Manopt.update_prox_parameters!Function
update_prox_parameters!(o)`

update the prox parameters as described in Algorithm 2 of Chambolle, Pock, 2010, i.e.

1. $θ_{n} = \frac{1}{\sqrt{1+2γτ_n}}$
2. $τ_{n+1} = θ_nτ_n$
3. $σ_{n+1} = \frac{σ_n}{θ_n}$
source