Announcing Basin: A Numerical Optimization Library for Rust

[u/johlars]

Hi!

I've been working on Basin, a numerical optimization library for Rust. It's heavily inspired by argmin; same overall shape (Executor driver loop, Solver/Problem trait split, per-solver State, pluggable termination). Basin exists because I wanted to push on a few specific design directions that were awkward to retrofit.

What's Different

• Framework-level termination, bound to state shape. max_iter, the *_tolerance family, max_time, eval budgets all live on the Executor and compose across solvers. Each criterion binds on the minimum state it needs, so asking for a GradientTolerance on a derivative-free solver is a compile error, not a runtime surprise.
• First-class constraints. Constraints describe the problem, so they live problem-side (not on the executor, never on state). A constrained problem handed to an unconstrained solver is a compile error; there are opt-in adapters (projection/log-barrier/augmented Lagrangian) to wrap unconstrained solvers. Box bounds and linear (in)equalities today; nonlinear is on the roadmap.
• Backend-generic linear algebra. Solvers are generic over Vec<f64> (no features), nalgebra, ndarray, and faer. A small universal vector tier keeps first-order/derivative-free solvers backend-generic; a richer linalg tier holds matrix ops that LA-heavy solvers bound on by the minimum subset they need.
• WASM in the default build. No BLAS/LAPACK, no threads, no std::time::Instant in default paths. CI enforces wasm32-unknown-unknown. Parallelism and BLAS-backed paths are opt-in features.

Current Solvers Supported

• First-order/quasi-Newton: gradient descent (with momentum + pluggable line searches), BFGS, L-BFGS, L-BFGS-B
• Derivative-free: Nelder--Mead, Brent
• Nonlinear least squares: Gauss--Newton, Levenberg--Marquardt, trust-region-reflective
• Global/stochastic: random search, CMA-ES, steady-state GA, memetic combinations
• Constrained: projected gradient, bounded Nelder--Mead/L-BFGS-B/CMA-ES, log-barrier, augmented Lagrangian

Example

use basin::{BasicState, CostFunction, Executor, Gradient, GradientDescent, GradientTolerance};

struct Rosenbrock;

impl CostFunction for Rosenbrock {
    type Param = Vec<f64>;
    type Output = f64;
    type Error = std::convert::Infallible;

    fn cost(&self, x: &Vec<f64>) -> Result<f64, std::convert::Infallible> {
        Ok((1.0 - x[0]).powi(2) + 100.0 * (x[1] - x[0].powi(2)).powi(2))
    }
}

impl Gradient for Rosenbrock {
    type Gradient = Vec<f64>;

    fn gradient(&self, x: &Vec<f64>) -> Result<Vec<f64>, std::convert::Infallible> {
        Ok(vec![
            -2.0 * (1.0 - x[0]) - 400.0 * x[0] * (x[1] - x[0].powi(2)),
            200.0 * (x[1] - x[0].powi(2)),
        ])
    }
}

let result = Executor::new(Rosenbrock, GradientDescent::new(1e-3), BasicState::new(vec![-1.2, 1.0]))
    .max_iter(50_000)
    .terminate_on(GradientTolerance(1e-6))
    .run()
    .unwrap();

Links

• Crate: https://crates.io/crates/basin (cargo add basin)
• Docs: https://basin.bz/docs/, API: https://docs.rs/basin
• In-browser solver visualizer: https://basin.bz/visualizer/
• Benchmarks vs other crates and across backends: https://basin.bz/benchmarks/
• Source: https://github.com/jolars/basin (MIT)

Feedback is very welcome, especially on the trait surface, naming, and any solver/backend combinations you'd want that aren't there yet.

[u/mtj23]

Great work! I am definitely going to look into using this in some of my projects.

I have a question that I've never had a chance to ask of someone who understands numerical solvers. In my work I do a lot of analysis of 3D shapes, and for the past 15 years I've used various Levenberg Marquardt implementations to perform best-fit alignments between shapes in 2D and 3D. I've been happy with its performance and results.

There's a particular type of measurement in metrology (floating line and surface profiles in ISO 1101) where you're trying to find the minimum zone around an expected surface that encloses all points in a set, and you can move the points around to do so. It ends up being the equivalent of trying to minimize the absolute value of the worst residual.

Do you have a recommendation for an algorithm or set of algorithms I should try for this type of problem? The parameters are either 3 (2d) or 6 (3d) values composed to form an isometry, the samples are a large number of points that get transformed, and the residuals and jacobian are calculated from closest distance searches to some kind of fixed reference geometry.

[u/johlars → u/mtj23]

Hm, off the top of my head: have you tried a smooth approximation of the loss? That should enable you to keep using the LM algorithm.

[u/mtj23 → u/johlars]

Help me figure out if I understand you. Is the idea that I would apply some sort of smoothing function to the individual residuals, reweighting them? And that would effectively transform the sum-of-squares into a minimax problem?

[u/johlars → u/mtj23]

No, sorry, I thought you had a mini-max problem already and wanted a solver for that, in which case you could try using a smooth approximation of that mini-max problem and solve it with LM.