The GO paradigm subsumes and significantly extends the traditional (local) optimization framework in which an essentially convex model structure and/or the knowledge of a "sufficiently good" initial solution estimate is postulated. As is well known, local optimization strategies could (and often will) fail to find the global solution in multimodal problems.

The continuous global optimization model can be stated as:

min f(x) x∈D:={x: 1≤x≤u, g(x)≤0}: here x∈Rⁿ the decision vector to optimize; l, u are finite component-wise vector bounds of x; f(x) is the continuous scalar objective function, and g(x) is the m-vector of continuous constraint functions.

This model formally covers not only linear and convex nonlinear programming but — as a highly special case — also the entire class of combinatorial optimization models. This fact immediately hints at the tremendous potential difficulty of the GO model class. The theoretical and numerical complexity of GO models could increase at a massively exponential rate as the number of decision variables and/or of constraints increases.

Due to its theoretical challenges and practical relevance, GO has become an important area of research. As of today, well over a hundred (English or other) textbooks and an increasing number of Web sites are devoted partly or completely to the subject. The most important GO model types and solution approaches (mostly exact, but also several prominent heuristic methods) are discussed in detail by the "Handbook of Global Optimization" volumes, edited by Horst and Pardalos (1995) and by Pardalos and Romeijn (2002). We also refer to the topical Webs site of Neumaier (2006), with numerous links to other useful information sources.

The early development in GO (approximately until the late 1980s) was primarily devoted to model classifications and structural studies, and to the analysis of algorithmic frameworks to handle such problems with proven deterministic or stochastic global convergence properties. Several of the most important, broadly applicable GO model classes are: concave minimization (over a convex or nonconvex set), general complementarity problems, general quadratic programming, DC programming (all model functions can be represented as the difference of two convex functions), Lipschitz optimization (all functions are Lipschitz-continuous) or the most general case defined by merely continuous functions. These model classes are not disjoint; in fact, their hierarchy can be easily established.

With respect to GO strategies, we mention here only a few prominent approaches. These include, in many variants, deterministically convergent branch-and-bound methods and stochastically convergent sequential search methods. The various heuristic approaches include adaptive neighborhood searches (simulated annealing and others), population-based (evolutionary and other) search procedures, as well as methods specifically targeted to handle GO models with computationally expensive functions.

The key theoretical developments have been followed more recently by GO software implementations. As of today, professionally developed and supported software products are available for compiler platforms (C and FORTRAN), spreadsheets, optimization modeling languages (to our knowledge, currently for AIMMS, GAMS, LINGO and MPL), and for integrated scientific-technical computing systems (such as Maple, Mathematica and MATLAB).

These model development and corresponding solver environments are aimed at meeting the needs of arguably different types of users. Key categories include educational users (instructors and students); research scientists, engineers, consultants and other practitioners (possibly, but not necessarily equipped with an in-depth optimization related background); optimization experts; software application developers; and other "power users." (The user categories listed are not necessarily disjoint.)

The pros and cons of the individual software products (in terms of their hardware and software demands, ease of usage, model prototyping options, detailed code development and maintenance features, optimization model verification and processing tools, availability of solver options and other auxiliary tools, program execution speed, overall level of system integration, quality of related documentation and support, customization options and communication with end users) make the corresponding modeling and solver approaches more or less attractive for various user groups. In addition to professional software developments, non-commercial software projects are also devoted to solving various GO problem types. Both Mittelmann (2006) and Neumaier (2006) provide more extensive information on non-commercial systems.

In recent decades, global optimization gradually has become an established discipline that is now taught worldwide at leading academic institutions. GO software is also increasingly applied in various contexts, including education, research, industrial and consulting practice. The currently available professional software implementations are routinely used to handle models with tens, hundreds and sometimes even thousands of variables and constraints. We recall the potential numerical difficulty of GO model instances; if one is interested in a guaranteed high-quality solution, then the necessary runtime could become minutes, hours, days or more, even on today's high-performance computers. Although one can expect further significant speed-up due to both further algorithm and software development and to progress in hardware/software technology, the theoretically exponential "curse of dimensionality" associated with the subject of GO will always remain.

In the most general terms, global optimization technology is well-suited to analyze and solve complex nonlinear models in applied mathematics and the natural sciences; advanced engineering (acoustic, aerospace, chemical, control, electrical, environmental, process, telecommunications); biotechnology, medical and pharmaceutical studies; econometrics and financial modeling; and other areas. For GO application examples, case studies and further perspectives, see e.g. Corliss and Kearfott (1999); Edgar, Himmelblau and Lasdon (2001); Floudas et al. (1999); Gao, Ogden and Stavroulakis (2001); Grossmann (1996); Neumaier (2006); Nowak (2005); Papalambros and Wilde (2000); Pardalos, Shalloway and Xue (1996); Pintér (1996, 2002, 2006a and b); Schittkowski (2002); Tawarmalani and Sahinidis (2002); Zabinsky (2003).



János D. Pintér (jdpinter@hfx.eastlink.ca) is president of Pintér Consulting Services, Inc. (www.pinterconsulting.com) based in Halifax, Nova Scotia, Canada.

References

1. Corliss, G.F. and Kearfott, R.B., 1999, "Rigorous global search: industrial applications," in Csendes, T., ed., "Developments in Reliable Computing," pp. 1-16, Kluwer Academic Publishers, Dordrecht.
2. Edgar, T.F., Himmelblau, D.M., and Lasdon, L.S., 2001, "Optimization of Chemical Processes (2nd Edition)", McGraw-Hill, New York.
3. Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gumus, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., and Schweiger, C.A., 1999, "Handbook of Test Problems in Local and Global Optimization," Kluwer Academic Publishers, Dordrecht.
4. Gao, D.Y., Ogden, R.W. and Stavroulakis, G.E., eds., 2001, "Nonsmooth/Nonconvex Mechanics: Modeling, Analysis and Numerical Methods," Kluwer Academic Publishers, Dordrecht.
5. Grossmann, I.E., ed., 1996, "Global Optimization in Engineering Design," Kluwer Academic Publishers, Dordrecht.
6. Horst, R. and Pardalos, P.M., eds., 1995, "Handbook of Global Optimization, Vol.1," Kluwer Academic Publishers, Dordrecht.
7. Mittelmann, H.D., 2006, "Decision Tree for Optimization Software," plato.la.asu.edu/guide.html.
8. Neumaier, A., 2006, "Global Optimization," www.mat.univie.ac.at/~neum /glopt.html.
9. Nowak, I., 2005, "Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming," Birkhäuser, Basel.
10. Papalambros, P.Y. and Wilde, D.J., 2000, "Principles of Optimal Design," Cambridge University Press, Cambridge, U.K.
11. Pardalos, P.M. and Romeijn, H.E., eds., 2002, "Handbook of Global Optimization, Vol.2," Kluwer Academic Publishers, Dordrecht.
12. Pardalos, P.M., Shalloway, D. and Xue, G., eds, 1996, "Global Minimization of Nonconvex Energy Functions: Molecular Conformation and Protein Folding," DIMACS Series, Vol. 23, American Mathematical Society, Providence, R.I.
13. Pintér, J.D., 1996, "Global Optimization in Action," Kluwer Academic Publishers, Dordrecht.
14. Pintér, J.D., 2002, "Global Optimization: Software, Test Problems and Applications," in Pardalos and Romeijn, eds., "Handbook of Global Optimization, Vol.2," pp. 515-569.
15. Pintér, J.D., ed., 2006a, "Global Optimization: Scientific and Engineering Case Studies," Springer, New York.
16. Pintér, J.D., 2006b, "Global Optimization with Maple: An Introduction with Illustrative Examples," electronic book published and distributed by Pintér Consulting Services Inc., Halifax, Nova Scotia, Canada, and Maplesoft, a division of Waterloo Maple Inc., Waterloo, Ontario, Canada.
17. Schittkowski, K., 2002, "Numerical Data Fitting in Dynamical Systems," Kluwer Academic Publishers, Dordrecht.
18. Tawarmalani, M. and Sahinidis, N.V., 2002, "Convexification and Global Optimization in Continuous and Mixed-integer Nonlinear Programming," Kluwer Academic Publishers, Dordrecht.
19. Zabinsky, Z.B., 2003, "Stochastic Adaptive Search for Global Optimization," Kluwer Academic Publishers, Dordrecht.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2007 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com


Web Site © Copyright 2007 by Lionheart Publishing, Inc. All rights reserved.