×

zbMATH — the first resource for mathematics

A deterministic algorithm for global optimization. (English) Zbl 0807.90103
Consider the global optimization problem (1) \(\max_{x\in X} f(x)\), where \(f: X\to\mathbb{R}^ 1\) is a differentiable function and \(X\subset \mathbb{R}^ m\) is a compact polytope. To solve (1) the author presents a deterministic space covering algorithm strictly related to algorithms introduced in the literature by B. O. Shubert [SIAM J. Numer. Analysis 9, No. 3, 379–388 (1972; Zbl 0251.65052)] and by R. H. Mladineo [Math. Program. 34, 188–200 (1986; Zbl 0598.90075)]. While those authors assumed \(f\) to satisfy the Lipschitz condition, in this paper the following condition is assumed to hold: \[ f(x)\leq f(y)+ \nabla f(y)'(x- y)+ K\| x- y\|^ 2\quad\text{for any }x,y\in X, \] where \(K\) is a known constant. This leads to simpler geometric properties. The main idea of the algorithm is to construct a sequence of upper envelopes for \(f\); their global maxima are easily found and converge to the solution of (1).
An implementation of the algorithm has been tested in solving standard test functions; the results are reported.

MSC:
90C30 Nonlinear programming
Software:
BRENT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. de Biase and F. Frontini, ”A stochastic method for global optimization: Its structure and numerical performance,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization 2 (North-Holland, Amsterdam, 1978) pp. 85–102. · Zbl 0396.90082
[2] H. Bremermann, ”A method of unconstrained global optimization,”Mathematical Biosciences 9 (1970) 1–15. · Zbl 0212.51204 · doi:10.1016/0025-5564(70)90087-8
[3] R.P. Brent,Algorithms for Minimization Without Derivatives (Prentice-Hall, Englewood Cliffs, NJ, 1973). · Zbl 0245.65032
[4] A. Cutler, ”Optimization methods in statistics,” Ph.D thesis, U.C. Berkeley (Berkeley, CA, 1988).
[5] L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization (North-Holland, Amsterdam, 1975). · Zbl 0309.90052
[6] L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization 2 (North-Holland, Amsterdam, 1978). · Zbl 0385.00011
[7] L.C.W. Dixon and G.P. Szegö, ”The global optimization problem: An introduction,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization 2 (North-Holland, Amsterdam, 1978) pp. 1–15.
[8] D.A. Freedman and W. Navidi, ”On the multistage model for carcinogenesis,” Technical Report No. 97, Statistics Department, U.C. Berkeley (Berkeley, CA, 1988).
[9] A.O. Griewank, ”Generalized descent for global optimization,”Journal of Optimization Theory and Applications 34(1) (1981) 11–39. · Zbl 0431.49036 · doi:10.1007/BF00933356
[10] 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
[11] S.A. Piyavskii, ”An algorithm for finding the absolute extremum of a function,”USSR Computational Mathematics and Mathematical Physics 12(4) (1972) 57–67. · Zbl 0282.65052 · doi:10.1016/0041-5553(72)90115-2
[12] W.L. Price, ”Global optimization by controlled random search,”Journal of Optimization Theory and Applications 40 (1983) 333–348. · Zbl 0494.90063 · doi:10.1007/BF00933504
[13] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. Part I: Clustering methods,”Mathematical Programming 39 (1987) 27–56. · Zbl 0634.90066 · doi:10.1007/BF02592070
[14] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. Part II: Multi level methods,”Mathematical Programming 39 (1987) 57–78. · Zbl 0634.90067 · doi:10.1007/BF02592071
[15] B.O. 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
[16] C.H. Slump and B.J. Hoenders, ”The determination of the location of the global maximum of a function in the presence of several local extrema,”IEEE Transactions on Information Theory IT-31 (1985) 490–497. · Zbl 0578.65149
[17] J.A. Snyman and L.P. Fatti, ”A multi-start global minimization algorithm with dynamic search trajectories,”Journal of Optimization Theory and Applications 54 (1987) 121–141. · Zbl 0595.90073 · doi:10.1007/BF00940408
[18] A.A. Törn, ”A search-clustering approach to global optimization,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization 2 (North-Holland, Amsterdam, 1978) pp. 49–62.
[19] D. Vanderbilt and S.G. Louie, ”A Monte Carlo simulated annealing approach to optimization over continuous variables,”Journal of Computational Physics 56 (1984) 259–271. · Zbl 0551.65045 · doi:10.1016/0021-9991(84)90095-0
[20] D.R. Wingo, ”Estimating the location of the Cauchy distribution by numerical global optimization,”Communications in Statistics Part B: Simulation and Computation 12(2) (1983) 201–212. · doi:10.1080/03610918308812311
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.