The symbols used in the proof are as follows:
a: (T-1), or the number of iterations covered by a history comparison.
t: Number of iterations in each cycle of length T that the algorithm is guaranteed to allow an inverse-quadratic-interpolation step.
r: Specified ratio. The algorithm will take a bisection step if the ratio of the current interval to that a iterations previous is greater than r -a .
|
|
||||||||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The red entries in the table indicate steps where bisection was performed. Setting t to zero (or, equivalently, r to at least 2) represents an extreme case where bisection is always used once the history table has been fully populated. Similarly, setting r =1 or less represents an extreme case where bisection will never be used (unless forced by nonmonotonicities in the objective function).
The table is constructed using the basic rule of the Bent algorithm: if the interval of convergence has not shrunk by at least a factor of r^a over the past a iterations, then take a bisection step, else take a inverse-quadratic-interpolation step.
The pattern in Table 1, where each value of r
allows quadratic interpolation to be used at least t
times during each cycle of length a +1=T
through the history table, can be cast into equation form as a lower bound
on convergence. After n iterations, where n T-1,
the initial interval containing the root will be reduced by at least the
ratio given by Equation 1:
![]() |
Equation 1
|
Given a predetermined value of a
and t , use Equation 2 to select a value for
r .
![]() |
Equation 2
|
![]() |
Equation 3
|