The authors consider the following global optimization problems for a univariate Lipschitz function f defined on an interval [a,b]: Problem P: find a globally optimal value of f and a corresponding point; Problem P': find a globally •-optimal value of f and a corresponding point; Problem Q: localize all globally optimal points; Problem Q': find a set of disjoint subintervals of small length whose union contains all globally optimal points; Problem Q“: find a set of disjoint subintervals containing only points with a globally •-optimal value and whose union contains all globally optimal points. The authors present necessary conditions on f for finite convergence in Problem P and Problem Q, recall the concepts necessary for a worst-case and an empirical study of algorithms (i.e., those of passive and of best possible algorithms), summarize and discuss algorithms of Evtushenko, Piyavskii-Shubert, Timonov, Schoen, Galperin, Shen and Zhu, presenting them in a simplified and uniform way, in a high-level computer language. They address in particular the problems of using an approximation for the Lipschitz constant, reducing as much as possible the expected length of the region of indeterminacy which contains all globally optimal points and avoiding remaining subintervals without points with a globally •-optimal value. New algorithms for Problems P' and Q” and an extensive computational comparison of algorithms are presented in a companion paper.
