basin 0.7.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
117
118
119

//! Integration tests for the augmented-Lagrangian [`AugmentedLagrangianMethod`]
//! on linearly-equality-constrained quadratics over the plain `Vec<f64>`
//! backend, using the hand-rolled [`DenseMatrix`]. Mirrors
//! `augmented_lagrangian_nalgebra.rs`.

use basin::problems::EqualityConstrainedQuadratic;
use basin::{
    AugmentedLagrangianMethod, Backtracking, BasicState, DenseMatrix, Executor, GradientDescent,
    GradientState, TerminationReason, LBFGSB,
};

/// `min ‖x − (2,2)‖²` s.t. `x₀ + x₁ = 2`. The unconstrained min (2,2) is
/// infeasible (sum 4 ≠ 2); the constrained optimum is the projection of (2,2)
/// onto the line `x₀ + x₁ = 2`, namely (1,1).
fn single_row_problem() -> EqualityConstrainedQuadratic<DenseMatrix, Vec<f64>> {
    EqualityConstrainedQuadratic::new(
        vec![2.0, 2.0],
        DenseMatrix::from_row_slice(1, 2, &[1.0, 1.0]),
        vec![2.0],
    )
}

#[test]
fn converges_to_affine_projection() {
    let problem = single_row_problem();
    // Start at the *infeasible* origin (0 + 0 = 0 ≠ 2): the augmented
    // Lagrangian has no feasibility wall, so this is fine.
    let initial = vec![0.0, 0.0];

    let result = Executor::new(
        problem,
        AugmentedLagrangianMethod::new(GradientDescent::with_line_search(Backtracking::new())),
        BasicState::new(initial),
    )
    .max_iter(50)
    .run();

    assert_eq!(result.reason, TerminationReason::SolverConverged);
    assert!(
        (result.param()[0] - 1.0).abs() < 1e-4 && (result.param()[1] - 1.0).abs() < 1e-4,
        "expected (1, 1), got {:?}",
        result.param()
    );
}

#[test]
fn fully_determined_system() {
    // Two equalities `x₀ + x₁ = 2` and `x₀ = 0.5` pin a unique point
    // (0.5, 1.5); the quadratic center (2,2) is irrelevant to the solution
    // since the feasible set is a single point.
    let problem = EqualityConstrainedQuadratic::new(
        vec![2.0, 2.0],
        DenseMatrix::from_row_slice(2, 2, &[1.0, 1.0, 1.0, 0.0]),
        vec![2.0, 0.5],
    );
    let initial = vec![0.0, 0.0];

    let result = Executor::new(
        problem,
        AugmentedLagrangianMethod::new(GradientDescent::with_line_search(Backtracking::new())),
        BasicState::new(initial),
    )
    .max_iter(50)
    .run();

    assert_eq!(result.reason, TerminationReason::SolverConverged);
    assert!(
        (result.param()[0] - 0.5).abs() < 1e-4 && (result.param()[1] - 1.5).abs() < 1e-4,
        "expected (0.5, 1.5), got {:?}",
        result.param()
    );
}

#[test]
fn eval_counts_are_recorded() {
    let problem = single_row_problem();
    let initial = vec![0.0, 0.0];

    let result = Executor::new(
        problem,
        AugmentedLagrangianMethod::new(GradientDescent::with_line_search(Backtracking::new())),
        BasicState::new(initial),
    )
    .max_iter(50)
    .run();

    // Inner subproblem solves plus the per-outer-iter true-objective evals
    // must have accumulated onto the outer state.
    assert!(result.cost_evals() > 0, "no cost evals recorded");
    assert!(
        result.state.gradient_evals() > 0,
        "no gradient evals recorded"
    );
}

/// An unbounded `LBFGS` inner (state `LbfgsState`, not `BasicState`) proves the
/// augmented-Lagrangian method is inner-agnostic on the `Vec<f64>` backend too.
/// `L_ρ` is finite everywhere, so the inner's default line search is fine.
/// Converges to the same projection (1,1).
#[test]
fn lbfgs_inner_converges_to_affine_projection() {
    let problem = single_row_problem();
    let initial = vec![0.0, 0.0];

    let result = Executor::new(
        problem,
        AugmentedLagrangianMethod::new(LBFGSB::new().unbounded()),
        BasicState::new(initial),
    )
    .max_iter(50)
    .run();

    assert_eq!(result.reason, TerminationReason::SolverConverged);
    assert!(
        (result.param()[0] - 1.0).abs() < 1e-4 && (result.param()[1] - 1.0).abs() < 1e-4,
        "expected (1, 1), got {:?}",
        result.param()
    );
}