Difference of convex

difference_of_convex_algorithm(M, f, g, ∂h, p=rand(M); kwargs...)
difference_of_convex_algorithm(M, mdco, p; kwargs...)
difference_of_convex_algorithm!(M, f, g, ∂h, p; kwargs...)
difference_of_convex_algorithm!(M, mdco, p; kwargs...)

Compute the difference of convex algorithm [BFSS24] to minimize

\[ \operatorname*{arg\,min}_{p∈\mathcal M}\ g(p) - h(p)\]

where you need to provide $f(p) = g(p) - h(p)$, $g$ and the subdifferential $∂h$ of $h$.

This algorithm performs the following steps given a start point p= $p^{(0)}$. Then repeat for $k=0,1,…$

1. Take $X^{(k)} ∈ ∂h(p^{(k)})$
2. Set the next iterate to the solution of the subproblem

\[ p^{(k+1)} ∈ \operatorname*{arg\,min}_{q ∈ \mathcal M} g(q) - ⟨X^{(k)}, \log_{p^{(k)}}q⟩\]

until the stopping criterion (see the stopping_criterion keyword is fulfilled.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$

• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> vtotal cost function f = g - h

• g: the smooth part $g$of the cost function

• ∂h: the subgradient $∂h: \mathcal M → T\mathcal M$ of $h$ as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place. This function should always only return one element from the subgradient.

• p: a point on the manifold $\mathcal M$

Keyword arguments

• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• gradient=nothing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion=
• grad_g=nothing: specify the gradient of g. If specified, a subsolver is automatically set up.
• stopping_criterion=StopAfterIteration(200)|StopWhenChangeLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• g=nothing: specify the function g If specified, a subsolver is automatically set up.
• sub_cost=LinearizedDCCost(g, p, initial_vector): a cost to be used within the default sub_problem. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_grad=LinearizedDCGrad(grad_g, p, initial_vector; evaluation=evaluation): gradient to be used within the default sub_problem. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_hess: (a finite difference approximation using sub_grad by default): specify a Hessian of the sub_cost, which the default solver, see sub_state= needs. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_kwargs=(;): a named tuple of keyword arguments that are passed to decorate_objective! of the sub solvers objective, the decorate_state! of the subsovlers state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hessif provided the objective used within sub_problem. This is used to define the sub_problem= keyword and has hence no effect, if you set sub_problem directly.
• sub_state=(GradientDescentState or TrustRegionsState if sub_hess is provided): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• sub_problem=DefaultManoptProblem(M, sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_stopping_criterion=StopAfterIteration(300)|StopWhenStepsizeLess(1e-9)|StopWhenGradientNormLess(1e-9): a stopping criterion used withing the default sub_state= This is used to define the sub_state= keyword and has hence no effect, if you set sub_state directly.
• sub_stepsize=ArmijoLinesearch(M)) specify a step size used within the sub_state. This is used to define the sub_state= keyword and has hence no effect, if you set sub_state directly.
• X=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$to specify the representation of a tangent vector

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.

difference_of_convex_algorithm(M, f, g, ∂h, p=rand(M); kwargs...)
difference_of_convex_algorithm(M, mdco, p; kwargs...)
difference_of_convex_algorithm!(M, f, g, ∂h, p; kwargs...)
difference_of_convex_algorithm!(M, mdco, p; kwargs...)

Compute the difference of convex algorithm [BFSS24] to minimize

\[ \operatorname*{arg\,min}_{p∈\mathcal M}\ g(p) - h(p)\]

where you need to provide $f(p) = g(p) - h(p)$, $g$ and the subdifferential $∂h$ of $h$.

This algorithm performs the following steps given a start point p= $p^{(0)}$. Then repeat for $k=0,1,…$

1. Take $X^{(k)} ∈ ∂h(p^{(k)})$
2. Set the next iterate to the solution of the subproblem

\[ p^{(k+1)} ∈ \operatorname*{arg\,min}_{q ∈ \mathcal M} g(q) - ⟨X^{(k)}, \log_{p^{(k)}}q⟩\]

until the stopping criterion (see the stopping_criterion keyword is fulfilled.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$

• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> vtotal cost function f = g - h

• g: the smooth part $g$of the cost function

• ∂h: the subgradient $∂h: \mathcal M → T\mathcal M$ of $h$ as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place. This function should always only return one element from the subgradient.

• p: a point on the manifold $\mathcal M$

Keyword arguments

• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• gradient=nothing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion=
• grad_g=nothing: specify the gradient of g. If specified, a subsolver is automatically set up.
• stopping_criterion=StopAfterIteration(200)|StopWhenChangeLess(1e-8): a functor indicating that the stopping criterion is fulfilled
• g=nothing: specify the function g If specified, a subsolver is automatically set up.
• sub_cost=LinearizedDCCost(g, p, initial_vector): a cost to be used within the default sub_problem. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_grad=LinearizedDCGrad(grad_g, p, initial_vector; evaluation=evaluation): gradient to be used within the default sub_problem. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_hess: (a finite difference approximation using sub_grad by default): specify a Hessian of the sub_cost, which the default solver, see sub_state= needs. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_kwargs=(;): a named tuple of keyword arguments that are passed to decorate_objective! of the sub solvers objective, the decorate_state! of the subsovlers state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hessif provided the objective used within sub_problem. This is used to define the sub_problem= keyword and has hence no effect, if you set sub_problem directly.
• sub_state=(GradientDescentState or TrustRegionsState if sub_hess is provided): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• sub_problem=DefaultManoptProblem(M, sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_stopping_criterion=StopAfterIteration(300)|StopWhenStepsizeLess(1e-9)|StopWhenGradientNormLess(1e-9): a stopping criterion used withing the default sub_state= This is used to define the sub_state= keyword and has hence no effect, if you set sub_state directly.
• sub_stepsize=ArmijoLinesearch(M)) specify a step size used within the sub_state. This is used to define the sub_state= keyword and has hence no effect, if you set sub_state directly.
• X=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$to specify the representation of a tangent vector

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.

difference_of_convex_proximal_point(M, grad_h, p=rand(M); kwargs...)
difference_of_convex_proximal_point(M, mdcpo, p=rand(M); kwargs...)
difference_of_convex_proximal_point!(M, grad_h, p; kwargs...)
difference_of_convex_proximal_point!(M, mdcpo, p; kwargs...)

Compute the difference of convex proximal point algorithm [SO15] to minimize

\[ \operatorname*{arg\,min}_{p∈\mathcal M} g(p) - h(p)\]

where you have to provide the subgradient $∂h$ of $h$ and either

• the proximal map $\operatorname{prox}_{λg}$ of g as a function prox_g(M, λ, p) or prox_g(M, q, λ, p)
• the functions g and grad_g to compute the proximal map using a sub solver
• your own sub-solver, specified by sub_problem=and sub_state=

This algorithm performs the following steps given a start point p= $p^{(0)}$. Then repeat for $k=0,1,…$

1. $X^{(k)} ∈ \operatorname{grad} h(p^{(k)})$
2. $q^{(k)} = \operatorname{retr}_{p^{(k)}}(λ_kX^{(k)})$
3. $r^{(k)} = \operatorname{prox}_{λ_kg}(q^{(k)})$
4. $X^{(k)} = \operatorname{retr}^{-1}_{p^{(k)}}(r^{(k)})$
5. Compute a stepsize $s_k$ and
6. set $p^{(k+1)} = \operatorname{retr}_{p^{(k)}}(s_kX^{(k)})$.

until the stopping_criterion is fulfilled.

See [ACOO20] for more details on the modified variant, where steps 4-6 are slightly changed, since here the classical proximal point method for DC functions is obtained for $s_k = 1$ and one can hence employ usual line search method.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> vtotal cost function f = g - h
• grad_h: the (Riemannian) gradient $\operatorname{grad}h: \mathcal M → T_{p}\mathcal M$ of h as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
• p: a point on the manifold $\mathcal M$

Keyword arguments

• λ: ( k -> 1/2 ) a function returning the sequence of prox parameters $λ_k$
• cost=nothing: provide the cost f, for debug reasons / analysis
• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• gradient=nothing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion
• prox_g=nothing: specify a proximal map for the sub problem or both of the following
• g=nothing: specify the function g.
• grad_g=nothing: specify the gradient of g. If both gand grad_g are specified, a subsolver is automatically set up.
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize=ConstantLength(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion=StopAfterIteration(200)|StopWhenChangeLess(1e-8)): a functor indicating that the stopping criterion is fulfilled A StopWhenGradientNormLess(1e-8) is added with |, when a gradient is provided.
• sub_cost=ProximalDCCost(g, copy(M, p), λ(1))): cost to be used within the default sub_problem that is initialized as soon as g is provided. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_grad=ProximalDCGrad(grad_g, copy(M, p), λ(1); evaluation=evaluation): gradient to be used within the default sub_problem, that is initialized as soon as grad_g is provided. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_hess: (a finite difference approximation using sub_grad by default): specify a Hessian of the sub_cost, which the default solver, see sub_state= needs.
• sub_kwargs=(;): a named tuple of keyword arguments that are passed to decorate_objective! of the sub solvers objective, the decorate_state! of the subsovlers state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hessif provided the objective used within sub_problem. This is used to define the sub_problem= keyword and has hence no effect, if you set sub_problem directly.
• sub_problem=DefaultManoptProblem(M, sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state=(GradientDescentState or TrustRegionsState if sub_hess is provided): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• sub_stopping_criterion=(StopAfterIteration(300)|[StopWhenGradientNormLess](@ref)(1e-8): a functor indicating that the stopping criterion is fulfilled This is used to define thesubstate=keyword and has hence no effect, if you setsubstate` directly.

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.

difference_of_convex_proximal_point(M, grad_h, p=rand(M); kwargs...)
difference_of_convex_proximal_point(M, mdcpo, p=rand(M); kwargs...)
difference_of_convex_proximal_point!(M, grad_h, p; kwargs...)
difference_of_convex_proximal_point!(M, mdcpo, p; kwargs...)

Compute the difference of convex proximal point algorithm [SO15] to minimize

\[ \operatorname*{arg\,min}_{p∈\mathcal M} g(p) - h(p)\]

where you have to provide the subgradient $∂h$ of $h$ and either

• the proximal map $\operatorname{prox}_{λg}$ of g as a function prox_g(M, λ, p) or prox_g(M, q, λ, p)
• the functions g and grad_g to compute the proximal map using a sub solver
• your own sub-solver, specified by sub_problem=and sub_state=

This algorithm performs the following steps given a start point p= $p^{(0)}$. Then repeat for $k=0,1,…$

1. $X^{(k)} ∈ \operatorname{grad} h(p^{(k)})$
2. $q^{(k)} = \operatorname{retr}_{p^{(k)}}(λ_kX^{(k)})$
3. $r^{(k)} = \operatorname{prox}_{λ_kg}(q^{(k)})$
4. $X^{(k)} = \operatorname{retr}^{-1}_{p^{(k)}}(r^{(k)})$
5. Compute a stepsize $s_k$ and
6. set $p^{(k+1)} = \operatorname{retr}_{p^{(k)}}(s_kX^{(k)})$.

until the stopping_criterion is fulfilled.

See [ACOO20] for more details on the modified variant, where steps 4-6 are slightly changed, since here the classical proximal point method for DC functions is obtained for $s_k = 1$ and one can hence employ usual line search method.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ ℝ$ implemented as (M, p) -> vtotal cost function f = g - h
• grad_h: the (Riemannian) gradient $\operatorname{grad}h: \mathcal M → T_{p}\mathcal M$ of h as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
• p: a point on the manifold $\mathcal M$

Keyword arguments

• λ: ( k -> 1/2 ) a function returning the sequence of prox parameters $λ_k$
• cost=nothing: provide the cost f, for debug reasons / analysis
• evaluation=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating its result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• gradient=nothing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion
• prox_g=nothing: specify a proximal map for the sub problem or both of the following
• g=nothing: specify the function g.
• grad_g=nothing: specify the gradient of g. If both gand grad_g are specified, a subsolver is automatically set up.
• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize=ConstantLength(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion=StopAfterIteration(200)|StopWhenChangeLess(1e-8)): a functor indicating that the stopping criterion is fulfilled A StopWhenGradientNormLess(1e-8) is added with |, when a gradient is provided.
• sub_cost=ProximalDCCost(g, copy(M, p), λ(1))): cost to be used within the default sub_problem that is initialized as soon as g is provided. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_grad=ProximalDCGrad(grad_g, copy(M, p), λ(1); evaluation=evaluation): gradient to be used within the default sub_problem, that is initialized as soon as grad_g is provided. This is used to define the sub_objective= keyword and has hence no effect, if you set sub_objective directly.
• sub_hess: (a finite difference approximation using sub_grad by default): specify a Hessian of the sub_cost, which the default solver, see sub_state= needs.
• sub_kwargs=(;): a named tuple of keyword arguments that are passed to decorate_objective! of the sub solvers objective, the decorate_state! of the subsovlers state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hessif provided the objective used within sub_problem. This is used to define the sub_problem= keyword and has hence no effect, if you set sub_problem directly.
• sub_problem=DefaultManoptProblem(M, sub_objective): specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state=(GradientDescentState or TrustRegionsState if sub_hess is provided): a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• sub_stopping_criterion=(StopAfterIteration(300)|[StopWhenGradientNormLess](@ref)(1e-8): a functor indicating that the stopping criterion is fulfilled This is used to define thesubstate=keyword and has hence no effect, if you setsubstate` directly.

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.

DifferenceOfConvexState{Pr,St,P,T,SC<:StoppingCriterion} <:
           AbstractManoptSolverState

A struct to store the current state of the [difference_of_convex_algorithm])(@ref). It comes in two forms, depending on the realisation of the subproblem.

Fields

• p::P: a point on the manifold $\mathcal M$ storing the current iterate
• X::T: a tangent vector at the point $p$ on the manifold $\mathcal M$storing a subgradient at the current iterate
• sub_problem::Union{AbstractManoptProblem, F}: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptProblem, F}: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled

The sub task consists of a method to solve

\[ \operatorname*{arg\,min}_{q∈\mathcal M}\ g(p) - ⟨X, \log_p q⟩\]

is needed. Besides a problem and a state, one can also provide a function and an AbstractEvaluationType, respectively, to indicate a closed form solution for the sub task.

Constructors

DifferenceOfConvexState(M, sub_problem, sub_state; kwargs...)
DifferenceOfConvexState(M, sub_solver; evaluation=InplaceEvaluation(), kwargs...)

Generate the state either using a solver from Manopt, given by an AbstractManoptProblem sub_problem and an AbstractManoptSolverState sub_state, or a closed form solution sub_solver for the sub-problem the function expected to be of the form (M, p, X) -> q or (M, q, p, X) -> q, where by default its AbstractEvaluationType evaluation is in-place of q. Here the elements passed are the current iterate p and the subgradient X of h can be passed to that function.

further keyword arguments

• p=rand(M): a point on the manifold $\mathcal M$ to specify the initial value
• stopping_criterion=StopAfterIteration(200): a functor indicating that the stopping criterion is fulfilled
• X=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$to specify the representation of a tangent vector

DifferenceOfConvexProximalState{P, T, Pr, St, S<:Stepsize, SC<:StoppingCriterion, RTR<:AbstractRetractionMethod, ITR<:AbstractInverseRetractionMethod}
    <: AbstractSubProblemSolverState

A struct to store the current state of the algorithm as well as the form. It comes in two forms, depending on the realisation of the subproblem.

Fields

• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• p::P: a point on the manifold $\mathcal M$ storing the current iterate
• q::P: a point on the manifold $\mathcal M$ storing the gradient step
• r::P: a point on the manifold $\mathcal M$ storing the result of the proximal map
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize: a functor inheriting from Stepsize to determine a step size
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• X, Y: the current gradient and descent direction, respectively their common type is set by the keyword X
• sub_problem::Union{AbstractManoptProblem, F}: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state::Union{AbstractManoptProblem, F}: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.

Constructor

DifferenceOfConvexProximalState(M::AbstractManifold, sub_problem, sub_state; kwargs...)

construct an difference of convex proximal point state

DifferenceOfConvexProximalState(M::AbstractManifold, sub_problem;
    evaluation=AllocatingEvaluation(), kwargs...

)

construct an difference of convex proximal point state, where sub_problem is a closed form solution with evaluation as type of evaluation.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• sub_problem: specify a problem for a solver or a closed form solution function, which can be allocating or in-place.
• sub_state: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.

Keyword arguments

• inverse_retraction_method=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses

• p=rand(M): a point on the manifold $\mathcal M$ to specify the initial value

• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions

• stepsize=ConstantLength(): a functor inheriting from Stepsize to determine a step size

• stopping_criterion=StopWhenChangeLess`(1e-8): a functor indicating that the stopping criterion is fulfilled

• X=zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal M$to specify the representation of a tangent vector

ManifoldDifferenceOfConvexObjective{E} <: AbstractManifoldCostObjective{E}

Specify an objective for a difference_of_convex_algorithm.

The objective $f: \mathcal M → ℝ$ is given as

\[ f(p) = g(p) - h(p)\]

where both $g$ and $h$ are convex, lower semicontinuous and proper. Furthermore the subdifferential $∂h$ of $h$ is required.

Fields

• cost: an implementation of $f(p) = g(p)-h(p)$ as a function f(M,p).
• ∂h!!: a deterministic version of $∂h: \mathcal M → T\mathcal M$, in the sense that calling ∂h(M, p) returns a subgradient of $h$ at p and if there is more than one, it returns a deterministic choice.

Note that the subdifferential might be given in two possible signatures

• ∂h(M,p) which does an AllocatingEvaluation
• ∂h!(M, X, p) which does an InplaceEvaluation in place of X.

LinearizedDCCost

A functor (M,q) → ℝ to represent the inner problem of a ManifoldDifferenceOfConvexObjective. This is a cost function of the form

\[ F_{p_k,X_k}(p) = g(p) - ⟨X_k, \log_{p_k}p⟩\]

for a point p_k and a tangent vector X_k at p_k (for example outer iterates) that are stored within this functor as well.

Fields

• g a function
• pk a point on a manifold
• Xk a tangent vector at pk

Both interim values can be set using set_parameter!(::LinearizedDCCost, ::Val{:p}, p) and set_parameter!(::LinearizedDCCost, ::Val{:X}, X), respectively.

Constructor

LinearizedDCCost(g, p, X)

LinearizedDCGrad

A functor (M,X,p) → ℝ to represent the gradient of the inner problem of a ManifoldDifferenceOfConvexObjective. This is a gradient function of the form

\[ F_{p_k,X_k}(p) = g(p) - ⟨X_k, \log_{p_k}p⟩\]

its gradient is given by using $F=F_1(F_2(p))$, where $F_1(X) = ⟨X_k,X⟩$ and $F_2(p) = \log_{p_k}p$ and the chain rule as well as the adjoint differential of the logarithmic map with respect to its argument for $D^*F_2(p)$

\[ \operatorname{grad} F(q) = \operatorname{grad}f(q) - DF_2^*(q)[X]\]

for a point pk and a tangent vector Xk at pk (the outer iterates) that are stored within this functor as well

Fields

• grad_g!! the gradient of $g$ (see also LinearizedDCCost)
• pk a point on a manifold
• Xk a tangent vector at pk

Both interim values can be set using set_parameter!(::LinearizedDCGrad, ::Val{:p}, p) and set_parameter!(::LinearizedDCGrad, ::Val{:X}, X), respectively.

Constructor

LinearizedDCGrad(grad_g, p, X; evaluation=AllocatingEvaluation())

Where you specify whether grad_g is AllocatingEvaluation or InplaceEvaluation, while this function still provides both signatures.

ManifoldDifferenceOfConvexProximalObjective{E} <: Problem

Specify an objective difference_of_convex_proximal_point algorithm. The problem is of the form

\[ \operatorname*{arg\,min}_{p∈\mathcal M} g(p) - h(p)\]

where both $g$ and $h$ are convex, lower semicontinuous and proper.

Fields

• cost: implementation of $f(p) = g(p)-h(p)$
• gradient: the gradient of the cost
• grad_h!!: a function $\operatorname{grad}h: \mathcal M → T\mathcal M$,

Note that both the gradients might be given in two possible signatures as allocating or in-place.

Constructor

ManifoldDifferenceOfConvexProximalObjective(gradh; cost=nothing, gradient=nothing)

an note that neither cost nor gradient are required for the algorithm, just for eventual debug or stopping criteria.

ProximalDCCost

A functor (M, p) → ℝ to represent the inner cost function of a ManifoldDifferenceOfConvexProximalObjective. This is the cost function of the proximal map of g.

\[ F_{p_k}(p) = \frac{1}{2λ}d_{\mathcal M}(p_k,p)^2 + g(p)\]

for a point pk and a proximal parameter $λ$.

Fields

• g - a function
• pk - a point on a manifold
• λ - the prox parameter

Both interim values can be set using set_parameter!(::ProximalDCCost, ::Val{:p}, p) and set_parameter!(::ProximalDCCost, ::Val{:λ}, λ), respectively.

Constructor

ProximalDCCost(g, p, λ)

ProximalDCGrad

A functor (M,X,p) → ℝ to represent the gradient of the inner cost function of a ManifoldDifferenceOfConvexProximalObjective. This is the gradient function of the proximal map cost function of g. Based on

\[ F_{p_k}(p) = \frac{1}{2λ}d_{\mathcal M}(p_k,p)^2 + g(p)\]

it reads

\[ \operatorname{grad} F_{p_k}(p) = \operatorname{grad}} g(p) - \frac{1}{λ}\log_p p_k\]

for a point pk and a proximal parameter λ.

Fields

• grad_g - a gradient function
• pk - a point on a manifold
• λ - the prox parameter

Both interim values can be set using set_parameter!(::ProximalDCGrad, ::Val{:p}, p) and set_parameter!(::ProximalDCGrad, ::Val{:λ}, λ), respectively.

Constructor

ProximalDCGrad(grad_g, pk, λ; evaluation=AllocatingEvaluation())

Where you specify whether grad_g is AllocatingEvaluation or InplaceEvaluation, while this function still always provides both signatures.

X = get_subtrahend_gradient(amp, q)
get_subtrahend_gradient!(amp, X, q)

Evaluate the (sub)gradient of the subtrahend h from within a ManifoldDifferenceOfConvexObjective amp at the point q (in place of X).

The evaluation is done in place of X for the !-variant. The T=AllocatingEvaluation problem might still allocate memory within. When the non-mutating variant is called with a T=InplaceEvaluation memory for the result is allocated.

X = get_subtrahend_gradient(M::AbstractManifold, dcpo::ManifoldDifferenceOfConvexProximalObjective, p)
get_subtrahend_gradient!(M::AbstractManifold, X, dcpo::ManifoldDifferenceOfConvexProximalObjective, p)

Evaluate the gradient of the subtrahend $h$ from within a ManifoldDifferenceOfConvexProximalObjectivePat the pointp` (in place of X).