Engineering Optimization: Theory and Practice, Fourth Edition

280 Nonlinear Programming I: One-Dimensional Minimization Methods

5.11 Cubic Interpolation Method

The cubic interpolation method finds the minimizing step lengthλ∗in four stages [5.5,

5 .11]. It makes use of the derivative of the functionf:

f′(λ)=

df

dλ

=

d

dλ

f (X+λS)=ST∇ f(X+λS)

The first stage normalizes theSvector so that a step sizeλ=1 is acceptable. The

second stage establishes bounds onλ∗, and the third stage finds the value ofλ ̃∗by

approximatingf (λ)by a cubic polynomial h(λ). If theλ ̃∗found in stage 3 does

not satisfy the prescribed convergence criteria, the cubic polynomial is refitted in the

fourth stage.

Stage 1. Calculate =maxi|si| where, |si| s the absolute value of thei ith compo-

nent ofS, and divide each component ofSby. An alternative method of normalization

is to find

=(s^21 +s 22 + · · · +s^2 n)^1 /^2

and divide each component ofSby.

Stage 2. To establish lower and upper bounds on the optimal step sizeλ∗, we need

to find two pointsAandBat which the slopedf/dλhas different signs. We know that

atλ=0,

df

dλ

∣

∣

∣

∣

λ= 0

=ST∇ f(X) < 0

sinceSis presumed to be a direction of descent.†

Hence to start with we can takeA= 0 and try to find a pointλ=Bat which the

slopedf/dλis positive. PointBcan be taken as the first value out oft 0 , 2 t 0 , 4 t 0 , 8 t 0 ,...

at whichf′is nonnegative, wheret 0 is a preassigned initial step size. It then follows

thatλ∗is bounded in the intervalA< λ∗≤ B(Fig. 5.16).

Stage 3. If the cubic equation

h(λ)=a+bλ+cλ^2 +λ^3 (5.45)

f(l)

l

Figure 5.16 Minimum off (λ)lies betweenAandB.

†In this case the angle between the direction of steepest descent andSwill be less than 90◦.