Solvers

Basin ships a large catalog of optimization solvers driven by the same Executor loop, plus a direct scalar root-finding API. Pick an optimization solver based on what your problem provides (a gradient? only costs? residuals?) and whether it is constrained.

Each algorithm name links to its API page on docs.rs; the trailing note cites the paper it implements (or the source it ports). Backend support applies to every enabled version of the listed backend. Multiple versions can be used in the same build; see the backend migration notes for feature selection and the shared FirstOrderState used by quasi-Newton solvers.

Root Finding

  • BrentRoot: bracketed scalar root finding by bisection, secant steps, and inverse quadratic interpolation (Brent, 1971). It uses a direct fallible-closure API rather than Executor, preserving the signed function value and final bracket in a root-specific result.
  • SecantRoot: secant iteration with bracket preservation and bisection safeguards (SciPy 1.16.3, scipy.optimize.newton, secant update; Basin adds bracketing and bracket-based termination).
  • NewtonRoot: safeguarded Newton iteration using first derivatives (Boost.Math 1.89.0, “Root Finding With Derivatives: Newton-Raphson, Halley & Schroeder”; Basin adds secant fallback, a two-trial contraction safeguard, and bracket-based termination).
  • HalleyRoot: safeguarded Halley iteration using first and second derivatives (Boost.Math 1.89.0, “Root Finding With Derivatives: Newton-Raphson, Halley & Schroeder”; Basin adds secant fallback, a two-trial contraction safeguard, and bracket-based termination).
  • Toms748Root: derivative-free bracketed root finding using Algorithm 4.2 (k = 2, μ = 0.5) from Alefeld, Potra, and Shi (1995), “Algorithm 748: Enclosing Zeros of Continuous Functions,” ACM Transactions on Mathematical Software, 21(3), 327–344, doi:10.1145/210089.210111.

All five use direct fallible callbacks and preserve signed function values and the final bracket. Newton and Halley accept separate or combined derivative callbacks. Convergence requires an exact zero or a sufficiently narrow bracket.

RootBracketer and MinimumBracketer provide automatic geometric bracket searches with optional domain limits. Bracketing is a separate stage with its own evaluation counts. Pass a root bracket to a root solver, or put a minimum bracket’s outer endpoints on the problem’s BoxBounds declaration and use its middle point to seed a scalar minimizer. Both searches follow the scalar recurrences in SciPy 1.16.3’s elementwise bracketing routines.

First-Order

  • NonlinearCg: nonlinear conjugate gradient with selectable Hager–Zhang (default) and Polak–Ribière+ updates, O(n) storage, a pluggable line search, and optional periodic restarts. Select PR+ with with_update(CgUpdate::PolakRibierePlus); it truncates negative coefficients to zero and restarts when the next direction fails its descent safeguard. Selecting an update leaves the line search unchanged. This minimizes smooth unconstrained objectives; Steihaug’s linear CG solves a trust-region subproblem. References: William W. Hager and Hongchao Zhang, “A new conjugate gradient method with guaranteed descent and an efficient line search,” SIAM Journal on Optimization 16(1), 2005, pp. 170–192, equations (1.3), (1.5), and (1.6), doi:10.1137/030601880; Elijah Polak and Gérard Ribière, “Note sur la convergence de méthodes de directions conjuguées,” Revue française d’informatique et de recherche opérationnelle, Série rouge 3(R1), 1969, pp. 35–43, doi:10.1051/m2an/196903R100351; and Jean Charles Gilbert and Jorge Nocedal, “Global Convergence Properties of Conjugate Gradient Methods for Optimization,” SIAM Journal on Optimization 2(1), 1992, pp. 21–42, doi:10.1137/0802003.
  • GradientDescent: steepest descent with a pluggable step rule (Constant, Backtracking, MoreThuente, Wolfe, or HagerZhang line searches) and optional heavy-ball momentum (Polyak, 1964). Supports all four dense backends with f32 or f64 and publishes FirstOrderState.
  • Sgd: mini-batch stochastic gradient descent with a constant learning rate and optional Polyak (1964) heavy-ball momentum. Supports all four dense backends with f32 or f64 and publishes the last fully evaluated point in PointState; the solver retains the working iterate between objective refreshes.
  • ProjectedGradientDescent: gradient descent for box-constrained problems, projecting each step back onto the feasible box. Supports all four dense backends with f32 or f64 and publishes FirstOrderState.
  • BrentDerivative: Brent’s method using first derivatives (“dbrent”): 1-D minimization on a bracketed interval, the gradient-using sibling of Brent/GoldenSection (uses the sign of f' to bracket and secant extrapolation on f' to step; Brent, 1973, as transcribed in Numerical Recipes §10.3).

Derivative-Free

  • NelderMead: the classic reflection, expansion, and contraction simplex; needs only a CostFunction. Implements Lagarias et al. (1998); NelderMead::adaptive() uses the dimension-aware coefficients of Gao & Han (2012). Its projected variant clamps trial points into box bounds; use Gbnm for the full Luersen–Le Riche restart algorithm. Publishes SimplexProgress, with observable vertices and an independent historical incumbent; scratch belongs to the solver. Both variants support all four dense backends with f32 or f64 and require coordinate access through VectorIndex. Paired simplex size and cost-spread tests are enabled by default in Basin 2.0; see the Basin 2.0 migration guide and API reference for tolerance settings and scaling limits.
  • Mads: mesh adaptive direct search (the deterministic OrthoMADS instance): polls a positive spanning set of 2n directions on a shrinking mesh, generated from the Halton sequence and a scaled Householder reflection. Unlike Nelder-Mead it has a convergence guarantee on nonsmooth or non-continuous objectives, a box-constrained variant (Mads::bounded()) via the extreme barrier, and a nonlinearly-constrained variant (Mads::constrained()) handling c(x) ≤ 0 via the progressive barrier (which tolerates an infeasible start). Needs only a CostFunction (plus NonlinearInequalityValues for the constrained mode). All modes support f32 and f64 on every dense backend release. Unbounded and box-bounded runs use PointState; progressive-barrier runs use SelectedState with an unscaled ViolationReport tagged SquaredL2. Mesh and poll diagnostics belong to the solver. Selected constrained states expose matching current and incumbent violation reports through ConstraintViolationState, without additional evaluations or changes to solver convergence. Implements Audet & Dennis (2006), OrthoMADS (Abramson, Audet, Dennis & Le Digabel 2009), and the progressive barrier (Audet & Dennis 2009).
  • Newuoa: Powell’s model-based trust-region method: maintains a quadratic surrogate interpolating the objective on 2n+1 points and updates it by the least-Frobenius-norm rule, so each iteration needs only one new value. Needs only a CostFunction. Uses PointState with f32 and f64 on every supported dense backend release; model and radius diagnostics live on the solver. Implements Powell (2006), cross-validated against PRIMA v0.7.2.
  • Bobyqa: the bound-constrained sibling of Newuoa: the same least-Frobenius-norm quadratic model, with a box-aware trust-region step (TRSBOX) and geometry step (ALTMOV), plus the RESCUE restoration procedure. Needs a CostFunction and ConstraintSet<BoxBounds<V>>. Uses PointState with f32 and f64 on every supported dense backend release; the solver owns the model and radius schedule. Implements Powell (2009), cross-validated against PRIMA v0.7.2.
  • Lincoa: the linearly-constrained sibling of Newuoa: the same least-Frobenius-norm quadratic model, with a projected truncated-CG trust-region step (TRSTEP) and active-set QR (GETACT) that keep every iterate feasible under A x ≤ b. Needs a CostFunction and a canonical set of bounds and linear blocks, folded into A x ≤ b. Uses PointState with f32 and f64 on every supported dense backend release; constraint matrices require MatrixShape, MatrixFinite, and MatTransposeVecInto. Infeasible starts relax the constraints. Implements Powell (2015), ported from PRIMA v0.7.2.
  • Cobyla: Powell’s nonlinearly-constrained solver: it builds linear models by interpolation at the n+1 vertices of a simplex and steers by an L-infinity exact-penalty merit function. Supply a CostFunction with a canonical Constraints declaration containing any combination of box bounds, linear equalities and inequalities, and nonlinear equalities and inequalities. Pass the problem directly to the executor; nonlinear values use the separate NonlinearEqualityValues and NonlinearInequalityValues capabilities. The solver folds the full feasible set into inequalities while retaining Basin’s interpolation algorithm. Bound constraints do not guarantee feasible callbacks, and radius convergence does not certify feasibility. Uses SelectedState for the filter-selected point and an unscaled LInf violation report tagged PrimaModeration; the solver owns its model and radius. Supports f32 and f64 on every dense backend release. Only present linear blocks require MatrixShape, MatrixFinite, and MatVecInto; nonlinear-only input needs no matrix type. Nonempty nonlinear callbacks count as residual evaluations. Implements Powell (1994), ported from PRIMA.
  • SolisWets: adaptive random local search: a randomized hill-climber testing x + b + d and x − b − d with d ~ N(0, ρ²I), a success-direction bias b, and a step size ρ that expands after 5 successive successes and contracts after 3 failures. The cheapest local search in the library (O(n) memory and time, cost evaluations only) and the classic memetic LS operator. Needs only a CostFunction. Supports all four dense backends with f32 or f64 and publishes PointState; the solver owns its bias and adaptive step size. Implements Solis & Wets (1981).
  • Brent: robust 1-D minimization on a bracketed interval (Brent, 1973, as transcribed in Numerical Recipes §10.2); also used inside line searches.
  • GoldenSection: golden-section search: 1-D minimization on a bracketed interval, the robust linearly-converging companion to Brent (Kiefer, 1953; Numerical Recipes §10.1).

Quasi-Newton

  • Bfgs: dense quasi-Newton with a full inverse-Hessian approximation (Nocedal & Wright, 2006). Supports all four dense backends with f32 or f64. Optional fixed initial matrices require cloning and entry access; closure initializers require entry access. Named initializers enforce their own seed contracts.
  • Lbfgs: limited-memory BFGS for larger problems (two-loop recursion, Nocedal & Wright Alg. 7.4). Supports all four dense backends with f32 or f64; parameter storage must be contiguous (including ndarray).
  • Lbfgsb: L-BFGS with box bounds; a faithful port of the Nocedal–Zhu L-BFGS-B v3.0 Fortran source (Byrd, Lu & Nocedal, 1995; Zhu, Byrd, Lu & Nocedal, 1997, ACM TOMS Alg. 778; Nocedal & Morales, 2011). Supports all four dense backends with f32 or f64 and contiguous parameter storage. A custom line search must implement bounded steps.

Trust Region

For problems exposing a Hessian or, matrix-free, a HessianProduct (either analytic, or synthesized by FiniteDiff):

  • TrustRegion: second-order trust-region Newton minimizer (Nocedal & Wright, 2006, Alg. 4.1). The subproblem strategy is pluggable: Steihaug (truncated CG, the default), Dogleg, MoreSorensen (the near-exact secular solve with hard-case treatment; Moré & Sorensen, 1983, “Computing a Trust Region Step”), or CauchyPoint. TrustRegion::matrix_free() drives the subproblem purely through Hessian-vector products (HessianProduct), never forming a matrix, so it scales to large problems (Steihaug and CauchyPoint only; Dogleg and MoreSorensen need the matrix). With ndarray, exact-Hessian mode requires a supplied Array2 Hessian because FiniteDiff cannot construct one. Its matrix-free Hessian-vector products work on every backend. Both modes publish FirstOrderState and support f32 and f64.

Nonlinear Least Squares

For problems expressed as residuals (Residual + Jacobian):

All five solvers accept RobustLeastSquares to fit with Huber, soft-L1, Cauchy, arctangent, or custom losses and a residual scale. The adapter adjusts the Gauss–Newton model while reporting the true robust objective. It supports f32 and f64 on each solver’s supported backends and also exposes the objective to general optimizers. See the loss API and model for the safeguarded curvature formula, following Triggs et al. (1999), Bundle Adjustment — A Modern Synthesis, and SciPy’s least-squares wrapper.

  • GaussNewton: undamped normal-equations solver (Madsen, Nielsen & Tingleff, 2004, §3.1).
  • LevenbergMarquardt: damped least squares; the workhorse for curve fitting. Marquardt (1963) with Moré (1978)/MINPACK column scaling and scaled trust-region damping by default for both f32 and f64. LmDamping::Nielsen selects Nielsen’s (1999) smooth damping update (Madsen, Nielsen & Tingleff, 2004, §3.2). The default LmDamping::TrustRegion selects damping against a scaled radius, following MINPACK’s lmder radius updates with a bracketed parameter search. Both damping strategies retain Basin’s stopping tests.
  • LevenbergMarquardtQr: opt-in pivoted QR with the same configurable damping and stopping rules as LevenbergMarquardt. Avoids forming the Gram matrix; supports all four dense backends, with numerical rank checks after regularization. Sparse QR is not supported. Madsen, Nielsen & Tingleff (2004), Methods for Non-Linear Least Squares Problems, §3.2; MINPACK’s qrfac and qrsolv (Garbow, Hillstrom & Moré, 1980). The default trust-region damping follows MINPACK’s lmder radius updates, using bracketed parameter selection instead of lmpar.
  • BoundedLevenbergMarquardt: bounded Levenberg–Marquardt with Coleman–Li affine scaling, Nielsen damping, and strictly feasible steps. Supports all four dense backends, nalgebra-sparse, and faer-sparse, for f32 and f64. Sparse Jacobians require the diagonal of JᵀJ in the CSC pattern. Named Trf in Basin 1.x. Branch, Coleman & Li (1999), “A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems,” SIAM Journal on Scientific Computing 21(1), 1–23 (doi:10.1137/S1064827595289108).
  • TrustRegionReflective: dense trust-region-reflective least squares with an explicit radius, reflected steps, a rank-aware SVD solve, and fixed-parameter elimination. Supports all four dense backends in pure Rust, including f32 and f64. Branch, Coleman & Li (1999), “A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems,” SIAM Journal on Scientific Computing 21(1), 1–23 (doi:10.1137/S1064827595289108); Moré (1978), “The Levenberg-Marquardt Algorithm: Implementation and Theory,” Numerical Analysis, Lecture Notes in Mathematics 630, 105–116 (doi:10.1007/BFb0067700). Reference comparisons use SciPy 1.16.2’s dense TRF.

Global & Stochastic

  • Direct: original DIRECT for deterministic global optimization over finite box bounds. It selects potentially optimal rectangles by their center costs and half-diagonals, then trisects every longest axis. Fixed coordinates are eliminated, and PointState exposes the best sampled point. All four dense backends support f32 and f64. Normalized radius stopping defaults to 1e-6; relative volume stopping is opt-in. Cross-validated against SciPy 1.16.2 with locally_biased=False. Reference: Donald R. Jones, Cary D. Perttunen, and Bruce E. Stuckman, “Lipschitzian optimization without the Lipschitz constant,” Journal of Optimization Theory and Applications 79, 157–181 (1993), especially pp. 169–170, the subdivision procedure and Definition 4.1, doi:10.1007/BF00941892.
  • Gbnm: Globalized Bounded Nelder-Mead over a feasible box. It combines projected local simplex searches with Parzen-density probabilistic restarts and the small-, flat-, and degenerate-simplex restart state machine. It retains the possible local optima found along the way and supports exact solver-aware resume. Publishes PointState while the solver owns local geometry and restart history. Supports all four dense backends with f32 or f64. Implements M. A. Luersen and R. Le Riche, “Globalized Nelder–Mead method for engineering optimization,” Computers & Structures 82 (2004), 2251–2260 (doi:10.1016/j.compstruc.2004.03.072).
  • SimulatedAnnealing: classical single-proposal simulated annealing with a user-supplied Neighbor, explicit geometric, reciprocal, or normalized-log cooling, and optional independently composable schedule restart triggers. ProposalState retains accepted progress and acceptance history; the solver owns its neighbor, RNG, and cooling history. Supports all four dense backends with f32 or f64. It accepts arbitrary cloneable parameter types, including discrete structures, and supports exact solver-aware resume. Uses Metropolis et al. (1953; DOI 10.1063/1.1699114), implements Kirkpatrick, Gelatt & Vecchi (1983; DOI 10.1126/science.220.4598.671), and takes its logarithmic-schedule context from Hajek (1988; DOI 10.1287/moor.13.2.311).
  • CmaEs/BoundedCmaEs: covariance-matrix adaptation evolution strategy (Hansen, 2016), unconstrained and box-bounded; the bounded variant uses Hansen’s adaptive BoundPenalty (the pycma default). Publishes PopulationProgress with an evaluated mean; distributions and penalty history live on the solver. The bounded variant publishes repaired points and raw costs, retaining penalized rankings in its model. All four dense backends support f32 and f64.
  • De: differential evolution over a feasible box, with six mutation rules, independently selected binomial or exponential crossover, and optional generation-wise mutation dithering. Defaults to DE/rand/1/bin and supports exact resume and DeInject local refinement. All four dense backends support f32 and f64. Implements R. Storn and K. Price, “Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces,” Journal of Global Optimization 11 (1997), 341–359. Mutation formulas, crossover, and dithering follow SciPy 1.16.2 differential evolution, which also supplies the donor and solution references. Publishes PopulationProgress and supports all four dense backends with f32 or f64.
  • GlobalBestPso: synchronous inertia-weight global-best particle swarm optimization over a feasible box, with independent boundary-response and velocity-limit policies. Implements Kennedy & Eberhart’s (1995; DOI 10.1109/ICNN.1995.488968) update with Shi & Eberhart’s inertia formulation (1998; DOI 10.1109/ICEC.1998.699146) and the Standard PSO 2006 coefficient/population profile (Bratton & Kennedy, 2007; DOI 10.1109/SIS.2007.368035), and is cross-validated against Argmin 0.11.0 commit c94c32adefd6c2525ce05806092ca868ec85fba4. It remains distinct from SPSO-2011 (Zambrano-Bigiarini, Clerc & Rojas, 2013; DOI 10.1109/CEC.2013.6557848). Publishes PopulationProgress; the solver owns particle velocities, personal bests, and RNG state. Supports all four dense backends with f32 or f64 and requires solver-aware exact checkpoints.
  • RandomSearch: elitist (1+λ) uniform sampling over a box. Publishes PopulationProgress, accepts explicit initial members, and supports all four dense backends with f32 or f64.
  • Ssga: steady-state real-coded genetic algorithm (replace-worst) with BLX-α crossover (Eshelman & Schaffer, 1993), negative assortative mating (Fernandes & Rosa, 2001), and BGA mutation (Mühlenbein & Schlierkamp-Voosen, 1993); the SSGA component of Molina et al. (2010), §4.4. Publishes PopulationProgress and supports all four dense backends with f32 or f64.
  • BasinHopping: basin-hopping (Wales & Doye, 1997): a Metropolis Monte-Carlo walk over the Ẽ(x) = min{f(x)} transform, wrapping any local solver with a pluggable step taker and acceptance test; adaptive step size on by default. Publishes PointState and supports all four dense backends with f32 or f64 when the chosen inner solver does. Custom step takers or inner solvers can narrow backend support.

Memetic (Composed)

These run a local solver inside a global one using Basin’s solver composition primitives. Custom inner solvers or local-search operators can narrow backend support. Bounded CMA and DE injection require RelaxedInner::new(inner) when an unconstrained local solver explores the bounded objective. Local solvers that enforce the same box can be supplied directly.

  • CmaInject/BoundedCmaInject: CMA-ES with per-generation local polishing of the best individuals, re-injected via Hansen’s (2011) injection mechanism. Publishes PopulationProgress and preserves all six evaluation categories. All four dense backends support f32 and f64 with a compatible inner solver; custom inners can narrow that support.
  • DeInject: differential evolution with per-generation top-k local refinement and conditional write-back. References: Noman & Iba, Accelerating Differential Evolution Using an Adaptive Local Search (IEEE TEC, 2008); Neri & Tirronen, Recent advances in differential evolution: a survey and experimental analysis (Artificial Intelligence Review, 2010); and Caponio, Neri & Tirronen, Super-fit control adaptation in memetic differential evolution frameworks (Soft Computing, 2009). Publishes PopulationProgress and supports all four dense backends with f32 or f64 when the chosen inner solver does. Nelder-Mead with RelaxedInner and L-BFGS-B cover all four; custom inners or strategies can narrow support.
  • MaLsCh/MaLsChCma: a memetic framework with persistent local-search chains and its CMA-ES configuration. Molina, Lozano, García-Martínez, and Herrera (2010), Memetic algorithms for continuous optimisation based on local search chains, Evolutionary Computation 18(1), 27–63 (DOI 10.1162/evco.2010.18.1.18102). Publishes PopulationProgress; the solver owns retained chains, their eligibility history, and RNG. Supports all four dense backends with f32 and f64, using CMA-ES’s matrix capabilities. Requires SamplingBounds on an unconstrained objective, or SamplingDomain::new(problem) for an existing box-only objective. Local chains and accepted points may leave the sampling box.
  • MaLsChSw: the high-dimensional sibling of MaLsChCma: the same local-search-chain framework with a Solis-Wets inner, whose O(n) chain snapshots keep chain-memetic search viable when the dimension grows (MA-SW-Chains: Molina, Lozano, and Herrera, 2010, winner of the CEC’2010 large-scale competition). Publishes PopulationProgress and supports all four dense backends with f32 and f64 using only vector operations. Both are type aliases of the generic MaLsCh<V, LS, F>, which accepts any local-search operator implementing the ResumableInner (seed + snapshot + resume) trait.

Constrained

  • Slsqp: dense Han–Powell sequential least-squares programming with damped BFGS, constrained least-squares subproblems, and an inexact L1 merit line search. Supports box bounds, linear and nonlinear equalities, and linear and nonlinear inequalities through the canonical Constraints declaration, with analytic or finite-difference derivatives. Only present nonlinear blocks require ConstraintJacobian; linear-only sets need no nonlinear callback. Reports feasibility, projected Lagrangian stationarity, and complementarity on the solver alongside Kraft’s native convergence tests. Uses SelectedFirstOrderState with a matching objective gradient and an unscaled L1 violation report tagged NonFiniteToInfinity. Supports f32 and f64 on every dense backend release; vectors need indexing and matrices need shape and finite entry access. Each block can use independent storage. Kraft, D. (1988), A software package for sequential quadratic programming, Technical Report DFVLR-FB 88-28, Institut für Dynamik der Flugsysteme, Oberpfaffenhofen, §§2.2 and 3.2 (report). Reference implementation: Jacob Williams’s SLSQP 1.6.1, commit 97884f98042624007f736dc536fa5636906ff26a, original NNLS and inexact line search.

The following wrap a gradient inner solver in an outer loop for linear constraints:

  • BarrierMethod: two-phase log-barrier interior-point continuation for linear inequality constraints (A x ≤ b); automatically finds a strictly feasible start when one exists (Boyd & Vandenberghe, Convex Optimization, §§11.3–11.4.1). Publishes PointState with the original objective inside the strict feasible domain and a rejection cost of positive infinity outside it. Incumbents contain only strictly feasible points. Supports all four dense backends with f32 or f64; custom inner solvers can require additional capabilities.
  • AugmentedLagrangianMethod: quadratic penalty plus multiplier updates for linear equality constraints (A x = b); tolerates an infeasible start (Nocedal & Wright, §17.3, Alg. 17.4, LANCELOT-style). Publishes SelectedState with the objective and unscaled L2 constraint-violation report, retaining an incumbent chosen by feasibility before objective. Supports all four dense backends with f32 or f64; custom inner solvers can require additional capabilities.

The pluggable line searches are documented alongside the first-order solvers: Backtracking (Armijo; Nocedal & Wright §3.1), Wolfe (strong Wolfe; Nocedal & Wright Alg. 3.5/3.6), MoreThuente (Moré & Thuente, 1994; a port of MINPACK-2’s dcsrch), and HagerZhang (ordinary and approximate Wolfe; Hager & Zhang, 2005, DOI 10.1137/030601880).

Backends and Constraints

All vector-based solvers support the four dense backends: Vec, nalgebra, ndarray, and faer. Scalar algorithms need no linear-algebra backend. Each solver’s Backends section on docs.rs describes its supported scalar types, sparse support, and any additional requirements.

Box bounds and other constraints belong to the problem. Choose a solver that supports those constraints, or use an explicit projection, barrier, or penalty adapter.

See Getting Started for a worked example, or open the Visualizer to watch several of these solvers converge.