Abstract
We investigate the role of additional information in reducing the
computational complexity of the global optimization problem (GOP).
Following this approach, we develop GMG -- an algorithm to find
the Global Minimum with a Guarantee. The new algorithm breaks up
an originally continuous GOP into a discrete (grid) search problem followed by a descent problem. The discrete search identifies the basin of attraction of the global minimum after which the actual location of the minimizer is found upon applying a descent algorithm. The algorithm is first applied to the golf course problem, which serves as a litmus test for its
performance in the presence of both complete and degraded
additional information. GMG is further assessed on a set of
standard benchmark functions. We then illustrate the performance
of the the validated algorithm on a simple realization of the
monocular passive ranging (MPR) problem in remote sensing, which
consists of identifying the range of an airborne target
(missile, plane, etc.) from its observed radiance. This inverse
problem is set as a GOP whereby the
difference between the observed and model predicted radiances is
minimized over the possible ranges and atmospheric
conditions. We solve the GOP using GMG and report on the
performance of the algorithm.