Global optimization of univariate Lipschitz functions. I: Survey and properties (Q1198732)

This paper and its sequel provide a timely synthesis of known (and new) results about the optimization of a Lipschitz continuous function \(f\) of a single variable. The authors carefully specify the raw problem, that for finding both the globally optimal value and a corresponding point, together with four variations. Necessary conditions on \(f\) for finite convergence in certain of the problem types are given. Uniform and simplified descriptions of the algorithms of Evtuschenko, Piyavskii and Shubert, Timonov, Schoen, Galperin and Shen, and Zhu are presented. In order to compare such algorithms, two extreme algorithm types are introduced: a passive algorithm (involving a systematic grid search from one end of the domain to the other) and a best possible algorithm (using the minimum number of evaluation points). Amidst the many interesting results of the paper, it is shown for example that the algorithms of Timonov and Schoen never require more evaluations than does the passive algorithm. On the other hand, the Piyavskii-Shubert algorithm is shown to never require more evaluations than one more than four times the best possible figure. [For Part II see the following review].