Crate basin

Expand description

basin: a numerical optimization library.

The framework lives in core: problem traits the user implements (CostFunction, Gradient, BoxConstraints, LinearInequalityConstraints, LinearEqualityConstraints, LinearConstraints, NonlinearInequalityConstraints), state shapes solvers iterate over (State, GradientState, SimplexState), the Solver trait, a pluggable termination layer (TerminationCriterion), and a read-only observer layer (Observe). Concrete solvers are in solver; line searches in line_search.

Start at Executor for the user-facing driver, or core for the trait taxonomy and the iteration-loop contract.

See CONTRIBUTING.md at the repo root for the design tenets that shape these APIs (notably tenet 3 on framework-level termination, tenet 4 on first-class constraints, and tenet 5 on backend tiering).

§Example

Implement CostFunction (and Gradient when the solver needs derivatives), then hand the problem, a solver, and an initial state to the Executor:

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

struct Sphere;
impl CostFunction for Sphere {
    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().map(|xi| xi * xi).sum())
    }
}
impl Gradient for Sphere {
    type Gradient = Vec<f64>;
    fn gradient(&self, x: &Vec<f64>) -> Result<Vec<f64>, std::convert::Infallible> {
        Ok(x.iter().map(|xi| 2.0 * xi).collect())
    }
}

let result = Executor::new(Sphere, GradientDescent::new(0.1), BasicState::new(vec![1.0, 1.0]))
    .max_iter(1_000)
    .terminate_on(GradientTolerance(1e-8))
    .run()
    .unwrap();
assert!(result.cost() < 1e-12);

§Seeding the initial state

Executor::new takes a fully-built State so you control the initial iterate (a custom simplex, a warm-started inverse Hessian, an anisotropic CMA-ES covariance). For the common case (start at a point, use the solver’s natural defaults) Executor::from_start takes the bare starting vector instead and builds the state for you via InitialState::seed, so you never name the concrete state type:

use basin::{Executor, MaxIter, NelderMead};
let result = Executor::from_start(Sphere, NelderMead::new(), vec![1.0, 1.0])
    .terminate_on(MaxIter(500))
    .run()
    .unwrap();

Most solvers support from_start; the few whose natural initialization needs more than a point do not implement InitialState, so calling from_start with one is a compile error (use Executor::new with an explicit state). The map:

Solver	State	`from_start`
`GradientDescent`, `Sgd`	`BasicState`	✓
`ProjectedGradientDescent`	`BasicState`	✓ (`f64` only)
`Bfgs`	`QuasiNewtonState`	✓ (`Vec`/nalgebra/ndarray/faer)
`Lbfgs`, `Lbfgsb`	`LbfgsState`	✓
`TrustRegion`	`BasicState`	✓
`GaussNewton`, `LevenbergMarquardt`, `Trf`	`NllsState`	✓
`NelderMead`	`BasicSimplexState`	✓
`Newuoa`, `Bobyqa`, `Lincoa`, `Cobyla`	`NewuoaState`/…	✓
`Mads`	`MadsState`/`ConstrainedMadsState`	✓
`BarrierMethod`, `AugmentedLagrangianMethod`	`BasicState`	✓
`CmaEs`, `BoundedCmaEs`, `CmaInject`, `BoundedCmaInject`, `MaLsChCma`	`CmaEsState`	✗ (needs a step-size σ)
`RandomSearch`, `Ssga`, `De`, `DeInject`	`BasicPopulationState`	✗ (sample the box, ignore a point)
`Brent`, `BrentDerivative`, `GoldenSection`	`ScalarState`	✗ (bracket, not a point)

§Error model

basin distinguishes three outcomes a run can produce. The split is a stable part of the public contract; downstream code can rely on it:

Soft reject: return Ok(f64::INFINITY) from CostFunction::cost to reject a single point without stopping the solve. Line searches treat +∞ as worse and retreat; population solvers treat it as worst fitness. This is the channel for “this x is outside my domain, but the solve should continue.”
Clean stop: the run ends normally with a TerminationReason, either because a TerminationCriterion fired or because the Solver reported a mid-iteration stop. Executor::run returns Ok(OptimizationResult) carrying that reason. This is not an error.
Hard abort: return Err(_) from a problem-trait method to terminate the entire solve. The error is your own type and bubbles out of Executor::run untouched, typed as Result<_, P::Error>. Use it when the failure is not about a particular x: a downstream service vanished, the user pressed cancel, an early-stop condition in your own problem state fired.

§One error type, threaded through

The hard-abort error is chosen once, on the problem (CostFunction::Error, or Residual::Error for nonlinear least squares). Every downstream trait mirrors it: Solver::Error and LineSearch::Error are set to P::Error, so a custom problem error flows through the solver and line search out to the caller with no conversion glue. Problems that cannot fail pick std::convert::Infallible; its niche optimization keeps Result<f64, Infallible> the same layout as a bare f64, so the happy path stays zero-cost.

The problem module docs carry the per-trait detail.

§Backends

Parameters and linear algebra are generic over the backend. Vec<f64> needs no features; nalgebra, ndarray, and faer are enabled one feature each, each pinning a single major version. basin pins one major version per backend; each basin 1.x release supports exactly these versions:

Backend	Feature	Version
nalgebra	`nalgebra`	0.34 (with `nalgebra-sparse` 0.11)
ndarray	`ndarray`	0.17
faer	`faer`	0.24

Vec<f64> is the built-in default backend, so no feature is needed for that.

A backend major-version bump is a breaking change and ships only in a basin major release; within the 1.x series these pins are fixed.

Two backends have opt-in, BLAS/LAPACK-backed acceleration. Both are off by default and not wasm-compatible (each links a Fortran/BLAS toolchain), and both expect you to bring your own BLAS/LAPACK source crate:

Feature	Effect
`ndarray-blas`	Forwards `ndarray/blas` for BLAS-backed ndarray linear algebra.
`nalgebra-lapack`	Swaps the nalgebra backend’s Cholesky/symmetric eigendecomposition for LAPACK-backed ones.

The default build is wasm-friendly: no BLAS/LAPACK and no threads. Parallelism is behind the opt-in parallel feature.

Re-exports§

pub use crate::core::augmented_lagrangian::AugmentedLagrangian;
pub use crate::core::barrier::LogBarrier;
pub use crate::core::constraint::BoxConstraints;
pub use crate::core::constraint::LinearConstraints;
pub use crate::core::constraint::LinearEqualityConstraints;
pub use crate::core::constraint::LinearInequalityConstraints;
pub use crate::core::constraint::NonlinearInequalityConstraints;
pub use crate::core::executor::Executor;
pub use crate::core::executor::OptimizationResult;
pub use crate::core::executor::StepOutcome;
pub use crate::core::executor::Stepper;
pub use crate::core::executor::run_loop;
pub use crate::core::inner::InitialState;
pub use crate::core::inner::InnerExecutor;
pub use crate::core::inner::WarmStart;
pub use crate::core::math::ClampInPlace;
pub use crate::core::math::ComponentMulAssign;
pub use crate::core::math::DenseMatrix;
pub use crate::core::math::DenseMatrixFromFn;
pub use crate::core::math::Dot;
pub use crate::core::math::GramMatrix;
pub use crate::core::math::LinearSolveError;
pub use crate::core::math::LinearSolveLstsq;
pub use crate::core::math::LinearSolveSpd;
pub use crate::core::math::MatTransposeVec;
pub use crate::core::math::MatVec;
pub use crate::core::math::MatrixFromDiagonal;
pub use crate::core::math::MatrixIdentity;
pub use crate::core::math::NegInPlace;
pub use crate::core::math::NormInfinity;
pub use crate::core::math::NormSquared;
pub use crate::core::math::SampleStandardNormal;
pub use crate::core::math::SampleUniformBox;
pub use crate::core::math::Scalar;
pub use crate::core::math::ScaleInPlace;
pub use crate::core::math::ScaledAdd;
pub use crate::core::math::SymmetricEigen;
pub use crate::core::math::SymmetricEigenError;
pub use crate::core::math::VectorIndex;
pub use crate::core::math::VectorLen;
pub use crate::core::numdiff::FiniteDiff;
pub use crate::core::numdiff::Method;
pub use crate::core::numdiff::central_difference_gradient;
pub use crate::core::numdiff::central_difference_hessian;
pub use crate::core::numdiff::central_difference_jacobian;
pub use crate::core::numdiff::forward_difference_gradient;
pub use crate::core::numdiff::forward_difference_hessian;
pub use crate::core::numdiff::forward_difference_jacobian;
pub use crate::core::observer::Observe;
pub use crate::core::observer::ObserverMode;
pub use crate::core::problem::CostFunction;
pub use crate::core::problem::EvalCounts;
pub use crate::core::problem::Gradient;
pub use crate::core::problem::Hessian;
pub use crate::core::problem::Jacobian;
pub use crate::core::problem::MiniBatchGradient;
pub use crate::core::problem::Problem;
pub use crate::core::problem::Residual;
pub use crate::core::solver::Solver;
pub use crate::core::state::FaerQuasiNewtonState;faer
pub use crate::core::state::NalgebraQuasiNewtonState;nalgebra
pub use crate::core::state::NdarrayQuasiNewtonState;ndarray
pub use crate::core::state::BasicPopulationState;
pub use crate::core::state::BasicSimplexState;
pub use crate::core::state::BasicState;
pub use crate::core::state::BobyqaState;
pub use crate::core::state::CmaEsState;
pub use crate::core::state::CobylaState;
pub use crate::core::state::ConstrainedMadsState;
pub use crate::core::state::CountsMirror;
pub use crate::core::state::GradientState;
pub use crate::core::state::IntoInitialSimplex;
pub use crate::core::state::LbfgsState;
pub use crate::core::state::LincoaState;
pub use crate::core::state::MadsState;
pub use crate::core::state::MeshState;
pub use crate::core::state::NewuoaState;
pub use crate::core::state::NllsState;
pub use crate::core::state::PopulationState;
pub use crate::core::state::RhoState;
pub use crate::core::state::ScalarGradientState;
pub use crate::core::state::ScalarState;
pub use crate::core::state::SimplexState;
pub use crate::core::state::State;
pub use crate::core::state::DenseQuasiNewtonState;
pub use crate::core::state::QuasiNewtonState;
pub use crate::core::termination::CmaEsTolerance;
pub use crate::core::termination::CostTolerance;
pub use crate::core::termination::GradientTolerance;
pub use crate::core::termination::MaxCostEvals;
pub use crate::core::termination::MaxGradientEvals;
pub use crate::core::termination::MaxIter;
pub use crate::core::termination::MaxTime;
pub use crate::core::termination::MeshTolerance;
pub use crate::core::termination::NoImprovement;
pub use crate::core::termination::ParamTolerance;
pub use crate::core::termination::ProjectedGradientTolerance;
pub use crate::core::termination::RelativeCostTolerance;
pub use crate::core::termination::RelativeGradientTolerance;
pub use crate::core::termination::RelativeParamTolerance;
pub use crate::core::termination::RhoTolerance;
pub use crate::core::termination::SimplexTolerance;
pub use crate::core::termination::TargetCost;
pub use crate::core::termination::TerminationCriterion;
pub use crate::core::termination::TerminationReason;
pub use crate::line_search::Backtracking;
pub use crate::line_search::Constant;
pub use crate::line_search::LineSearch;
pub use crate::line_search::MoreThuente;
pub use crate::line_search::Wolfe;
pub use crate::solver::Bfgs;
pub use crate::solver::lbfgs::Lbfgs;
pub use crate::solver::lbfgs::Lbfgsb;
pub use crate::solver::trust_region::CauchyPoint;
pub use crate::solver::trust_region::Dogleg;
pub use crate::solver::trust_region::Steihaug;
pub use crate::solver::trust_region::TrustRegion;
pub use crate::solver::AcceptanceTest;
pub use crate::solver::AugmentedLagrangianMethod;
pub use crate::solver::BarrierMethod;
pub use crate::solver::BasinHopping;
pub use crate::solver::Bobyqa;
pub use crate::solver::BoundedCmaEs;
pub use crate::solver::BoundedCmaInject;
pub use crate::solver::Brent;
pub use crate::solver::BrentDerivative;
pub use crate::solver::ClosureInner;
pub use crate::solver::CmaEs;
pub use crate::solver::CmaInject;
pub use crate::solver::Cobyla;
pub use crate::solver::De;
pub use crate::solver::DeInject;
pub use crate::solver::GaussNewton;
pub use crate::solver::GoldenSection;
pub use crate::solver::GradientDescent;
pub use crate::solver::LevenbergMarquardt;
pub use crate::solver::Lincoa;
pub use crate::solver::MaLsChCma;
pub use crate::solver::MaLsChState;
pub use crate::solver::Mads;
pub use crate::solver::MemeticInner;
pub use crate::solver::Metropolis;
pub use crate::solver::NelderMead;
pub use crate::solver::Newuoa;
pub use crate::solver::ProjectedGradientDescent;
pub use crate::solver::RandomDisplacement;
pub use crate::solver::RandomSearch;
pub use crate::solver::Sgd;
pub use crate::solver::Ssga;
pub use crate::solver::StepTaker;
pub use crate::solver::Trf;

Modules§

core: Framework: traits, state shapes, the iteration driver, and the termination layer. The slot taxonomy is:
line_search: Line searches: produce a step size α along a caller-supplied descent direction. Used by first-order solvers (gradient descent, BFGS).
problemsproblems: Catalog of test problems used by the example tests and benchmarks. Standard optimization test problems.
solver: Concrete solver implementations.

Crate basin

Crate basin Copy item path

§Example

§Seeding the initial state

§Error model

§One error type, threaded through

§Backends

Re-exports§

Modules§

Crate basin