Successive parabolic interpolation is a technique for finding the
extremum (minimum or maximum) of a continuous
unimodal function
In mathematics, unimodality means possessing a unique mode. More generally, unimodality means there is only a single highest value, somehow defined, of some mathematical object.
Unimodal probability distribution
In statistics, a unimodal pr ...
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 descript ...
s (
polynomials
In mathematics, a polynomial is an expression (mathematics), expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addition, subtrac ...
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). 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. F ...
s makes successive parabolic interpolation a popular alternative to other methods that do require them (such as
gradient descent 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-valu ...
).
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
The golden-section search is a technique for finding an extremum (minimum or maximum) of a function inside a specified interval. For a strictly unimodal function with an extremum inside the interval, it will find that extremum, while for an interv ...
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 polynomial interpolation, quadratic interpolation to approxima ...
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 sur ...
s rather than extrema.
*
Simpson's rule uses parabolas to approximate definite integrals.
References
{{Optimization algorithms, unconstrained
Numerical analysis
Optimization algorithms and methods