Module Jera.Minimize

The type for methods for objectives of type 'f over values of type 'x.

bfgs ~linear is BFGS, for a smooth objective of up to some thousands of unknowns.

Method. Keeps an estimate H of the inverse Hessian, scaled to yᵀs / yᵀy before its first update, and takes Broyden, Fletcher, Goldfarb and Shanno's rank-two update after each step s that changed the gradient by y; each step is −H ∇f, searched to the strong Wolfe conditions by bracketing and zoom (Nocedal and Wright, Algorithms 3.5 and 3.6), so every update keeps H positive-definite. Cost. n² numbers and O(n²) work per iteration, one evaluation of f and its gradient per trial; superlinear convergence near a minimum.

lbfgs ~memory ~linear is limited-memory BFGS (Liu and Nocedal, 1989), for a smooth objective of many unknowns.

Method. The direction is the two-loop recursion over the last memory pairs of steps and gradient changes, with the initial inverse Hessian yᵀs / yᵀy of the newest pair; a pair of non-positive curvature enters neither loop. Steps are searched as bfgs's. Cost. 2 memory n numbers and O(memory n) work per iteration; linear convergence.

Raises Invalid_argument if memory < 1.

newton ~linear is Newton's method, for a smooth, ill-conditioned objective.

Method. Each step solves H δ = −∇f with linear on rune's Hessian-vector products, truncated by its tolerance with Linear.cg, then backtracks by halving from x + δ to the sufficient decrease f ≤ f x + 10⁻⁴ ∇fᵀ (α δ), Bertsekas's (1982) search, so near a minimum it takes the full step. Where the sufficient decrease's bound rounds to f x, a decrease f cannot show, a trial decreases where the gradient's norm strictly falls, as System.newton's search does on |f| for ∇f = 0. A Hessian that is not positive-definite gives a step that is not downhill, or ends Linear.cg, and the lane stalls. Cost. One solve of linear per iteration and one evaluation of f and its gradient per trial; quadratic convergence near a minimum.

levenberg_marquardt r ~linear is for |r x|² / 2 given by its residual r, a value of structure r whose float tensors are one vector.

Method. Each iteration materialises r's Jacobian J with one Jacobian-vector product per unknown and solves (JᵀJ + λ D) δ = −Jᵀ r with linear; D is the running maximum of JᵀJ's diagonal. A step is accepted when it achieves more than 10⁻⁴ of the decrease the linear model predicts: the decrease of |r|² / 2 measured or, where that changes by less than its rounding √ε |r|² / 2, estimated from rune's gradients at the step's ends, −(∇ + ∇') · s / 2, so a minimum with residuals left still converges. λ then falls, and grows on each rejection (Nielsen, 1999), so near a small-residual minimum the steps are Gauss–Newton's. Error. The undamped step is the Gauss–Newton step at the estimate, solved once the damped step has met the test. Stability. The normal equations square J's condition: above about ε^(−1/2) its steps lose accuracy and convergence slows, while the answer's equation is unaffected. Cost. n products and one solve of linear per iteration, and one evaluation of r per trial. Derivative. The minimum is the zero of rune's gradient of |r|² / 2; at a rank-deficient minimum the derivative does not exist and is not finite.

nelder_mead is the Nelder–Mead simplex, for an objective with no useful gradient: non-smooth or piecewise constant.

Method. The simplex of x0 and x0 + h_i e_i, h_i a twentieth of x0_i or 2.5 · 10⁻⁴ where it is zero, reflects its worst vertex through the others' centroid and expands, contracts or shrinks, with Gao and Han's (2012) coefficients for n unknowns, 1, 1 + 2/n, 3/4 − 1/(2n) and 1 − 1/n, so the simplex keeps its shape as n grows. Error. e is the simplex's diameter per component around its best vertex, y that vertex. Once e meets tol, the points y ± σ e_i are evaluated, σ twice the largest component of e and of tol's scale at y, or where both are 0, as a relative tol's scale is at y = 0, the first simplex's largest step at y: if none is lower than y by 10⁻⁴ of the norm of each pair's lower difference from f y, a point where f is not finite differing by 0, the lane converges, and otherwise it continues from the simplex of y and the lower point of each pair (Kelley, 1999). Where f is smooth and its gradient is not zero, one of the 2n directions ±e_i descends, so a lane converges where a step σ along none of them descends by that margin; a diameter alone converges on McKinnon's function at a point whose gradient is (0, 1). A non-finite value counts as +∞, one at the start ends the lane Not_finite. budget counts evaluations. Cost. One evaluation per trip, two when it expands or contracts, n + 1 more when it shrinks, and 2n for each diameter that meets tol. Derivative. None: its answer is the detached best vertex, since an objective with no useful gradient has a minimum with no equation.

solve x m ~lo ~hi ~tol ~budget f x0 is a local minimum of f from x0 by m, in the box [lo, hi] when either side is given: values of x0's structure whose float tensors bound each coordinate from below and from above. −∞ in lo or +∞ in hi is no bound, and an absent side is none in any coordinate: ~lo:(Nx.Ptree.map x (fun _ a -> Nx.zeros_like a) x0) alone keeps every coordinate nonnegative.

Box. bfgs and lbfgs take the generalised Cauchy point and subspace step of L-BFGS-B (Byrd, Lu, Nocedal and Zhu, 1995): the projected gradient path P (x − t ∇f), P the projection on the box, is walked segment by segment to the first minimum of the method's quadratic model, every coordinate that reached its bound held there; the model is then minimised over the free coordinates, truncated to the box, and the step to that point is searched to the strong Wolfe conditions within it. Many bounds change in one step, as they do on the path. lbfgs's model is its compact representation, O(n m) numbers per step; bfgs's is H⁻¹, n². newton takes Bertsekas's (1982) projected step: the coordinates within ε of a bound whose gradient pushes out of the box are held, ε the norm of x − P (x − ∇f x), its Hessian solve acts on the others and −∇f on the held ones, and the search backtracks by halving along the projection arc P (x + α d) to the sufficient decrease f ≤ f x + 10⁻⁴ ∇fᵀ (P (x + α d) − x), or where its bound rounds to f x to a strict fall of the norm of x − P (x − ∇f x). levenberg_marquardt holds the same coordinates and solves its damped system on the others, with the diagonal of JᵀJ + λ D on the held ones, so every step tends to zero as λ grows; its trial point is P (x + δ), rejected where the linear model predicts no decrease there. nelder_mead clips its vertices and the points y ± σ e_i of its convergence test: where f is smooth and x − P (x − ∇f x) is not zero, one of the directions ±e_i descends and stays in the box (Lewis and Torczon, 1999), and where the box clips one of a pair to y the other enters the simplex the lane continues from. The undamped step is the projected one, P (x + δ) − x, and the gradient of bfgs's and lbfgs's bound the projected one, x − P (x − ∇f x). The answer is stated as the zero of x − P (x − ∇f x), so its derivative is zero in a coordinate held at a constant bound and follows a bound that moves; that system is not symmetric, so its linear must not be Linear.cg. A box that holds no point, where a coordinate's lo exceeds its hi or is +∞ or its hi is −∞, or either is NaN, ends the lane Stalled.

x0 is projected on the box first. Its evaluations count the calls of f, with its gradient for a gradient method, and budget its iterations, or its evaluations for nelder_mead.

Raises Invalid_argument if budget < 1, if the float tensors of x0 differ in dtype, if lo or hi differs from x0 in its structure or the shape of a float tensor, naming the path, or if f returns other than a scalar.

iterates x m ~steps f x0 is the first steps estimates of m's search from x0, x0 first, detached, stacked on a new leading axis of every tensor. A lane stops at a zero gradient, or when its search finds no decrease, and then repeats its estimate. Its tensors that are not floats are x0's, repeated.

Raises Invalid_argument if steps < 1, or as solve does.

bracket ~tol f ~lo ~hi is a minimum of f in each [lo, hi], elementwise: every element is its own problem, the ends broadcast together and come in either order, and f must compute each element of its result from the same element of its argument alone.

Method. Brent's method: parabolic steps through the three best points, forced to a golden-section step whenever the bracket has not shrunk by 0.618 over two evaluations, so an element ends within about 3b evaluations for a b-bit dtype. On a function with several minima in the bracket it finds one of them. Error. e is half the final bracket and y its midpoint; an element also ends when no float lies strictly inside its bracket. A non-finite value of f ends it Not_finite. Derivative. A minimum inside the bracket is stated as a zero of rune's derivative of f, so its derivative is −∂²f/∂x∂θ / ∂²f/∂x²; a minimum at an end is that end, with its derivative; a lane that did not converge has a zero derivative.