# Difference of convex

## Difference of convex algorithm

`Manopt.difference_of_convex_algorithm`

— Function```
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 [BFSS23] 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,…$

- Take $X^{(k)} ∈ ∂h(p^{(k)})$
- 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.

**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_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=`

(`GradientDescentState`

or`TrustRegionsState`

if`sub_hessian`

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.

`Manopt.difference_of_convex_algorithm!`

— Function```
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 [BFSS23] 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,…$

- Take $X^{(k)} ∈ ∂h(p^{(k)})$
- 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.

**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_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=`

(`GradientDescentState`

or`TrustRegionsState`

if`sub_hessian`

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

`Manopt.difference_of_convex_proximal_point`

— Function```
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,…$

- $X^{(k)} ∈ \operatorname{grad} h(p^{(k)})$
- $q^{(k)} = \operatorname{retr}_{p^{(k)}}(λ_kX^{(k)})$
- $r^{(k)} = \operatorname{prox}_{λ_kg}(q^{(k)})$
- $X^{(k)} = \operatorname{retr}^{-1}_{p^{(k)}}(r^{(k)})$
- Compute a stepsize $s_k$ and
- 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.

**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`g`

and`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_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=`

`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_hessian`

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 the`

sub*state=*state` directly.`keyword and has hence no effect, if you set`

sub

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.

`Manopt.difference_of_convex_proximal_point!`

— Function```
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=`

`p`

= $p^{(0)}$. Then repeat for $k=0,1,…$

- $X^{(k)} ∈ \operatorname{grad} h(p^{(k)})$
- $q^{(k)} = \operatorname{retr}_{p^{(k)}}(λ_kX^{(k)})$
- $r^{(k)} = \operatorname{prox}_{λ_kg}(q^{(k)})$
- $X^{(k)} = \operatorname{retr}^{-1}_{p^{(k)}}(r^{(k)})$
- Compute a stepsize $s_k$ and
- 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.

**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`g`

and`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_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=`

`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_hessian`

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 the`

sub*state=*state` directly.`keyword and has hence no effect, if you set`

sub

`decorate_state!`

for state decorators or `decorate_objective!`

for objective decorators, respectively.

**Output**

`get_solver_return`

for details, especially the `return_state=`

keyword.

## Solver states

`Manopt.DifferenceOfConvexState`

— Type```
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

`Manopt.DifferenceOfConvexProximalState`

— Type```
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`retraction_method::AbstractRetractionMethod`

: a retraction $\operatorname{retr}$ to use, see the section on retractions`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`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

## The difference of convex objective

`Manopt.ManifoldDifferenceOfConvexObjective`

— Type`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`

.

as well as for the corresponding sub problem

`Manopt.LinearizedDCCost`

— Type`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)`

`Manopt.LinearizedDCGrad`

— Type`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.

`Manopt.ManifoldDifferenceOfConvexProximalObjective`

— Type`ManifoldDifferenceOfConvexProximalObjective{E} <: Problem`

Specify an objective `difference_of_convex_proximal_point`

algorithm. The problem is of the form

\[ \operatorname*{argmin}_{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.

as well as for the corresponding sub problems

`Manopt.ProximalDCCost`

— Type`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, λ)`

`Manopt.ProximalDCGrad`

— Type`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.

## Helper functions

`Manopt.get_subtrahend_gradient`

— Function```
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 `ManifoldDifferenceOfConvexProximalObjective`

`P`

`at the point`

p` (in place of X).

## Technical details

The `difference_of_convex_algorithm`

and `difference_of_convex_proximal_point`

solver requires the following functions of a manifold to be available

- A
`retract!`

`(M, q, p, X)`

; it is recommended to set the`default_retraction_method`

to a favourite retraction. If this default is set, a`retraction_method=`

or`retraction_method_dual=`

(for $\mathcal N$) does not have to be specified. - An
`inverse_retract!`

`(M, X, p, q)`

; it is recommended to set the`default_inverse_retraction_method`

to a favourite retraction. If this default is set, a`inverse_retraction_method=`

or`inverse_retraction_method_dual=`

(for $\mathcal N$) does not have to be specified.

By default, one of the stopping criteria is `StopWhenChangeLess`

, which either requires

- A
`retract!`

`(M, q, p, X)`

; it is recommended to set the`default_retraction_method`

to a favourite retraction. If this default is set, a`retraction_method=`

or`retraction_method_dual=`

(for $\mathcal N$) does not have to be specified. - An
`inverse_retract!`

`(M, X, p, q)`

; it is recommended to set the`default_inverse_retraction_method`

to a favourite retraction. If this default is set, a`inverse_retraction_method=`

or`inverse_retraction_method_dual=`

(for $\mathcal N$) does not have to be specified or the`distance`

`(M, p, q)`

for said default inverse retraction. - A `copyto!
`(M, q, p)`

and`copy`

`(M,p)`

for points. - By default the tangent vector storing the gradient is initialized calling
`zero_vector`

`(M,p)`

. - everything the subsolver requires, which by default is the
`trust_regions`

or if you do not provide a Hessian`gradient_descent`

.

## Literature

- [ACOO20]
- Y. T. Almeida, J. X. Cruz Neto, P. R. Oliveira and J. C. Oliveira Souza.
*A modified proximal point method for DC functions on Hadamard manifolds*. Computational Optimization and Applications**76**, 649–673 (2020). - [BFSS23]
- R. Bergmann, O. P. Ferreira, E. M. Santos and J. C. Souza.
*The difference of convex algorithm on Hadamard manifolds*, arXiv preprint (2023). - [SO15]
- J. C. Souza and P. R. Oliveira.
*A proximal point algorithm for DC fuctions on Hadamard manifolds*. Journal of Global Optimization**63**, 797–810 (2015).