The authors 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.
