TITLE:
Modified Piyavskii’s Global One-Dimensional Optimization of a Differentiable Function
AUTHORS:
Rachid Ellaia, Mohamed Zeriab Es-Sadek, Hasnaa Kasbioui
KEYWORDS:
Global Optimization; Piyavskii’s Algorithm
JOURNAL NAME:
Applied Mathematics,
Vol.3 No.10A,
November
1,
2012
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 (nC) to obtain a bounding piece-wise concave function Φ whose maximum is within ε of the globally optimal value foptwith that required by the reference sequential algorithm (nref). The main result is that nC≤ 2nref + 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 (nB) satisfies nBnref + 1 Lower and upper bounds for nref are obtained as functions of f(x) , ε, M1 and M0 where M0 is a constant defined by M0 = supx∈[a,b] - f’’(x) and M1 ≥ M0 is an evaluation of M0.