Groupe d’études et de recherche en analyse des décisions


Lipschitz Optimization


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 -optimal one, all optimal solutions, and a small volume enclosure of all optimal solutions within hyperrectangles (possibly containing only -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 -optimal algorithms. Methods of Piyavskii, 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 Piyavskii; 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 Piyavskii'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.

, 122 pages