Successive parabolic interpolation is a technique for finding the
extremum (minimum or maximum) of a continuous
unimodal function by successively fitting
parabola
In mathematics, a parabola is a plane curve which is mirror-symmetrical and is approximately U-shaped. It fits several superficially different mathematical descriptions, which can all be proved to define exactly the same curves.
One descri ...
s (
polynomials
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exam ...
of degree two) to a function of one variable at three unique points or, in general, a function of ''n'' variables at ''1+n(n+3)/2'' 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
In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence (x_n) that converges to x^* is said to have ''order of co ...
of approximately ''1.325''. The superlinear rate of convergence is superior to that of other methods with only linear convergence (such as
line search
In optimization, the line search strategy is one of two basic iterative approaches to find a local minimum \mathbf^* of an objective function f:\mathbb R^n\to\mathbb R. The other approach is trust region.
The line search approach first finds a ...
). Moreover, not requiring the computation or approximation of function
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
s makes successive parabolic interpolation a popular alternative to other methods that do require them (such as
gradient descent
In mathematics, gradient descent (also often called steepest descent) is a first-order iterative optimization algorithm for finding a local minimum of a differentiable function. The idea is to take repeated steps in the opposite direction of the ...
and
Newton's method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real- ...
).
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
In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned o ...
, 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 In numerical analysis, inverse quadratic interpolation is a root-finding algorithm, meaning that it is an algorithm for solving equations of the form ''f''(''x'') = 0. The idea is to use quadratic interpolation to approximate the inverse of ''f''. ...
is a related method that uses parabolas to find
root
In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the su ...
s rather than extrema.
*
Simpson's rule
In numerical integration, Simpson's rules are several approximations for definite integrals, named after Thomas Simpson (1710–1761).
The most basic of these rules, called Simpson's 1/3 rule, or just Simpson's rule, reads
\int_a^b f(x) \, ...
uses parabolas to approximate definite integrals.
References
{{Optimization algorithms, unconstrained
Numerical analysis
Optimization algorithms and methods