Engineering Optimization: Theory and Practice, Fourth Edition

7.16 Extrapolation Techniques in the Interior Penalty Function Method 449

From Eqs. (7.206) and (7.208), the extrapolated value of the true minimum can be
obtained as

X∗(r= 0 )=A 0 =

X∗k−cX∗k− 1

1 −c

(7.209)

The extrapolation technique [Eq. (7.203)] has several advantages:

1.It can be used to find a good estimate to the optimum of the original problem

with the help of Eq. (7.205).

2.It can be used to provide an additional convergence criterion to terminate the

minimization process. The point obtained at the end of thekth iteration,X∗k,

can be taken as the true minimum if the relation

|X∗k−X∗(r = 0 )|≤ε (7.210)

is satisfied, whereεis the vector of prescribed small quantities.

3.This method can also be used to estimate the next minimum of theφfunction

after a number of minimizations have been completed. This estimate†can be

used as a starting point for the (k+1)st minimization of theφfunction. The

estimate of the (k+1)st minimum, based on the information collected from the

previouskminima, is given by Eq. (7.203) as

X∗k+ 1 ≃X∗(r=rk+ 1 =r 1 ck)

=A 0 + (r 1 ck)A 1 + (r 1 ck)^2 A 2 + · · · +Ak− 1 (r 1 ck)k−^1 (7.211)

If Eqs. (7.206) and (7.208) are used, this estimate becomes

Xk+ 1 ≃X∗(r=c^2 rk− 1 )=A 0 +c^2 rk− 1 A 1

= ( 1 +c)X∗k−cX∗k− 1 (7.212)

Discussion. It has been proved that under certain conditions, the difference between
the true minimumX∗and the estimateX∗(r= 0 )=A 0 will be of the orderr 1 k[7.17].
Thus asr 1 → 0 ,A 0 →X∗. Moreover, ifr 1 < , the estimates of 1 X∗obtained by
usingkminima will be better than those using (k−1) minima, and so on. Hence as
more minima are achieved, the estimate ofX∗orX∗k+ 1 presumably gets better. This
estimate can be used as the starting point for the (k+1)st minimization of the φ
function. This accelerates the entire process by substantially reducing the effort needed
to minimize the successiveφfunctions. However, the computer storage requirements
and accuracy considerations (such as numerical round-off errors that become important
for higher-order estimates) limit the order of polynomial in Eq. (7.203). It has been
found in practice that extrapolations with the help of even quadratic and cubic equations
inrgenerally yield good estimates forX∗k+ 1 andX∗. Note that the extrapolated points
givenby any of Eqs. (7.205), (7.209), (7.211), and (7.212) may sometimes violate the
constraints. Hence we have to check any extrapolated point for feasibility before using
it as a starting point for the next minimization ofφ. If the extrapolated point is found
infeasible, it has to be rejected.

†The estimate obtained forX∗can also be used as a starting point for the (k+ 1 )st minimization of theφ
function.