Crate optimization

Source
Expand description

Collection of various optimization algorithms and strategies.

§Building Blocks

Each central primitive is specified by a trait:

  • Function - Specifies a function that can be minimized
  • Function1 - Extends a Function by its first derivative
  • Summation - Represents a summation of functions, exploited, e.g., by SGD
  • Summation1 - Analogous to Function and Function1 but for Summation
  • Minimizer - A minimization algorithm
  • Evaluation - A function evaluation f(x) = y that is returned by a Minimizer
  • Func - A new-type wrapper for the Function trait
  • NumericalDifferentiation - Provides numerical differentiation for arbitrary Functions

§Algorithms

Currently, the following algorithms are implemented. This list is not final and being expanded over time.

  • GradientDescent - Iterative gradient descent minimization, supporting various line search methods:
    • FixedStepWidth - No line search is performed, but a fixed step width is used
    • ExactLineSearch - Exhaustive line search over a set of step widths
    • ArmijoLineSearch - Backtracking line search using the Armijo rule as stopping criterion
  • StochasticGradientDescent - Iterative stochastic gradient descenent minimazation, currently using a fixed step width

Modules§

  • Common optimization problems for testing purposes.

Structs§

  • Backtracking line search evaluating the Armijo rule at each step width.
  • Brute-force line search minimizing the objective function over a set of step width candidates, also known as exact line search.
  • Uses a fixed step width γ in each iteration instead of performing an actual line search.
  • New-type to support optimization of arbitrary functions without requiring to implement a trait.
  • A simple Gradient Descent optimizer.
  • Wraps a function for which to provide numeric differentiation.
  • Provides stochastic Gradient Descent optimization.

Traits§

  • Captures the essence of a function evaluation.
  • Defines an objective function f that is subject to minimization.
  • Defines an objective function f that is able to compute the first derivative f'(x).
  • Define a line search method, i.e., choosing an appropriate step width.
  • Defines an optimizer that is able to minimize a given objective function F.
  • Defines a summation of individual functions, i.e., f(x) = ∑ᵢ fᵢ(x).
  • Defines a summation of individual functions fᵢ(x), assuming that each function has a first derivative.