GLOBAL OPTIMIZATION OF UNIVARIATE LIPSCHITZ FUNCTIONS .2. NEW ALGORITHMS AND COMPUTATIONAL COMPARISON

We consider the following global optimization problems for a Lipschitz function f implicitly defined on an interval [a, b]. Problem P': find a globally epsilon-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 epsilon-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 epsilon-optimal. Moreover, a sufficient condition on f for this to be the case is given. In phase II, the algorithm proves the epsilon-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally epsilon-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 epsilon, 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.