Powell's method

Powell's method, strictly Powell's conjugate direction 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. The caller passes in the initial point. The caller also passes in a set of initial search vectors. Typically N search vectors (say${\textstyle \{s_{1},\dots ,s_{N}\}}$) are passed in which are simply the normals aligned to each axis.^[1]

The method minimises the function by a bi-directional search along each search vector, in turn. The bi-directional line search along each search vector can be done by Golden-section search or Brent's method. Let the minima found during each bi-directional line search be ${\textstyle \{x_{0}+\alpha _{1}s_{1},{x}_{0}+\sum _{i=1}^{2}\alpha _{i}{s}_{i},\dots ,{x}_{0}+\sum _{i=1}^{N}\alpha _{i}{s}_{i}\}}$, where ${\textstyle {x}_{0}}$ is the initial starting point and ${\textstyle \alpha _{i}}$ is the scalar determined during bi-directional search along ${\textstyle {s}_{i}}$. The new position (${\textstyle x_{1}}$) can then be expressed as a linear combination of the search vectors i.e. ${\textstyle x_{1}=x_{0}+\sum _{i=1}^{N}\alpha _{i}s_{i}}$. The new displacement vector (${\textstyle \sum _{i=1}^{N}\alpha _{i}s_{i}}$) 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 (${\textstyle i_{d}=\arg \max _{i=1}^{N}|\alpha _{i}|\|s_{i}\|}$), is deleted from the search vector list. The new set of N search vectors is ${\textstyle \{s_{1},\dots ,s_{i_{d}-1},s_{i_{d}+1},\dots ,s_{N},\sum _{i=1}^{N}\alpha _{i}s_{i}\}}$. The algorithm iterates an arbitrary number of times until no significant improvement is made.^[1]

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.

References

• Powell, M. J. D. (1964). "An efficient method for finding the minimum of a function of several variables without calculating derivatives". Computer Journal. 7 (2): 155–162. doi:10.1093/comjnl/7.2.155. hdl:10338.dmlcz/103029.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.7. Direction Set (Powell's) Methods in Multidimensions". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Brent, Richard P. (1973). "Section 7.3: Powell's algorithm". Algorithms for minimization without derivatives. Englewood Cliffs, N.J.: Prentice-Hall. ISBN 0-486-41998-3.

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software