Levenberg-Marquardt

LevenbergMarquardt(M, f, jacobian_f, p, num_components=-1; kwargs...)
LevenbergMarquardt(M, vgf, p; kwargs...)
LevenbergMarquardt(M, nlso, p; kwargs...)
LevenbergMarquardt!(M, f, jacobian_f, p, num_components=-1; kwargs...)
LevenbergMarquardt!(M, vgf, p, num_components=-1; kwargs...)
LevenbergMarquardt!(M, nlso, p, num_components=-1; kwargs...)

compute the the Riemannian Levenberg-Marquardt algorithm [Pee93, AOT22] to solve

\[\operatorname*{arg\,min}_{p ∈ \mathcal M} \frac{1}{2} \sum_{i=1}^{m} \lvert f_i(p) \rvert^2\]

where $f: \mathcal M → ℝ^m$ is written with component functions $f_i: \mathcal M → ℝ$, $i=1,…,m$, and each component function is continuously differentiable.

The second block of signatures perform the optimization in-place of p.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ℝ^m$. The cost function can be provided in two different ways
  • as a single function returning a vector $f(p) ∈ ℝ^m$
  • as a vector of functions, where each single function returns a scalar $f_i(p) ∈ ℝ$
  The type is determined by the function_type= keyword argument.
• jacobian_f: the Jacobian of $f$. The Jacobian can be provided in three different ways
  • as a single function returning a vector of gradient vectors $\bigl(\operatorname{grad} f_i(p)\bigr)_{i=1}^m$
  • as a vector of functions, where each single function returns a gradient vector $\operatorname{grad} f_i(p)$, $i=1,…,m$
  • as a single function returning a (coefficient) matrix $J ∈ ℝ^{m×d}$, where $d$ is the dimension of the manifold.
  These coefficients are given with respect to an AbstractBasis of the tangent space at p. The type is determined by the jacobian_type= keyword argument.
• p: a point on the manifold $\mathcal M$
• num_components: length $m$ of the vector returned by the cost function. By default its value is -1 which means that it is determined automatically by calling f one additional time. This is only possible when evaluation is AllocatingEvaluation, for mutating evaluation this value must be explicitly specified.

You can also provide the cost and its Jacobian already as aVectorGradientFunction vgf, Alternatively, passing a NonlinearLeastSquaresObjective nlso.

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.
• η=0.2: scaling factor for the sufficient cost decrease threshold required to accept new proposal points. Allowed range: 0 < η < 1.
• expect_zero_residual=false: whether or not the algorithm might expect that the value of residual (objective) at minimum is equal to 0.
• damping_term_min=0.1: initial (and also minimal) value of the damping term
• β=5.0: parameter by which the damping term is multiplied when the current new point is rejected
• function_type=FunctionVectorialType: an AbstractVectorialType specifying the type of cost function provided.
• initial_jacobian_f: the initial Jacobian of the cost function f. By default this is a matrix of size num_components times the manifold dimension of similar type as p.
• initial_residual_values: the initial residual vector of the cost function f. By default this is a vector of length num_components of similar type as p.
• jacobian_type=FunctionVectorialType: an AbstractVectorialType specifying the type of Jacobian provided.
• linear_subsolver!: a function with three arguments sk, JJ, grad_f_c that solves the linear subproblem sk .= JJ \ grad_f_c, where JJ is (up to numerical issues) a symmetric positive definite matrix. Default value is default_lm_lin_solve!.
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions

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.

LevenbergMarquardt(M, f, jacobian_f, p, num_components=-1; kwargs...)
LevenbergMarquardt(M, vgf, p; kwargs...)
LevenbergMarquardt(M, nlso, p; kwargs...)
LevenbergMarquardt!(M, f, jacobian_f, p, num_components=-1; kwargs...)
LevenbergMarquardt!(M, vgf, p, num_components=-1; kwargs...)
LevenbergMarquardt!(M, nlso, p, num_components=-1; kwargs...)

compute the the Riemannian Levenberg-Marquardt algorithm [Pee93, AOT22] to solve

\[\operatorname*{arg\,min}_{p ∈ \mathcal M} \frac{1}{2} \sum_{i=1}^{m} \lvert f_i(p) \rvert^2\]

where $f: \mathcal M → ℝ^m$ is written with component functions $f_i: \mathcal M → ℝ$, $i=1,…,m$, and each component function is continuously differentiable.

The second block of signatures perform the optimization in-place of p.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ℝ^m$. The cost function can be provided in two different ways
  • as a single function returning a vector $f(p) ∈ ℝ^m$
  • as a vector of functions, where each single function returns a scalar $f_i(p) ∈ ℝ$
  The type is determined by the function_type= keyword argument.
• jacobian_f: the Jacobian of $f$. The Jacobian can be provided in three different ways
  • as a single function returning a vector of gradient vectors $\bigl(\operatorname{grad} f_i(p)\bigr)_{i=1}^m$
  • as a vector of functions, where each single function returns a gradient vector $\operatorname{grad} f_i(p)$, $i=1,…,m$
  • as a single function returning a (coefficient) matrix $J ∈ ℝ^{m×d}$, where $d$ is the dimension of the manifold.
  These coefficients are given with respect to an AbstractBasis of the tangent space at p. The type is determined by the jacobian_type= keyword argument.
• p: a point on the manifold $\mathcal M$
• num_components: length $m$ of the vector returned by the cost function. By default its value is -1 which means that it is determined automatically by calling f one additional time. This is only possible when evaluation is AllocatingEvaluation, for mutating evaluation this value must be explicitly specified.

You can also provide the cost and its Jacobian already as aVectorGradientFunction vgf, Alternatively, passing a NonlinearLeastSquaresObjective nlso.

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.
• η=0.2: scaling factor for the sufficient cost decrease threshold required to accept new proposal points. Allowed range: 0 < η < 1.
• expect_zero_residual=false: whether or not the algorithm might expect that the value of residual (objective) at minimum is equal to 0.
• damping_term_min=0.1: initial (and also minimal) value of the damping term
• β=5.0: parameter by which the damping term is multiplied when the current new point is rejected
• function_type=FunctionVectorialType: an AbstractVectorialType specifying the type of cost function provided.
• initial_jacobian_f: the initial Jacobian of the cost function f. By default this is a matrix of size num_components times the manifold dimension of similar type as p.
• initial_residual_values: the initial residual vector of the cost function f. By default this is a vector of length num_components of similar type as p.
• jacobian_type=FunctionVectorialType: an AbstractVectorialType specifying the type of Jacobian provided.
• linear_subsolver!: a function with three arguments sk, JJ, grad_f_c that solves the linear subproblem sk .= JJ \ grad_f_c, where JJ is (up to numerical issues) a symmetric positive definite matrix. Default value is default_lm_lin_solve!.
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions

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.

LevenbergMarquardtState{P,T} <: AbstractGradientSolverState

Describes a Gradient based descent algorithm, with

Fields

A default value is given in brackets if a parameter can be left out in initialization.

• p::P: a point on the manifold $\mathcal M$ storing the current iterate
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• residual_values: value of $F$ calculated in the solver setup or the previous iteration
• residual_values_temp: value of $F$ for the current proposal point
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• jacobian: the current Jacobian of $F$
• gradient: the current gradient of $F$
• step_vector: the tangent vector at x that is used to move to the next point
• last_stepsize: length of step_vector
• η: Scaling factor for the sufficient cost decrease threshold required to accept new proposal points. Allowed range: 0 < η < 1.
• damping_term: current value of the damping term
• damping_term_min: initial (and also minimal) value of the damping term
• β: parameter by which the damping term is multiplied when the current new point is rejected
• expect_zero_residual: if true, the algorithm expects that the value of the residual (objective) at minimum is equal to 0.
• linear_subsolver!: a function with three arguments sk, JJ, grad_f_cthat solves the linear subproblemsk .= JJ \ gradfc, whereJJis (up to numerical issues) a symmetric positive definite matrix. Default value is [defaultlmlin_solve!`](@ref).

Constructor

LevenbergMarquardtState(M, initial_residual_values, initial_jacobian; kwargs...)

Generate the Levenberg-Marquardt solver state.

Keyword arguments

The following fields are keyword arguments

• β=5.0
• damping_term_min=0.1
• η=0.2,
• expect_zero_residual=false
• initial_gradient=zero_vector(M, p)
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stopping_criterion=StopAfterIteration(200)|StopWhenGradientNormLess(1e-12)|StopWhenStepsizeLess(1e-12): a functor indicating that the stopping criterion is fulfilled

See also

gradient_descent, LevenbergMarquardt

default_lm_lin_solve!(sk, JJ, grad_f_c)

Solve the system JJ \ grad_f_c where JJ is (mathematically) a symmetric positive definite matrix and save the result to sk. In case of numerical errors the PosDefException is caught and the default symmetric solver (Symmetric(JJ) \ grad_f_c) is used.

The function is intended to be used with LevenbergMarquardt.