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

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