Introduction to Optimization

13
TABLE 1.1
Comparison of Nelder-Meade and BFGS Algorithms
Nelder-Mead
BFGS
Starting Point
Ending Point
Ending Point
x
y
x
y
cost
x
y
cost
8.9932
3.7830
9.0390
5.5427
-15.1079
9.0390
2.4567
-11.6835
3.4995
8.9932
5.9011
2.4566
-8.5437
5.9011
2.4566
-8.5437
0.4985
7.3803
1.2283
8.6682
-10.7228
0.0000
8.6682
-9.5192
8.4066
5.9238
7.4696
5.5428
-13.5379
9.0390
5.5428
-15.1079
0.8113
6.3148
1.2283
5.5427
-7.2760
0.0000
5.5428
-6.0724
6.8915
1.8475
7.4696
2.4566
-10.1134
7.4696
2.4566
-10.1134
7.3021
9.5406
5.9011
8.6682
-15.4150
7.4696
8.6682
-16.9847
5.6989
8.2893
5.9011
8.6682
-15.4150
5.9011
8.6682
-16.9847
6.3245
3.2649
5.9011
2.4566
-8.5437
5.9011
2.4566
-8.5437
5.6989
4.6725
5.9011
5.5428
-11.9682
5.9011
5.5428
-11.9682
4.0958
0.3226
4.3341
0.0000
-4.3269
4.3341
0.0000
-4.3269
4.2815
8.2111
4.3341
8.6622
-13.8461
4.3341
8.6622
-13.8461
Average
-11.2347
-11.1412

---

14
INTRODUCTION TO OPTIMIZATION
start
x
y
Figure 1.8
Possible path that the coordinate search method might take on a quadratic
cost surface.
start
x
y
Figure 1.9
Possible path that the Rosenbrock method might take on a quadratic cost
surface.
ables. Then the algorithm cycles through the variables until an acceptable solu-
tion is found. Figure 1.8 models a possible path the algorithm might take in a
quadratic cost surface. In general, this method is slow.
Rosenbrock (1960) developed a method that does not limit search direc-
tions to be parallel to the variable axes. The first iteration of the Rosenbrock
method uses coordinate search along each variable to find the first improved
point (see Figure 1.9). The coordinate axes are then rotated until the first new
coordinate axis points from the starting location to the first point. Gram-
Schmidt orthogonalization finds the directions of the other new coordinate
axes based on the first new coordinate axis. A coordinate search is then per-

---

MINIMUM-SEEKING ALGORITHMS
15
Figure 1.10
Flowchart for a typical line search algorithm.
formed along each new coordinate axis. As before, this process iterates until
an acceptable solution is found.
A line search finds the optimum in one direction or dimension. For an n-
dimensional objective function, the line search repeats for at least n iterations
until the optimum is found. A flowchart of successive line search optimization
appears in Figure 1.10. All the algorithms in this category differ in how the
search direction at step n is found. For detailed information on the 
three methods described here, consult Luenberger (1984) and Press et al.
(1992).
The steepest descent algorithm originated with Cauchy in 1847 and has
been extremely popular. It starts at an arbitrary point on the cost surface and
minimizes along the direction of the gradient. The simple formula for the 
(n
+ 1)th iteration is given by
(1.14)
where 
g
n
is a nonnegative scalar that minimizes the function in the direction
of the gradient. By definition, the new gradient formed at each iteration 
is orthogonal to the previous gradient. If the valley is narrow (ratio of
maximum to minimum eigenvalue large), then this algorithm bounces 
from side to side for many iterations before reaching the bottom. Figure 1.11
shows a possible path of the steepest descent algorithm. Note that the path is
orthogonal to the contours and any path is orthogonal to the previous and
next path.
The method of steepest descent is not normally used anymore, because
more efficient techniques have been developed. Most of these techniques
involve some form of Newton’s method. Newton’s method is based on a mul-
x
y
y
n
n
n
n
n
n
n
x
f x y
+1
+
È
ÎÍ
˘
˚˙
=
È
ÎÍ
˘
˚˙
-
—
(
)
1
g
,

---

tidimensional Taylor series expansion of the function about the point x
k
given by
(1.15)
where
x
n
= point about which Taylor series is expanded
x
= point near x
n
x
T
= transpose of vector (in this case row vector becomes column vector)
H
= Hessian matrix with elements given by h
mn
= ∂
2
f/
∂x
m
∂x
n
Taking the gradient of the first two terms of (1.15) and setting it equal to zero
yields
(1.16)
Starting with a guess x
0
, the next point, x
n
+1
, can be found from the previous
point, x
n
, by
(1.17)
Rarely is the Hessian matrix known. A myriad of algorithms have spawned
around this formulation. In general, these techniques are formulated as
x
x
f x
n
n
n
+
-
=
-
—
( )
1
1
H
—
( )
= —
( )
+
-
(
)
=
f x
f x
x
x
n
n
H
0
f
f x
f x
x
x
x
x
x
x
n
n
n
T
n
n
T
x
( )
=
( )
+ —
( )
-
(
)
+
-
(
)
-
(
)
+
2 !
. . .