Powell's method
Encyclopedia
Powell's method, strictly Powell's conjugate gradient descent method, is an algorithm
proposed by Michael J. D. Powell
for finding a local minimum of a function. The function need not be differentiable, and no derivatives are taken.
The function must be a real-valued function of a fixed number of real-valued inputs, creating an N-dimensional hypersurface or Hamiltonian
. The caller passes in the initial point. The caller also passes in a set of initial search vectors. Typically N search vectors are passed in which are simply the normals aligned to each axis.
The method minimises the function by a bi-directional search along each search vector, in turn. The new position can then be expressed as a linear combination of the search vectors. The new displacement vector becomes a new search vector, and is added to the end of the search vector list. Meanwhile the search vector which contributed most to the new direction, i.e. the one which was most successful, is deleted from the search vector list. The algorithm iterates an arbitrary number of times until no significant improvement is made.
The method is useful for calculating the local minimum of a continuous but complex function, especially one without an underlying mathematical definition, because it is not necessary to take derivatives. The basic algorithm is simple, the complexity is in the linear searches along the search vectors, which can be achieved via Brent's method
.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
proposed by Michael J. D. Powell
Michael J. D. Powell
Michael James David Powell FRS, FIMA is a British mathematics Professor, retired from Cambridge University, where he earned his bachelors degree and, in 1979, his D.Sc. . He is known for his extensive work in numerical analysis, especially nonlinear optimization and Approximation...
for finding a local minimum of a function. The function need not be differentiable, and no derivatives are taken.
The function must be a real-valued function of a fixed number of real-valued inputs, creating an N-dimensional hypersurface or Hamiltonian
Hamiltonian (quantum mechanics)
In quantum mechanics, the Hamiltonian H, also Ȟ or Ĥ, is the operator corresponding to the total energy of the system. Its spectrum is the set of possible outcomes when one measures the total energy of a system...
. The caller passes in the initial point. The caller also passes in a set of initial search vectors. Typically N search vectors are passed in which are simply the normals aligned to each axis.
The method minimises the function by a bi-directional search along each search vector, in turn. The new position can then be expressed as a linear combination of the search vectors. The new displacement vector becomes a new search vector, and is added to the end of the search vector list. Meanwhile the search vector which contributed most to the new direction, i.e. the one which was most successful, is deleted from the search vector list. The algorithm iterates an arbitrary number of times until no significant improvement is made.
The method is useful for calculating the local minimum of a continuous but complex function, especially one without an underlying mathematical definition, because it is not necessary to take derivatives. The basic algorithm is simple, the complexity is in the linear searches along the search vectors, which can be achieved via Brent's method
Brent's method
In numerical analysis, Brent's method is a complicated but popular root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less reliable methods...
.