Module optimize 

Minimizing a function of several variables, and solving equations, nonlinear or linear.

minimize runs one of five methods on an Objective. solve finds a zero of a Mapping, or its least-squares solution where it gives more values than it has variables: by Brent’s method for one equation in one variable, and by Levenberg–Marquardt otherwise. solve_linear solves A x = b by a Krylov method, where a Mapping gives A’s products with vectors, and solve_affine solves f(x) = 0 the same way for an affine f, through f’s values alone. Options gives the method, the bounds and when to stop. Where it gives no method, Method::choose picks one for the Task.

minimize and solve start from the start point moved inside the bounds, evaluate the function only inside them, and return the best point they evaluated. A NaN value counts as +∞. An error from the function stops the search and comes back as the front’s error. A search that uses up its evaluations returns its best point with converged false.

The Krylov methods use A only through its products. Conjugate gradients (CG) solves a symmetric positive definite system, MINRES a symmetric one, and GMRES any square one. Least squares runs CG or MINRES on the normal equations AᵀA x = Aᵀb, with one product with A and one with Aᵀ for each product with AᵀA. MINRES there gives the iterates of Fong and Saunders’ LSMR, and CG those of CGLS, which match Paige and Saunders’ LSQR. Running on AᵀA squares A’s condition number. On ill-conditioned problems that costs some accuracy next to LSMR’s and LSQR’s own Golub–Kahan bidiagonalization, which works on A itself. A mapping’s Mapping::precondition gives a preconditioner, an approximation to the inverse of the matrix the method runs on, which cuts the steps a solve needs. CG and MINRES apply it on each step, and GMRES on the right. CG and MINRES both build on the Lanczos process. MINRES and GMRES both track the residual through plane rotations, the same ones the tridiagonal and bidiagonal iterations use.

Structs

Bounds

The least and greatest value of each variable. An infinite limit leaves that side open.

Differentiable

A function and its derivative, from two closures. As an Objective, value gives the value and derivative writes the gradient. As a Mapping, value writes the values and derivative takes (u, x, out) and writes the vector–Jacobian product.

Found

What a front found.

Options

What a front runs and when it stops. Options::default() lets Method::choose pick the method and leaves every variable unbounded.

Enums

Method

The methods minimize, solve and solve_linear run.

Task

What a front is for, which decides the methods that suit it.

Constants

GMRES_RESTART

The most steps GMRES takes between restarts. A system with fewer unknowns restarts after one step for each unknown.

Traits

Mapping

A function from a slice of F to a slice of F, for solve and solve_linear. A closure that writes the values into its second argument and returns a Result is one. Differentiable adds vector–Jacobian products.

Objective

A function of a slice of F to minimize. A closure that returns a Result is one. Differentiable adds a gradient.

Functions

minimize

The minimum of objective from start, by the method Options::method_for gives.

solve

A zero of mapping from start, by the method Options::method_for gives. first holds mapping’s values at start, which the caller computes. They give the number of values, and count as the search’s first evaluation. Where mapping gives more values than it has variables, the result is the least-squares solution, and where it gives fewer, a nearby solution.

solve_affine

The solution of f(x) = 0 for an affine f, f(x) = A x − b, from start, by solve_linear on products that it computes from f’s values alone. first holds f(start), which the caller computes. It gives the number of residuals, and serves as f(0) where start is zero. f(0) gives −b. Each product A v is (f(t v) − f(0)) ÷ t, for the power of two t that makes t |A v| about 16 |b|. The subtraction of f(0) then loses no digits, however large b is. f’s vjp gives the transpose’s products, and its precondition the preconditioner’s. A product evaluates f once, or twice where the ratio |A v| ÷ |v| from the last product gave too small a t. evaluations counts products, as for solve_linear.

solve_linear

The solution of A x = b from start, by the method Options::method_for gives. a gives A’s products with vectors, and b has one item for each equation. A system that isn’t square, or whose a gives products with A’s transpose through Mapping::vjp, gets its least-squares solution, from the normal equations AᵀA x = Aᵀb. A right-hand side of zeros gives zeros. a’s Mapping::precondition gives the products of a preconditioner M, which approximates A⁻¹, or (AᵀA)⁻¹ for least squares. CG and MINRES need M symmetric positive definite, and GMRES applies it on the right. A good M cuts the products a solve needs.