1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

use std::borrow::Borrow;


/// Defines an objective function `f` that is subject to minimization.
///
/// For convenience every function with the same signature as `value()` qualifies as
/// an objective function, e.g., minimizing a closure is perfectly fine.
pub trait Function {
    /// Computes the objective function at a given `position` `x`, i.e., `f(x) = y`.
    fn value(&self, position: &[f64]) -> f64;
}


/// New-type to support optimization of arbitrary functions without requiring
/// to implement a trait.
pub struct Func<F: Fn(&[f64]) -> f64>(pub F);

impl<F: Fn(&[f64]) -> f64> Function for Func<F> {
    fn value(&self, position: &[f64]) -> f64 {
        self.0(position)
    }
}


/// Defines an objective function `f` that is able to compute the first derivative
/// `f'(x)`.
pub trait Function1: Function {
    /// Computes the gradient of the objective function at a given `position` `x`,
    /// i.e., `∀ᵢ ∂/∂xᵢ f(x) = ∇f(x)`.
    fn gradient(&self, position: &[f64]) -> Vec<f64>;
}


/// Defines a summation of individual functions, i.e., f(x) = ∑ᵢ fᵢ(x).
pub trait Summation: Function {
    /// Returns the number of individual functions that are terms of the summation.
    fn terms(&self) -> usize;

    /// Comptues the value of one individual function indentified by its index `term`,
    /// given the `position` `x`.
    fn term_value(&self, position: &[f64], term: usize) -> f64;

    /// Computes the partial sum over a set of individual functions identified by `terms`.
    fn partial_value<T: IntoIterator<Item=I>, I: Borrow<usize>>(&self, position: &[f64], terms: T) -> f64 {
        let mut value = 0.0;

        for term in terms {
            value += self.term_value(position, *term.borrow());
        }

        value
    }
}

impl<S: Summation> Function for S {
    fn value(&self, position: &[f64]) -> f64 {
        self.partial_value(position, 0..self.terms())
    }
}


/// Defines a summation of individual functions `fᵢ(x)`, assuming that each function has a first
/// derivative.
pub trait Summation1: Summation + Function1 {
    /// Computes the gradient of one individual function identified by `term` at the given
    /// `position`.
    fn term_gradient(&self, position: &[f64], term: usize) -> Vec<f64>;

    /// Computes the partial gradient over a set of `terms` at the given `position`.
    fn partial_gradient<T: IntoIterator<Item=I>, I: Borrow<usize>>(&self, position: &[f64], terms: T) -> Vec<f64> {
        let mut gradient = vec![0.0; position.len()];

        for term in terms {
            for (g, gi) in gradient.iter_mut().zip(self.term_gradient(position, *term.borrow())) {
                *g += gi;
            }
        }

        gradient
    }
}

impl<S: Summation1> Function1 for S {
    fn gradient(&self, position: &[f64]) -> Vec<f64> {
        self.partial_gradient(position, 0..self.terms())
    }
}


/// Defines an optimizer that is able to minimize a given objective function `F`.
pub trait Minimizer<F: ?Sized> {
    /// Type of the solution the `Minimizer` returns.
    type Solution: Evaluation;

    /// Performs the actual minimization and returns a solution that
    /// might be better than the initially provided one.
    fn minimize(&self, function: &F, initial_position: Vec<f64>) -> Self::Solution;
}


/// Captures the essence of a function evaluation.
pub trait Evaluation {
    /// Position `x` with the lowest corresponding value `f(x)`.
    fn position(&self) -> &[f64];

    /// The actual value `f(x)`.
    fn value(&self) -> f64;
}


/// A solution of a minimization run providing only the minimal information.
///
/// Each `Minimizer` might yield different types of solution structs which provide more
/// information.
#[derive(Debug, Clone)]
pub struct Solution {
    /// Position `x` of the lowest corresponding value `f(x)` that has been found.
    pub position: Vec<f64>,
    /// The actual value `f(x)`.
    pub value: f64
}

impl Solution {
    /// Creates a new `Solution` given the `position` as well as the corresponding `value`.
    pub fn new(position: Vec<f64>, value: f64) -> Solution {
        Solution {
            position,
            value
        }
    }
}

impl Evaluation for Solution {
    fn position(&self) -> &[f64] {
        &self.position
    }

    fn value(&self) -> f64 {
        self.value
    }
}