×

zbMATH — the first resource for mathematics

Convergence rates of a global optimization algorithm. (English) Zbl 0756.90082
This paper presents a best and worst case analysis of convergence rates for a deterministic global optimization algorithm published recently by the author [ibid. 34, 188-200 (1986; Zbl 0598.90075)], which is the \(N\)- dimensional extension of the Pijavskij-Shubert algorithm [see S. A. Pijavskij [Zh. Vychislit. Mat. Mat. Fiz. 12, 888-896 (1972; Zbl 0249.65046); English translation in U.S.S.R. Comput. Math. Math. Phys. 12(1972), No. 4, 57-67 (1973)], and B. O. Shubert [SIAM J. Numer. Anal. 9, 379-388 (1972; Zbl 0251.65052)]. Superlinear convergence is proved for Lipschitz functions which are convex in the direction of the global maximum (concave in the direction of the global minimum).
In verifying computationally the expected convergence rates the author used the program he has implemented on a VAX 11-780 and the following test functions: \[ \text{Invert}(x)=1-{\sqrt N\over N}\| x^*- x\|,\quad 0\leq x^ i\leq 1, x^*=(1,\dots,1),\quad\text{and} \] \[ \text{Expo}(x)=e^{-\| x^*-x\|},\quad 0\leq x^ i\leq 1, x^*=(1,\dots,1). \] Computational results are given which confirm the theoretical convergence rates.

MSC:
90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L.C.W. Dixon and G.P. Szego,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978).
[2] Y.P. Evtushenko, ”Numerical methods for finding global extrema of a non-uniform mesh,”USSR Computational Mathematics and Mathematical Physics 11 (1971). · Zbl 0233.90007
[3] P. Gill, W. Murray and M. Wright,Practical Optimization (Academic Press, London, 1981). · Zbl 0503.90062
[4] R. Horst, ”A general class of branch-and-bound methods in global optimization,”Journal of Optimization Theory and Applications (1985).
[5] R.H. Mladineo, ”An algorithm for finding the global maximum of a multimodal, multivariate function,”Mathematical Programming 34 (1986) 188–200. · Zbl 0598.90075 · doi:10.1007/BF01580583
[6] S.A. Pijavskii, ”An algorithm for finding the absolute extremum of a function,”USSR Computational Mathematics and Mathematical Physics (1972) 57–67. · Zbl 0282.65052
[7] J. Pinter, ”Globally convergent methods forn-dimensional multi-extremal optimization,”Optimisation 17 (1986).
[8] H. Ratschek, ”Inclusion functions and global optimization,”Mathematical Programming 33 (1985) 300–317. · Zbl 0579.90082 · doi:10.1007/BF01584379
[9] B. Shubert, ”A sequential method seeking the global maximum of a function,”SIAM Journal of Numerical Analysis 9(3) (1972) 379–388. · Zbl 0251.65052 · doi:10.1137/0709036
[10] A.G. Sukharev, ”A stochastic algorithm for extremum search, optimal in one step,”USSR Computational Mathematics and Mathematical Physics (1981) 23–39. · Zbl 0498.90072
[11] G.R. Wood, ”Multidimensional bisection applied to global optimization,”Computers & Mathematics with Applications 21 (1991) 161–172. · Zbl 0735.65041 · doi:10.1016/0898-1221(91)90170-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.