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


An On-Line Cone Intersection Algorithm for Global Optimization of Multivariate Lipschitz Functions

, et

We study the generalization of Piyavskii's algorithm (1972), proposed by Mladineo (1986), for the global optimization of multivariate Lipschitz functions. It is based on the determination of the maximum value of an upper-bounding function defined as the lower envelope of a set of circular cones. We propose a significant improvement of Mladineo's method with respect to the number of computations required at each iteration, i.e., the number of cone (hyperplane) intersecting points to be evaluated. Moreover, we show that Mladineo's algorithm can be viewed as a branch-and-bound method, leading to some additional reduction tests. Comparative computational experience on standard test functions shows that computing times can be reduced by a factor larger than 1,000 in some cases.

, 33 pages