Struct MoreThuenteLineSearch

pub struct MoreThuenteLineSearch<P, G, F> { /* private fields */ }

More-Thuente line search

The More-Thuente line search is a method which finds an appropriate step length from a starting point and a search direction. This point obeys the strong Wolfe conditions.

With the method with_c the scaling factors for the sufficient decrease condition and the curvature condition can be supplied. By default they are set to c1 = 1e-4 and c2 = 0.9.

Bounds on the range where step lengths are being searched for can be set with with_bounds which accepts a lower and an upper bound. Both values need to be non-negative and lower < upper.

One of the reasons for the algorithm to terminate is when the the relative width of the uncertainty interval is smaller than a given tolerance (default: 1e-10). This tolerance can be set via with_width_tolerance and must be non-negative.

TODO: Add missing stopping criteria!

Requirements on the optimization problem

The optimization problem is required to implement CostFunction and Gradient.

References

This implementation follows the excellent MATLAB implementation of Dianne P. O’Leary at http://www.cs.umd.edu/users/oleary/software/

Jorge J. More and David J. Thuente. “Line search algorithms with guaranteed sufficient decrease.” ACM Trans. Math. Softw. 20, 3 (September 1994), 286-307. DOI: https://doi.org/10.1145/192115.192132

Implementations

impl<P, G, F> MoreThuenteLineSearch<P, G, F>

where F: ArgminFloat,

pub fn new() -> Self

Construct a new instance of MoreThuenteLineSearch

Example

let mtls: MoreThuenteLineSearch<Vec<f64>, Vec<f64>, f64> = MoreThuenteLineSearch::new();

pub fn with_c(self, c1: F, c2: F) -> Result<Self, Error>

Set the constants c1 and c2 for the sufficient decrease and curvature conditions, respectively. 0 < c1 < c2 < 1 must hold.

The default values are c1 = 1e-4 and c2 = 0.9.

Example

let mtls: MoreThuenteLineSearch<Vec<f64>, Vec<f64>, f64> =
    MoreThuenteLineSearch::new().with_c(1e-3, 0.8)?;

pub fn with_bounds(self, step_min: F, step_max: F) -> Result<Self, Error>

Set lower and upper bound of step

Defaults are step_min = sqrt(EPS) and step_max = INF.

step_min must be smaller than step_max.

Example

let mtls: MoreThuenteLineSearch<Vec<f64>, Vec<f64>, f64> =
    MoreThuenteLineSearch::new().with_bounds(1e-6, 10.0)?;

pub fn with_width_tolerance(self, xtol: F) -> Result<Self, Error>

Set relative tolerance on width of uncertainty interval

The algorithm terminates when the relative width of the uncertainty interval is below the supplied tolerance.

Must be non-negative and defaults to 1e-10.

Example

let mtls: MoreThuenteLineSearch<Vec<f64>, Vec<f64>, f64> =
    MoreThuenteLineSearch::new().with_width_tolerance(1e-9)?;

Trait Implementations

impl<P: Clone, G: Clone, F: Clone> Clone for MoreThuenteLineSearch<P, G, F>

fn clone(&self) -> MoreThuenteLineSearch<P, G, F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<P, G, F> Default for MoreThuenteLineSearch<P, G, F>

where F: ArgminFloat,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, P, G, F> Deserialize<'de> for MoreThuenteLineSearch<P, G, F>

where P: Deserialize<'de>, G: Deserialize<'de>, F: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<P, G, F> LineSearch<G, F> for MoreThuenteLineSearch<P, G, F>

where F: ArgminFloat,

fn search_direction(&mut self, search_direction: G)

Set search direction

fn initial_step_length(&mut self, alpha: F) -> Result<(), Error>

Set initial alpha value

impl<P, G, F> Serialize for MoreThuenteLineSearch<P, G, F>

where P: Serialize, G: Serialize, F: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<P, G, O, F> Solver<O, IterState<P, G, (), (), (), F>> for MoreThuenteLineSearch<P, G, F>

where O: CostFunction<Param = P, Output = F> + Gradient<Param = P, Gradient = G>, P: Clone + ArgminDot<G, F> + ArgminScaledAdd<G, F, P>, G: Clone + ArgminDot<G, F>, F: ArgminFloat,

fn name(&self) -> &str

Name of the solver. Mainly used in Observers.

fn init( &mut self, problem: &mut Problem<O>, state: IterState<P, G, (), (), (), F>, ) -> Result<(IterState<P, G, (), (), (), F>, Option<KV>), Error>

Initializes the algorithm.

fn next_iter( &mut self, problem: &mut Problem<O>, state: IterState<P, G, (), (), (), F>, ) -> Result<(IterState<P, G, (), (), (), F>, Option<KV>), Error>

Computes a single iteration of the algorithm and has access to the optimization problem definition and the internal state of the solver. Returns an updated state and optionally a KV which holds key-value pairs used in Observers.

fn terminate_internal(&mut self, state: &I) -> TerminationStatus

Checks whether basic termination reasons apply.

fn terminate(&mut self, _state: &I) -> TerminationStatus

Used to implement stopping criteria, in particular criteria which are not covered by (terminate_internal.