blob: e28fa00a345e215dc4d0f5a102bfb2a5745eecaa [file] [log] [blame]
// 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
// A localMethod can optimize an objective function.
//
// It uses a reverse-communication interface between the optimization method
// and the caller. Method acts as a client that asks the caller to perform
// needed operations via Operation returned from Init and Iterate methods.
// This provides independence of the optimization algorithm on user-supplied
// data and their representation, and enables automation of common operations
// like checking for (various types of) convergence and maintaining statistics.
//
// A Method can command an Evaluation, a MajorIteration or NoOperation operations.
//
// An evaluation operation is one or more of the Evaluation operations
// (FuncEvaluation, GradEvaluation, etc.) which can be combined with
// the bitwise or operator. In an evaluation operation, the requested fields of
// Problem will be evaluated at the point specified in Location.X.
// The corresponding fields of Location will be filled with the results that
// can be retrieved upon the next call to Iterate. The Method interface
// requires that entries of Location are not modified aside from the commanded
// evaluations. Thus, the type implementing Method may use multiple Operations
// to set the Location fields at a particular x value.
//
// Instead of an Evaluation, a Method may declare MajorIteration. In
// a MajorIteration, the values in the fields of Location are treated as
// a potential optimizer. The convergence of the optimization routine
// (GradientThreshold, etc.) is checked at this new best point. In
// a MajorIteration, the fields of Location must be valid and consistent.
//
// A Method must not return InitIteration and PostIteration operations. These are
// reserved for the clients to be passed to Recorders. A Method must also not
// combine the Evaluation operations with the Iteration operations.
type localMethod interface {
// Init initializes the method based on the initial data in loc, updates it
// and returns the first operation to be carried out by the caller.
// The initial location must be valid as specified by Needs.
initLocal(loc *Location) (Operation, error)
// Iterate retrieves data from loc, performs one iteration of the method,
// updates loc and returns the next operation.
iterateLocal(loc *Location) (Operation, error)
needser
}
type needser interface {
// needs specifies information about the objective function needed by the
// optimizer beyond just the function value. The information is used
// internally for initialization and must match evaluation types returned
// by Init and Iterate during the optimization process.
needs() struct {
Gradient bool
Hessian bool
}
}
// Statuser can report the status and any error. It is intended for methods as
// an additional error reporting mechanism apart from the errors returned from
// Init and Iterate.
type Statuser interface {
Status() (Status, error)
}
// Linesearcher is a type that can perform a line search. It tries to find an
// (approximate) minimum of the objective function along the search direction
// dir_k starting at the most recent location x_k, i.e., it tries to minimize
// the function
// φ(step) := f(x_k + step * dir_k) where step > 0.
// Typically, a Linesearcher will be used in conjunction with LinesearchMethod
// for performing gradient-based optimization through sequential line searches.
type Linesearcher interface {
// Init initializes the Linesearcher and a new line search. Value and
// derivative contain φ(0) and φ'(0), respectively, and step contains the
// first trial step length. It returns an Operation that must be one of
// FuncEvaluation, GradEvaluation, FuncEvaluation|GradEvaluation. The
// caller must evaluate φ(step), φ'(step), or both, respectively, and pass
// the result to Linesearcher in value and derivative arguments to Iterate.
Init(value, derivative float64, step float64) Operation
// Iterate takes in the values of φ and φ' evaluated at the previous step
// and returns the next operation.
//
// If op is one of FuncEvaluation, GradEvaluation,
// FuncEvaluation|GradEvaluation, the caller must evaluate φ(step),
// φ'(step), or both, respectively, and pass the result to Linesearcher in
// value and derivative arguments on the next call to Iterate.
//
// If op is MajorIteration, a sufficiently accurate minimum of φ has been
// found at the previous step and the line search has concluded. Init must
// be called again to initialize a new line search.
//
// If err is nil, op must not specify another operation. If err is not nil,
// the values of op and step are undefined.
Iterate(value, derivative float64) (op Operation, step float64, err error)
}
// NextDirectioner implements a strategy for computing a new line search
// direction at each major iteration. Typically, a NextDirectioner will be
// used in conjunction with LinesearchMethod for performing gradient-based
// optimization through sequential line searches.
type NextDirectioner interface {
// InitDirection initializes the NextDirectioner at the given starting location,
// putting the initial direction in place into dir, and returning the initial
// step size. InitDirection must not modify Location.
InitDirection(loc *Location, dir []float64) (step float64)
// NextDirection updates the search direction and step size. Location is
// the location seen at the conclusion of the most recent linesearch. The
// next search direction is put in place into dir, and the next step size
// is returned. NextDirection must not modify Location.
NextDirection(loc *Location, dir []float64) (step float64)
}
// StepSizer can set the next step size of the optimization given the last Location.
// Returned step size must be positive.
type StepSizer interface {
Init(loc *Location, dir []float64) float64
StepSize(loc *Location, dir []float64) float64
}
// A Recorder can record the progress of the optimization, for example to print
// the progress to StdOut or to a log file. A Recorder must not modify any data.
type Recorder interface {
Init() error
Record(*Location, Operation, *Stats) error
}