Piyavskii’s algorithm maximizes a univariate function f satisfying a Lipschitz condition. The authors compare the numbers of iterations needed by Piyavskii’s algorithm (nP) to obtain a bounding function whose maximum value is within ∈ of the (unknown) globally optimal value with that required by the best possible algorithm (nB). The main result is that: nP•2nB+1 and that this bound is sharp. The authors also show that the number of iterations needed by Piyavskii’s algorithm to obtain a 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 points are deduced from these bounds.
