6.6 Powell’s Method 319
denotes the number of design variables and then searches for the minimum along the
pattern directionSi, defined by
Si=Xi−Xi−n (6.24)
whereXiis the point obtained at the end ofnunivariate steps andXi−nis the starting
point before taking thenunivariate steps. In general, the directions used prior to taking
a move along a pattern direction need not be univariate directions.
6.6 Powell’s Method
Powell’s methodis an extension of the basic pattern search method. It is the most
widely used direct search method and can be proved to be a method of conjugate
directions [6.7]. A conjugate directions method will minimize a quadratic function in
a finite number of steps. Since a general nonlinear function can be approximated rea-
sonably well by a quadratic function near its minimum, a conjugate directions method
is expected to speed up the convergence of even general nonlinear objective functions.
The definition, a method of generation of conjugate directions, and the property of
quadratic convergence are presented in this section.
6.6.1 Conjugate Directions
Definition: Conjugate Directions. LetA=[A] be ann×nsymmetric matrix. A set
ofnvectors (or directions){Si} s said to be conjugate (more accuratelyi A-conjugate) if
STiASj= 0 for alli
=j, i= 1 , 2 ,... , n, j= 1 , 2 ,... , n (6.25)
It can be seen thatorthogonal directionsare a special case of conjugate directions
(obtained with [A]=[I] in Eq. (6.25)).
Definition: Quadratically Convergent Method. If a minimization method, using
exact arithmetic, can find the minimum point innsteps while minimizing a quadratic
function innvariables, the method is called aquadratically convergent method.
Theorem 6.1Given a quadratic function ofnvariables and two parallel hyperplanes
1 and 2 of dimensionk < n. Let the constrained stationary points of the quadratic
function in the hyperplanes beX 1 andX 2 , respectively. Then the line joiningX 1 and
X 2 is conjugate to any line parallel to the hyperplanes.
Proof: Let the quadratic function be expressed as
Q(X)=^12 XTAX+BTX+C (6.26)
The gradient ofQis given by
∇Q(X)=AX+B
