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.
Published June 1988 , 28 pages
This cahier was revised in August 1989