Modified Piyavskii’s Global One-Dimensional Optimization of a Differentiable Function

Abstract

Piyavskii’s algorithm maximizes a univariate function satisfying a Lipschitz condition. We propose a modified Piyavskii’s sequential algorithm which maximizes a univariate differentiable function f by iteratively constructing an upper bounding piece-wise concave function Φ of f and evaluating f at a point where Φ reaches its maximum. We compare the numbers of iterations needed by the modified Piyavskii’s algorithm ( n C ) to obtain a bounding piece-wise concave function Φ whose maximum is within ε of the globally optimal value f opt with that required by the reference sequential algorithm ( n ref ). The main result is that n C ≤ 2 n ref + 1 and this bound is sharp. We also show that the number of iterations needed by modified Piyavskii’s algorithm to obtain a globally ε-optimal value together with a corresponding point ( n B ) satisfies n B n ref + 1 Lower and upper bounds for n ref are obtained as functions of f ( x ) , ε, M1 and M0 where M0 is a constant defined by M 0 = sup x∈[a,b] - f’’ ( x ) and M 1 ≥ M 0 is an evaluation of M 0 .