Graphics Programs Reference
In-Depth Information
=
,
,...,
do with
i
1
2
n
v
i
←
v
i
+
1
(
v
1
is discarded, the othervectors are reused)
end do
end cycle
Powell demonstrated that the vectors
v
n
+
1
producedinsuccessivecycles are mu-
tually conjugate,sothat the minimum pointofa quadraticsurface is reachedin
precisely
n
cycles. Inpractice, the meritfunctionis seldom quadratic, but aslong as
itcan be approximated locallybyEq. (10.5), Powell's methodwill work. Of course, it
usually takes morethan
n
cycles to arrive at the minimum of anonquadraticfunction.
Note that ittakes
n
line minimizationstoconstruct each conjugate direction.
Figure 10.3(a) illustrates onetypicalcycle of the methodinatwo dimensional
design space (
n
2).Westart with point
x
0
and vectors
v
1
and
v
2
. Thenwe find the
distance
s
1
that minimizes
F
(
x
0
+
=
s
v
1
), finishing up at point
x
1
=
x
0
+
s
1
v
1
.
Next, we
determine
s
2
that minimizes
F
(
x
1
+
s
v
2
), which takes usto
x
2
=
x
1
+
s
2
v
2
. The last
search directionis
v
3
=
x
2
−
x
0
.After finding
s
3
by minimizing
F
(
x
0
+
s
v
3
) we get to
x
3
=
x
0
+
s
3
v
3
,completing the cycle.
P
0
(
x
0
)
P
0
s
1
v
1
s
3
v
3
v
3
P
1
(
x
1
)
P
5
P
1
P
6
P
3
(
x
3
)
P
3
v
1
P
4
s
2
v
2
P
2
P
2
(
x
2
)
v
2
(a)
(b)
Figure 10.3.
The method of Powell.
Figure 10.3(b) shows the moves carried out in twocycles superimposed on the
contour map of a quadraticsurface.Asexplainedbefore, the first cycle starts at point
P
0
and ends up at
P
3
. The second cycle takes usto
P
6
, which is the optimal point. The
directions
P
0
P
3
and
P
3
P
6
are mutually conjugate.
Powell's methoddoes have a major flaw thathastobe remedied—if
F
(
x
) is not
a quadratic, the algorithm tendstoproduce search directionsthat graduallybecome
linearlydependent, thereby ruining the progress towards the minimum. The source
of the problemis the automatic discarding of
v
1
at the end of each cycle. It has been
suggested that it is better to throw out the direction that resultedinthe
largest decrease
of
F
(
x
), apolicy that we adopt. It seemscounterintuitivetodiscard the best direction,
but it islikely to be close to the direction addedinthe nextcycle, thereby contributing
Search WWH ::
Custom Search