ON THE NUMBER OF ITERATIONS OF PIYAVSKII GLOBAL OPTIMIZATION ALGORITHM

Piyavskii's algorithm maximizes a univariate function f satisfying a Lipschitz condition. We compare the numbers of iterations needed by Piyavskii's algorithm (n(p)) to obtain a bounding function whose maximum value is within epsilon of the (unknown) globally optimal value with that required by the best possible algorithm (n(B)). The main result is that: np less-than-or-equal-to 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 epsilon-optimal value together with a corresponding point (n(PY)) satisfies n(PY)) less-than-or-equal-to 4n(B) + 1 and that this bound is again sharp. Lower and upper bounds on n(B) are obtained as functions of f(x), epsilon, L0, and L1, where L0 is the smallest valid Lipschitz constant and L1 the Lipschitz constant used. Several properties of n(B) and of the distribution of evaluation points are deduced from these bounds.