README
¶
A Nelder-Mead implementation in Go 
The Go package documentation has in-depth usage help and algorithm tuning suggestions. This package intends to be super easy to use and optimize.
This repository contains a Go implementation of the Nelder-Mead optimization algorithm, which is a gradient-free optimization method for continuous, possibly non-convex, and noisy functions in low to moderate dimensions.
The algorithm uses a simplex, a polytope with n+1 vertices in n-dimensional space, to explore the search space. The algorithm iteratively updates the simplex by reflecting, expanding, contracting, or shrinking it, based on the values of the objective function at its vertices. The algorithm terminates when the difference in the objective function values between the best and worst points in the simplex falls below the specified tolerance or when the maximum number of iterations is reached.
Installation
This package can be installed using Go modules with the following command:
go get github.com/crhntr/neldermead
Usage
The Rosenbrock function is a well-known test function for optimization algorithms, and its global minimum is at (1, 1), where the function value is 0. The Run function takes the Rosenbrock function as the objective function to minimize, the initial guess x0 as the starting point, and the Options struct with the desired parameters for the Nelder-Mead algorithm.
The algorithm found a solution close to the global minimum with a very small objective function value.
package main
import (
"fmt"
"math"
"github.com/crhntr/neldermead"
)
func main() {
rosenbrock := func(x []float64) float64 {
return math.Pow(1-x[0], 2) + 100*math.Pow(x[1]-x[0]*x[0], 2)
}
x0 := []float64{-1, -1} // initial guess
options := neldermead.NewOptions()
point, err := neldermead.Run(rosenbrock, x0, options)
if err != nil {
fmt.Printf("Error: %v\n", err)
}
fmt.Printf("Solution: %.6f\n", point.X)
fmt.Printf("Objective function value: %.6f\n", point.F)
}
The output of this program should be:
Solution: [1.000329 1.000714]
Objective function value: 0.000000
Now let's look at an example with constraints,
package main
import (
"fmt"
"math"
"github.com/crhntr/neldermead"
)
func main() {
// Define the objective function to be minimized.
objective := func(x []float64) float64 {
// y = x^3 - x
return math.Pow(x[0], 3) - x[1]
}
// Define the starting point for the optimizer.
x0 := []float64{4, 5}
// Define the optimization options.
options := neldermead.NewOptions()
// (optional) add constraints
options.Constraints = []neldermead.Constraint{
{Min: 3, Max: 5},
{Min: 0, Max: 10},
}
// Run the optimizer.
result, err := neldermead.Run(objective, x0, options)
if err != nil {
panic(err)
}
fmt.Printf("Found minimum at x = %v, f(x) = %.2f\n", result.X, result.F)
}
The output of this program should be:
Found minimum at x = [3 10], f(x) = 17.00
Documentation
¶
Overview ¶
Package neldermead implements the Nelder-Mead simplex optimization algorithm, a gradient-free method for minimizing continuous functions.
Index ¶
Examples ¶
Constants ¶
const ( DefaultAlpha = 1.0 DefaultBeta = 0.5 DefaultGamma = 2.0 DefaultDelta = 0.5 DefaultTolerance = 1e-6 DefaultMaxIterations = 1000 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Constraint ¶
type Constraint struct {
Min, Max float64
}
Constraint defines lower and upper bounds for a single dimension.
type ErrorSimplexCollapse ¶
type ErrorSimplexCollapse struct{}
ErrorSimplexCollapse is returned by Run when the simplex degenerates (average edge length falls below CollapseThreshold).
func (ErrorSimplexCollapse) Error ¶
func (ErrorSimplexCollapse) Error() string
type Objective ¶
Objective is a function that takes an n-dimensional input vector and returns a scalar value to minimize.
type Options ¶
type Options struct {
// Alpha is the reflection coefficient (commonly 1.0).
// Controls the size of the reflection step. Must be positive.
Alpha float64
// Beta is the contraction coefficient (commonly 0.5).
// Controls the size of the contraction step when the reflected point
// does not improve the objective function value.
// Must be in the open interval (0, 1).
Beta float64
// Gamma is the expansion coefficient (commonly 2.0).
// Controls the size of the expansion step when the reflected point
// improves the objective function value significantly.
// Must be greater than 1.
Gamma float64
// Delta is the shrinkage coefficient (commonly 0.5).
// Controls the size of the shrinking step when contraction fails
// to improve the objective function value.
// Must be in the open interval (0, 1).
Delta float64
// Tolerance is the convergence criterion.
// The algorithm terminates when the difference in objective function values
// between the best and worst simplex vertices is less than Tolerance.
Tolerance float64
// CollapseThreshold is the minimum average edge length of the simplex.
// If the average edge length falls below this value, Run returns
// ErrorSimplexCollapse. Set to 0 to disable collapse detection.
CollapseThreshold float64
// MaxIterations sets an upper bound on how long the algorithm should run to find the minima.
MaxIterations int
// Constraints is an optional list of per-dimension bounds.
// If provided, the length must match the dimensionality of x0.
// If empty, the optimization is unconstrained.
Constraints []Constraint
}
Options configures the behavior of the Nelder-Mead algorithm. Use NewOptions for commonly-used defaults.
func NewOptions ¶
func NewOptions() Options
NewOptions returns Options with commonly-used default values. These should be considered a starting point; tune them for your specific problem.
type Point ¶
Point holds an n-dimensional input vector X and its objective function value F.
func Run ¶
Run minimizes the objective function f starting from initial guess x0. It returns the best Point found (input vector and objective value).
The algorithm terminates when the difference in objective function values between the best and worst simplex vertices falls below Tolerance, or when MaxIterations is reached.
Run returns an error if options are invalid, x0 violates constraints, or the simplex collapses (see ErrorSimplexCollapse).
Example ¶
package main
import (
"fmt"
"math"
"github.com/crhntr/neldermead"
)
func main() {
// Define the objective function to be minimized.
objective := func(x []float64) float64 {
// y = x^3
return math.Pow(x[0], 3) - x[1]
}
// Define the starting point for the optimizer.
x0 := []float64{4, 5}
// Define the optimization options.
options := neldermead.NewOptions()
options.Constraints = []neldermead.Constraint{
{Min: 3, Max: 5},
{Min: 0, Max: 10},
}
// Run the optimizer.
result, err := neldermead.Run(objective, x0, options)
if err != nil {
panic(err)
}
// Print the result.
fmt.Printf("Found minimum at x = %v, f(x) = %.2f\n", result.X, result.F)
}
Output: Found minimum at x = [3 10], f(x) = 17.00
Source Files