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) -> v total 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::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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=missing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion=
• grad_g=missing: specify the gradient of g. If specified, a subsolver is automatically set up.
• stopping_criterion::StoppingCriterion=StopAfterIteration(300)|StopWhenChangeLess(1.0e-9), plus (when a gradient is provided)|StopWhenGradientNormLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• g=missing: 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 solver's objective, the decorate_state! of the sub solver's state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hess if 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::Union{AbstractManoptSolverState,AbstractEvaluationType} =(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::Union{AbstractManoptProblem, F} =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)|StopWhenGradientNormLess(1.0e-8): a stopping criterion used within the default sub_state=. This is used to define the sub_state= keyword and has hence no effect if you set sub_state directly.
• X::T =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) -> v total 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::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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=missing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion=
• grad_g=missing: specify the gradient of g. If specified, a subsolver is automatically set up.
• stopping_criterion::StoppingCriterion=StopAfterIteration(300)|StopWhenChangeLess(1.0e-9), plus (when a gradient is provided)|StopWhenGradientNormLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• g=missing: 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 solver's objective, the decorate_state! of the sub solver's state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hess if 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::Union{AbstractManoptSolverState,AbstractEvaluationType} =(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::Union{AbstractManoptProblem, F} =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)|StopWhenGradientNormLess(1.0e-8): a stopping criterion used within the default sub_state=. This is used to define the sub_state= keyword and has hence no effect if you set sub_state directly.
• X::T =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, f, grad_h, p; 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, f, 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 [AdCOdO20] 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) -> v total cost function $f = g - h$; optional, when given positionally p has to be provided as well
• grad_h: the (Riemannian) gradient $\operatorname{grad}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
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• λ: ( k -> 1/2 ) a function returning the sequence of prox parameters $λ_k$
• cost=missing: provide the cost f, for debug reasons / analysis
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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=missing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion
• prox_g=missing: specify a proximal map for the sub problem or both of the following
• g=missing: specify the function g.
• grad_g=missing: specify the gradient of g. If both g and grad_g are specified, a subsolver is automatically set up.
• inverse_retraction_method::AbstractInverseRetractionMethod=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::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=ConstantLength(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(300)|StopWhenChangeLess(1.0e-9), plus (when a gradient is provided)|StopWhenGradientNormLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• 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 solver's objective, the decorate_state! of the sub solver's state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hess if 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::Union{AbstractManoptProblem, F} =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::Union{AbstractManoptSolverState,AbstractEvaluationType} =(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::StoppingCriterion=StopAfterIteration(300)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled This is used to define the sub_state= keyword and has hence no effect if you set sub_state 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, f, grad_h, p; 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, f, 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 [AdCOdO20] 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) -> v total cost function $f = g - h$; optional, when given positionally p has to be provided as well
• grad_h: the (Riemannian) gradient $\operatorname{grad}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
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• λ: ( k -> 1/2 ) a function returning the sequence of prox parameters $λ_k$
• cost=missing: provide the cost f, for debug reasons / analysis
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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=missing: specify $\operatorname{grad} f$, for debug / analysis or enhancing the stopping_criterion
• prox_g=missing: specify a proximal map for the sub problem or both of the following
• g=missing: specify the function g.
• grad_g=missing: specify the gradient of g. If both g and grad_g are specified, a subsolver is automatically set up.
• inverse_retraction_method::AbstractInverseRetractionMethod=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::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=ConstantLength(): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(300)|StopWhenChangeLess(1.0e-9), plus (when a gradient is provided)|StopWhenGradientNormLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• 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 solver's objective, the decorate_state! of the sub solver's state, and the sub state constructor itself.
• sub_objective: a gradient or Hessian objective based on sub_cost=, sub_grad=, and sub_hess if 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::Union{AbstractManoptProblem, F} =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::Union{AbstractManoptSolverState,AbstractEvaluationType} =(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::StoppingCriterion=StopAfterIteration(300)|StopWhenGradientNormLess(1e-8): a functor indicating that the stopping criterion is fulfilled This is used to define the sub_state= keyword and has hence no effect if you set sub_state 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. It comes in two forms, depending on the realization of the subproblem.

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• 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{AbstractManoptSolverState,AbstractEvaluationType}: 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

For the sub task a method to solve

\[ \operatorname*{arg\,min}_{q∈\mathcal{M}}\ g(q) - ⟨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=AllocatingEvaluation(), 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, of the form (M, p, X) -> q for AllocatingEvaluation() (the default) or (M, q, p, X) -> q for InplaceEvaluation().

further keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
• stopping_criterion::StoppingCriterion=StopAfterIteration(300)|StopWhenChangeLess(1.0e-9): a functor indicating that the stopping criterion is fulfilled
• X::T =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<:AbstractManoptSolverState, C<:AbstractDict{Symbol}, S<:Stepsize, SC<:StoppingCriterion, RTR<:AbstractRetractionMethod, ITR<:AbstractInverseRetractionMethod, Tλ}
    <: AbstractSubProblemSolverState

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

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• λ: a function k -> λ_k returning the sequence of prox parameters
• 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: the current gradient
• 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{AbstractManoptSolverState,AbstractEvaluationType}: 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 a difference of convex proximal point state

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

construct a 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::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{AbstractManoptSolverState,AbstractEvaluationType}: a state to specify the sub solver to use. For a closed form solution, this indicates the type of function.

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys

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

• λ = k -> 1: a function returning the sequence of prox parameters $λ_k$

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

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

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

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

• X::T =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 <: AbstractManifoldCostObjective

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).
• gradient!: a gradient of the cost $f$
• ∂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 gradient and the subdifferential might be given in two possible signatures

• (M,p) -> X which does an AllocatingEvaluation
• (M, X, p) -> X which does an InplaceEvaluation in place of X.

Constructor

ManifoldDifferenceOfConvexObjective(cost, ∂h; gradient = missing, evaluation = AllocatingEvaluation(), p = missing)

Create the difference of convex objective given a cost function and the subdifferential ∂h of the non-smooth part. The gradient of the cost and the evaluation = type are keywords.

Keyword Arguments

• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their 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 = missing provide a gradient of the cost $f$
• p = missing provide a point to automatically ensure the functions of the objective “act” on mutating variables.

ManifoldDifferenceOfConvexProximalObjective <: AbstractManifoldFirstOrderObjective

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(    grad_h;    cost = missing, gradient = missing, evaluation = AllocatingEvaluation())

and note that neither cost nor gradient are required for the algorithm, just for eventual debug or recording functionality or for the stopping criterion.

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

Evaluate the (sub)gradient of the subtrahend h from within the ManifoldDifferenceOfConvexObjective of an AbstractManoptProblem amp at the point p.

The evaluation is done in place of X for the !-variant. An objective using AllocatingEvaluation might still allocate memory within. When the non-mutating variant is called with an 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 ManifoldDifferenceOfConvexProximalObjective dcpo at the point p (in place of X).