104
Test for global
optimum
Yes
The global optimum
No
Initial search point
generator
Fig.3.1S. A robust and efficient global optimization scheme
3: Hua-mei Chen
mum. If there is a way to distinguish the global optimum of a function from its
local optimum, then a robust yet efficient global optimizer is achievable. Figure 3.15 shows such a global optimization scheme. It is efficient because a local
optimizer is employed to accelerate convergence, and once the global optimum
is reached, the search process terminates immediately. It is also robust because
the process will not terminate until the global optimum is reached.
Generally, it is very difficult, if not impossible, to determine whether or not
the optimum found for a function is global without evaluating the function
completely. However, for the global image registration problem ( a single transformation is sufficient for registering entire images), there exists a heuristic test
to determine whether the optimum determined is global or not (Chen 200lb).
The heuristic test algorithm may be described with the help of Fig. 3.16a that
shows a function with several local maxima. The goal is to find the position
of the global maximum. As mentioned earlier, to identify the global optimum
of a function without completely evaluating the whole function is very hard, if
not impossible. However, if a second function like the one (thick line) shown in
Fig. 3.16b is available, then it is possible to identify the global maximum of the
function represented by the thin line. If we observe Fig. 3.16b carefully, we can
see the unique relationship of the two functions: their global maxima appear
at the same location. Using this property, it is expedient to identify the global
maximum of the function represented by the thin line. Fig. 3.16c illustrates this
approach. For example, if we use a local optimizer and find Point 1 in Fig. 3.16c
as an optimum and would like to know whether it is a global maximum or just
a local maximum, we can use the position of Point 1 as the initial position and
use a local optimizer to find a local maximum of the second function shown by
the thick line. In this case, the local optimizer will result in Point 3 as the local
maximum. Now we can compare the positions of Point 1 and Point 3. Since they
are different in this case, we can conclude that Point 1 is just a local maximum
Test for global
optimum
Yes
The global optimum
No
Initial search point
generator
Fig.3.1S. A robust and efficient global optimization scheme
3: Hua-mei Chen
mum. If there is a way to distinguish the global optimum of a function from its
local optimum, then a robust yet efficient global optimizer is achievable. Figure 3.15 shows such a global optimization scheme. It is efficient because a local
optimizer is employed to accelerate convergence, and once the global optimum
is reached, the search process terminates immediately. It is also robust because
the process will not terminate until the global optimum is reached.
Generally, it is very difficult, if not impossible, to determine whether or not
the optimum found for a function is global without evaluating the function
completely. However, for the global image registration problem ( a single transformation is sufficient for registering entire images), there exists a heuristic test
to determine whether the optimum determined is global or not (Chen 200lb).
The heuristic test algorithm may be described with the help of Fig. 3.16a that
shows a function with several local maxima. The goal is to find the position
of the global maximum. As mentioned earlier, to identify the global optimum
of a function without completely evaluating the whole function is very hard, if
not impossible. However, if a second function like the one (thick line) shown in
Fig. 3.16b is available, then it is possible to identify the global maximum of the
function represented by the thin line. If we observe Fig. 3.16b carefully, we can
see the unique relationship of the two functions: their global maxima appear
at the same location. Using this property, it is expedient to identify the global
maximum of the function represented by the thin line. Fig. 3.16c illustrates this
approach. For example, if we use a local optimizer and find Point 1 in Fig. 3.16c
as an optimum and would like to know whether it is a global maximum or just
a local maximum, we can use the position of Point 1 as the initial position and
use a local optimizer to find a local maximum of the second function shown by
the thick line. In this case, the local optimizer will result in Point 3 as the local
maximum. Now we can compare the positions of Point 1 and Point 3. Since they
are different in this case, we can conclude that Point 1 is just a local maximum