### G-89-14

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

## Pierre Hansen, Brigitte Jaumard, and Shi-Hui Lu

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.

Published **May 1989**
,
32 pages

This cahier was revised in **March 1990**