Graphics Programs Reference
In-Depth Information
λ
=
10 000 and changed the starting pointto(0.733 07, 7.587 76), the end pointofthe
first run. The results shown beloware nowacceptable.
>>Intersection point = 0.65561 7.62654
Constraint x*y = 5.00006
Distance = 4.36041
Number of cycles = 4
10 000 in the first run?In thiscase we wouldbelucky and
obtain the minimum in 17 cycles. Hence wesaveonly six cycles by using two runs.
However, a large
Couldwehave used
λ
=
λ
often causes the algorithm to hang up,sothat it generallywise to
start with a small
λ
.
Fletcher-Reeves Method
Let us assume again that the meritfunction has the quadraticform in Eq. (10.5). Given
a direction
v
, it took Powell's method
n
line minimizationstoconstruct a conjugate
direction. Wecan reduce thistoa single line minimizationwith afirst-ordermethod.
Here is the procedure, known as the Fletcher-Reeves method:
Choose a starting point
x
0
.
g
0
←−
∇
F
(
x
0
)
v
0
←
g
0
(lacking a previoussearch direction, we choose the steepest descent).
loopwith
i
=
0
,
1
,
2
,...
Minimize
F
(
x
) along
v
i
; let the minimum point be
x
i
+
1
.
g
i
+
1
←−
∇
F
(
x
i
+
1
).
if
g
i
+
1
<ε
|
|
<ε
or
F
(
x
i
+
1
)
−
F
(
x
i
)
exit loop (convergence criterion).
γ
←
(
g
i
+
1
·
/
(
g
i
·
.
g
i
+
1
)
g
i
)
v
i
+
1
←
g
i
+
1
+
γ
v
i
.
end loop
It can be shown that
v
i
and
v
i
+
1
are mutually conjugate; that is, they satisfy the
relationship
v
i
Av
i
+
1
=
0.
The Fletcher-Reeves methodwill find the minimum of a quadraticfunctionin
n
iterations. If
F
(
x
) is not quadratic, it is necessary to restart the process after every
n
iterations. A variant of the Fletcher-Reeves methodreplaces the expression for
0 .Also
g
i
·
g
i
+
1
=
γ
by
(
g
i
+
1
−
g
i
)
·
g
i
+
1
γ
=
(10.6)
g
i
·
g
i
Foraquadratic
F
(
x
)thischange makes no difference since
g
i
and
g
i
+
1
areorthogonal.
However,formeritfunctionsthat are not quadratic, Eq. (10.6) isclaimed to eliminate
the need forarestart after
n
iterations.
Search WWH ::
Custom Search