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.