Edit on GitHub

The Primal-dual Riemannian semismooth Newton Algorithm

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

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, 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 comes down to applying the Riemannian semismooth Newton method to the rewritten primal-dual optimality conditions, i.e., we define the vector field $X: \mathcal{M} \times \mathcal{T}_{n}^{*} \mathcal{N} \rightarrow \mathcal{T} \mathcal{M} \times \mathcal{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)} ∈ \mathcal T_{n}^{*}\mathcal N$, and primal and dual step sizes $\sigma$, $\tau$.

The algorithms performs the steps $k=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 $\mathcal{T}_{p^{(k)}} \mathcal{M} \times \mathcal{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. All these cases are covered in the algorithm.

Manopt.primal_dual_semismooth_Newton — Function
primal_dual_semismooth_Newton(M, N, cost, x0, ξ0, m, n, prox_F, diff_prox_F, prox_G_dual, diff_prox_dual_G, linearized_operator, adjoint_linearized_operator)

Perform the Primal-Dual Riemannian Semismooth Newton algorithm.

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

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

where $F\colon\mathcal M \to \overline{ℝ}$, $G\colon\mathcal N \to \overline{ℝ}$, and $\Lambda\colon\mathcal M \to \mathcal N$. The remaining input parameters are

  • x,ξ primal and dual start points $x\in\mathcal M$ and $\xi\in 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)\colon T_{m}\mathcal M \to T_{Λ(m)}\mathcal N$
  • prox_F, prox_G_Dual the proximal maps of $F$ and $G^\ast_n$
  • diff_prox_F, diff_prox_dual_G the (Clarke Generalized) differentials of the proximal maps of $F$ and $G^\ast_n$

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

Optional Parameters

  • primal_stepsize – (1/sqrt(8)) proximal parameter of the primal prox
  • Λ (missing) the exact operator, that is required if Λ(m)=n does not hold;

missing indicates, that the forward operator is exact.

  • dual_stepsize – (1/sqrt(8)) proximal parameter of the dual prox
  • reg_param – (1e-5) regularisation parameter for the Newton matrix

Note that this changes the arguments the forward_operator will be called.

  • stopping_criterion – (stopAtIteration(50)) 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

Output

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

source
Manopt.primal_dual_semismooth_Newton! — Function
primal_dual_semismooth_Newton(M, N, cost, x0, ξ0, m, n, prox_F, diff_prox_F, prox_G_dual, diff_prox_G_dual, linearized_forward_operator, adjoint_linearized_operator)

Perform the Riemannian Primal-dual Riemannian semismooth Newton algorithm in place of x, ξ, and potentially m, n if they are not fixed. See primal_dual_semismooth_Newton for details and optional parameters.

source

Options

Manopt.PrimalDualSemismoothNewtonOptions — Type
PrimalDualSemismoothNewtonOptions <: PrimalDualOptions
  • m - base point on $ \mathcal M $
  • n - base point on $ \mathcal N $
  • x - an initial point on $x^{(0)} \in \mathcal M$ (and its previous iterate)
  • ξ - an initial tangent vector $\xi^{(0)}\in T_{n}^*\mathcal N$ (and its previous iterate)
  • primal_stepsize – (1/sqrt(8)) proximal parameter of the primal prox
  • dual_stepsize – (1/sqrt(8)) proximal parameter of the dual prox
  • reg_param – (1e-5) regularisation parameter for the Newton matrix
  • stop - a StoppingCriterion
  • 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 – (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

where for the last two the functions a Problem p, Options o 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).

Constructor

PrimalDualSemismoothNewtonOptions(M::AbstractManifold,
    m::P, n::Q, x::P, ξ::T, primal_stepsize::Float64, dual_stepsize::Float64, reg_param::Float64;
    stopping_criterion::StoppingCriterion = StopAfterIteration(50),
    update_primal_base::Union{Function,Missing} = missing,
    update_dual_base::Union{Function,Missing} = missing,
    retraction_method = default_retraction_method(M),
    inverse_retraction_method = default_inverse_retraction_method(M),
    vector_transport_method = default_vector_transport_method(M),
)
source
  • DiepeveenLellmann2021

    W. Diepeveen, J. Lellmann: An Inexact Semismooth Newton Method on Riemannian Manifolds with Application to Duality-Based Total Variation Denoising, SIAM Journal on Imaging Sciences, 2021. doi: 10.1137/21M1398513