Crate optimization

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

• problems
  Common optimization problems for testing purposes.

Structs

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

Traits

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