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$. The remaining input parameters are

  • 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$. The remaining input parameters are

  • 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, evaluation=AllocatingEvaluation())
source

State

Manopt.PrimalDualSemismoothNewtonState — Type
PrimalDualSemismoothNewtonState <: AbstractPrimalDualSolverState

Fields

  • callbacks::D: provided callback functions given as a dictionary with symbols as keys
  • dual_stepsize::Float64: proximal parameter of the dual prox
  • inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
  • m::P: a point on the manifold $\mathcal{M}$
  • n::Q: a point on the manifold $\mathcal{N}$
  • p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
  • primal_stepsize::Float64: proximal parameter of the primal prox
  • regularization_parameter::Float64: regularization parameter for the Newton matrix
  • retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
  • stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
  • update_dual_base: function to update the dual base
  • update_primal_base: function to update the primal base
  • vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
  • X::T: a tangent vector at the point $n$ on the manifold $\mathcal{N}$

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

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.