Group for Research in Decision Analysis


Global Optimization of Univariate Lipschitz Functions: II. New Algorithms and Computational Comparison

, , and

We consider the following global optimization problems for a Lipschitz function f implicitly defined on an interval [a,b]. Problem P': find a globally -optimal value of f and a corresponding point; Problem Q'' : find a set of disjoint subintervals of [a,b] containing only points with a globally -optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P'. In Phase I, this algorithm obtains rapidly a solution which is often globally -optimal. Moreover, a sufficient condition on f for this to be the case is given. In Phase II, the algorithm proves the -optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally -optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small , the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for Problem Q''. A sufficient condition on f is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.

, 32 pages

This cahier was revised in March 1990