Mathematics Source Library
C & ASM

 Home Optimization Home Nonlinear Optimization Home One-Dimensional Optimization Home Rosenbrock's Success/Failure Routines Exhaustive Grid Search Three Point Equal Interval Search Golden Section Search Fibonacci Search Parabolic Extrapolation for Bracketing an Extremum Parabolic Interpolation Minimize Down the Line / Maximize Up the Line

## Parabolic Interpolation

The extremum of the parabola y = cx2 + bx + a where c ≠ 0 is located at x* = - b / 2c. If
c < 0, then the extremum is a maximum and if c > 0, then the extremum is a minimum.

Suppose that we are given a smooth function f : [α,β] → R, where α < β for which we seek to locate a relative minimum. Assume that also we are given the initial data (x1, f (x1) ),
(x2, f (x2) ), and (x3, f (x3) ), where α ≤ x1 < x2 < x3 ≤ β such that f (x1) > f (x2) < f( x3). Then the location of minimum, x*, of the parabola through the same three points must lie between x1 and x3. If x* = x2 then perturb it by a small amount η either towards x1 or x3 depending on whether f (x1) is less than or f (x3) or not. Then either x* < x2 or x* > x2. If x* < x2 then either f (x*) ≤ f (x2) or f (x*) > f (x2). If f (x*) ≤ f (x2) then set x3x2, x2x* or if f (x*) > f (x2) then set x1x*. The process is analogous to that above if x* > x2. Repeat the process unless the length of the interval of uncertainty is less than a preassigned tolerance in which case terminate the procedure.

### Function List

• int Min_Search_Parabolic_Interpolation( double (*f)(double), double* x0, double* fx0, double tolerance )

Given initial data ( x0, fx0 ), ( x0, fx0 ), and ( x0, fx0 ) where
x0 < x0 < x0, fx0 > fx0 < fx0 and fx0[i] = f ( x0[i] ), i = 0, 1, 2 this routine reduces the interval of uncertainty [ x0, x0 ] by an extension of the iterative process described above. The iteration halts when the length of the interval of uncertainty relative to its midpoint is less than tolerance. Upon return, x0 is the lower endpoint of the interval of uncertainty, x0 is the upper endpoint and x0 is the current best estimate of the location of the minimum. The array fx0 will contain the value of f ( x ) evaluated at the three points.

• int Max_Search_Parabolic_Interpolation( double (*f)(double), double* x0, double* fx0, double tolerance )

Given initial data ( x0, fx0 ), ( x0, fx0 ), and ( x0, fx0 ) where
x0 < x0 < x0, fx0 < fx0 > fx0 and fx0[i] = f ( x0[i] ), i = 0, 1, 2 this routine reduces the interval of uncertainty [ x0, x0 ] by an extension of the iterative process described above. The iteration halts when the length of the interval of uncertainty relative to its midpoint is less than tolerance. Upon return, x0 is the lower endpoint of the interval of uncertainty, x0 is the upper endpoint and x0 is the current best estimate of the location of the maximum. The array fx0 will contain the value of f ( x ) evaluated at the three points.