GLOBAL OPTIMIZATION OF UNIVARIATE LIPSCHITZ FUNCTIONS .1. SURVEY AND PROPERTIES

We 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 epsilon-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 epsilon-optimal value and whose union contains all globally optimal points. We 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. We 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 epsilon-optimal value. New algorithms for Problems P'and Q" and an extensive computational comparison of algorithms are presented in a companion paper.