Modified Piyavskii’s Global One-Dimensional Optimization of a Differentiable Function
Modified Piyavskii’s Global One-Dimensional Optimization of a Differentiable Function作者机构:Mohammadia School of Engineering Mohammed V University Rabat Morocco
出 版 物:《Applied Mathematics》 (应用数学(英文))
年 卷 期:2012年第3卷第10期
页 面:1306-1320页
学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题:Global Optimization Piyavskii’s Algorithm
摘 要: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.