optimize

package
v0.8.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 19, 2026 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Package optimize implements one-dimensional root finding and function optimization for real-valued functions of a single real variable.

The package gathers the classical numerical methods used to locate the zeros and extrema of a scalar function. It is organised into several families:

  • Bracketing solvers, which start from an interval [a, b] on which the function changes sign and are guaranteed to converge: Bisection, RegulaFalsi (with the Illinois, Pegasus and Anderson-Björck accelerations), Brent's method (zeroin), Ridders' method and Dekker's method.
  • Open solvers, which iterate from one or more starting guesses and converge quickly when close to a simple root: Secant, Newton, Halley, Schröder (for multiple roots), Steffensen, inverse quadratic interpolation, Muller's method and fixed-point iteration (optionally accelerated with Aitken's Δ² process).
  • Polynomial solvers, which return all real (or complex) roots of a polynomial: closed forms for linear, quadratic and cubic equations, and the iterative Durand-Kerner and Aberth-Ehrlich methods together with a companion-matrix constructor.
  • Minimizers, which locate a local minimum of a unimodal function: golden-section search, Brent's parabolic minimizer, ternary search and Newton/gradient descent on the derivative, plus routines that bracket a minimum.
  • Supporting numerical utilities: finite-difference derivatives, sign and bracketing predicates, and convergence helpers.

Polynomials are represented throughout as a slice of coefficients in ascending order of degree: coeffs[i] is the coefficient of x^i, so that coeffs = {c0, c1, c2} denotes c0 + c1*x + c2*x^2.

Every routine is deterministic and depends only on the Go standard library.

Index

Constants

View Source 
const DefaultLearningRate = 0.01

DefaultLearningRate is a reasonable default step size for the first-order descent methods when the caller has no specific requirement.

View Source 
const DefaultMaxIter = 1000

DefaultMaxIter is a reasonable default cap on the number of iterations performed by the iterative multivariate routines.

View Source 
const DefaultMaxIterations = 100

DefaultMaxIterations is a reasonable default cap on the number of iterations performed by the iterative routines before they give up.

View Source 
const DefaultStep = 1e-6

DefaultStep is the default finite-difference step used by the numeric gradient and directional-derivative routines when the caller passes h <= 0.

View Source 
const DefaultTol = 1e-8

DefaultTol is a reasonable default convergence tolerance for the multivariate routines.

View Source 
const DefaultTolerance = 1e-10

DefaultTolerance is a reasonable default convergence tolerance for the iterative routines when the caller has no specific requirement.

View Source 
const GoldenRatio = 1.6180339887498948482045868343656381

GoldenRatio is the golden ratio phi = (1 + sqrt(5)) / 2.

View Source 
const InvGoldenRatio = 0.6180339887498948482045868343656381

InvGoldenRatio is the reciprocal of the golden ratio, 1/phi = phi - 1, the shrink factor used by golden-section search.

Variables

View Source 
var ErrDimensionMismatch = errors.New("optimize: vector or matrix dimensions do not match")

ErrDimensionMismatch is returned when two vectors or a matrix and a vector have incompatible lengths.

View Source 
var ErrEmptyPoint = errors.New("optimize: starting point has zero length")

ErrEmptyPoint is returned when a routine is called with an empty starting point.

View Source 
var ErrInvalidInterval = errors.New("optimize: invalid interval")

ErrInvalidInterval is returned when an interval or set of starting points is degenerate or otherwise unusable.

View Source 
var ErrMaxIterations = errors.New("optimize: maximum number of iterations exceeded before convergence")

ErrMaxIterations is returned when a routine exhausts its iteration budget before satisfying the requested tolerance.

View Source 
var ErrNoBracket = errors.New("optimize: interval does not bracket a root (endpoints share the same sign)")

ErrNoBracket is returned by bracketing solvers when the supplied endpoints do not straddle a root, i.e. the function has the same sign at both ends.

View Source 
var ErrNonFinite = errors.New("optimize: encountered a non-finite value")

ErrNonFinite is returned when a computation produces a NaN or infinite value.

View Source 
var ErrSingularMatrix = errors.New("optimize: matrix is singular")

ErrSingularMatrix is returned by SolveLinearSystem and the Newton solver when the coefficient matrix is (numerically) singular.

View Source 
var ErrZeroDerivative = errors.New("optimize: derivative (or denominator) evaluated to zero")

ErrZeroDerivative is returned when a method divides by a derivative or a finite difference that has collapsed to zero.

Functions

func Aberth 

func Aberth(coeffs []float64, tol float64, maxIter int) []complex128

Aberth returns all n roots (real and complex) of the degree-n polynomial given by coeffs (ascending order) using the Aberth-Ehrlich simultaneous iteration, which incorporates the derivative for cubic local convergence and typically needs fewer iterations than Durand-Kerner. Initial guesses are distributed on a circle whose radius bounds the roots.

func AbsoluteError 

func AbsoluteError(a, b float64) float64

AbsoluteError returns the absolute difference |a - b|.

func AitkenDelta2 

func AitkenDelta2(x0, x1, x2 float64) float64

AitkenDelta2 applies a single step of Aitken's Δ² process to three consecutive terms x0, x1, x2 of a linearly convergent sequence and returns the accelerated estimate of the limit. When the second difference is zero it returns x2 unchanged.

func AndersonBjorck 

func AndersonBjorck(f Func, a, b, tol float64, maxIter int) (float64, error)

AndersonBjorck finds a root of f in [a, b] using the Anderson-Björck variant of the method of false position, whose damping factor 1-fc/fb yields asymptotic convergence close to that of the secant method while retaining the bracketing guarantee.

func ArmijoStep 

func ArmijoStep(f MultiFunc, x, dir, grad []float64) float64

ArmijoStep is a convenience wrapper around BacktrackingLineSearch using the conventional parameters alpha0 = 1, c = 1e-4, rho = 0.5 and 50 reductions.

func BacktrackingLineSearch 

func BacktrackingLineSearch(f MultiFunc, x, dir, grad []float64, alpha0, c, rho float64, maxIter int) float64

BacktrackingLineSearch returns a step length alpha along the descent direction dir from x that satisfies the Armijo (sufficient decrease) condition f(x + alpha*dir) <= f(x) + c*alpha*(grad . dir). Starting from alpha0 it repeatedly multiplies the step by rho (0 < rho < 1) until the condition holds or maxIter reductions have been made. grad must be the gradient of f at x and dir must be a descent direction (grad . dir < 0) for the guarantee to hold.

func BackwardDifference 

func BackwardDifference(f Func, x, h float64) float64

BackwardDifference approximates f'(x) by the backward difference (f(x)-f(x-h))/h, a first-order accurate one-sided estimate.

func Bisection 

func Bisection(f Func, a, b, tol float64, maxIter int) (float64, error)

Bisection finds a root of f in the bracketing interval [a, b] by repeated interval halving. It converges linearly and is unconditionally reliable whenever f is continuous and f(a) and f(b) have opposite signs. It returns ErrNoBracket if the interval does not straddle a root and ErrMaxIterations if the width tolerance is not reached within maxIter steps.

func Booth 

func Booth(x []float64) float64

Booth is the two-dimensional convex test objective (x0 + 2*x1 - 7)^2 + (2*x0 + x1 - 5)^2, with its unique minimum value 0 at (1, 3). It panics if x does not have length 2.

func BracketExpand 

func BracketExpand(f Func, a, b, factor float64, maxIter int) (float64, float64, bool)

BracketExpand geometrically expands the interval [a, b] outward (moving the endpoint with the larger |f| by a factor of the current width) until f changes sign across it or maxIter expansions have been tried. It reports the possibly-widened endpoints and whether a bracket was found.

func BracketMinimum 

func BracketMinimum(f Func, a, b float64) (float64, float64, float64)

BracketMinimum searches downhill from the initial points a and b to return a triple (a, b, c) with a < b < c (or c < b < a) such that f(b) is less than both f(a) and f(c), thereby bracketing a minimum. It implements the classic mnbrak algorithm.

func Brent 

func Brent(f Func, a, b, tol float64, maxIter int) (float64, error)

Brent finds a root of f in [a, b] using Brent's method (the classic zeroin algorithm), which combines the reliability of bisection with the speed of the secant method and inverse quadratic interpolation. It is the recommended general-purpose bracketing solver.

func BrentMinimize 

func BrentMinimize(f Func, a, b, tol float64, maxIter int) (float64, float64, error)

BrentMinimize returns the location and value of a minimum of f on [a, b] using Brent's method, which blends golden-section search with parabolic interpolation for fast, reliable convergence without requiring derivatives. It returns (xmin, f(xmin), error).

func Centroid 

func Centroid(points [][]float64) []float64

Centroid returns the arithmetic mean of a set of points, all assumed to have the same dimension. It returns nil for an empty set.

func Clamp 

func Clamp(x, lo, hi float64) float64

Clamp constrains x to the closed interval [lo, hi], swapping the bounds if they are given in the wrong order.

func CompanionMatrix 

func CompanionMatrix(coeffs []float64) [][]float64

CompanionMatrix returns the companion matrix of the polynomial given by coeffs (ascending order), a real n×n matrix whose characteristic polynomial equals the given polynomial made monic. Its eigenvalues are the roots of the polynomial. The matrix is returned in row-major order.

func Converged 

func Converged(prev, cur, tol float64) bool

Converged reports whether successive iterates prev and cur satisfy a combined relative/absolute convergence test with tolerance tol.

func CubicRealRoots 

func CubicRealRoots(a, b, c, d float64) []float64

CubicRealRoots returns the real roots of a*x^3 + b*x^2 + c*x + d = 0 in ascending order (with multiplicity), discarding any genuinely complex roots.

func CubicRoots 

func CubicRoots(a, b, c, d float64) []complex128

CubicRoots returns all three roots of the cubic a*x^3 + b*x^2 + c*x + d = 0 as complex numbers, using Cardano's formula together with the trigonometric solution for the three-real-roots case. When a is zero it degenerates to the quadratic case.

func Dekker 

func Dekker(f Func, a, b, tol float64, maxIter int) (float64, error)

Dekker finds a root of f in [a, b] using Dekker's method, the secant/bisection hybrid that is the historical predecessor of Brent's method. It maintains a bracketing contrapoint and falls back to bisection whenever the secant step leaves the interval.

func Derivative 

func Derivative(f Func, x, h float64) float64

Derivative approximates f'(x) by the central difference (f(x+h)-f(x-h))/(2h), which has second-order accuracy in h.

func DirectionalDerivative 

func DirectionalDerivative(f MultiFunc, x, dir []float64, h float64) float64

DirectionalDerivative approximates the derivative of f at x along the unit- scaled direction dir using a central finite difference with step h. If h <= 0 the DefaultStep is used. The direction need not be normalized; the returned value is grad(f) . dir.

func DurandKerner 

func DurandKerner(coeffs []float64, tol float64, maxIter int) []complex128

DurandKerner returns all n roots (real and complex) of the degree-n polynomial given by coeffs (ascending order) using the Durand-Kerner (Weierstrass) simultaneous iteration. The polynomial is made monic internally; roots are refined until the largest update falls below tol or maxIter iterations are reached.

func FalsePosition 

func FalsePosition(f Func, a, b, tol float64, maxIter int) (float64, error)

FalsePosition is an alias for RegulaFalsi, the traditional English name for the method of false position.

func FixedPoint 

func FixedPoint(g Func, x0, tol float64, maxIter int) (float64, error)

FixedPoint finds a fixed point of g (a value x with g(x) = x) by the direct iteration x_{n+1} = g(x_n) starting from x0. It converges linearly when g is a contraction near the fixed point.

func FixedPointAitken 

func FixedPointAitken(g Func, x0, tol float64, maxIter int) (float64, error)

FixedPointAitken finds a fixed point of g using Aitken's Δ² acceleration (Steffensen's fixed-point method): it applies g twice and extrapolates, turning linear convergence into quadratic convergence near the fixed point.

func ForwardDifference 

func ForwardDifference(f Func, x, h float64) float64

ForwardDifference approximates f'(x) by the forward difference (f(x+h)-f(x))/h, a first-order accurate one-sided estimate.

func GoldenSectionMin 

func GoldenSectionMin(f Func, a, b, tol float64, maxIter int) (float64, error)

GoldenSectionMin returns the location of a minimum of the unimodal function f on [a, b] using golden-section search, which narrows the bracket by the golden ratio at each step and needs a single function evaluation per iteration.

func GradientDescent 

func GradientDescent(df Func, x0, rate, tol float64, maxIter int) (float64, error)

GradientDescent locates a stationary point of a function by taking fixed-rate steps against its derivative df from the starting point x0. It converges for a sufficiently small rate and is included as a simple, dependency-free descent method.

func Halley 

func Halley(f, df, d2f Func, x0, tol float64, maxIter int) (float64, error)

Halley finds a root of f using Halley's method, a third-order iteration that uses the first derivative df and second derivative d2f. It converges cubically near a simple root, roughly one iteration faster than Newton's method.

func Himmelblau 

func Himmelblau(x []float64) float64

Himmelblau is the two-dimensional test objective (x0^2 + x1 - 11)^2 + (x0 + x1^2 - 7)^2, which has four equal local minima of value 0, one of which is (3, 2). It panics if x does not have length 2.

func Illinois 

func Illinois(f Func, a, b, tol float64, maxIter int) (float64, error)

Illinois finds a root of f in [a, b] using the Illinois variant of the method of false position, which halves the retained (stagnant) endpoint's function value to break the one-sided convergence of RegulaFalsi. It keeps the root bracketed and converges super-linearly.

func InverseQuadratic 

func InverseQuadratic(f Func, x0, x1, x2, tol float64, maxIter int) (float64, error)

InverseQuadratic finds a root of f by inverse quadratic interpolation through three starting points x0, x1 and x2: it fits x as a quadratic in f and evaluates it at f = 0. Where the three function values are not distinct it falls back to a secant step.

func IsBracket 

func IsBracket(f Func, a, b float64) bool

IsBracket reports whether [a, b] strictly brackets a sign change of f.

func LinearRoot 

func LinearRoot(a, b float64) (float64, bool)

LinearRoot returns the root of the linear equation a*x + b = 0. The boolean result is false when a is zero and no unique root exists.

func MatCopy 

func MatCopy(a [][]float64) [][]float64

MatCopy returns a deep copy of the matrix a.

func MatIdentity 

func MatIdentity(n int) [][]float64

MatIdentity returns the n-by-n identity matrix.

func MatTranspose 

func MatTranspose(a [][]float64) [][]float64

MatTranspose returns the transpose of the (rectangular) matrix a.

func MatVec 

func MatVec(a [][]float64, x []float64) []float64

MatVec returns the matrix-vector product a*x. It panics if the column count of a does not equal len(x).

func Muller 

func Muller(f func(complex128) complex128, x0, x1, x2 complex128, tol float64, maxIter int) (complex128, error)

Muller finds a (possibly complex) root of the complex function f using Muller's method, which fits a parabola through three starting points and takes the root of that parabola nearest the latest iterate. It is well suited to polynomials because it can converge to complex roots from real starting data.

func Newton 

func Newton(f, df Func, x0, tol float64, maxIter int) (float64, error)

Newton finds a root of f using the Newton-Raphson iteration, which requires the derivative df and a single starting guess x0. It converges quadratically near a simple root. It returns ErrZeroDerivative if df vanishes at an iterate.

func NewtonComplex 

func NewtonComplex(f, df func(complex128) complex128, x0 complex128, tol float64, maxIter int) (complex128, error)

NewtonComplex finds a complex root of the complex function f with derivative df using the Newton-Raphson iteration in the complex plane. It converges quadratically near a simple root and is the natural tool for tracing the roots of complex polynomials.

func NewtonMinimize 

func NewtonMinimize(df, d2f Func, x0, tol float64, maxIter int) (float64, error)

NewtonMinimize locates a stationary point of a function by applying Newton's method to its derivative, using the first derivative df and second derivative d2f. Near a non-degenerate minimum it converges quadratically. It returns ErrZeroDerivative if the second derivative vanishes.

func NewtonSafe 

func NewtonSafe(f, df Func, a, b, tol float64, maxIter int) (float64, error)

NewtonSafe finds a root of f in the bracketing interval [a, b] using a safeguarded Newton iteration (the rtsafe algorithm): it takes a Newton step when that step stays inside the current bracket and is decreasing, and falls back to bisection otherwise. It combines quadratic convergence with the global reliability of bisection.

func NumericGradient 

func NumericGradient(f MultiFunc, x []float64) []float64

NumericGradient approximates the gradient of f at x using central finite differences. It is a convenience alias for NumericGradientCentral with the DefaultStep.

func NumericGradientCentral 

func NumericGradientCentral(f MultiFunc, x []float64, h float64) []float64

NumericGradientCentral approximates the gradient of f at x using central finite differences with step h. If h <= 0 the DefaultStep is used. This is the most accurate of the finite-difference gradient estimators.

func NumericGradientForward 

func NumericGradientForward(f MultiFunc, x []float64, h float64) []float64

NumericGradientForward approximates the gradient of f at x using forward finite differences with step h. If h <= 0 the DefaultStep is used. It uses one fewer evaluation per coordinate than the central estimator at the cost of accuracy.

func NumericHessian 

func NumericHessian(f MultiFunc, x []float64, h float64) [][]float64

NumericHessian approximates the Hessian of f at x using central second differences with step h. If h <= 0 a step of 1e-4 is used. The returned matrix is symmetric by construction.

func NumericJacobian 

func NumericJacobian(g VectorFunc, x []float64, h float64) [][]float64

NumericJacobian approximates the Jacobian of the vector-valued function g at x using central finite differences with step h. If h <= 0 the DefaultStep is used. The result is an m-by-n matrix whose (i, j) entry is d g_i / d x_j.

func OppositeSign 

func OppositeSign(a, b float64) bool

OppositeSign reports whether a and b have strictly opposite signs.

func OuterProduct 

func OuterProduct(a, b []float64) [][]float64

OuterProduct returns the outer product a*b^T, an len(a)-by-len(b) matrix whose (i, j) entry is a[i]*b[j].

func ParabolicMinimum 

func ParabolicMinimum(x0, x1, x2, f0, f1, f2 float64) (float64, bool)

ParabolicMinimum fits a parabola through the three points (x0,f0), (x1,f1) and (x2,f2) and returns the abscissa of its vertex. The boolean result is false when the points are collinear and no unique vertex exists.

func PartialDerivative 

func PartialDerivative(f MultiFunc, x []float64, i int, h float64) float64

PartialDerivative approximates the partial derivative of f with respect to coordinate i at x by a central finite difference with step h. If h <= 0 the DefaultStep is used.

func Pegasus 

func Pegasus(f Func, a, b, tol float64, maxIter int) (float64, error)

Pegasus finds a root of f in [a, b] using the Pegasus variant of the method of false position. Like Illinois it damps the stagnant endpoint, but scales its function value by fb/(fb+fc), giving faster convergence in practice.

func PolyComplexRoots 

func PolyComplexRoots(coeffs []float64) []complex128

PolyComplexRoots returns all roots of the polynomial given by coeffs (ascending order) as complex numbers, using Durand-Kerner with default settings.

func PolyDeflate 

func PolyDeflate(coeffs []float64, root float64) ([]float64, float64)

PolyDeflate divides the polynomial given by coeffs (ascending order) by the linear factor (x - root) using synthetic division. It returns the ascending-order quotient coefficients and the scalar remainder, which is zero exactly when root is a root of the polynomial.

func PolyDerivative 

func PolyDerivative(coeffs []float64) []float64

PolyDerivative returns the coefficients (ascending order) of the derivative of the polynomial given by coeffs. A constant polynomial yields an empty slice.

func PolyEval 

func PolyEval(coeffs []float64, x float64) float64

PolyEval evaluates the polynomial with the given ascending-order coefficients at x using Horner's scheme. An empty slice evaluates to zero.

func PolyEvalComplex 

func PolyEvalComplex(coeffs []float64, x complex128) complex128

PolyEvalComplex evaluates the real-coefficient polynomial (ascending order) at a complex argument x using Horner's scheme.

func PolyEvalDeriv 

func PolyEvalDeriv(coeffs []float64, x float64) (float64, float64)

PolyEvalDeriv simultaneously evaluates the polynomial (ascending-order coefficients) and its first derivative at x in a single Horner pass, returning (value, derivative).

func PolyIntegral 

func PolyIntegral(coeffs []float64, constant float64) []float64

PolyIntegral returns the coefficients (ascending order) of an antiderivative of the polynomial given by coeffs, using constant as the value of the integration constant (the new degree-zero term).

func PolyRoots 

func PolyRoots(coeffs []float64, tol float64) []float64

PolyRoots returns the real roots of the polynomial given by coeffs (ascending order) in ascending order. A root is considered real when the magnitude of its imaginary part is within tol (scaled by the root magnitude) of zero.

func ProjectBox 

func ProjectBox(x, lo, hi []float64) []float64

ProjectBox returns a copy of x projected onto the axis-aligned box defined by the per-coordinate bounds lo and hi. It panics if the lengths differ.

func QuadraticRealRoots 

func QuadraticRealRoots(a, b, c float64) []float64

QuadraticRealRoots returns the distinct real roots of a*x^2 + b*x + c = 0 in ascending order. Complex roots are omitted, so the result has length 0, 1 or 2.

func QuadraticRoots 

func QuadraticRoots(a, b, c float64) (complex128, complex128)

QuadraticRoots returns both roots of the quadratic a*x^2 + b*x + c = 0 as complex numbers, using a numerically stable formulation that avoids cancellation. When a is zero it degenerates to the linear (or empty) case.

func QuarticRoots 

func QuarticRoots(a, b, c, d, e float64) []complex128

QuarticRoots returns all four roots of the quartic a*x^4 + b*x^3 + c*x^2 + d*x + e = 0 as complex numbers, computed with the Durand-Kerner iteration.

func RegulaFalsi 

func RegulaFalsi(f Func, a, b, tol float64, maxIter int) (float64, error)

RegulaFalsi (the method of false position) finds a root of f in [a, b] by linear interpolation between the bracketing endpoints. It keeps the root bracketed at all times but can converge slowly when one endpoint stagnates; see Illinois, Pegasus and AndersonBjorck for accelerated variants.

func RelativeError 

func RelativeError(approx, exact float64) float64

RelativeError returns the relative error of an approximation with respect to an exact value. When exact is zero it falls back to the absolute magnitude of the approximation.

func RichardsonDerivative 

func RichardsonDerivative(f Func, x, h float64) float64

RichardsonDerivative approximates f'(x) by Richardson extrapolation of the central difference at step sizes h and h/2, cancelling the leading error term to yield a fourth-order accurate estimate.

func Ridders 

func Ridders(f Func, a, b, tol float64, maxIter int) (float64, error)

Ridders finds a root of f in [a, b] using Ridders' method, which fits an exponential to the two endpoints and their midpoint to obtain a superlinearly convergent, always-bracketed iterate. It is robust and requires only two function evaluations per step.

func Rosenbrock 

func Rosenbrock(x []float64) float64

Rosenbrock is the classic non-convex test objective sum_i [100*(x_{i+1} - x_i^2)^2 + (1 - x_i)^2], with its global minimum value 0 at the all-ones point. It requires at least two coordinates.

func RosenbrockGrad 

func RosenbrockGrad(x []float64) []float64

RosenbrockGrad returns the exact gradient of Rosenbrock at x.

func SameSign 

func SameSign(a, b float64) bool

SameSign reports whether a and b are both strictly positive or both strictly negative.

func Schroeder 

func Schroeder(f, df Func, x0 float64, m int, tol float64, maxIter int) (float64, error)

Schroeder finds a root of known multiplicity m using the modified Newton (or Schröder) iteration x -= m*f/df, which restores quadratic convergence at a root where the ordinary Newton method would degrade to linear convergence. Passing m = 1 recovers the standard Newton method.

func Secant 

func Secant(f Func, x0, x1, tol float64, maxIter int) (float64, error)

Secant finds a root of f using the secant method, starting from two initial guesses x0 and x1. It approximates the derivative by a finite difference of successive iterates and converges super-linearly (order ≈ 1.618) near a simple root. It returns ErrZeroDerivative if two successive function values coincide.

func SecondDerivative 

func SecondDerivative(f Func, x, h float64) float64

SecondDerivative approximates f”(x) by the central difference (f(x+h)-2f(x)+f(x-h))/h^2, which has second-order accuracy in h.

func Sign 

func Sign(x float64) float64

Sign returns +1, -1 or 0 according to the sign of x.

func SignChange 

func SignChange(f Func, a, b float64) bool

SignChange reports whether f takes opposite-signed values at a and b, i.e. whether [a, b] is guaranteed (for continuous f) to contain a root.

func SolveLinearSystem 

func SolveLinearSystem(a [][]float64, b []float64) ([]float64, error)

SolveLinearSystem solves the linear system a*x = b for x using Gaussian elimination with partial pivoting. The inputs are left unmodified. It returns ErrSingularMatrix if the matrix is numerically singular and ErrDimensionMismatch if the shapes are inconsistent.

func Sphere 

func Sphere(x []float64) float64

Sphere is the separable convex test objective sum_i x_i^2, with its unique minimum value 0 at the origin.

func SphereGrad 

func SphereGrad(x []float64) []float64

SphereGrad returns the exact gradient 2x of Sphere at x.

func Steffensen 

func Steffensen(f Func, x0, tol float64, maxIter int) (float64, error)

Steffensen finds a root of f using Steffensen's method, a derivative-free iteration that achieves quadratic convergence by estimating the local slope from f(x) and f(x+f(x)). It needs only a single starting guess x0.

func TernarySearch 

func TernarySearch(f Func, a, b, tol float64, maxIter int) (float64, error)

TernarySearch returns the location of a minimum of the unimodal function f on [a, b] using ternary search, which discards one outer third of the interval at each step.

func VecAdd 

func VecAdd(a, b []float64) []float64

VecAdd returns the element-wise sum a + b. It panics if the lengths differ.

func VecAxpy 

func VecAxpy(s float64, x, y []float64) []float64

VecAxpy returns the combination s*x + y (the classic "a x plus y"). It panics if the lengths differ.

func VecClamp 

func VecClamp(x []float64, lo, hi float64) []float64

VecClamp returns a copy of x with every element confined to the scalar range [lo, hi].

func VecCopy 

func VecCopy(x []float64) []float64

VecCopy returns a fresh copy of x.

func VecDistance 

func VecDistance(a, b []float64) float64

VecDistance returns the Euclidean distance between a and b.

func VecDot 

func VecDot(a, b []float64) float64

VecDot returns the Euclidean inner product a . b. It panics if the lengths differ.

func VecFill 

func VecFill(n int, v float64) []float64

VecFill returns a new vector of length n with every element set to v.

func VecInfNorm 

func VecInfNorm(a []float64) float64

VecInfNorm returns the maximum-absolute-value (L-infinity) norm of a.

func VecLinComb 

func VecLinComb(a float64, x []float64, b float64, y []float64) []float64

VecLinComb returns the linear combination a*x + b*y. It panics if the lengths differ.

func VecNegate 

func VecNegate(a []float64) []float64

VecNegate returns -a.

func VecNorm 

func VecNorm(a []float64) float64

VecNorm returns the Euclidean (L2) norm |a|.

func VecNormSquared 

func VecNormSquared(a []float64) float64

VecNormSquared returns the squared Euclidean norm |a|^2.

func VecScale 

func VecScale(a []float64, s float64) []float64

VecScale returns the vector s*a.

func VecSub 

func VecSub(a, b []float64) []float64

VecSub returns the element-wise difference a - b. It panics if the lengths differ.

func VecZeros 

func VecZeros(n int) []float64

VecZeros returns a new zero vector of length n.

func WithinTolerance 

func WithinTolerance(a, b, tol float64) bool

WithinTolerance reports whether a and b differ by at most tol in absolute value.

Types

type Bracket 

type Bracket struct {
	Lo float64
	Hi float64
}

Bracket describes a closed interval [Lo, Hi] believed to enclose a root or a minimum.

func BracketSubdivide 

func BracketSubdivide(f Func, a, b float64, n int) []Bracket

BracketSubdivide divides [a, b] into n equal sub-intervals and returns every sub-interval across which f changes sign, each as a Bracket. It is the tool for isolating several roots of a function on a wide interval before refining each with a bracketing solver.

func FindBracket 

func FindBracket(f Func, a, b float64) (Bracket, bool)

FindBracket expands the interval [a, b] outward until it encloses a root and returns the resulting Bracket together with a flag reporting success.

func (Bracket) Contains 

func (br Bracket) Contains(x float64) bool

Contains reports whether x lies within the closed bracket, irrespective of whether Lo or Hi is the larger endpoint.

func (Bracket) Midpoint 

func (br Bracket) Midpoint() float64

Midpoint returns the arithmetic midpoint of the bracket.

func (Bracket) Width 

func (br Bracket) Width() float64

Width returns the (non-negative) length of the bracket.

type Func 

type Func func(float64) float64

Func is a real-valued function of a single real variable, the fundamental object operated on by the solvers and minimizers in this package.

type GradFunc 

type GradFunc func(x []float64) []float64

GradFunc returns the gradient vector (vector of first partial derivatives) of an objective evaluated at x. The returned slice has the same length as x.

type HessFunc 

type HessFunc func(x []float64) [][]float64

HessFunc returns the Hessian matrix (matrix of second partial derivatives) of an objective evaluated at x, as an n-by-n row-major slice of slices.

type MultiFunc 

type MultiFunc func(x []float64) float64

MultiFunc is a scalar-valued objective function of a real vector argument. It is the fundamental object minimized by the multivariate routines in this file. Implementations must not mutate the slice they are handed.

type Options 

type Options struct {
	// Tol is the convergence tolerance on the gradient norm (or on the
	// simplex/step size for derivative-free methods).
	Tol float64
	// MaxIter is the maximum number of iterations.
	MaxIter int
	// Step is the finite-difference step for numeric derivatives.
	Step float64
	// LearningRate is the base step size for first-order methods.
	LearningRate float64
	// Momentum is the momentum coefficient for the momentum methods.
	Momentum float64
}

Options bundles the common tuning parameters shared by the iterative multivariate minimizers. A zero Options is not usable directly; obtain a populated value from DefaultOptions and adjust the fields you care about.

func DefaultOptions 

func DefaultOptions() Options

DefaultOptions returns an Options value populated with sensible defaults.

type Result 

type Result struct {
	X          []float64
	F          float64
	Iterations int
	Converged  bool
}

Result reports the outcome of a multivariate minimization: the located point X, the objective value F at that point, the number of Iterations performed, and whether the routine Converged to the requested tolerance.

func BFGS 

func BFGS(f MultiFunc, grad GradFunc, x0 []float64, tol float64, maxIter int) Result

BFGS minimizes f by the BFGS quasi-Newton method starting from x0, maintaining a dense approximation to the inverse Hessian that is refined by the rank-two BFGS update after each Armijo-backtracked line search. If grad is nil the gradient is estimated by central finite differences. Iteration stops when the gradient norm falls below tol or after maxIter steps.

func ConjugateGradient 

func ConjugateGradient(f MultiFunc, grad GradFunc, x0 []float64, tol float64, maxIter int) Result

ConjugateGradient minimizes f by the nonlinear conjugate-gradient method with Fletcher-Reeves updates and Armijo backtracking line searches, starting from x0. If grad is nil the gradient is estimated by central finite differences. The search direction is reset to steepest descent every len(x0) iterations to preserve convergence. Iteration stops when the gradient norm falls below tol or after maxIter steps.

func CoordinateDescent 

func CoordinateDescent(f MultiFunc, x0 []float64, window, tol float64, maxIter int) Result

CoordinateDescent minimizes f by cyclically minimizing along each coordinate axis in turn. Each coordinate sub-problem is solved by BrentParabolic on the window [x_i - window, x_i + window] centred on the current value. Iteration stops when a full sweep moves the point by less than tol or after maxIter sweeps. It is well suited to separable or mildly coupled convex objectives.

func GradientDescentMomentum 

func GradientDescentMomentum(f MultiFunc, grad GradFunc, x0 []float64, rate, momentum, tol float64, maxIter int) Result

GradientDescentMomentum minimizes f by gradient descent with classical (heavy-ball) momentum starting from x0. The velocity is updated as v <- momentum*v - rate*grad and the point as x <- x + v. If grad is nil the gradient is estimated by central finite differences. Iteration stops when the gradient norm falls below tol or after maxIter steps.

func GradientDescentNesterov 

func GradientDescentNesterov(f MultiFunc, grad GradFunc, x0 []float64, rate, momentum, tol float64, maxIter int) Result

GradientDescentNesterov minimizes f by gradient descent with Nesterov's accelerated (look-ahead) momentum starting from x0. The gradient is evaluated at the look-ahead point x + momentum*v. If grad is nil it is estimated by central finite differences. Iteration stops when the gradient norm at x falls below tol or after maxIter steps.

func NelderMead 

func NelderMead(f MultiFunc, x0 []float64, step, tol float64, maxIter int) Result

NelderMead minimizes f by the Nelder-Mead downhill simplex method starting from x0. An initial simplex is built by perturbing each coordinate of x0 by step. The method uses the standard reflection, expansion, contraction and shrink operations and requires no derivatives. Iteration stops when the spread of objective values across the simplex falls below tol or after maxIter iterations.

func NewtonMultivariate 

func NewtonMultivariate(f MultiFunc, grad GradFunc, hess HessFunc, x0 []float64, tol float64, maxIter int) Result

NewtonMultivariate minimizes f by the damped Newton method starting from x0. At each step it solves H*p = -g for the Newton direction p (where g and H are the gradient and Hessian) and takes an Armijo-backtracked step along p. If grad or hess is nil the corresponding quantity is estimated by finite differences. If the Hessian is singular the method falls back to a steepest- descent step. Iteration stops when the gradient norm falls below tol or after maxIter steps.

func SimulatedAnnealing 

func SimulatedAnnealing(f MultiFunc, x0 []float64, opts SAOptions, seed int64) Result

SimulatedAnnealing minimizes f by simulated annealing starting from x0. Neighbours are proposed by adding independent Gaussian perturbations scaled by opts.StepSize, and uphill moves are accepted with the Metropolis probability exp(-Δf/T). The temperature starts at opts.InitialTemp and is multiplied by opts.CoolingRate each step, floored at opts.MinTemp. All randomness is drawn from a generator seeded by seed, so the result is fully deterministic for a given seed. The best point ever visited is returned.

type SAOptions 

type SAOptions struct {
	// InitialTemp is the starting temperature; higher values accept more
	// uphill moves early on.
	InitialTemp float64
	// CoolingRate is the geometric cooling factor in (0, 1); the temperature
	// is multiplied by it each iteration.
	CoolingRate float64
	// MinTemp is a floor below which the temperature is not allowed to fall.
	MinTemp float64
	// StepSize scales the Gaussian perturbation used to propose neighbours.
	StepSize float64
	// MaxIter is the number of annealing steps to perform.
	MaxIter int
}

SAOptions configures the SimulatedAnnealing minimizer.

func DefaultSAOptions 

func DefaultSAOptions() SAOptions

DefaultSAOptions returns an SAOptions value populated with sensible defaults.

type ScalarFunc 

type ScalarFunc func(x float64) float64

ScalarFunc is a real-valued function of a single real variable, operated on by the one-dimensional minimizers GoldenSection and BrentParabolic.

type ScalarResult 

type ScalarResult struct {
	X          float64
	F          float64
	Iterations int
	Converged  bool
}

ScalarResult reports the outcome of a one-dimensional minimization: the located abscissa X, the objective value F there, the number of Iterations performed, and whether the routine Converged.

func BrentParabolic 

func BrentParabolic(f ScalarFunc, a, b, tol float64, maxIter int) ScalarResult

BrentParabolic locates a minimum of the function f on the interval [a, b] using Brent's method, which combines the reliability of golden-section search with the fast convergence of successive parabolic interpolation. It stops when the estimate is bracketed to within tol or after maxIter iterations.

func GoldenSection 

func GoldenSection(f ScalarFunc, a, b, tol float64, maxIter int) ScalarResult

GoldenSection locates a minimum of the unimodal function f on the interval [a, b] by golden-section search, which shrinks the bracket by the constant factor 1/phi each step. It stops when the bracket width falls below tol or after maxIter iterations.

func MinimizeScalar 

func MinimizeScalar(f ScalarFunc, a, b float64) ScalarResult

MinimizeScalar locates a minimum of f on [a, b] using BrentParabolic with the DefaultTol and DefaultMaxIter. It is a convenience wrapper for the common case where the caller does not need to tune the stopping rule.

type VectorFunc 

type VectorFunc func(x []float64) []float64

VectorFunc is a vector-valued function of a vector argument, used by the Jacobian utility. It maps an n-vector to an m-vector.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.