Convergence qualification of adaptive partition algorithms in global optimization | Mathematical Programming Skip to main content
Springer Nature Link
Log in

Convergence qualification of adaptive partition algorithms in global optimization

  • Published:
Mathematical Programming Submit manuscript

Abstract

Following the presentation of a general partition algorithm scheme for seeking the globally best solution in multiextremal optimization problems, necessary and sufficient convergence conditions are formulated, in terms of respectively implied or postulated properties of the partition operator. The convergence results obtained are pertinent to a number of deterministic algorithms in global optimization, permitting their diverse modifications and generalizations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • F. Archetti and B. Betró, “A probabilistic algorithm for global optimization,”Calcolo 16 (1979) 335–343.

    Google Scholar 

  • F. Archetti and B. Betró, “Stochastic models and optimization,”Bolletino della Unione Matematica Italiana A (5) 17 (1980) 295–301.

    Google Scholar 

  • P. Basso, “Iterative methods for the localization of the global maximum,”SIAM Journal of Numerical Analysis 19 (1982) 781–792.

    Google Scholar 

  • P. Basso, “Optimal search for the global maximum of a function with bounded seminorm,”SIAM Journal of Numerical Analysis 22 (1985) 888–903.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • C.G.E. Boender, “The generalized multinomial distribution: A Bayesian analysis and applications,” Ph.D. Dissertation, Erasmus University (Rotterdam, 1984).

    Google Scholar 

  • 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.

  • 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.

    Google Scholar 

  • Y.M. Danilin, “Estimation of the efficiency of an absolute minimum finding algorithm,”USSR Computational Mathematics and Mathematical Physics 11 (1971) 261–267.

    Google Scholar 

  • L.P. Devroye, “Progressive global random search of continuous functions,”Mathematical Programming 15 (1978) 330–342.

    Google Scholar 

  • L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation, Vols. 1–2 (North-Holland, Amsterdam, 1975, 1978).

    Google Scholar 

  • 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.

    Google Scholar 

  • J.E. Falk and R.M. Soland, “An algorithm for separable non-convex programming problems,”Management Science 15 (1969) 550–569.

    Google Scholar 

  • V.V. Fedorov, ed.,Problems of Cybernetics. Models and Methods in Global Optimization (USSR Academy of Sciences, Moscow, 1985).

    Google Scholar 

  • 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).

    Google Scholar 

  • E. A. Galperin, “Precision, complexity, and computational schemes of the cubic algorithm,”Journal of Optimization Theory and Applications 57 (1988) 223–238.

    Google Scholar 

  • E.R. Hansen, “Global optimization using interval analysis — the one-dimensional case,”Journal of Optimization Theory and Applications 29 (1980) 331–344.

    Google Scholar 

  • E.R. Hansen, “Global optimization using interval analysis — the multidimensional case,”Numerische Mathematik 34 (1980) 247–270.

    Google Scholar 

  • P. Hansen, B. Jaumard and S.-H. Lu, “An analytical approach to global optimization,”Mathematical Programming (Series B) 52 (1991) 227–254.

    Google Scholar 

  • P. Hansen, B. Jaumard and S.-H. Lu, “Global optimization of univariate Lipschitz functions: I. Survey and properties,”Mathematical Programming 55 (1992) 251–272.

    Google Scholar 

  • 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).

  • K.L. Hoffman, “A method for globally minimizing concave functions over convex sets,”Mathematical Programming 20 (1981) 22–32.

    Google Scholar 

  • R. Horst, “An algorithm for nonconvex programming problems,”Mathematical Programming 10 (1976) 312–321.

    Google Scholar 

  • R. Horst, “A note on the convergence of an algorithm for nonconvex programming problems,”Mathematical Programming 19 (1980) 237–238.

    Google Scholar 

  • R. Horst, “On the global minimization of concave functions — Introduction and survey,”Operations Research Spektrum 6 (1984) 195–205.

    Google Scholar 

  • 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.

    Google Scholar 

  • R. Horst, “Deterministic methods in constrained global optimization: Some recent advances and new fields of application,”Naval Research Logistics 37 (1990) 433–471.

    Google Scholar 

  • R. Horst and H. Tuy, “On the convergence of global methods in multiextremal optimization,”Journal of Optimization Theory and Applications 54 (1987) 253–271.

    Google Scholar 

  • R. Horst and H. Tuy,Global Optimization — Deterministic Approaches (Springer, Berlin, 1990).

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • R.H. Mladineo, “An algorithm for finding the global maximum of a multimodal, multivariate function,”Mathematical Programming 34 (1986) 188–200.

    Google Scholar 

  • 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.

    Google Scholar 

  • P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications. Lecture Notes in Computer Science No. 268 (Springer, Berlin, 1987).

    Google Scholar 

  • 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).

    Google Scholar 

  • J. Pintér, “Convergence properties of stochastic optimization procedures,”Optimization 15 (1984) 405–427.

    Google Scholar 

  • J. Pintér, “Globally convergent methods forn-dimensional multiextremal optimization,”Optimization 17 (1986a) 187–202.

    Google Scholar 

  • J. Pintér, “Extended univariate algorithms forn-dimensional global optimization,”Computing 36 (1986b) 91–103.

    Google Scholar 

  • J. Pintér, “Global optimization on convex sets,”Operations Research Spektrum 8 (1986c) 197–202.

    Google Scholar 

  • J. Pintér, “Branch-and-bound algorithms for solving global optimization problems with Lipschitzian structure,”Optimization 19 (1988) 101–110.

    Google Scholar 

  • J. Pintér, “Solving nonlinear equation systems by global partition and search: Some experimental results,”Computing 43 (1990a) 309–323.

    Google Scholar 

  • J. Pintér, “Globally optimized calibration of environmental models,”Annals of Operations Research 25 (1990b) 211–222.

    Google Scholar 

  • 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).

    Google Scholar 

  • J. Pintér and G. Pesti, “Set partition by globally optimized cluster seed points,”European Journal of Operational Research 51 (1991) 127–135.

    Google Scholar 

  • 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.

    Google Scholar 

  • S.A. Piyavskii, “An algorithm for finding the absolute extremum of a function,”USSR Computational Mathematics and Mathematical Physics 12 (1972) 57–67.

    Google Scholar 

  • H. Ratschek, “Inclusion functions and global optimization,”Mathematical Programming 33 (1985) 300–317.

    Google Scholar 

  • H. Ratschek and J. Rokne,New Computer Methods for Global Optimization (Ellis Horwood, Chichester, 1988).

    Google Scholar 

  • A.H.G. Rinnooy Kan and G.T. Timmer, “Stochastic global optimization methods. Part I: Clustering methods,”Mathematical Programming 39 (1987a) 27–56.

    Google Scholar 

  • A.H.G. Rinnooy Kan and G.T. Timmer, “Stochastic global optimization methods. Part II: Multi-level methods,”Mathematical Programming 39 (1987b) 57–78.

    Google Scholar 

  • J.B. Rosen, “Minimization of a linearly constrained concave function by partition of the feasible domain,”Mathematics of Operations Research 8 (1983) 215–230.

    Google Scholar 

  • F. Schoen, “On a sequential search strategy in global optimization problems,”Calcolo 19 (1982) 321–334.

    Google Scholar 

  • 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.

    Google Scholar 

  • B.O. Shubert, “A sequential method seeking the global maximum of a function,”SIAM Journal of Numerical Analysis 9 (1972) 379–388.

    Google Scholar 

  • F.J. Solis and R. Wets, “Minimization by random search techniques,”Mathematics of Operations Research 6 (1981) 19–30.

    Google Scholar 

  • R.G. Strongin,Numerical Methods for Multiextremal Problems (Nauka, Moscow, 1978).

    Google Scholar 

  • N.V. Thoai and H. Tuy, “Convergent algorithms for minimizing a concave function,”Mathematics of Operations Research 5 (1980) 556–566.

    Google Scholar 

  • 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.

    Google Scholar 

  • A.A. Törn and A. Žilinskas,Global Optimization. Lecture Notes in Computer Science No. 350 (Springer, Berlin, 1989).

    Google Scholar 

  • G.R. Wood, “Multidimensional bisection and global minimization,” Working Paper, University of Canterbury (New Zealand, 1985).

    Google Scholar 

  • A. Žilinskas, “Two algorithms for one-dimensional multimodal minimization,”Optimization 12 (1981) 53–63.

    Google Scholar 

  • A. Žilinskas, “Axiomatic approach to statistical models and their use in multimodal optimization theory,”Mathematical Programming 22 (1982) 104–116.

    Google Scholar 

  • A. Žilinskas,Global Optimization (Mokslas, Vilnius, 1986).

    Google Scholar 

Download references

Author information

Author notes

  1. János Pintér

    Present address: School of Business Administration and School for Resource and Environmental Studies, Dalhousie University, 1312 Robie Street, B3H 3E2, Halifax, NS, Canada

Authors and Affiliations

  1. Water Resources Research Centre, Budapest, Hungary

    János Pintér

Authors
  1. János Pintér
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pintér, J. Convergence qualification of adaptive partition algorithms in global optimization. Mathematical Programming 56, 343–360 (1992). https://doi.org/10.1007/BF01580907

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01580907

Key words

Search

Navigation