Stepsize

Stepsize

An abstract type for the functors representing step sizes. These are callable structures. The naming scheme is TypeOfStepSize, for example ConstantStepsize.

Every Stepsize has to provide a constructor and its function has to have the interface (problem, state, k) where an AbstractManoptProblem problem, an AbstractManoptSolverState state, and the current iteration k are the arguments, and returns a number, namely the stepsize to use.

The functor usually should accept arbitrary keyword arguments. Common ones used are

• gradient=nothing: to pass a pre-calculated gradient, otherwise it is computed.

For most it is advisable to employ a ManifoldDefaultsFactory. Then the function creating the factory should either be called TypeOf or, if that is confusing or too generic, TypeOfLength.

See also

Linesearch

Linesearch <: Stepsize

An abstract functor to represent line search type step size determinations, see Stepsize for details. One example is the ArmijoLinesearchStepsize functor.

Compared to simple step sizes, the line search functors provide an interface of the form (problem, state, k, X) -> s with an additional (but optional) fourth parameter to provide a search direction; this should default to something reasonable, most prominently the negative gradient.

AbstractInitialLinesearchGuess

An abstract type for initial line search guess strategies. These are functors that map (problem, state, k, last_stepsize, η) -> α_0, where α_0 is the initial step size, based on

• an AbstractManoptProblem problem
• an AbstractManoptSolverState state
• the current iteration k
• the last step size last_stepsize
• the search direction η

default_stepsize(M::AbstractManifold, ams::AbstractManoptSolverState)

Returns the default Stepsize functor used when running the solver specified by the AbstractManoptSolverState ams running with an objective on the AbstractManifold M.

get_last_stepsize(amp::AbstractManoptProblem, ams::AbstractManoptSolverState, vars...)

return the last computed stepsize stored within AbstractManoptSolverState ams when solving the AbstractManoptProblem amp.

This method takes into account that ams might be decorated. In case this returns NaN, a concrete call to the stored stepsize is performed. For this, usually, the first of the vars... should be the current iterate.

get_last_stepsize(::Stepsize, vars...)

return the last computed stepsize from within the stepsize. If no last step size is stored, this returns NaN.

get_stepsize(amp::AbstractManoptProblem, ams::AbstractManoptSolverState, vars...)

return the stepsize stored within AbstractManoptSolverState ams when solving the AbstractManoptProblem amp. This method also works for decorated options and the Stepsize function within the options, by default stored in ams.stepsize.

initialize_stepsize!(sm::Stepsize)

Initialize the state of a stepsize functor. This function should be called in the initialize_solver! function for solvers that do possess a stepsize and can be used to set up internal state of the stepsize functor that is preserved between line searches in the same optimization, for example adaptive thresholds for Wolfe criteria in Hager-Zhang line search.

By default it does nothing.

s = linesearch_backtrack(M, f, p, s, decrease, contract, η; kwargs...)
s = linesearch_backtrack!(M, q, f, p, s, decrease, contract, η; kwargs...)

perform a line search along $\ellf(s) = f(\operatorname{retr}_p(sη))$ to find a stepsize s. See [NW06, Section 3] for details.

The linesearch starts with a first phase where the stepsize is increased as $s ↦ s / σ$ until

\[f(\operatorname{retr}_p(sη)) ≥ f(p) + a * s * Df(p)[η]\]

where $a$ is the decrease parameter, and $Df(p)[η]$ is the directional derivative.

Then the actual backtracking phase starts, where the stepsize is decreased as $s ↦ σ s$ until

\[f(\operatorname{retr}_p(sη)) ≤ f(p) + a * s * Df(p)[η]\]

with the same decrease parameter $a$ as above.

This can be done in-place, where q is the point to store the point reached in.

Both phases have a safeguard on the maximal number of steps to perform as well as an upper and lower bound for the stepsize, respectively. The upper bound is a special case on manifolds to avoid exceeding the injectivity radius. Furthermore, both phases can be equipped with additional conditions to be fulfilled in order to accept the current stepsize.

Arguments

• M: the manifold to perform the line search on
• f: the cost function
• p: the current point
• s: an initial stepsize
• decrease: the sufficient decrease parameter $a$
• contract: the contraction factor $σ$
• η: the search direction

Keyword arguments

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

• additional_increase_condition=(M,p) -> true: impose an additional condition for an increased step size to be accepted

• additional_decrease_condition=(M,p) -> true: impose an additional condition for a decreased step size to be accepted

• Dlf0: precomputed directional derivative at point p in direction η if the gradient is specified, this is computed as the real part of inner(M, p, gradient, η), otherwise it is nothing

• lf0 = f(M, p): the function value at the initial point p

• gradient = nothing: precomputed gradient at point p

• report_messages_in::NamedTuple = (; ): a named tuple of StepsizeMessages to report messages in. currently supported keywords are :non_descent_direction, :stepsize_exceeds, :stepsize_less, :stop_increasing, :stop_decreasing

• stop_when_stepsize_less::Real=0.0: to avoid numerical underflow

• stop_when_stepsize_exceeds::Real=max_stepsize(M, p) / norm(M, p, η): to avoid leaving the injectivity radius on a manifold or exceeding boundaries on a manifold with corners

• stop_increasing_at_step=100: stop the initial increase of step size after these many steps

• stop_decreasing_at_step=1000: stop the decreasing search after these many steps

  These keywords are used as safeguards, where only the max stepsize is a very manifold specific one.

Return value

A stepsize s and a message msg (in case any of the 5 criteria hit)

s = linesearch_backtrack(M, f, p, s, decrease, contract, η; kwargs...)
s = linesearch_backtrack!(M, q, f, p, s, decrease, contract, η; kwargs...)

perform a line search along $\ellf(s) = f(\operatorname{retr}_p(sη))$ to find a stepsize s. See [NW06, Section 3] for details.

The linesearch starts with a first phase where the stepsize is increased as $s ↦ s / σ$ until

\[f(\operatorname{retr}_p(sη)) ≥ f(p) + a * s * Df(p)[η]\]

where $a$ is the decrease parameter, and $Df(p)[η]$ is the directional derivative.

Then the actual backtracking phase starts, where the stepsize is decreased as $s ↦ σ s$ until

\[f(\operatorname{retr}_p(sη)) ≤ f(p) + a * s * Df(p)[η]\]

with the same decrease parameter $a$ as above.

This can be done in-place, where q is the point to store the point reached in.

Both phases have a safeguard on the maximal number of steps to perform as well as an upper and lower bound for the stepsize, respectively. The upper bound is a special case on manifolds to avoid exceeding the injectivity radius. Furthermore, both phases can be equipped with additional conditions to be fulfilled in order to accept the current stepsize.

Arguments

• M: the manifold to perform the line search on
• f: the cost function
• p: the current point
• s: an initial stepsize
• decrease: the sufficient decrease parameter $a$
• contract: the contraction factor $σ$
• η: the search direction

Keyword arguments

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

• additional_increase_condition=(M,p) -> true: impose an additional condition for an increased step size to be accepted

• additional_decrease_condition=(M,p) -> true: impose an additional condition for a decreased step size to be accepted

• Dlf0: precomputed directional derivative at point p in direction η if the gradient is specified, this is computed as the real part of inner(M, p, gradient, η), otherwise it is nothing

• lf0 = f(M, p): the function value at the initial point p

• gradient = nothing: precomputed gradient at point p

• report_messages_in::NamedTuple = (; ): a named tuple of StepsizeMessages to report messages in. currently supported keywords are :non_descent_direction, :stepsize_exceeds, :stepsize_less, :stop_increasing, :stop_decreasing

• stop_when_stepsize_less::Real=0.0: to avoid numerical underflow

• stop_when_stepsize_exceeds::Real=max_stepsize(M, p) / norm(M, p, η): to avoid leaving the injectivity radius on a manifold or exceeding boundaries on a manifold with corners

• stop_increasing_at_step=100: stop the initial increase of step size after these many steps

• stop_decreasing_at_step=1000: stop the decreasing search after these many steps

  These keywords are used as safeguards, where only the max stepsize is a very manifold specific one.

Return value

A stepsize s and a message msg (in case any of the 5 criteria hit)

max_stepsize(M::AbstractManifold, p)
max_stepsize(M::AbstractManifold)

Get the maximum stepsize (at point p) on manifold M. It should be used to limit the distance an algorithm is trying to move in a single step.

By default, this returns injectivity_radius(M), if this exists. If this is not available on the manifold, the method returns Inf.

max_stepsize(M::AbstractManifold, p)
max_stepsize(M::AbstractManifold)

Get the maximum stepsize (at point p) on manifold M. It should be used to limit the distance an algorithm is trying to move in a single step.

By default, this returns injectivity_radius(M), if this exists. If this is not available on the manifold, the method returns Inf.