×

zbMATH — the first resource for mathematics

Convergence qualification of adaptive partition algorithms in global optimization. (English) Zbl 0762.90071
The author considers the optimization problem \(\min f(x)\), subject to \(x\in M\), where \(M\) is a bounded set, which is a closure of a non-empty open set of the real Euclidean \(n\)-space. The objective function \(f\) is continuous and may be multiextremal on \(M\). A general class of methods solving this problem via “complete” partition and search of \(M\) is investigated. Necessary and sufficient convergence conditions are formulated.

MSC:
90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Archetti and B. Betró, ”A probabilistic algorithm for global optimization,”Calcolo 16 (1979) 335–343. · Zbl 0428.90064
[2] F. Archetti and B. Betró, ”Stochastic models and optimization,”Bolletino della Unione Matematica Italiana A (5) 17 (1980) 295–301. · Zbl 0429.90055
[3] P. Basso, ”Iterative methods for the localization of the global maximum,”SIAM Journal of Numerical Analysis 19 (1982) 781–792. · Zbl 0483.65038
[4] P. Basso, ”Optimal search for the global maximum of a function with bounded seminorm,”SIAM Journal of Numerical Analysis 22 (1985) 888–903. · Zbl 0591.65046
[5] H. Benson, ”On the convergence of two branch and bound algorithms for nonconvex programming problems,”Journal of Optimization Theory and Applications 36 (1982) 129–134. · Zbl 0453.65046
[6] C.G.E. Boender, A.H.G. Rinnooy Kan, L. Stougie and G.T. Timmer, ”A stochastic method for global optimization,”Mathematical Programming 22 (1982) 125–140. · Zbl 0525.90076
[7] C.G.E. Boender, ”The generalized multinomial distribution: A Bayesian analysis and applications,” Ph.D. Dissertation, Erasmus University (Rotterdam, 1984).
[8] J.G. Boon, J. Pintér and L. Somlyódy, ”A new stochastic approach for controlling point source river pollution,” in:Proceedings of the 3rd Scientific Assembly of the International Association for Hydrologic Sciences. IAHS Publications No. 180 (London, 1989) pp. 141–149.
[9] Y.M. Danilin and S.A. Piyavskii, ”On an algorithm for finding the absolute minimum,” in:Theory of Optimal Solutions (Institute of Cybernetics, Kiev, 1967) pp. 25–37.
[10] Y.M. Danilin, ”Estimation of the efficiency of an absolute minimum finding algorithm,”USSR Computational Mathematics and Mathematical Physics 11 (1971) 261–267. · Zbl 0255.65030
[11] L.P. Devroye, ”Progressive global random search of continuous functions,”Mathematical Programming 15 (1978) 330–342. · Zbl 0387.90083
[12] L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation, Vols. 1–2 (North-Holland, Amsterdam, 1975, 1978). · Zbl 0309.90052
[13] Y.G. Evtushenko, ”Numerical methods for finding global extrema (case of a non-uniform mesh),”USSR Computational Mathematics and Mathematical Physics 11 (1971) 38–54. · Zbl 0258.90045
[14] J.E. Falk and R.M. Soland, ”An algorithm for separable non-convex programming problems,”Management Science 15 (1969) 550–569. · Zbl 0172.43802
[15] V.V. Fedorov, ed.,Problems of Cybernetics. Models and Methods in Global Optimization (USSR Academy of Sciences, Moscow, 1985).
[16] V. Fujii, K. Ichida and M. Ozasa, ”Maximization of multivariable functions using interval analysis,” in: K.L.E. Nickel, ed.,Interval Mathematics 1985 (Springer, Berlin, 1986). · Zbl 0598.65046
[17] E. A. Galperin, ”Precision, complexity, and computational schemes of the cubic algorithm,”Journal of Optimization Theory and Applications 57 (1988) 223–238. · Zbl 0621.90070
[18] E.R. Hansen, ”Global optimization using interval analysis – the one-dimensional case,”Journal of Optimization Theory and Applications 29 (1980) 331–344. · Zbl 0388.65023
[19] E.R. Hansen, ”Global optimization using interval analysis – the multidimensional case,”Numerische Mathematik 34 (1980) 247–270. · Zbl 0442.65052
[20] P. Hansen, B. Jaumard and S.-H. Lu, ”An analytical approach to global optimization,”Mathematical Programming (Series B) 52 (1991) 227–254. · Zbl 0747.90091
[21] P. Hansen, B. Jaumard and S.-H. Lu, ”Global optimization of univariate Lipschitz functions: I. Survey and properties,”Mathematical Programming 55 (1992) 251–272. · Zbl 0825.90755
[22] E.M.T. Hendrix and J. Pintér, ”An application of Lipschitzian global optimization to product design,” to appear in:Journal of Global Optimization (1991). · Zbl 0752.90066
[23] K.L. Hoffman, ”A method for globally minimizing concave functions over convex sets,”Mathematical Programming 20 (1981) 22–32. · Zbl 0441.90096
[24] R. Horst, ”An algorithm for nonconvex programming problems,”Mathematical Programming 10 (1976) 312–321. · Zbl 0337.90062
[25] R. Horst, ”A note on the convergence of an algorithm for nonconvex programming problems,”Mathematical Programming 19 (1980) 237–238. · Zbl 0437.90069
[26] R. Horst, ”On the global minimization of concave functions – Introduction and survey,”Operations Research Spektrum 6 (1984) 195–205. · Zbl 0551.65043
[27] R. Horst, ”A general class of branch-and-bound methods in global optimization, with some new approaches for concave minimization,”Journal of Optimization Theory and Applications 51 (1986) 271–291. · Zbl 0581.90073
[28] R. Horst, ”Deterministic methods in constrained global optimization: Some recent advances and new fields of application,”Naval Research Logistics 37 (1990) 433–471. · Zbl 0709.90093
[29] R. Horst and H. Tuy, ”On the convergence of global methods in multiextremal optimization,”Journal of Optimization Theory and Applications 54 (1987) 253–271. · Zbl 0595.90079
[30] R. Horst and H. Tuy,Global Optimization – Deterministic Approaches (Springer, Berlin, 1990). · Zbl 0704.90057
[31] H.J. Kushner, ”A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise,”Transactions of ASME, Series D, Journal of Basic Engineering 86 (1964) 97–105.
[32] C.C. Meewella and D.Q. Mayne, ”An algorithm for global optimization of Lipschitz functions,”Journal of Optimization Theory and Applications 57 (1988) 307–323. · Zbl 0619.90065
[33] C.C. Meewella and D.Q. Mayne, ”Efficient domain partitioning algorithms for global optimization of rational and Lipschitzian functions,”Journal of Optimization Theory and Applications 61 (1989) 247–270. · Zbl 0644.90080
[34] R.H. Mladineo, ”An algorithm for finding the global maximum of a multimodal, multivariate function,”Mathematical Programming 34 (1986) 188–200. · Zbl 0598.90075
[35] J. Mockus, V. Tiesis and A. Žilinskas, ”The application of Bayesian methods for seeking the extremum,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation, Vol. 2 (North-Holland, Amsterdam, 1978) pp. 117–129. · Zbl 0394.90090
[36] P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications. Lecture Notes in Computer Science No. 268 (Springer, Berlin, 1987). · Zbl 0638.90064
[37] J. Pintér, ”A unified approach to globally convergent one-dimensional optimization algorithms,” Research Report IAMI 83-5, Institute of Applied Mathematics and Informatics CNR (Milan, 1983).
[38] J. Pintér, ”Convergence properties of stochastic optimization procedures,”Optimization 15 (1984) 405–427. · Zbl 0568.62076
[39] J. Pintér, ”Globally convergent methods forn-dimensional multiextremal optimization,”Optimization 17 (1986a) 187–202. · Zbl 0595.90071
[40] J. Pintér, ”Extended univariate algorithms forn-dimensional global optimization,”Computing 36 (1986b) 91–103. · Zbl 0572.65047
[41] J. Pintér, ”Global optimization on convex sets,”Operations Research Spektrum 8 (1986c) 197–202. · Zbl 0618.90085
[42] J. Pintér, ”Branch-and-bound algorithms for solving global optimization problems with Lipschitzian structure,”Optimization 19 (1988) 101–110. · Zbl 0645.90065
[43] J. Pintér, ”Solving nonlinear equation systems by global partition and search: Some experimental results,”Computing 43 (1990a) 309–323. · Zbl 0689.65031
[44] J. Pintér, ”Globally optimized calibration of environmental models,”Annals of Operations Research 25 (1990b) 211–222. · Zbl 0711.90088
[45] J. Pintér, ”Lipschitzian global optimization: Some prospective applications,” to appear in: C.A. Floudas and P.M. Pardalos, eds.,Recent Advances in Global Optimization (Princeton University Press, Princeton, NJ, 1991).
[46] J. Pintér and G. Pesti, ”Set partition by globally optimized cluster seed points,”European Journal of Operational Research 51 (1991) 127–135. · Zbl 0732.90050
[47] S.A. Piyavskii, ”An algorithm for finding the absolute minimum of a function,” in:Theory of Optimal Solutions (Institute of Cybernetics, Kiev, 1967) pp. 13–24.
[48] S.A. Piyavskii, ”An algorithm for finding the absolute extremum of a function,”USSR Computational Mathematics and Mathematical Physics 12 (1972) 57–67. · Zbl 0282.65052
[49] H. Ratschek, ”Inclusion functions and global optimization,”Mathematical Programming 33 (1985) 300–317. · Zbl 0579.90082
[50] H. Ratschek and J. Rokne,New Computer Methods for Global Optimization (Ellis Horwood, Chichester, 1988). · Zbl 0648.65049
[51] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. Part I: Clustering methods,”Mathematical Programming 39 (1987a) 27–56. · Zbl 0634.90066
[52] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. Part II: Multi-level methods,”Mathematical Programming 39 (1987b) 57–78. · Zbl 0634.90067
[53] J.B. Rosen, ”Minimization of a linearly constrained concave function by partition of the feasible domain,”Mathematics of Operations Research 8 (1983) 215–230. · Zbl 0526.90072
[54] F. Schoen, ”On a sequential search strategy in global optimization problems,”Calcolo 19 (1982) 321–334. · Zbl 0506.90074
[55] Z. Shen and Y. Zhu, ”An interval version of Shubert’s iterative method for the localization of the global maximum,”Computing 38 (1987) 275–280. · Zbl 0602.65040
[56] B.O. Shubert, ”A sequential method seeking the global maximum of a function,”SIAM Journal of Numerical Analysis 9 (1972) 379–388. · Zbl 0251.65052
[57] F.J. Solis and R. Wets, ”Minimization by random search techniques,”Mathematics of Operations Research 6 (1981) 19–30. · Zbl 0502.90070
[58] R.G. Strongin,Numerical Methods for Multiextremal Problems (Nauka, Moscow, 1978). · Zbl 0458.65062
[59] N.V. Thoai and H. Tuy, ”Convergent algorithms for minimizing a concave function,”Mathematics of Operations Research 5 (1980) 556–566. · Zbl 0472.90054
[60] A.A. Törn, ”A search clustering approach to global optimization,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation, Vol 2 (North-Holland, Amsterdam, 1978) pp. 49–62.
[61] A.A. Törn and A. Žilinskas,Global Optimization. Lecture Notes in Computer Science No. 350 (Springer, Berlin, 1989).
[62] G.R. Wood, ”Multidimensional bisection and global minimization,” Working Paper, University of Canterbury (New Zealand, 1985).
[63] A. Žilinskas, ”Two algorithms for one-dimensional multimodal minimization,”Optimization 12 (1981) 53–63. · Zbl 0467.90058
[64] A. Žilinskas, ”Axiomatic approach to statistical models and their use in multimodal optimization theory,”Mathematical Programming 22 (1982) 104–116. · Zbl 0481.90071
[65] A. Žilinskas,Global Optimization (Mokslas, Vilnius, 1986).
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.