Lipschitz optimization. (English) Zbl 0833.90105

Horst, Reiner et al., Handbook of global optimization. Dordrecht: Kluwer Academic Publishers. Nonconvex Optim. Appl. 2, 407-493 (1995).
Summary: Lipschitz optimization solves global optimization problems in which the objective function and constraint left-hand sides may be given by oracles (or explicitly) and have a bounded slope. The problems of finding an optimal solution, an \(\varepsilon\)-optimal one, all optimal solutions, and a small volume enclosure of all optimal solutions within hyperrectangles (possibly containing only \(\varepsilon\)-optimal points) are investigated. In the univariate case, necessary conditions for finite convergence are studied as well as bounds on the number of iterations and convergence of \(\varepsilon\)-optimal algorithms.
Methods of Piyavskij, Evtushenko, Timonov, Schoen, Galperin, Shen and Zhu, and Hansen, Jaumard and Lu are discussed and compared experimentally. The same is done in the multivariate case for the algorithms of Piyavskij; Mladineo; Jaumard, Herrmann and Ribault; Pinter; Galperin; Meewella and Mayne; Wood; Gourdin, Hansen and Jaumard.
Constrained Lipschitz optimization is then discussed focusing on extensions of Piyavskij’s algorithm and methods which consider all constraints simultaneously, i.e., those of Thach and Tuy, as well as the recent method of Gourdin, Jaumard and MacGibbon. Heuristic algorithms, some of which involve estimation of the Lipschitz constant, are then briefly reviewed. A representative sample of the many existing and potential applications is discussed. An evaluation of the scope, strength and limitations of Lipschitz optimization completes the paper.
For the entire collection see [Zbl 0805.00009].


90C30 Nonlinear programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming