Graphics Programs Reference
In-Depth Information
Note that the change in the gradient is
s
Au
. If thischange is perpendicular to avector
v
; that is, if
v
T
Au
=
0
(10.7)
the directionsof
u
and
v
aresaid to be mutually
conjugate
(noninterfering). The
implicationisthatonce wehave minimized
F
(
x
) in the direction of
v
, wecan move
along
u
without ruining the previous minimization.
Foraquadraticfunction of
n
independent variables it is possible to construct
n
mutually conjugate directions. Therefore, it would take precisely
n
lineminimizations
along these directionstoreach the minimumpoint. If
F
(
x
) is not a quadraticfunction,
Eq. (10.5)can betreatedas a local approximation of the meritfunction,obtainedby
truncating the Taylor series expansion of
F
(
x
) about
x
0
(see Appendix A1):
1
2
(
x
x
0
)
T
H
(
x
0
)(
x
F
(
x
)
≈
F
(
x
0
)
+
∇
F
(
x
0
)(
x
−
x
0
)
+
−
−
x
0
)
Now the conjugate directions based on the quadraticform areonly approximations,
valid in the close vicinity of
x
0
.Consequently, it would take severalcycles of
n
line
minimizationstoreach the optimal point.
The variousconjugate gradientmethods use different techniques for constructing
conjugate directions. The so-called
zero-order methods
work with
F
(
x
)only, whereas
the
first-order methods
utilize both
F
(
x
) and
F
. The first-ordermethods arecom-
putationallymoreefficient, of course, but the inputof
∇
∇
F
(if it is available at all) can
be very tedious.
Powell's Method
Powell's methodis a zero-ordermethod, requiring the evaluation of
F
(
x
)only. If the
problem involves
n
design variables, the basic algorithmis
Choose apoint
x
0
in the design space.
Choose the starting vectors
v
i
,
i
=
1
,
2
,...,
n
(the usual choice is
v
i
=
e
i
, where
e
i
is the unit vectorinthe
x
i
-coordinate direction).
cycle
do with
i
n
Minimize
F
(
x
) along the linethrough
x
i
−
1
in the direction of
v
i
.Let the
minimum point be
x
i
.
=
1
,
2
,...,
end do
v
n
+
1
←
x
0
−
x
n
(this vectorisconjugate to
v
n
+
1
producedinthe previous loop)
Minimize
F
(
x
) along the linethrough
x
0
in the direction of
v
n
+
1
.Let theminimum
point be
x
n
+
1
.
if
|
x
n
+
1
−
x
0
|
<ε
exit loop
Search WWH ::
Custom Search