lbfgsb

package module
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Jul 3, 2013 License: BSD-2-Clause Imports: 5 Imported by: 1

README

Go L-BFGS-B

Description

Go L-BFGS-B is software for solving numerical optimization problems using the limited-memory (L) Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm with bounds constraints (B). L-BFGS-B is a deterministic, gradient-based algorithm for finding local minima of smooth, continuous objective functions subject to bounds on each variable. The bounds are optional, so this software also solves unconstrained problems. L-BFGS-B is accurate and efficient for problems of 1000s of variables. There is more information about L-BFGS-B on Wikipedia or in your favorite optimization textbook.

This software provides modern, intuitive interfaces to the L-BFGS-B Fortran software by the authors of the algorithm, Jorge Nocedal et al. Interfaces are provided for Go (Golang), C, and Fortran 2003.

License

Go L-BFGS-B is free, open source software. You are permitted to copy and use it however you wish. It is released under the BSD 2-Clause License. See the file LICENSE.txt in your distribution (or on GitHub) for details.

The original Fortran code is released under the BSD 3-Clause License (see lbfgsb/License.txt in your distribution or on GitHub). Since I have not modified the Fortran code, I have decided just to incorporate it rather than re-license it.

Features

Go L-BFGS-B is version 0.1.0.

This software is young, but has already been useful and reliable in a machine learning application.

  • Simple API allowing Go programs to easily do efficient, accurate optimization. You only need to provide functions (or an object) that evaluate the objective function value and gradient.

  • Bounds constraints allow typical, simple inequality (box) constraints on individual variables without needing a more specialized algorithm.

  • Incorporates recent improvements and corrections to L-BFGS-B algorithm. (Uses L-BFGS-B version 3.0 from March, 2011.)

  • Customizable logging.

Future Features

  • Modern (Fortran 2003) API for original FORTRAN 77 optimizer.

  • C API for original FORTRAN 77 optimizer.

  • Customizable termination conditions.

Go-Fortran Interface

The architecture of this software has two main pieces: a library with a C API (but written in modern Fortran), and a Go package providing the functionality of the library as a Go API. The library is designed to be used from both Fortran and C, and so could work with other languages besides Go.

I have endeavored to make this a good Go-Fortran interface example as well as a useful package. Accordingly, I have included my experimental interface prototype code to be used for learning and experimenting with Cgo and interfaces between Go and C (or Fortran). However, let me know about (or contribute!) possible improvements.

Requirements

Building this software requires:

  • Fortran 2003 compiler with support for procedure pointers, such as GCC 4.4.6 or later (gfortran)

  • Go 1.0 or later

  • Standard development tools: make, ar, ld.

Download, Build, Install

Conveniently, you can use the Go tools to download, build, and install this package, but it is not quite fully automatic: there is an intervening step to compile the Fortran code.

  1. Download. Using go get requires git. If you want to download the latest code after having downloaded this package previously, add the update flag (-u) to the command.

    [go-wrkspc]$ go get -d github.com/afbarnard/go-lbfgsb

  2. Build Fortran. Change to the directory containing the downloaded package and run make. The workspace that Go uses to download and install packages is the first workspace in your GOPATH, or the Go installation directory if GOPATH is empty.

    [go-wrkspc]$ echo $GOPATH
/home/go-pkgs:/home/go-wrkspc
[go-wrkspc]$ cd ~/go-pkgs/src/github.com/afbarnard/go-lbfgsb
[go-lbfgsb]$ make
[go-lbfgsb]$ cd ~/go-wrkspc

  3. Build, install Go. Run go get again to complete the Go installation.

    [go-wrkspc]$ go get github.com/afbarnard/go-lbfgsb

  4. Use. Import the go-lbfgsb package into your Go program. Build your program normally.

    import lbfgsb "github.com/afbarnard/go-lbfgsb"

    [main-prog]$ go build

Alternative Download, Install, Build

If you do not want to use go get, you can download this package manually and make it part of your Go workspace.

  1. Download. Get a project release archive from GitHub.

  2. Install. Extract the release archive into your Go workspace.

    [go-wrkspc]$ tar -zxf ~/downloads/go-lbfsgb-1.2.3.tar.gz --directory optim

  3. Build. Run make in the package directory.

    [go-wrkspc]$ cd optim/go-lbfgsb-1.2.3
[go-lbfgsb-1.2.3]$ make
[go-lbfgsb-1.2.3]$ cd ~/go-wrkspc

  4. Use. Import the package as a local package and build normally.

    import lbfgsb "optim/go-lbfgsb-1.2.3"

    [main-prog]$ go build

Contact

Contributions of all sorts, patches, bugs, issues, etc. are welcome, but are most welcome after due diligence.

Copyright (c) 2013 Aubrey Barnard. This is free software. See LICENSE.txt for details.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type ExitStatus 

type ExitStatus struct {
	Code    ExitStatusCode
	Message string
}

ExitStatus is the exit status of an optimization algorithm. Includes a status code and a message explaining the situation.

func (ExitStatus) AsError 

func (es ExitStatus) AsError() error

AsError returns an error representing this exit status. If the exit status code is 'SUCCESS' then AsError returns nil. Otherwise returns an error object (which happens to be this object).

func (ExitStatus) Error 

func (es ExitStatus) Error() string

Error allows this ExitStatus to be treated like an error object.

func (ExitStatus) String 

func (es ExitStatus) String() string

String returns the exit status code and message as text.

type ExitStatusCode 

type ExitStatusCode uint8

ExitStatusCode describes the exit status of an optimization algorithm. Multiple statuses are necessary because success in optimization is not binary and so a simple error is not adequate. There are four exit statuses to distinguish:

1. Success. Normal termination having converged.

2. Approximate success. Normal operation resulting in a more approximate answer. For example, unable to meet termination tolerances.

3. Warning. The result could be OK, but there were some issues that may have reduced the quality of the result and require examination. For example, slight numerical problems, exceeding iteration or time bounds.

4. Failure of optimization. For example, a necessary condition of the algorithm was not met, severe numerical problems. (This status includes failures to evaluate the objective function or objective gradient.)

There are also the typical runtime errors due to usage, bugs, etc.:

5. Usage error. For example, invalid constraints, bad parameters. Responsibility is on the caller.

6. Internal error. Other runtime or programming/logic error which may be a bug. Responsibility is on this package. 

const (
	SUCCESS ExitStatusCode = iota
	APPROXIMATE
	WARNING
	FAILURE
	USAGE_ERROR
	INTERNAL_ERROR
)

ExitStatusCode values.

func (ExitStatusCode) String 

func (esc ExitStatusCode) String() string

String returns a word for each ExitStatusCode.

type FunctionWithGradient 

type FunctionWithGradient interface {
	// Evaluate returns the value of the function at the given point.
	Evaluate(point []float64) float64
	// EvaluateGradient returns the gradient of the function at the
	// given point.
	EvaluateGradient(point []float64) []float64
}

FunctionWithGradient is the interface for a function (f: R**n -> R) and its gradient (f': R**n -> R**n) suitable for use as an objective function for optimization.

type GeneralObjectiveFunction 

type GeneralObjectiveFunction struct {
	Function func([]float64) float64
	Gradient func([]float64) []float64
}

GeneralObjectiveFunction is a utility object that combines individual Go functions into a FunctionWithGradient.

func (GeneralObjectiveFunction) Evaluate 

func (gof GeneralObjectiveFunction) Evaluate(point []float64) float64

func (GeneralObjectiveFunction) EvaluateGradient 

func (gof GeneralObjectiveFunction) EvaluateGradient(point []float64) []float64

type Lbfgsb 

type Lbfgsb struct {
	// contains filtered or unexported fields
}

Lbfgsb provides the functionality of the Fortran L-BFGS-B optimizer as a Go object. A Lbfgsb solver object contains the setup for an optimization problem of a particular dimensionality. It stores bounds, parameters, and results so it is relatively lightweight (especially if no bounds are specified). It can be re-used for other problems with the same dimensionality, but using a different solver object for each problem is probably better organization. A zero-value Lbfgsb object is valid and needs no explicit construction. A solver object will perform unconstrained optimization unless bounds are set.

func NewLbfgsb 

func NewLbfgsb(dimensionality int) *Lbfgsb

NewLbfgsb creates, initializes, and returns a new Lbfgsb solver object. Equivalent to 'new(Lbfgsb).Init(dimensionality)'. A zero-value Lbfgsb object is valid and needs no explicit construction. However, this constructor is convenient and explicit.

func (*Lbfgsb) ClearBounds 

func (lbfgsb *Lbfgsb) ClearBounds() *Lbfgsb

ClearBounds clears all bounds resulting in an unconstrained optimization problem.

func (*Lbfgsb) Init 

func (lbfgsb *Lbfgsb) Init(dimensionality int) *Lbfgsb

Init initializes this Lbfgsb solver for problems of the given dimensionality. Also sets default parameters that are not zero values. Returns this for method chaining. Ignores calls subsequent to the first (because a solver is intended for only a particular dimensionality).

func (*Lbfgsb) Minimize 

func (lbfgsb *Lbfgsb) Minimize(
	objective FunctionWithGradient,
	initialPoint []float64) (
	minimum PointValueGradient,
	exitStatus ExitStatus)

Minimize optimizes the given objective using the L-BFGS-B algorithm. Implements OptimizationFunctionMinimizer.Minimize.

func (*Lbfgsb) OptimizationStatistics 

func (lbfgsb *Lbfgsb) OptimizationStatistics() OptimizationStatistics

Statistics returns some statistics about the most recent minimization: the total number of iterations and the total numbers of function and gradient evaluations.

func (*Lbfgsb) SetApproximationSize 

func (lbfgsb *Lbfgsb) SetApproximationSize(size int) *Lbfgsb

SetApproximationSize sets the amount of history (points and gradients) stored and used to approximate the inverse Hessian matrix. More history allows better approximation at the cost of more memory. The recommended range is [3,20]. Defaults to 5.

func (*Lbfgsb) SetBounds 

func (lbfgsb *Lbfgsb) SetBounds(bounds [][2]float64) *Lbfgsb

SetBounds sets the upper and lower bounds on the individual dimensions to the given intervals resulting in a constrained optimization problem. Individual bounds may be (+/-)Inf.

func (*Lbfgsb) SetBoundsAll 

func (lbfgsb *Lbfgsb) SetBoundsAll(lower, upper float64) *Lbfgsb

SetBoundsAll sets the bounds of all the dimensions to [lower,upper]. Init must be called first to set the dimensionality.

func (*Lbfgsb) SetBoundsSparse 

func (lbfgsb *Lbfgsb) SetBoundsSparse(sparseBounds map[int][]float64) *Lbfgsb

SetBoundsSparse sets the bounds to only those in the given map; others are unbounded. Each entry in the map is a (zero-based) dimension index mapped to a slice representing an interval. Individual bounds may be (+/-)Inf. Init must be called first to set the dimensionality.

The slice is interpreted as an interval as follows: 

nil | []: [-Inf, +Inf]
[x]: [-|x|, |x|]
[l, u, ...]: [l, u]

func (*Lbfgsb) SetFTolerance 

func (lbfgsb *Lbfgsb) SetFTolerance(fTolerance float64) *Lbfgsb

SetFTolerance sets the tolerance of the precision of the objective function required for convergence. Defaults to 1e-6.

func (*Lbfgsb) SetFortranPrintControl 

func (lbfgsb *Lbfgsb) SetFortranPrintControl(verbosity int) *Lbfgsb

SetFortranPrintControl sets the level of output verbosity from the Fortran L-BFGS-B code. Defaults to 0, no output. Ranges from 0 to 102: 1 displays a summary, 100 displays details of each iteration, 102 adds vectors (X and G) to the output.

func (*Lbfgsb) SetGTolerance 

func (lbfgsb *Lbfgsb) SetGTolerance(gTolerance float64) *Lbfgsb

SetGTolerance sets the tolerance of the precision of the objective gradient required for convergence. Defaults to 1e-6.

func (*Lbfgsb) SetLogger 

func (lbfgsb *Lbfgsb) SetLogger(
	logger OptimizationIterationLogger) *Lbfgsb

SetLogger sets a logging function for the optimization that will be called after each iteration. May be nil, which disables logging. Defaults to nil.

type ObjectiveFunctionMinimizer 

type ObjectiveFunctionMinimizer interface {
	// Minimize finds a numerically-approximate minimum of the given
	// objective function starting from the given point.  Returns the
	// minimum (or the best point found) and the status of the algorithm
	// at exit.
	Minimize(objective FunctionWithGradient, initialPoint []float64) (
		minimum PointValueGradient, exitStatus ExitStatus)
}

ObjectiveFunctionMinimizer is the interface for all n-dimensional numerical minimization optimization algorithms that use gradients. Finds a local minimum. The idea is that an optimization algorithm object will provide this method as well as methods for setting parameters, getting performance results, logging, etc., methods that are specific to the implementation. This interface should specify the minimum necessary to be a useful optimization algorithm.

type OptimizationIterationInformation 

type OptimizationIterationInformation struct {
	Iteration   int
	FEvals      int
	GEvals      int
	FEvalsTotal int
	GEvalsTotal int
	StepLength  float64
	X           []float64
	F           float64
	G           []float64
	FDelta      float64
	FDeltaBound float64
	GNorm       float64
	GNormBound  float64
}

OptimizationIterationInformation is a container for information about an optimization iteration.

func (*OptimizationIterationInformation) Header 

func (oii *OptimizationIterationInformation) Header() string

Header returns a string with descriptions for the fields returned by String().

func (*OptimizationIterationInformation) String 

func (oii *OptimizationIterationInformation) String() string

String formats the iteration information fields as a row in a table.

type OptimizationIterationLogger 

type OptimizationIterationLogger func(info *OptimizationIterationInformation)

OptimizationIterationLogger is the type of function that logs/records/processes information about a single iteration in an optimization run.

type OptimizationStatistics 

type OptimizationStatistics struct {
	Iterations          int
	FunctionEvaluations int
	GradientEvaluations int
}

OptimizationStatistics is a container for basic statistics about an optimization run. Values can be negative to indicate they were not tracked.

type OptimizationStatisticser 

type OptimizationStatisticser interface {
	OptimizationStatistics() OptimizationStatistics
}

OptimizationStatisticser is an object that can supply statistics about an optimization run.

type PointValueGradient 

type PointValueGradient struct {
	X []float64
	F float64
	G []float64
}

PointValueGradient is a point in optimization space as well as the result of optimization: a point (x), its function value (f), and its gradient (g). The lengths of X and G must agree.

Source Files

View all Source files

Directories

Path Synopsis
Install go-lbfgsb and build by running the following commands from this directory: $ go get -d github.com/afbarnard/go-lbfgsb $ pushd ~/go-pkgs/src/github.com/afbarnard/go-lbfgsb $ make $ popd $ go get github.com/afbarnard/go-lbfgsb $ go build Then run.
 Install go-lbfgsb and build by running the following commands from this directory: $ go get -d github.com/afbarnard/go-lbfgsb $ pushd ~/go-pkgs/src/github.com/afbarnard/go-lbfgsb $ make $ popd $ go get github.com/afbarnard/go-lbfgsb $ go build Then run.

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.