Successive parabolic interpolation

Successive parabolic interpolation is a technique for finding the extremum (minimum or maximum) of a continuous unimodal function by successively fitting parabolas (polynomials of degree two) to the function at three unique points, and at each iteration replacing the "oldest" point with the extremum of the fitted parabola.

Advantages

Only function values are used, and when this method converges to an extremum, it does so with an order of convergence of approximately 1.325. The superlinear rate of convergence is superior to that of other methods with only linear convergence (such as line search). Moreover, not requiring the computation or approximation of function derivatives makes successive parabolic interpolation a popular alternative to other methods that do require them (such as gradient descent and Newton's method).

Disadvantages

On the other hand, convergence (even to a local extremum) is not guaranteed when using this method in isolation. For example, if the three points are collinear, the resulting parabola is degenerate and thus does not provide a new candidate point. Furthermore, if function derivatives are available, Newton's method is applicable and exhibits quadratic convergence.

Improvements

Alternating the parabolic iterations with a more robust method (golden section search is a popular choice) to choose candidates can greatly increase the probability of convergence without hampering the convergence rate.

See also

• Inverse quadratic interpolation is a related method that uses parabolas to find roots rather than extrema.
• Simpson's rule uses parabolas to approximate definite integrals.

References

Michael Heath (2002). Scientific Computing: An Introductory Survey (2nd ed.). New York: McGraw-Hill. ISBN 0-07-239910-4. 

Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling … … functions Golden section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation … and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient … and 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 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 & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push-relabel maximum flow   Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search Categories Algorithms and methods Heuristics Software