Abstract
The traditional numerical analysis considers optimization algorithms which guarantee some accuracy for all functions to be optimized. This includes the exact algorithms. Limiting the maximal error requires a computational effort that in many cases increases exponentially with the size of the problem (Horst and Pardalos, 1995, Handbook of Global Optimization, Kluwer). That limits practical applications of the worst case analysis. An alternative is the average case analysis where the average error is made as small as possible (Calvin and Glynn, 1997, J. Appl. Prob., 32: 157). The average is taken over a set of functions to be optimized. The average case analysis is called the Bayesian Approach (BA) (Diaconis, 1988, Statistical Decision Theory and Related Topics, Springer; Mockus and Mockus, 1987, Theory of Optimal Decisions, Nauk, Lithuania). Application of BA to optimization of heuristics is called the Bayesian Heuristic Approach (BHA) (Mockus, 2000, A Set of Examples of Global and Discrete Optimization, Kluwer). In this paper a short presentation of the basic ideas of BHA (described in detail in Mockus (1989), Bayesian Approach to Global Optimization, Kluwer and Mockus (2000), A Set of Examples of Global and Discrete Optimization, Kluwer) is given using the knapsack problem as an example. The application potential is illustrated by the school scheduling example. In addition the new heuristic algorithm for solving a bimatrix game problem is investigated. The results ae applied while solving real life optimization problems and also as examples for distance graduate level studies of the theory of games and markets in the Internet environment.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andradottir, S. (1996), A Global Search Method for Discrete Stochastic Optimization. SIAM Journal Optimization, 6: 513–530.
Calvin, J. and Glynn, P. (1997), Average Case Behavior of Random Search for the Maximum. J. Apply. Prob., 32: 157–163.
DeGroot, M. (1970), Optimal Statistical Decisions. McGraw-Hill, New York.
Diaconis, P. (1988), Bayesian numerical analysis. In: Statistical Decision Theory and Related Topics, pp. 163–175. Springer, Berlin.
Fine, T. (1983), Theories of Probability. Academic Press, New York.
Floudas, C., Pardalos, P., Adjiman, C., Esposito, W., Z.H. Gu, u., Harding, S., Klepeis, J., Meyer, C. and Schweiger, C. (1999), Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, Dordrecht-Boston-London.
Forgo, F., Szep, J., and Szidarovszky, F. (1999), Introduction to the Theory of Games. Kluwer Academic Publishers, Dordrecht.
Glover, F. (1994), Tabu search: improved solution alternatives. In: Mathematical Programming. State of the Art 1994, pp. 64–92. University of Michigan.
Goldberg, D.E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
Horst, R. and Pardalo, P. (1995), Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht-Boston-London.
Kushner, H. (1964), A new method for locating the maximum point of an arbitrary multi-peak curve in the presence of noise. J. of Basic Engineering, 86: 97–100.
Lindley, D. (1965), Introduction to Probability and Statistics from a Bayesian Viewpoint. Cambridge University Press, London.
Mavridou, T., Pardalos, P., Pitsoulis, L. and Resende, M. (1998), A GRASP for the biquadratic assignment problem. European Journal of Operatons Research, 105: 613–621.
Mockus, J. (1989), Bayesian Approach to Global Optimization. Kluwer Academic Publishers, Dordrecht-London-Boston.
Mockus, J. (2000), A Set of Examples of Global and Discrete Optimization: Application of Bayesian Heuristic Approach. Kluwer Academic Publishers, Dordrecht.
Mockus, J. and Mockus, L. (1987), Bayesian approach to global optimization and applications. In Theory of Optimal Decision, volume 12, pp. 57–70. Institute of Mathematics and Cybernetics, Akademia Nauk Lithuania SSR, Vilnius, Lithuania (in Russian).
Mockus, J., Eddy, W., Mockus, A., Mockus, L. and Reklaitis, G. (1997), Bayesian Heuristic Approach to Discrete and Global Optimization. Kluwer Academic Publishers, Dordrecht-London-Boston.
Nash, J. (1950), Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA, 36: 48–49.
Owen, G. (1968), Game Theory. W.B. Saunders, Philadelphia, PA.
Saltenis, V. (1971), On a method of multi-extremal optimization. Automatics and Computers (Automatika i Vychislitelnayya Tekchnika), (3): 33–38 (in Russian).
Savage, L. (1954), The Foundation of Statistics. John Wiley, New York.
Torn, A. and Zilinskas, A. (1989), Global Optimization. Springer, Berlin.
Zilinskas, A. (1986), Global Optimization:Axiomatic of Statistical Models, Algorithms and their Applications. Mokslas, Vilnius, Lithuania (in Russian).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mockus, J. Bayesian heuristic approach to global optimization and examples. Journal of Global Optimization 22, 191–203 (2002). https://doi.org/10.1023/A:1013815314823
Issue Date:
DOI: https://doi.org/10.1023/A:1013815314823