Skip to main content
SpringerLink
Log in

An analytical approach to global optimization

  • Published:
Mathematical Programming Submit manuscript

Abstract

Global optimization problems with a few variables and constraints arise in numerous applications but are seldom solved exactly. Most often only a local optimum is found, or if a global optimum is detected no proof is provided that it is one. We study here the extent to which such global optimization problems can be solved exactly using analytical methods. To this effect, we propose a series of tests, similar to those of combinatorial optimization, organized in a branch-and-bound framework. The first complete solution of two difficult test problems illustrates the efficiency of the resulting algorithm. Computational experience with the programbagop, which uses the computer algebra systemmacsyma, is reported on. Many test problems from the compendiums of Hock and Schittkowski and others sources have been solved.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. A.M. Agogino and A.S. Almgren, “Techniques for integrating qualitative reasoning and symbolic computation in engineering optimization,”Engineering Optimization 12 (1987) 117–135.

    Google Scholar 

  2. F. Archetti and F. Schoen, “A survey on the global optimization problem: general theory and computational approaches,”Annals of Operations Research 1 (1984) 87–110.

    Google Scholar 

  3. B. Aspvall, M.F. Plass and R.E. Tarjan, “A linear-time algorithm for testing the truth of certain quantified Boolean formulas,”Information Processing Letters 8 (1979) 121–123.

    Google Scholar 

  4. M. Avriel and A.C. Williams, “An extension of geometric programming with applications in engineering optimization,”Journal of Engineering Mathematics 5 (1971) 187–194.

    Google Scholar 

  5. E.M.L. Beale and J.J.H. Forrest, “Global optimization using special ordered sets,”Mathematical Programming 10 (1976) 52–69.

    Google Scholar 

  6. E.M.L. Beale and J.J.H. Forrest, “Global optimization as an extension of integer programming,” in: [16] pp. 131–150.

  7. D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982).

    Google Scholar 

  8. A.H. Boas, “Optimization via linear and dynamic programming,”Chemical Engineering 70 (1963) 85–88.

    Google Scholar 

  9. Y. Cherruault and A. Guillez, “Une méthode pour la recherche du minimum global d'une fonctionnelle,”Comptes-Rendus de l'Académie des Sciences de Paris 296 (1983) 175–179.

    Google Scholar 

  10. S.H. Chew and Q. Zheng,Integral Global Optimization. Lecture Notes in Economics and Mathematical Systems No. 298 (Springer, New York, 1988).

    Google Scholar 

  11. F. Cole, “Some algorithms for geometric programming,” Ph.D. Thesis, Department of Applied Economics, University of Leuven (Leuven, Belgium, 1985).

    Google Scholar 

  12. A.R. Colville, “A comparative study of nonlinear programming codes,” IBM Scientific Report 320-2940 (New York, 1968).

  13. A. Corana, M. Marchesi, C. Martini and S. Ridella, “Minimizing multimodal functions of continuous variables with the ‘Simulated Annealing’ algorithm,”ACM Transactions on Mathematical Software 13 (1987) 262–280.

    Google Scholar 

  14. H. Cornelius and R. Lohner, “Computing the range of real functions with accuracy higher than second order,”Computing 33 (1984) 331–347.

    Google Scholar 

  15. R.S. Dembo, “A set of geometric programming test problems and their solutions,”Mathematical Programming 10(2) (1976) 192–213.

    Google Scholar 

  16. L.C.W. Dixon and G.P. Szëgo, eds.,Towards Global Optimization, Vol. 2 (North-Holland, Amsterdam, 1977).

    Google Scholar 

  17. A. Groch, L.M. Vidigal and S.W. Director, “A new global optimization method for electronic circuit design,”IEEE Transactions on Circuits and Systems CAS-32 (1985) 160–170.

    Google Scholar 

  18. Y. Fujii, K. Ichida and M. Ozasa, “Maximization of multivariate functions using interval analysis,” in: K. Nickel, ed.,Interval Mathematics. Lecture Notes in Computer Science No. 212 (Springer, New York, 1985) pp. 37–56.

    Google Scholar 

  19. C.B. Garcia and W.I. Zangwill,Pathways to Solutions, Fixed Points, and Equilibria. Series in Computational Mathematics (Prentice-Hall, Englewood Cliffs, NJ, 1981).

    Google Scholar 

  20. C.R. Hammond and G.E. Johnson, “A general approach to constrained optimal design based on symbolic mathematics,” in: S.S. Rao, ed.,Advances in Design Automation, Vol. 1: Design Methods, Computer Graphics and Expert Systems (ASME, New York, 1987) pp. 31–40.

    Google Scholar 

  21. E. Hansen, “Global optimization using interval analysis—the multi dimensional case,”Numerische Mathematik 34 (1980) 247–270.

    Google Scholar 

  22. E. Hansen and S. Sengupta, “Global constrained optimization using interval analysis,” in: K.L.E. Nickel, ed.,Interval Mathematics 1980 (Academic Press, New York, 1980) pp. 25–47.

    Google Scholar 

  23. P. Hansen, “Programmes mathématiques en variables 0–1,” Thèse d'agrégation, Université libre de Bruxelles (Bruxelles, 1974).

    Google Scholar 

  24. P. Hansen, “Les procédures d'optimisation et d'exploration par séparation et évaluation,” in: B. Roy, ed.,Combinatorial Programming (Reidel, Dordrecht, 1975) pp. 19–65.

    Google Scholar 

  25. P. Hansen, B. Jaumard and S.H. Lu, “Some further results on monotonicity analysis in globally optimal design,”ASME, Journal of Mechanisms, Transmissions, and Automation in Design 111 (1989) 345–352.

    Google Scholar 

  26. P. Hansen, B. Jaumard and S.H. Lu, “A framework for algorithms in globally optimal design,”ASME, Journal of Mechanisms, Transmissions, and Automation in Design 111 (1989) 353–360.

    Google Scholar 

  27. P. Hansen, B. Jaumard and M. Minoux, “A linear expected-time algorithm for deriving all logical conclusions implied by a set of Boolean inequalities,”Mathematical Programming 34 (1986) 223–231.

    Google Scholar 

  28. D.M. Himmelblau,Applied Nonlinear Programming (McGraw-Hill, New York, 1972).

    Google Scholar 

  29. W. Hock and K. Schittkowski,Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems No. 18 (Springer, Heidelberg, 1981).

    Google Scholar 

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

  31. R. Horst, “Deterministic global optimization with partition sets whose feasibility is not known: application to concave minimization, reverse convex constraints, d.c. programming, and Lipschitzian optimization,”Journal of Optimization Theory and Applications 58 (1988) 11–37.

    Google Scholar 

  32. R. Horst and N.V. Thoai, “Modification, implementation and comparison of three algorithms for globally solving linearly constrained concave minimization problems,”Computing 42 (1989) 271–289.

    Google Scholar 

  33. R. Horst, N.V. Thoai and H.P. Benson, “Concave minimization via conical partitions and polyhedral outer approximation,”Mathematical Programming 50 (1991) 259–274.

    Google Scholar 

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

  35. R. Horst, J. de Vries and N.V. Thoai, “On finding new vertices and redundant constraints in cutting-plane algorithms for global optimization,”Operations Research Letters 7 (1988) 85–90.

    Google Scholar 

  36. R.C. Johnson,Optimum Design of Mechanical Elements (Wiley, New York, 1980, 2nd ed.).

    Google Scholar 

  37. B. Kalantari and J.B. Rosen, “An algorithm for global minimization of linearly constrained concave quadratic functions,”Mathematics of Operations Research 12 (1987) 544–561.

    Google Scholar 

  38. A.V. Levy and A. Montalvo, “The tunneling algorithm for the global minimization of functions,”SIAM Journal on Scientific and Statistical Computing 6 (1985) 15–29.

    Google Scholar 

  39. R. Luus and T.H.I. Jaakola, “Optimization by direct search and systematic reduction of the size of search region,”AIChE Journal 19 (1973) 760–766.

    Google Scholar 

  40. G.P. McCormick,Nonlinear Programming (Wiley, New York, 1983).

    Google Scholar 

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

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

    Google Scholar 

  43. R.E. Moore,Interval Analysis (Prentice-Hall, Englewood Cliffs, NJ, 1966).

    Google Scholar 

  44. R.E. Moore,Methods and Applications of Interval Analysis. SIAM Studies in Applied Mathematics (SIAM, Philadelphia, PA, 1979).

    Google Scholar 

  45. R.E. Moore and H. Ratschek, “Inclusion functions and global optimization II,”Mathematical Programming 41 (1988) 341–356.

    Google Scholar 

  46. A. Morgan,Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems (Prentice-Hall, Englewood Cliffs, NJ, 1987).

    Google Scholar 

  47. K.G. Murty and S.N. Kabadi, “Some NP-complete problems in quadratic and nonlinear programming,”Mathematical Programming 39 (1987) 117–130.

    Google Scholar 

  48. P.Y. Papalambros and H.L. Li, “Notes on the operational utility of monotonicity in optimization,”ASME Journal of Mechanisms, Transmissions, and Automation in Design 105 (1983) 174–180.

    Google Scholar 

  49. P.Y. Papalambros and D.J. Wilde,Principles of Optimal Design: Modeling and Computation (Cambridge University Press, Cambridge, 1988).

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  52. S.A. Piyavskii, “An algorithm for finding the absolute extremum of a function,”USSR Computational Mathematics and Mathematical Physics 12 (1972) 57–67. [Zh. vychisl Mat. mat. Fiz. 12 (1972) 888–896.]

    Google Scholar 

  53. W.V. Quine, “A Way to Simplify Truth Functions,”American Mathematical Monthly 62 (1955) 627–631.

    Google Scholar 

  54. G.S. Rao, R.S. Tyagi and R.K. Mishra, “Calculation of the minimum energy conformation of biomolecules using a global optimization technique. I. Methodology and application to a model molecular fragment (normal pentane),”Journal of Theoretical Biology 90 (1981) 377–389.

    Google Scholar 

  55. H. Ratschek and J. Rokne,Computer Methods for the Range of Functions. Ellis Horwood Series in Mathematics and its Applications (Halsted, New York, 1984).

    Google Scholar 

  56. H. Ratschek and J. Rokne,New Computer Methods for Global Optimization. Ellis Horwood Series in Mathematics and its Applications (Halsted, New York, 1988).

    Google Scholar 

  57. A.H.G. Rinnooy Kan and G.T. Timmer, “A stochastic approach to global optimization,” in: P.T. Boggs, ed.,Numerical Optimization 84 (SIAM, Philadelphia, PA, 1985) pp. 245–262.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  60. R.Y. Rubinstein,Monte Carlo Optimization, Simulation and Sensitivity of Queuing Networks (Wiley, New York, 1986).

    Google Scholar 

  61. K. Schittkowski,More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems No. 282 (Springer, Heidelberg, 1987).

    Google Scholar 

  62. S. Sengupta, “Global nonlinear constrained optimization,” Ph.D. Thesis, Department of Pure and Applied Mathematics, Washington State University (Pullman, WA, 1981).

    Google Scholar 

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

    Google Scholar 

  64. D.R. Stoutemyer, “Analytical optimization using computer algebraic manipulation,”ACM Transactions on Mathematical Software 1 (1975) 147–164.

    Google Scholar 

  65. D.R. Stoutemyer, “Automatic categorization of optimization problems: an application of computer symbolic mathematics,”Operations Research 26 (1978) 773–788.

    Google Scholar 

  66. P.T. Thach and H. Tuy, “Global optimization under Lipschitzian constraints,”Japan Journal of Applied Mathematics 4 (1987) 205–217.

    Google Scholar 

  67. J. Tomlin, “A suggested extension of special ordered sets to non-separable non-convex programming problems,” in P. Hansen, ed.,Studies on Graphs and Discrete Programming, Annals of Discrete Mathematics 11 (1981) 359–370.

    Google Scholar 

  68. A. Törn and A. Zilinkas,Global Optimization. Lecture Notes in Computer Science No. 350 (Springer, New York, 1989).

    Google Scholar 

  69. G.W. Walster, E.R. Hansen and S. Sengupta, “Test results for a global optimization algorithm,” in: P.T. Boggs, R. Byrd and R. Schnabel, eds.,Numerical Optimization 84 (SIAM, Philadelphia, PA, 1985) pp. 272–287.

    Google Scholar 

  70. D. Wilde, “Monotonicity and dominance in optimal hydraulic cylinder design,”ASME Journal of Engineering for Industry 97 (1975) 1390–1394.

    Google Scholar 

  71. R.S. Womersley, “Censored discrete linear ℓ1 approximation,”SIAM Journal on Scientific and Statistical Computing 7 (1986) 105–122.

    Google Scholar 

  72. P.B. Zwart, “Computational aspects on the use of cutting-planes in global optimization,”Proceedings of the 1971 annual conference of the ACM (1971) 457–465.

Download references

Author information

Authors and Affiliations

  1. RUTCOR, Rutgers University, 08903, New Brunswick, NJ, USA

    Pierre Hansen & Shi-Hui Lu

  2. GERAD and École Polytechnique de Montréal, H3C 3A7, Montréal, Que., Canada

    Brigitte Jaumard

Authors
  1. Pierre Hansen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Brigitte Jaumard
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shi-Hui Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The research of the first and the third authors has been supported by AFOSR grants #0271 and #0066 to Rutgers University. Research of the second author has been supported by NSERC grant #GP0036426 and FCAR grants #89EQ4144 and #90NC0305.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hansen, P., Jaumard, B. & Lu, SH. An analytical approach to global optimization. Mathematical Programming 52, 227–254 (1991). https://doi.org/10.1007/BF01582889

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation