GitHub

Primal-dual Riemannian semismooth Newton algorithm

The Primal-dual Riemannian semismooth Newton Algorithm is a second-order method derived from the ChambollePock algorithm.

The aim is to solve an optimization problem on a manifold with a cost function of the form

\[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 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 comes down to applying the Riemannian semismooth Newton method to the rewritten primal-dual optimality conditions. Define the vector field $X: \mathcal{M} \times T_{n}^{*} \mathcal{N} \rightarrow T \mathcal{M} \times T_{n}^{*} \mathcal{N}$ as

\[X\left(p, \xi_{n}\right):=\left(\begin{array}{c} -\log _{p} \operatorname{prox}_{\sigma F}\left(\exp _{p}\left(\mathcal{P}_{p \leftarrow m}\left(-\sigma\left(D_{m} \Lambda\right)^{*}\left[\mathcal{P}_{\Lambda(m) \leftarrow n} \xi_{n}\right]\right)^{\sharp}\right)\right) \\ \xi_{n}-\operatorname{prox}_{\tau G_{n}^{*}}\left(\xi_{n}+\tau\left(\mathcal{P}_{n \leftarrow \Lambda(m)} D_{m} \Lambda\left[\log _{m} p\right]\right)^{\flat}\right) \end{array}\right)\]

and solve for $X(p,ξ_{n})=0$.

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$, $\tau$.

The algorithm performs the steps $k=0,1,…$ (until a StoppingCriterion is reached)

  1. Choose any element

    \[V^{(k)} ∈ ∂_C X(p^{(k)},ξ_n^{(k)})\]

    of the Clarke generalized covariant derivative
  2. Solve

    \[V^{(k)} [(d_p^{(k)}, d_n^{(k)})] = - X(p^{(k)},ξ_n^{(k)})\]

    in the vector space $T_{p^{(k)}} \mathcal{M} \times T_{n}^{*} \mathcal{N}$
  3. Update

    \[p^{(k+1)} := \exp_{p^{(k)}}(d_p^{(k)})\]

    and

    \[ξ_n^{(k+1)} := ξ_n^{(k)} + d_n^{(k)}\]

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 that $Λ(m^{(k)})\neq n^{(k)}$ at some point. The solver performs the transports of the dual variable and of $DΛ(m)[⋅]$ to $n$; the transport $\mathcal{P}_{\Lambda(m) \leftarrow n} \xi_{n}$ inside the adjoint, however, is expected to be part of the provided adjoint_linearized_operator, which is called with m, n and $ξ_n$ for this purpose.

Manopt.primal_dual_semismooth_Newton — Function
primal_dual_semismooth_Newton(M, N, cost, p, X, m, n, prox_F, diff_prox_F, prox_G_dual, diff_prox_G_dual, linearized_forward_operator, adjoint_linearized_operator; kwargs...)
primal_dual_semismooth_Newton!(M, N, cost, p, X, m, n, prox_F, diff_prox_F, prox_G_dual, diff_prox_G_dual, linearized_forward_operator, adjoint_linearized_operator; kwargs...)

Perform the Primal-Dual Riemannian semismooth Newton algorithm.

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

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

where $F: \mathcal M → \overline{ℝ}$, $G: \mathcal N → \overline{ℝ}$, and $Λ: \mathcal M → \mathcal N$.

Input

  • M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
  • N::AbstractManifold: a Riemannian manifold $\mathcal{N}$
  • cost: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
  • p, X: primal and dual start points $p∈\mathcal{M}$ and $X ∈ T_n\mathcal{N}$
  • m,n: base points on $\mathcal{M}$ and $\mathcal{N}$, respectively.
  • linearized_forward_operator: the linearization $DΛ(⋅)[⋅]$ of the operator $Λ(⋅)$.
  • 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$
  • diff_prox_F, diff_prox_G_dual: the (Clarke Generalized) differentials of the proximal maps of $F$ and $G^\ast_n$

For more details on the algorithm, see [DL21].

Keyword arguments

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.

source
Manopt.primal_dual_semismooth_Newton! — Function
primal_dual_semismooth_Newton(M, N, cost, p, X, m, n, prox_F, diff_prox_F, prox_G_dual, diff_prox_G_dual, linearized_forward_operator, adjoint_linearized_operator; kwargs...)
primal_dual_semismooth_Newton!(M, N, cost, p, X, m, n, prox_F, diff_prox_F, prox_G_dual, diff_prox_G_dual, linearized_forward_operator, adjoint_linearized_operator; kwargs...)

Perform the Primal-Dual Riemannian semismooth Newton algorithm.

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

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

where $F: \mathcal M → \overline{ℝ}$, $G: \mathcal N → \overline{ℝ}$, and $Λ: \mathcal M → \mathcal N$.

Input

  • M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
  • N::AbstractManifold: a Riemannian manifold $\mathcal{N}$
  • cost: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
  • p, X: primal and dual start points $p∈\mathcal{M}$ and $X ∈ T_n\mathcal{N}$
  • m,n: base points on $\mathcal{M}$ and $\mathcal{N}$, respectively.
  • linearized_forward_operator: the linearization $DΛ(⋅)[⋅]$ of the operator $Λ(⋅)$.
  • 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$
  • diff_prox_F, diff_prox_G_dual: the (Clarke Generalized) differentials of the proximal maps of $F$ and $G^\ast_n$

For more details on the algorithm, see [DL21].

Keyword arguments

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.

source

Objective

Manopt.PrimalDualManifoldSemismoothNewtonObjective — Type
PrimalDualManifoldSemismoothNewtonObjective{TC, PF, DPF, PG, DPG, LFO, TALO, L} <: AbstractPrimalDualManifoldObjective{TC, PF}

Describes a Problem for the Primal-dual Riemannian semismooth Newton algorithm. [DL21]

Fields

  • cost: $F + G(Λ(⋅))$ to evaluate interim cost function values
  • linearized_forward_operator!: the linearization $DΛ(⋅)[⋅]$ of the operator $Λ(⋅)$.
  • adjoint_linearized_operator!: the adjoint differential $(DΛ)^* : T\mathcal{N} → T\mathcal{M}$
  • prox_f!: the proximal map belonging to $F$
  • diff_prox_f!: the (Clarke Generalized) differential of the proximal maps of $F$
  • prox_g_dual!: the proximal map belonging to $G^\ast_n$
  • diff_prox_g_dual!: the (Clarke Generalized) differential of the proximal maps of $G^\ast_n$
  • Λ!: the exact forward operator. This operator is required if Λ(m)=n does not hold.

Constructor

PrimalDualManifoldSemismoothNewtonObjective(cost, prox_F, diff_prox_F, prox_G_dual, diff_prox_G_dual, linearized_forward_operator, adjoint_linearized_operator; Λ=missing, p=missing, evaluation=AllocatingEvaluation())

A point p= wraps the cost for points that are numbers.

source

State

Manopt.PrimalDualSemismoothNewtonState — Type
PrimalDualSemismoothNewtonState <: AbstractPrimalDualSolverState

Fields

The functions update_primal_base and update_dual_base are called with an AbstractManoptProblem amp, an AbstractManoptSolverState ams and the current iteration k as arguments. If you activate these to be different from the default identity, you have to provide the exact forward operator Λ (by default missing) for the algorithm to work.

Constructor

PrimalDualSemismoothNewtonState(M::AbstractManifold, N::AbstractManifold; kwargs...)

Generate a state for the primal_dual_semismooth_Newton.

Keyword arguments

source

Internal functions

Solver specific debug output

DebugDualBaseIterate, DebugDualBaseChange, DebugPrimalBaseIterate, DebugPrimalBaseChange, DebugDualChange, DebugDualIterate, DebugDualResidual, DebugPrimalChange, DebugPrimalIterate, DebugPrimalResidual, DebugPrimalDualResidual

Solver specific recording actions

RecordDualBaseIterate, RecordDualBaseChange, RecordPrimalBaseIterate, RecordPrimalBaseChange, RecordDualChange, RecordDualIterate, RecordPrimalChange, RecordPrimalIterate

Technical details

The primal_dual_semismooth_Newton solver requires the following functions of a manifold to be available for both the manifolds $\mathcal M$ and $\mathcal N$

Literature

[DL21]
W. Diepeveen and J. Lellmann. An Inexact Semismooth Newton Method on Riemannian Manifolds with Application to Duality-Based Total Variation Denoising. SIAM Journal on Imaging Sciences 14, 1565–1600 (2021), arXiv:2102.10309.