Author(s)

Rachid Ellaia, Mohamed Zeriab Es-Sadek, Hasnaa Kasbioui

Mohammadia School of Engineering, Mohammed V University, Rabat, Morocco.

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_optwith that required by the reference sequential algorithm (n_ref). The main result is that n_C≤ 2n_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_Bn_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₀ = sup_x∈[a,b] - f’’(x) and M₁ ≥ M₀ is an evaluation of M₀.

Global Optimization; Piyavskii’s Algorithm

R. Ellaia, M. Es-Sadek and H. Kasbioui, "Modified Piyavskii’s Global One-Dimensional Optimization of a Differentiable Function," Applied Mathematics, Vol. 3 No. 10A, 2012, pp. 1306-1320. doi: 10.4236/am.2012.330187.