First order objectives

AbstractManifoldFirstOrderObjective{E<:AbstractEvaluationType, FGD} <: AbstractManifoldCostObjective{E, FGD}

An abstract type for all objectives that provide

• a cost
• first order information, so either a (full) gradient or a differential, where

E is a AbstractEvaluationType for the gradient function.

ManifoldFirstOrderObjective{E<:AbstractEvaluationType, F} <: AbstractManifoldFirstOrderObjective{E, F}

specify an objective containing a cost and its gradient or differential, where the AbstractEvaluationType E indicates the type of evaluation for a gradient.

Fields

• functions::F: a function or a tuple of functions containing the cost and first order information.

Currently the following cases are covered, sorted by their popularity

1. a single function fg, i.e. a function or a functor, represents a combined function (M, p) -> (c, X) that computes the cost c=cost(M,p) and gradient X=grad_f(M,p);
2. a single function fdf, i.e. a function or a functor, represents a combined function (M, p) -> (c, d) that computes the cost c=cost(M,p) and differential d=diff_f(M,p);
3. pairs of single functions (f, g), (f, df) of a cost function f and either its gradient g or its differential d, respectively
4. The function (fg, d) and (fdf, g) from 1 and 2, respectively joined by the other missing third information, the differential for the first or the gradient for the second
5. a tuple (f, g, d) of three functions, computing cost, f, gradient g, and differentiald` separately
6. a (f, gd) of a cost function and a combined function (X, d) = gd(M, p, X) to compute gradient and differential together
7. a single function (c, X, d) = fgd(M, p,X)

For all cases where a gradient is present, also an in-place variant is possible, where the signature has the result Y in second place.

The cases of a common fg function for cost and gradient and the tuple (f,g) are the most common one. They can also be addressed by their alternate constructors ManifoldCostGradientObjective(fg) and ManifoldGradientObjective(f,g), respectively.

Constructors

ManifoldFirstOrderObjective(; kwargs...)

Keyword arguments

• cost = nothing the cost function c = f(M,p)
• differential = nothing the differential d = df(M, p, X)
• gradient=nothing the gradient function g(M, p) or in-place g!(M, X, p)
• costgradient = nothing the combined cost and gradient function fg(M,p) or in-place fg!(M, X, p))
• costdifferential = nothing the combined cost and differential function fdf(M, p, X)
• evaluation::AbstractEvaluationType=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.

Where:

• At least one of cost, costgradient or costdifferential must be provided.
• Either gradient, costgradient, differential or costdifferential must be provided.
• If more than one function provides the same thing (e.g. cost), it is assumed that all such functions return the same value. Optimization algorithms will attempt to make the most efficient use of provided functions.

Used with

gradient_descent, conjugate_gradient_descent, quasi_Newton

ManifoldAlternatingGradientObjective{E<:AbstractEvaluationType,F,G} <: AbstractManifoldFirstOrderObjective{E, Tuple{F,G}}

An alternating gradient objective consists of

• a cost function $F(x)$
• a gradient $\operatorname{grad}F$ that is either
  • given as one function $\operatorname{grad}F$ returning a tangent vector X on M or
  • an array of gradient functions $\operatorname{grad}F_i$, ì=1,…,n s each returning a component of the gradient
  which might be allocating or mutating variants, but not a mix of both.

Constructors

ManifoldAlternatingGradientObjective(F, gradF::Function;
    evaluation=AllocatingEvaluation()
)
ManifoldAlternatingGradientObjective(F, gradF::AbstractVector{<:Function};
    evaluation=AllocatingEvaluation()
)

Create a alternating gradient problem with an optional cost and the gradient either as one function (returning an array) or a vector of functions.

ManifoldStochasticGradientObjective{E<:AbstractEvaluationType, F, G} <: AbstractManifoldFirstOrderObjective{E, Tuple{F,G}}

A stochastic gradient objective consists of

• a(n optional) cost function $f(p) = \displaystyle\sum_{i=1}^{n} f_i(p)$
• an array of gradients, $\operatorname{grad} f_i(p), i=1,…,n$ which can be given in two forms
  • as one single function $(\mathcal{M}, p) ↦ (X_1,…,X_n) ∈ (T_{p}\mathcal{M}n$
  • as a vector of functions $\bigl( (\mathcal{M}, p) ↦ X_1, …, (\mathcal{M}, p) ↦ X_n\bigr)$.

Where both variants can also be provided as InplaceEvaluation functions (M, X, p) -> X, where X is the vector of X1,...,Xn and (M, X1, p) -> X1, ..., (M, Xn, p) -> Xn, respectively.

Constructors

ManifoldStochasticGradientObjective(
    grad_f::Function;
    cost=Missing(),
    evaluation=AllocatingEvaluation()
)
ManifoldStochasticGradientObjective(
    grad_f::AbstractVector{<:Function};
    cost=Missing(), evaluation=AllocatingEvaluation()
)

Create a Stochastic gradient problem with the gradient either as one function (returning an array of tangent vectors) or a vector of functions (each returning one tangent vector).

The optional cost can also be given as either a single function (returning a number) pr a vector of functions, each returning a value.

Used with

stochastic_gradient_descent

Note that this can also be used with a gradient_descent, since the (complete) gradient is just the sums of the single gradients.

ManifoldNonlinearLeastSquaresObjective{E<:AbstractEvaluationType} <: AbstractManifoldObjective{E}

An objective to model the robustified nonlinear least squares problem

\[\operatorname*{arg\,min}_{p ∈ \mathcal{M}} f(p), \qquad f(p) = \frac{1}{2} \sum_{i=1}^{m} ρ_i \bigl( \lVert F_i(p) \rVert^2 \bigr)\]

where $F_i: \mathcal{M} → ℝ^{n_i}$ is the $i$th block component of length $n_i > 0$ and each $ρ_i: ℝ → ℝ$ is a robustifier function, cf. AbstractRobustifierFunction, for each such a block component. The overall residual function is denoted by $F: \mathcal{M} → ℝ^{n}$ with $n = \sum_{i=1}^{m} n_i$ and concatenates all block components.

Fields

• objective: a vector of AbstractFirstOrderVectorFunction{E}s, one for each block component cost function $F_i$, which might internally also be a vector of component costs $(F_i)_j$, as well as their Jacobian $J_{F_i}$ or a vector of gradients $\operatorname{grad} (F_i)_j$ depending on the specified AbstractVectorialTypes.
• robustifier: a vector of AbstractRobustifierFunctions, one for each block component cost function $F_i$.
• value_cache::AbstractVector and internal cache to store the result of evaluating the cost functions

Constructors

ManifoldNonlinearLeastSquaresObjective(f, jacobian, range_dimension::Integer, robustifier=IdentityRobustifier(); kwargs...)

Create a nonlinear least squares objective for a single vectorial function f and its jacobian, where range_dimension is the dimension of the vector space f maps into. These three are internally wrapped into a VectorGradientFunction and calls the following constructor.

ManifoldNonlinearLeastSquaresObjective(vf::AbstractFirstOrderVectorFunction, robustifier::AbstractRobustifierFunction=IdentityRobustifier())

Create a nonlinear least squares objective for a given vectorial function. Note that for this constructor the robustifier is applied componentwise to each component of vf, i.e. wrapped in a ComponentwiseRobustifierFunction. Internally this wraps both vf and robustifier in an array and calls the next constructor. Hence to not use the componentwise robustifier but a global one, pass [vf,] and [robustifier,] instead.

ManifoldNonlinearLeastSquaresObjective(fs::Vector{<:AbstractFirstOrderVectorFunction}, robustifiers::Vector{<:AbstractRobustifierFunction}=fill(IdentityRobustifier(), length(fs)))

Given a vector of AbstractFirstOrderVectorFunction`s to represent the single blocks and a vector of robustifiers, one for each block, create the corresponding nonlinear least squares objective.

Keyword arguments

The first constructor allows to pass the following keyword arguments, that are passed on to the corresponding the constructor of the As well as for the first variant of having a single block

• evaluation::AbstractEvaluationType=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.
• function_type::AbstractVectorialType=FunctionVectorialType(): specify the format the residuals are given in. By default a function returning a vector.
• jacobian_tangent_basis::AbstractBasis=DefaultOrthonormalBasis(); shortcut to specify the basis the Jacobian matrix is build with.
• jacobian_type::AbstractVectorialType=CoefficientVectorialType(jacobian_tangent_basis): specify the format the Jacobian is given in. By default a matrix of the differential with respect to a certain basis of the tangent space.

See also

LevenbergMarquardt, LevenbergMarquardtState

residuals_count(nlso::ManifoldNonlinearLeastSquaresObjective)

Return the total number of residuals in ManifoldNonlinearLeastSquaresObjective nlso, which is the sum of the single block components lengths.

ManifoldGradientObjective(cost, gradient; evaluation::E=AllocatingEvaluation() kwargs...)

Generate an objective with a function cost and its gradient. Depending on the AbstractEvaluationType E the gradient can have to forms

• as a function (M, p) -> X that allocates memory for X, an AllocatingEvaluation
• as a function (M, X, p) -> X that work in place of X, an InplaceEvaluation

Internally this is stored in a ManifoldFirstOrderObjective. The kwargs... are also passed to this representation, which allows to add a special function to evaluate the differential.

Used with

gradient_descent, conjugate_gradient_descent, quasi_Newton

ManifoldCostGradientObjective(costgrad; evaluation::E=AllocatingEvaluation(), kwargs...)

create an objective containing one function to perform a combined computation of cost and its gradient

Depending on the AbstractEvaluationType E the gradient can have to forms

• as a function (M, p) -> (c, X) that allocates memory for the gradient X, an AllocatingEvaluation
• as a function (M, X, p) -> (c, X) that work in place of X, an InplaceEvaluation

Internally this is stored in a ManifoldFirstOrderObjective. The kwargs... are also passed to this representation, which allows to add a special function to evaluate the differential.

Used with

gradient_descent, conjugate_gradient_descent, quasi_Newton

get_gradient(s::AbstractManoptSolverState)

return the (last stored) gradient within AbstractManoptSolverStates`. By default also undecorates the state beforehand

get_gradient(amp::AbstractManoptProblem, p)
get_gradient!(amp::AbstractManoptProblem, X, p)

evaluate the gradient of an AbstractManoptProblem amp at the point p.

The evaluation is done in place of X for the !-variant.

get_gradient(agst::AbstractGradientSolverState)

return the gradient stored within gradient options. THe default returns agst.X.

get_gradient(M::AbstractManifold, mgo::ManifoldProximalGradientObjective, p)
get_gradient!(M::AbstractManifold, X, mgo::ManifoldProximalGradientObjective, p)

Evaluate the gradient of the smooth part of a ManifoldProximalGradientObjective mgo at p.

get_gradient(M::AbstractManifold, vgf::VectorGradientFunction, p, i)
get_gradient(M::AbstractManifold, vgf::VectorGradientFunction, p, i, range)
get_gradient!(M::AbstractManifold, X, vgf::VectorGradientFunction, p, i)
get_gradient!(M::AbstractManifold, X, vgf::VectorGradientFunction, p, i, range)

Evaluate the gradient(s) of the vector function vgf on the manifold M at p and the values given in range, specifying the representation of the gradients.

Since i is assumed to be a linear index, you can provide

• a single integer
• a UnitRange to specify a range to be returned like 1:3
• a BitVector specifying a selection
• a AbstractVector{<:Integer} to specify indices
• : to return the vector of all gradients

get_gradient(TpM::TangentSpace, aslso::AbstractSymmetricLinearSystemObjective, X)
get_gradient!(TpM::TangentSpace, Y, aslso::AbstractSymmetricLinearSystemObjective, X)

evaluate the gradient of

\[f(X) = \frac{1}{2} \lVert \mathcal{A}[X] + b \rVert_{p}^2,\qquad X ∈ T_{p}\mathcal{M},\]

Which is $\operatorname{grad} f(X) = \mathcal{A}[X]+b$. This can be computed in-place of Y.

get_gradient(TpM, trmo::TrustRegionModelObjective, X)

Evaluate the gradient of the TrustRegionModelObjective

\[\operatorname{grad} m(X) = \operatorname{grad} f(p) + \operatorname{Hess} f(p)[X].\]

get_gradient(TpM, trmo::AdaptiveRegularizationWithCubicsModelObjective, X)

Evaluate the gradient of the AdaptiveRegularizationWithCubicsModelObjective

\[\operatorname{grad} m(X) = \operatorname{grad} f(p) + \operatorname{Hess} f(p)[X] + σ\lVert X \rVert X,\]

at X, cf. Eq. (37) in [ABBC20].

get_gradient(M::AbstractManifold, nlso::ManifoldNonlinearLeastSquaresObjective, p; kwargs...)
get_gradient!(M::AbstractManifold, X, nlso::ManifoldNonlinearLeastSquaresObjective, p; kwargs...)

Compute the gradient for the ManifoldNonlinearLeastSquaresObjective nlso at the point $p ∈ M$, i.e.

\[\operatorname{grad} f(p) = \sum_{i=1}^{m} ρ'_i\bigl(\lVert F_i(p) \rVert_{2}^2\bigr) \sum_{j=1}^{n_i} f_{i,j}(p) \operatorname{grad} f_{i,j}(p)\]

where $F_i(p) ∈ ℝ^{n_i}$ is the vector of residuals for the i-th block component cost function and $f_{i,j}(p)$ its j-th component function.

Keyword arguments

• value_cache=nothing: if provided, this vector is used to store the residuals $F(p)$ internally to avoid re-computations.
• jacobian_cache=fill(nothing, length(nlso.objective)): if provided, this is used to store the Jacobians of the component functions.

get_gradient(M::AbstractManifold, lmsco::LevenbergMarquardtLinearSurrogateObjective, p, X)
get_gradient!(M::AbstractManifold, Y, lmsco::LevenbergMarquardtLinearSurrogateObjective, p, X)

Compute the gradient of the LevenbergMarquardtLinearSurrogateObjective, which is given by

\[\begin{aligned} \operatorname{grad} μ_p(X) &= \sum_{i=1}^{m} \mathcal{L}_i^*\bigl(\mathcal{L}_i(X) + y_i \bigr) + λX\\\\ &= \sum_{i=1}^{m} J_{F_i}^*(p)\Bigl[ ρ_i' \bigl(I- b F_i(p)F_i(p)^{\mathrm{T}}\bigr)^2 J_{F_i}(p)[X] + a\sqrt{ρ_i'}\bigl(I- b F_i(p)F_i(p)^{\mathrm{T}}\bigr) F_i(p) + λX \Bigr] \end{aligned} \]

where $ρ_i' = ρ_i'(\lVert F_i(p) \rVert_2^2)$, $ρ_i'' = ρ_i''(\lVert F_i(p) \rVert_2^2)$ are the values from the AbstractRobustifierFunction ρ its first and second derivative, respectively, and $a,b$ are the get_LevenbergMarquardt_scaling values of scaling the residual and operator, respectively. See also get_jacobian and get_adjoint_jacobian.

This can be computed inplace of Y.

get_gradient(M::AbstractManifold, sgo::ManifoldStochasticGradientObjective, p, k)
get_gradient!(M::AbstractManifold, sgo::ManifoldStochasticGradientObjective, Y, p, k)

Evaluate one of the summands gradients $\operatorname{grad}f_k$, $k ∈ \{1,…,n\}$, at p (in place of Y).

If you use a single function for the stochastic gradient, that works in-place, then get_gradient is not available, since the length (or number of elements of the gradient required for allocation) can not be determined.

get_gradient(M::AbstractManifold, sgo::ManifoldStochasticGradientObjective, p)
get_gradient!(M::AbstractManifold, sgo::ManifoldStochasticGradientObjective, X, p)

Evaluate the complete gradient $\operatorname{grad} f = \displaystyle\sum_{i=1}^{n} \operatorname{grad} f_i(p)$ at p (in place of X).

If you use a single function for the stochastic gradient, that works in-place, then get_gradient is not available, since the length (or number of elements of the gradient required for allocation) can not be determined.

get_gradient(M::AbstractManifold, emo::EmbeddedManifoldObjective, p)
get_gradient!(M::AbstractManifold, X, emo::EmbeddedManifoldObjective, p)

Evaluate the gradient function of an objective defined in the embedding, that is embed p before calling the gradient function stored in the EmbeddedManifoldObjective.

The returned gradient is then converted to a Riemannian gradient calling riemannian_gradient.

get_gradient(M::AbstractManifold, scaled_objective::ScaledManifoldObjective, p)
get_gradient!(M::AbstractManifold, X, scaled_objective::ScaledManifoldObjective, p)

Evaluate the scaled gradient. $s*\operatorname{grad}f(p)$

get_gradient(M::AbstractManifold, lmsco::LevenbergMarquardtLinearSurrogateObjective, p, X)
get_gradient!(M::AbstractManifold, Y, lmsco::LevenbergMarquardtLinearSurrogateObjective, p, X)

Compute the gradient of the LevenbergMarquardtLinearSurrogateObjective, which is given by

\[\begin{aligned} \operatorname{grad} μ_p(X) &= \sum_{i=1}^{m} \mathcal{L}_i^*\bigl(\mathcal{L}_i(X) + y_i \bigr) + λX\\\\ &= \sum_{i=1}^{m} J_{F_i}^*(p)\Bigl[ ρ_i' \bigl(I- b F_i(p)F_i(p)^{\mathrm{T}}\bigr)^2 J_{F_i}(p)[X] + a\sqrt{ρ_i'}\bigl(I- b F_i(p)F_i(p)^{\mathrm{T}}\bigr) F_i(p) + λX \Bigr] \end{aligned} \]

where $ρ_i' = ρ_i'(\lVert F_i(p) \rVert_2^2)$, $ρ_i'' = ρ_i''(\lVert F_i(p) \rVert_2^2)$ are the values from the AbstractRobustifierFunction ρ its first and second derivative, respectively, and $a,b$ are the get_LevenbergMarquardt_scaling values of scaling the residual and operator, respectively. See also get_jacobian and get_adjoint_jacobian.

This can be computed inplace of Y.

get_gradients(M::AbstractManifold, sgo::ManifoldStochasticGradientObjective, p)
get_gradients!(M::AbstractManifold, X, sgo::ManifoldStochasticGradientObjective, p)

Evaluate all summands gradients `\{\operatorname{grad}f_i\}_{i=1}^{n} atp(in place ofX`).

If you use a single function for the stochastic gradient, that works in-place, then get_gradient is not available, since the length (or number of elements of the gradient) can not be determined.

 get_differential(amp::AbstractManoptProblem, p, X; kwargs...)
 get_differential(M::AbstractManifold, amfo:AbstractManifoldFirstOrderObjective, p, X; kwargs...)
 get_differential(M::AbstractManifold, amfo:AbstractDecoratedManifoldObjective, p, X; kwargs...)

Evaluate the differential $Df(p)[X]$ of the function $f$ represented by the AbstractManifoldFirstOrderObjective. For AbstractManoptProblem the inner manifold and objectives are used, similarly, any objective decorator would “pass though” to its inner objective. By default this falls back to $Df(p)[X] = ⟨\operatorname{grad}f(p), X⟩$.

Keyword arguments

• gradient=nothing – pass a tangent vector to be used internally as interims memory, e.g. in the default variant to evaluate the gradient in-place in.
• evaluated=false – indicate whether gradient is just memory (false, default) or already contains the evaluated gradient (true).

get_residuals(M::AbstractManifold, nlso::ManifoldNonlinearLeastSquaresObjective, p)
get_residuals!(M::AbstractManifold, v, nlso::ManifoldNonlinearLeastSquaresObjective, p)

Compute the vector of residuals $F(p) ∈ ℝ^n$, $n = \sum_{1}^{m} n_i$. In other words this is the concatenation of the residual vectors $F_i(p)$, $i=1,…,m$ of the components of the the ManifoldNonlinearLeastSquaresObjective nlso at the current point $p$ on M.

This can be computed in-place of v.

Note that even in the presence of RobustifierFunctions, these are not applied here, this function computes the “pure” residuals.

get_residuals(M::AbstractManifold, nlso::ManifoldNonlinearLeastSquaresObjective, p)
get_residuals!(M::AbstractManifold, v, nlso::ManifoldNonlinearLeastSquaresObjective, p)

Compute the vector of residuals $F(p) ∈ ℝ^n$, $n = \sum_{1}^{m} n_i$. In other words this is the concatenation of the residual vectors $F_i(p)$, $i=1,…,m$ of the components of the the ManifoldNonlinearLeastSquaresObjective nlso at the current point $p$ on M.

This can be computed in-place of v.

Note that even in the presence of RobustifierFunctions, these are not applied here, this function computes the “pure” residuals.

 get_differential_function(admo::AbstractManifoldFirstOrderObjective, recursive::Bool=false)

Return the function to evaluate (just) the differential $Df(p)[X]$. For a decorated objective, the recursive positional parameter determines whether to directly call this function on the next decorator or whether to get the “most inner” objective.

get_gradient_function(amgo::AbstractManifoldFirstOrderObjective, recursive=false)

return the function to evaluate (just) the gradient $\operatorname{grad} f(p)$, where either the gradient function using the decorator or without the decorator is used.

By default recursive is set to false, since usually to just pass the gradient function somewhere, one still wants for example the cached one or the one that still counts calls.

Depending on the AbstractEvaluationType E this is a function

• (M, p) -> X for the AllocatingEvaluation case
• (M, X, p) -> X for the InplaceEvaluation working in-place of X.

AbstractRobustifierFunction <: Function

An abstract type to represent robustifiers, i.e., functions $ρ: ℝ → ℝ$, currently mainly used within Levenberg-Marquardt.

Usually these should be twice continuously differentiable functions with

• $ρ(0) = 0$
• $ρ'(0) = 1$

to mimic the classical least squares behaviour around zero residuals. and

• $ρ'(x) < 1$ in outlier regions
• $ρ''(x) < 0$ in outlier regions

Note that the robustifier is applied to the squared residuals within the nonlinear least squares framework, i.e., $ρ(f_i(p)^2)$.

ArctanRobustifier <: AbstractRobustifierFunction

A robustifier that is based on the arctangent function.

The formula for the robustifier is given as

\[ρ(x) = \mathrm{atan}(x)\]

and its first and second derivatives read as

\[ρ'(x) = \frac{1}{1 + x^2}\]

and

\[ρ''(x) = -\frac{2x}{(1 + x^2)^2}\]

CauchyRobustifier <: AbstractRobustifierFunction

A robustifier that is based on the Cauchy function. Note that robustifiers act on the squared residuals within the nonlinear least squares framework, i.e., $ρ(f_i(p)^2)$.

The formula for the Cauchy robustifier is given as

\[ρ(x) = \log\]

and its first and second derivatives read as

\[ρ'(x) = \frac{1}{1 + x}\]

and

\[ρ''(x) = -\frac{1}{(1 + x)^2}\]

ComponentwiseRobustifierFunction{F<:AbstractRobustifierFunction} <: AbstractRobustifierFunction

A robustifier to indicate that for a certain AbstractVectorGradientFunction a robustifier should be applied component wise.

Fields

• robustifier::R the robustifier to be applied componentwise

Constructor

ComponentwiseRobustifierFunction(robustifier::AbstractRobustifierFunction)

Create a new componentwise robustifier function, where this wrapper avoids to ”double wrap”, i.e. calling the constructor with a componentwise robustifier creates a new componentwise robustifier with the only taking the internal robustifier.

ComposedRobustifierFunction{F<:AbstractRobustifierFunction, G<:AbstractRobustifierFunction} <: AbstractRobustifierFunction

A robustifier that is the composition of two robustifier functions $ρ = ρ_1 ∘ ρ_2$.

For formulae for the first and second derivatives are

\[ρ'(x) = ρ_1'(ρ_2(x)) ⋅ ρ_2'(x)\]

and

\[ρ''(x) = ρ_1''(ρ_2(x)) ⋅ (ρ_2'(x))^2 + ρ_1'(ρ_2(x)) ⋅ ρ_2''(x)\]

Fields

• ρ1::F : the first robustifier function
• ρ2::G : the second robustifier function

Constructor

ComposedRobustifierFunction(ρ1::F, ρ2::G) where {F<:AbstractRobustifierFunction, G<:AbstractRobustifierFunction}
ρ1 ∘ ρ2

HuberRobustifier <: AbstractRobustifierFunction

A robustifier that is based on the Huber function. Note that robustifiers act on the squared residuals within the nonlinear least squares framework, i.e., $ρ(f_i(p)^2)$.

The formula for the Huber robustifier is given as

\[ρ(x) = \begin{cases} x & \text{if } x ≤ 1\\\\ 2\sqrt{x} - 1 & \text{if } x > 1\end{cases}\]

that is, its first and second derivatives read as

\[ρ'(x) = \begin{cases} 1 & \text{if } x ≤ 1\\\\ \frac{1}{\sqrt{x}} & \text{if } x > 1\end{cases}\]

and

\[ρ''(x) = \begin{cases} 0 & \text{if } x ≤ 1\\\\ -\frac{1}{2 x^{3/2}} & \text{if } x > 1\end{cases}\]

If you want to use a different threshold δ > 0, use a ScaledRobustifierFunction to scale the residuals accordingly, or even use the shorthand δ ∘ HuberRobustifier().

IdentityRobustifier <: AbstractRobustifierFunction

A robustifier that is the identity function, i.e., $ρ(x) = x$.

Its first and second derivatives read as $ρ'(x) = 1$ and $ρ''(x) = 0$.

RobustifierFunction{F, G, H} <: AbstractRobustifierFunction

A struct to represent a robustifier function $ρ: ℝ → ℝ$ along with its first and second derivative $ρ'$ and $ρ''$, respectively.

Fields

• ρ::F : the robustifier function
• ρ_prime::G : the first derivative of the robustifier function
• ρ_double_prime::H : the second derivative of the robustifier function

Constructor

RobustifierFunction(ρ, ρ_prime, ρ_double_prime)

Generate a RobustifierFunction given the function ρ and its first and second derivative.

ScaledRobustifierFunction{F<:AbstractRobustifierFunction, R <: Real} <: AbstractRobustifierFunction

A given robustifier function to scale the residuals a real value scale $s$, i.e. we consider $ρ_s(f(p)^2) = ρ(s^2⋅f(p)^2)$ for some AbstractRobustifierFunction $ρ$. The function and its derivatives hence read as

• $ρ_s(x) = s^2 ρ(x / s^2)$
• $ρ_s'(x) = ρ'(x / s^2)$
• $ρ_s''(x) = \frac{1}{s^2} ρ''(x / s^2)$

Fields

• robustifier::F : the underlying robustifier function
• scale::R : the scaling factor s

Constructor

ScaledRobustifierFunction(robustifier::F, scale::R) where {F<:AbstractRobustifierFunction, R <: Real}
scale ∘ robustifier

Generate a ScaledRobustifierFunction given a robustifier function and a scaling factor.

SoftL1Robustifier <: AbstractRobustifierFunction

A robustifier that is based on Soft $ℓ_1$ norm. Note that robustifiers act on the squared residuals within the nonlinear least squares framework, i.e., $ρ(f_i(p)^2)$.

The formula for the robustifier is given as

\[ρ(x) = 2(\sqrt{1 + x} - 1)\]

and its first and second derivatives read as

\[ρ'(x) = \frac{1}{\sqrt{1 + x}}\]

and

\[ρ''(x) = -\frac{1}{2 (1 + x)^{3/2}}.\]

TolerantRobustifier <: AbstractRobustifierFunction

A robustifier that is based on the tolerant function.

The formula for the robustifier is given as

\[ρ_{a,b}(x) = b\log(1+ \mathrm{e}^{(s-a)/b}) - b\log(1 + \mathrm{e}^{-a/b})\]

and its first and second derivatives read as

\[ρ'_{a,b}(x) = \frac{1}{1 + \mathrm{e}{(a - x)/b}}\]

and

\[ρ''_{a,b}(x) = \frac{1}{4b\mathrm{cosh}^2\Bigl(\frac{(a - x)}{2b}\Bigr)}.\]

TukeyRobustifier <: AbstractRobustifierFunction

A robustifier that is based on the Tukey function. Note that robustifiers act on the squared residuals within the nonlinear least squares framework, i.e., $ρ(f_i(p)^2)$.

The formula for the Tukey robustifier is given as

\[ρ(x) = \begin{cases} \frac{1}{3}(1-(1-x)^3) & \text{if } x ≤ 1\\\\ \frac{1}{3} & \text{if } x > 1\end{cases}\]

that is, its first and second derivatives read as

\[ρ'(x) = \begin{cases} (1 - x)^2 & \text{if } x ≤ 1\\\\ 0 & \text{if } x > 1\end{cases}\]

and

\[ρ''(x) = \begin{cases} -2(1 - x) & \text{if } x ≤ 1\\\\ 0 & \text{if } x > 1\end{cases}.\]

(a, b, c) = get_robustifier_values(ρ::AbstractRobustifierFunction, x::Real)

Evaluate the robustifier $ρ$ and its first two derivatives at x.

Returns

A tuple (a, b, c) with

• a = ρ(x)
• b = ρ'(x)
• c = ρ''(x)

ManifoldSubgradientObjective{T<:AbstractEvaluationType,C,S} <:AbstractManifoldCostObjective{T, C}

A structure to store information about a objective for a subgradient based optimization problem

Fields

• cost: the function $f$ to be minimized
• subgradient: a function returning a subgradient $∂f$ of $f$

Constructor

ManifoldSubgradientObjective(f, ∂f)

Generate the ManifoldSubgradientObjective for a subgradient objective, consisting of a (cost) function f(M, p) and a function ∂f(M, p) that returns a not necessarily deterministic element from the subdifferential at p on a manifold M.

X = get_subgradient(M::AbstractManifold, sgo::AbstractManifoldFirstOrderObjective, p)
get_subgradient!(M::AbstractManifold, X, sgo::AbstractManifoldFirstOrderObjective, p)

Evaluate the subgradient, which for the case of a objective having a gradient, means evaluating the gradient itself.

While in general, the result might not be deterministic, for this case it is.

get_subgradient(amp::AbstractManoptProblem, p)
get_subgradient!(amp::AbstractManoptProblem, X, p)

evaluate the subgradient of an AbstractManoptProblem amp at point p.

The evaluation is done in place of X for the !-variant. The result might not be deterministic, one element of the subdifferential is returned.

X = get_subgradient(M;;AbstractManifold, sgo::ManifoldSubgradientObjective, p)
get_subgradient!(M;;AbstractManifold, X, sgo::ManifoldSubgradientObjective, p)

Evaluate the (sub)gradient of a ManifoldSubgradientObjective sgo at the point p.

The evaluation is done in place of X for the !-variant. The result might not be deterministic, one element of the subdifferential is returned.

get_subgradient_function(amgo::ManifoldSubgradientObjective, recursive=false)

return the function to evaluate (just) the gradient $\operatorname{grad} f(p)$, where either the gradient function using the decorator or without the decorator is used.

By default recursive is set to false, since usually to just pass the gradient function somewhere, one still wants for example the cached one or the one that still counts calls.

Depending on the AbstractEvaluationType E this is a function

• (M, p) -> X for the AllocatingEvaluation case
• (M, X, p) -> X for the InplaceEvaluation working in-place of X.

ManifoldProximalMapObjective{E<:AbstractEvaluationType, TC, TP, V <: Vector{<:Integer}} <: AbstractManifoldCostObjective{E, TC}

specify a problem for solvers based on the evaluation of proximal maps, which represents proximal maps $\operatorname{prox}_{λf_i}$ for summands $f = f_1 + f_2+ … + f_N$ of the cost function $f$.

Fields

• cost: a function $f:\mathcal{M}→ℝ$ to minimize
• proxes: proximal maps $\operatorname{prox}_{λf_i}:\mathcal{M} → \mathcal{M}$ as functions (M, λ, p) -> q or in-place (M, q, λ, p).
• number_of_proxes: number of proximal maps per function, to specify when one of the maps is a combined one such that the proximal maps functions return more than one entry per function, you have to adapt this value. if not specified, it is set to one prox per function.

Constructor

ManifoldProximalMapObjective(f, proxes_f::Union{Tuple,AbstractVector}, number_of_proxes=onex(length(proxes));
   evaluation=Allocating)

Generate a proximal problem with a tuple or vector of functions, where by default every function computes a single prox of one component of $f$.

ManifoldProximalMapObjective(f, prox_f); evaluation=Allocating)

Generate a proximal objective for $f$ and its proxial map $\operatorname{prox}_{λf}$

See also

cyclic_proximal_point, get_cost, get_proximal_map

q = get_proximal_map(M::AbstractManifold, mpo::ManifoldProximalMapObjective, λ, p)
get_proximal_map!(M::AbstractManifold, q, mpo::ManifoldProximalMapObjective, λ, p)
q = get_proximal_map(M::AbstractManifold, mpo::ManifoldProximalMapObjective, λ, p, i)
get_proximal_map!(M::AbstractManifold, q, mpo::ManifoldProximalMapObjective, λ, p, i)

evaluate the (ith) proximal map of the ManifoldProximalMapObjectivempo at the point p of M with parameter $λ>0$.

q = get_proximal_map(M::AbstractManifold, mpo::ManifoldProximalGradientObjective, λ, p)
get_proximal_map!(M::AbstractManifold, q, mpo::ManifoldProximalGradientObjective, λ, p)

Evaluate proximal map of the nonsmooth component $h$ of the ManifoldProximalGradientObjectivempo at the point p on M with parameter $λ>0$.