optimize/types.go - third_party/github.com/gonum/gonum - Git at Google

 // Copyright ©2014 The gonum Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package optimize

 import (
 	"errors"
 	"fmt"
 	"math"
 	"time"

 	"gonum.org/v1/gonum/mat"
 )

 const defaultGradientAbsTol = 1e-6

 // Operation represents the set of operations commanded by Method at each
 // iteration. It is a bitmap of various Iteration and Evaluation constants.
 // Individual constants must NOT be combined together by the binary OR operator
 // except for the Evaluation operations.
 type Operation uint64

 // Supported Operations.
 const (
 	// NoOperation specifies that no evaluation or convergence check should
 	// take place.
 	NoOperation Operation = 0
 	// InitIteration is sent to Recorder to indicate the initial location.
 	// All fields of the location to record must be valid.
 	// Method must not return it.
 	InitIteration Operation = 1 << (iota - 1)
 	// PostIteration is sent to Recorder to indicate the final location
 	// reached during an optimization run.
 	// All fields of the location to record must be valid.
 	// Method must not return it.
 	PostIteration
 	// MajorIteration indicates that the next candidate location for
 	// an optimum has been found and convergence should be checked.
 	MajorIteration
 	// FuncEvaluation specifies that the objective function
 	// should be evaluated.
 	FuncEvaluation
 	// GradEvaluation specifies that the gradient
 	// of the objective function should be evaluated.
 	GradEvaluation
 	// HessEvaluation specifies that the Hessian
 	// of the objective function should be evaluated.
 	HessEvaluation

 	// Mask for the evaluating operations.
 	evalMask = FuncEvaluation | GradEvaluation | HessEvaluation
 )

 func (op Operation) isEvaluation() bool {
 	return op&evalMask != 0 && op&^evalMask == 0
 }

 func (op Operation) String() string {
 	if op&evalMask != 0 {
 		return fmt.Sprintf("Evaluation(Func: %t, Grad: %t, Hess: %t, Extra: 0b%b)",
 			op&FuncEvaluation != 0,
 			op&GradEvaluation != 0,
 			op&HessEvaluation != 0,
 			op&^(evalMask))
 	}
 	s, ok := operationNames[op]
 	if ok {
 		return s
 	}
 	return fmt.Sprintf("Operation(%d)", op)
 }

 var operationNames = map[Operation]string{
 	NoOperation:    "NoOperation",
 	InitIteration:  "InitIteration",
 	MajorIteration: "MajorIteration",
 	PostIteration:  "PostIteration",
 }

 // Location represents a location in the optimization procedure.
 type Location struct {
 	X        []float64
 	F        float64
 	Gradient []float64
 	Hessian  *mat.SymDense
 }

 // Result represents the answer of an optimization run. It contains the optimum
 // location as well as the Status at convergence and Statistics taken during the
 // run.
 type Result struct {
 	Location
 	Stats
 	Status Status
 }

 // Stats contains the statistics of the run.
 type Stats struct {
 	MajorIterations int           // Total number of major iterations
 	FuncEvaluations int           // Number of evaluations of Func
 	GradEvaluations int           // Number of evaluations of Grad
 	HessEvaluations int           // Number of evaluations of Hess
 	Runtime         time.Duration // Total runtime of the optimization
 }

 // complementEval returns an evaluating operation that evaluates fields of loc
 // not evaluated by eval.
 func complementEval(loc *Location, eval Operation) (complEval Operation) {
 	if eval&FuncEvaluation == 0 {
 		complEval = FuncEvaluation
 	}
 	if loc.Gradient != nil && eval&GradEvaluation == 0 {
 		complEval |= GradEvaluation
 	}
 	if loc.Hessian != nil && eval&HessEvaluation == 0 {
 		complEval |= HessEvaluation
 	}
 	return complEval
 }

 // Problem describes the optimization problem to be solved.
 type Problem struct {
 	// Func evaluates the objective function at the given location. Func
 	// must not modify x.
 	Func func(x []float64) float64

 	// Grad evaluates the gradient at x and stores the result in-place in grad.
 	// Grad must not modify x.
 	Grad func(grad []float64, x []float64)

 	// Hess evaluates the Hessian at x and stores the result in-place in hess.
 	// Hess must not modify x.
 	Hess func(hess mat.MutableSymmetric, x []float64)

 	// Status reports the status of the objective function being optimized and any
 	// error. This can be used to terminate early, for example when the function is
 	// not able to evaluate itself. The user can use one of the pre-provided Status
 	// constants, or may call NewStatus to create a custom Status value.
 	Status func() (Status, error)
 }

 // TODO(btracey): Think about making this an exported function when the
 // constraint interface is designed.
 func (p Problem) satisfies(method Needser) error {
 	if method.Needs().Gradient && p.Grad == nil {
 		return errors.New("optimize: problem does not provide needed Grad function")
 	}
 	if method.Needs().Hessian && p.Hess == nil {
 		return errors.New("optimize: problem does not provide needed Hess function")
 	}
 	return nil
 }

 // Settings represents settings of the optimization run. It contains initial
 // settings, convergence information, and Recorder information. In general, users
 // should use DefaultSettings rather than constructing a Settings literal.
 //
 // If UseInitData is true, InitialValue, InitialGradient and InitialHessian
 // specify function information at the initial location.
 //
 // If Recorder is nil, no information will be recorded.
 type Settings struct {
 	UseInitialData  bool          // Use supplied information about the conditions at the initial x.
 	InitialValue    float64       // Function value at the initial x.
 	InitialGradient []float64     // Gradient at the initial x.
 	InitialHessian  *mat.SymDense // Hessian at the initial x.

 	// FunctionThreshold is the threshold for acceptably small values of the
 	// objective function. FunctionThreshold status is returned if
 	// the objective function is less than this value.
 	// The default value is -inf.
 	FunctionThreshold float64

 	// GradientThreshold determines the accuracy to which the minimum is found.
 	// GradientThreshold status is returned if the infinity norm of
 	// the gradient is less than this value.
 	// Has no effect if gradient information is not used.
 	// The default value is 1e-6.
 	GradientThreshold float64

 	// FunctionConverge tests that the function value decreases by a
 	// significant amount over the specified number of iterations.
 	//
 	// If f < f_best and
 	//  f_best - f > FunctionConverge.Relative * maxabs(f, f_best) + FunctionConverge.Absolute
 	// then a significant decrease has occurred, and f_best is updated.
 	//
 	// If there is no significant decrease for FunctionConverge.Iterations
 	// major iterations, FunctionConvergence status is returned.
 	//
 	// If this is nil or if FunctionConverge.Iterations == 0, it has no effect.
 	FunctionConverge *FunctionConverge

 	// MajorIterations is the maximum number of iterations allowed.
 	// IterationLimit status is returned if the number of major iterations
 	// equals or exceeds this value.
 	// If it equals zero, this setting has no effect.
 	// The default value is 0.
 	MajorIterations int

 	// Runtime is the maximum runtime allowed. RuntimeLimit status is returned
 	// if the duration of the run is longer than this value. Runtime is only
 	// checked at iterations of the Method.
 	// If it equals zero, this setting has no effect.
 	// The default value is 0.
 	Runtime time.Duration

 	// FuncEvaluations is the maximum allowed number of function evaluations.
 	// FunctionEvaluationLimit status is returned if the total number of calls
 	// to Func equals or exceeds this number.
 	// If it equals zero, this setting has no effect.
 	// The default value is 0.
 	FuncEvaluations int

 	// GradEvaluations is the maximum allowed number of gradient evaluations.
 	// GradientEvaluationLimit status is returned if the total number of calls
 	// to Grad equals or exceeds this number.
 	// If it equals zero, this setting has no effect.
 	// The default value is 0.
 	GradEvaluations int

 	// HessEvaluations is the maximum allowed number of Hessian evaluations.
 	// HessianEvaluationLimit status is returned if the total number of calls
 	// to Hess equals or exceeds this number.
 	// If it equals zero, this setting has no effect.
 	// The default value is 0.
 	HessEvaluations int

 	Recorder Recorder

 	// Concurrent represents how many concurrent evaluations are possible.
 	Concurrent int
 }

 // DefaultSettings returns a new Settings struct containing the default settings.
 func DefaultSettings() *Settings {
 	return &Settings{
 		GradientThreshold: defaultGradientAbsTol,
 		FunctionThreshold: math.Inf(-1),
 		FunctionConverge: &FunctionConverge{
 			Absolute:   1e-10,
 			Iterations: 20,
 		},
 	}
 }

 // resize takes x and returns a slice of length dim. It returns a resliced x
 // if cap(x) >= dim, and a new slice otherwise.
 func resize(x []float64, dim int) []float64 {
 	if dim > cap(x) {
 		return make([]float64, dim)
 	}
 	return x[:dim]
 }

 func resizeSymDense(m *mat.SymDense, dim int) *mat.SymDense {
 	if m == nil || cap(m.RawSymmetric().Data) < dim*dim {
 		return mat.NewSymDense(dim, nil)
 	}
 	return mat.NewSymDense(dim, m.RawSymmetric().Data[:dim*dim])
 }
	// Copyright ©2014 The gonum Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package optimize

	import (
	"errors"
	"fmt"
	"math"
	"time"

	"gonum.org/v1/gonum/mat"
	)

	const defaultGradientAbsTol = 1e-6

	// Operation represents the set of operations commanded by Method at each
	// iteration. It is a bitmap of various Iteration and Evaluation constants.
	// Individual constants must NOT be combined together by the binary OR operator
	// except for the Evaluation operations.
	type Operation uint64

	// Supported Operations.
	const (
	// NoOperation specifies that no evaluation or convergence check should
	// take place.
	NoOperation Operation = 0
	// InitIteration is sent to Recorder to indicate the initial location.
	// All fields of the location to record must be valid.
	// Method must not return it.
	InitIteration Operation = 1 << (iota - 1)
	// PostIteration is sent to Recorder to indicate the final location
	// reached during an optimization run.
	// All fields of the location to record must be valid.
	// Method must not return it.
	PostIteration
	// MajorIteration indicates that the next candidate location for
	// an optimum has been found and convergence should be checked.
	MajorIteration
	// FuncEvaluation specifies that the objective function
	// should be evaluated.
	FuncEvaluation
	// GradEvaluation specifies that the gradient
	// of the objective function should be evaluated.
	GradEvaluation
	// HessEvaluation specifies that the Hessian
	// of the objective function should be evaluated.
	HessEvaluation

	// Mask for the evaluating operations.
	evalMask = FuncEvaluation \| GradEvaluation \| HessEvaluation
	)

	func (op Operation) isEvaluation() bool {
	return op&evalMask != 0 && op&^evalMask == 0
	}

	func (op Operation) String() string {
	if op&evalMask != 0 {
	return fmt.Sprintf("Evaluation(Func: %t, Grad: %t, Hess: %t, Extra: 0b%b)",
	op&FuncEvaluation != 0,
	op&GradEvaluation != 0,
	op&HessEvaluation != 0,
	op&^(evalMask))
	}
	s, ok := operationNames[op]
	if ok {
	return s
	}
	return fmt.Sprintf("Operation(%d)", op)
	}

	var operationNames = map[Operation]string{
	NoOperation: "NoOperation",
	InitIteration: "InitIteration",
	MajorIteration: "MajorIteration",
	PostIteration: "PostIteration",
	}

	// Location represents a location in the optimization procedure.
	type Location struct {
	X []float64
	F float64
	Gradient []float64
	Hessian *mat.SymDense
	}

	// Result represents the answer of an optimization run. It contains the optimum
	// location as well as the Status at convergence and Statistics taken during the
	// run.
	type Result struct {
	Location
	Stats
	Status Status
	}

	// Stats contains the statistics of the run.
	type Stats struct {
	MajorIterations int // Total number of major iterations
	FuncEvaluations int // Number of evaluations of Func
	GradEvaluations int // Number of evaluations of Grad
	HessEvaluations int // Number of evaluations of Hess
	Runtime time.Duration // Total runtime of the optimization
	}

	// complementEval returns an evaluating operation that evaluates fields of loc
	// not evaluated by eval.
	func complementEval(loc *Location, eval Operation) (complEval Operation) {
	if eval&FuncEvaluation == 0 {
	complEval = FuncEvaluation
	}
	if loc.Gradient != nil && eval&GradEvaluation == 0 {
	complEval \|= GradEvaluation
	}
	if loc.Hessian != nil && eval&HessEvaluation == 0 {
	complEval \|= HessEvaluation
	}
	return complEval
	}

	// Problem describes the optimization problem to be solved.
	type Problem struct {
	// Func evaluates the objective function at the given location. Func
	// must not modify x.
	Func func(x []float64) float64

	// Grad evaluates the gradient at x and stores the result in-place in grad.
	// Grad must not modify x.
	Grad func(grad []float64, x []float64)

	// Hess evaluates the Hessian at x and stores the result in-place in hess.
	// Hess must not modify x.
	Hess func(hess mat.MutableSymmetric, x []float64)

	// Status reports the status of the objective function being optimized and any
	// error. This can be used to terminate early, for example when the function is
	// not able to evaluate itself. The user can use one of the pre-provided Status
	// constants, or may call NewStatus to create a custom Status value.
	Status func() (Status, error)
	}

	// TODO(btracey): Think about making this an exported function when the
	// constraint interface is designed.
	func (p Problem) satisfies(method Needser) error {
	if method.Needs().Gradient && p.Grad == nil {
	return errors.New("optimize: problem does not provide needed Grad function")
	}
	if method.Needs().Hessian && p.Hess == nil {
	return errors.New("optimize: problem does not provide needed Hess function")
	}
	return nil
	}

	// Settings represents settings of the optimization run. It contains initial
	// settings, convergence information, and Recorder information. In general, users
	// should use DefaultSettings rather than constructing a Settings literal.
	//
	// If UseInitData is true, InitialValue, InitialGradient and InitialHessian
	// specify function information at the initial location.
	//
	// If Recorder is nil, no information will be recorded.
	type Settings struct {
	UseInitialData bool // Use supplied information about the conditions at the initial x.
	InitialValue float64 // Function value at the initial x.
	InitialGradient []float64 // Gradient at the initial x.
	InitialHessian *mat.SymDense // Hessian at the initial x.

	// FunctionThreshold is the threshold for acceptably small values of the
	// objective function. FunctionThreshold status is returned if
	// the objective function is less than this value.
	// The default value is -inf.
	FunctionThreshold float64

	// GradientThreshold determines the accuracy to which the minimum is found.
	// GradientThreshold status is returned if the infinity norm of
	// the gradient is less than this value.
	// Has no effect if gradient information is not used.
	// The default value is 1e-6.
	GradientThreshold float64

	// FunctionConverge tests that the function value decreases by a
	// significant amount over the specified number of iterations.
	//
	// If f < f_best and
	// f_best - f > FunctionConverge.Relative * maxabs(f, f_best) + FunctionConverge.Absolute
	// then a significant decrease has occurred, and f_best is updated.
	//
	// If there is no significant decrease for FunctionConverge.Iterations
	// major iterations, FunctionConvergence status is returned.
	//
	// If this is nil or if FunctionConverge.Iterations == 0, it has no effect.
	FunctionConverge *FunctionConverge

	// MajorIterations is the maximum number of iterations allowed.
	// IterationLimit status is returned if the number of major iterations
	// equals or exceeds this value.
	// If it equals zero, this setting has no effect.
	// The default value is 0.
	MajorIterations int

	// Runtime is the maximum runtime allowed. RuntimeLimit status is returned
	// if the duration of the run is longer than this value. Runtime is only
	// checked at iterations of the Method.
	// If it equals zero, this setting has no effect.
	// The default value is 0.
	Runtime time.Duration

	// FuncEvaluations is the maximum allowed number of function evaluations.
	// FunctionEvaluationLimit status is returned if the total number of calls
	// to Func equals or exceeds this number.
	// If it equals zero, this setting has no effect.
	// The default value is 0.
	FuncEvaluations int

	// GradEvaluations is the maximum allowed number of gradient evaluations.
	// GradientEvaluationLimit status is returned if the total number of calls
	// to Grad equals or exceeds this number.
	// If it equals zero, this setting has no effect.
	// The default value is 0.
	GradEvaluations int

	// HessEvaluations is the maximum allowed number of Hessian evaluations.
	// HessianEvaluationLimit status is returned if the total number of calls
	// to Hess equals or exceeds this number.
	// If it equals zero, this setting has no effect.
	// The default value is 0.
	HessEvaluations int

	Recorder Recorder

	// Concurrent represents how many concurrent evaluations are possible.
	Concurrent int
	}

	// DefaultSettings returns a new Settings struct containing the default settings.
	func DefaultSettings() *Settings {
	return &Settings{
	GradientThreshold: defaultGradientAbsTol,
	FunctionThreshold: math.Inf(-1),
	FunctionConverge: &FunctionConverge{
	Absolute: 1e-10,
	Iterations: 20,
	},
	}
	}

	// resize takes x and returns a slice of length dim. It returns a resliced x
	// if cap(x) >= dim, and a new slice otherwise.
	func resize(x []float64, dim int) []float64 {
	if dim > cap(x) {
	return make([]float64, dim)
	}
	return x[:dim]
	}

	func resizeSymDense(m mat.SymDense, dim int) mat.SymDense {
	if m == nil \|\| cap(m.RawSymmetric().Data) < dim*dim {
	return mat.NewSymDense(dim, nil)
	}
	return mat.NewSymDense(dim, m.RawSymmetric().Data[:dim*dim])
	}