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

On the Number of Iterations of Piyavskii's Global Optimization Algorithm

Pierre Hansen, Brigitte Jaumard et Shi-Hui Lu

Piyavskii's algorithm maximizes a univariate function f satisfying a Lipschitz condition. We compare the numbers of iterations needed to obtain a bound within ε of the (unknown) globally optimal value with a best possible algorithm (nB) and with Piyavskii's algorithm (nP). The main result if that: nP ≤ 2nB + 1 and that this bound is sharp. We also show that the number of iterations needed by Piyavskii's algorithm to obtain a proved globally ε-optimal value together with a corresponding point (nPY) satisfies nPY ≤ 4nB + 1 and that this bound is again sharp. Lower and upper bounds on nB are obtained as functions of f(x), ε, L0 and L1, where L0 is the smallest valid Lipschitz constant and L1 the Lipschitz constant used. Several properties of nB and of the distribution of evaluation poins are deduced from these bounds.

, 28 pages

Ce cahier a été révisé en août 1989