basin 0.11.0

Numerical optimization in pure Rust, with pluggable linear-algebra backends and WASM support.
Documentation 
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

//! Bfgs convergence over the default `Vec<f64>` backend (no feature gate).
//!
//! Mirrors the nalgebra tests in `tests/bfgs.rs` to confirm the generic
//! `Solver` impl runs on the hand-rolled
//! [`DenseMatrix`](basin::DenseMatrix) inverse-Hessian.

use basin::problems::Rosenbrock;
use basin::{
    Bfgs, CostFunction, DenseQuasiNewtonState, Executor, Gradient, GradientTolerance,
    TerminationReason,
};

#[test]
fn bfgs_converges_on_rosenbrock() {
    let problem = Rosenbrock::<Vec<f64>>::default();
    let initial = vec![-1.2, 1.0];

    let result = Executor::new(problem, Bfgs::new(), DenseQuasiNewtonState::new(initial))
        .max_iter(100)
        .run()
        .unwrap();

    assert!(
        result.cost() < 1e-8,
        "expected near-zero cost, got {}",
        result.cost()
    );
    assert!(
        (result.param()[0] - 1.0).abs() < 1e-4,
        "x[0] = {}",
        result.param()[0]
    );
    assert!(
        (result.param()[1] - 1.0).abs() < 1e-4,
        "x[1] = {}",
        result.param()[1]
    );
}

#[test]
fn bfgs_terminates_on_gradient_tolerance() {
    let problem = Rosenbrock::<Vec<f64>>::default();
    let initial = vec![-1.2, 1.0];

    let result = Executor::new(problem, Bfgs::new(), DenseQuasiNewtonState::new(initial))
        .max_iter(200)
        .terminate_on(GradientTolerance(1e-6))
        .run()
        .unwrap();

    assert_eq!(result.reason, TerminationReason::GradientTolerance);
    assert!(result.cost() < 1e-10, "cost = {}", result.cost());
}

/// Strictly convex 5-D quadratic `f(x) = ½ xᵀ A x − bᵀ x` with diagonal
/// `A = diag(1, 2, ..., 5)` and `b = (1, 1, ..., 1)`. Minimum at
/// `x* = A⁻¹ b`. Mirrors the nalgebra `Quadratic` test to exercise an
/// `n > 2` dense inverse-Hessian on the `Vec<f64>` backend.
struct Quadratic {
    diag: Vec<f64>,
}

impl CostFunction for Quadratic {
    type Param = Vec<f64>;
    type Output = f64;
    type Error = std::convert::Infallible;
    fn cost(&self, x: &Vec<f64>) -> Result<f64, std::convert::Infallible> {
        Ok({
            x.iter()
                .enumerate()
                .map(|(i, xi)| 0.5 * self.diag[i] * xi * xi - xi)
                .sum()
        })
    }
}

impl Gradient for Quadratic {
    type Gradient = Vec<f64>;
    fn gradient(&self, x: &Vec<f64>) -> Result<Vec<f64>, std::convert::Infallible> {
        Ok({
            x.iter()
                .enumerate()
                .map(|(i, xi)| self.diag[i] * xi - 1.0)
                .collect()
        })
    }
}

#[test]
fn bfgs_on_5d_quadratic_converges_quickly() {
    let problem = Quadratic {
        diag: vec![1.0, 2.0, 3.0, 4.0, 5.0],
    };
    let initial = vec![0.0; 5];

    let result = Executor::new(problem, Bfgs::new(), DenseQuasiNewtonState::new(initial))
        .max_iter(50)
        .terminate_on(GradientTolerance(1e-8))
        .run()
        .unwrap();

    assert_eq!(result.reason, TerminationReason::GradientTolerance);
    // Optimum: x[i] = 1 / diag[i]; cost = -½ Σ 1/diag[i].
    let expected_cost = -0.5 * (1.0 + 0.5 + 1.0 / 3.0 + 0.25 + 0.2);
    assert!(
        (result.cost() - expected_cost).abs() < 1e-10,
        "cost = {}, expected {}",
        result.cost(),
        expected_cost
    );
    assert!(
        result.iter() <= 15,
        "expected convergence in ≤ 15 iters, got {}",
        result.iter()
    );
}