Probability of Globality

Authors: Eva Eggeling, Dieter W. Fellner, Torsten Ullrich

Abstract:

The objective of global optimization is to find the globally best solution of a model. Nonlinear models are ubiquitous in many applications and their solution often requires a global search approach; i.e. for a function f from a set A ⊂ Rn to the real numbers, an element x0 ∈ A is sought-after, such that ∀ x ∈ A : f(x0) ≤ f(x). Depending on the field of application, the question whether a found solution x0 is not only a local minimum but a global one is very important. This article presents a probabilistic approach to determine the probability of a solution being a global minimum. The approach is independent of the used global search method and only requires a limited, convex parameter domain A as well as a Lipschitz continuous function f whose Lipschitz constant is not needed to be known.

Keywords: global optimization, probability theory, probability of globality

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062164

References:

[1] W. Boehm and H. Prautzsch, Numerical Methods, W. Boehm and H. Prautzsch, Eds. Vieweg, 1993.
[2] J. Nocedal and S. J. Wright, Numerical Optimization, J. Nocedal and S. J. Wright, Eds. Springer, 1999.
[3] U. Diwekar, Introduction to Applied Optimization, ser. Applied Optimization, U. Diwekar, Ed. Springer, 2003, vol. 80.
[4] J. C. Nash, Compact Numerical Methods for Computers: Linear Algebra and Function Minimisation, second edition ed., J. C. Nash, Ed. Adam Hilger, 1990.
[5] K. H¨ollig, J. H¨oner, and M. Pfeil, Numerische Methoden der Analysis, K. H¨ollig, J. H¨oner, and M. Pfeil, Eds. Mathematik-Online, 2010.
[6] P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization, P. E. Gill, W. Murray, and M. H. Wright, Eds. Academic Press, 1982.
[7] R. Fletcher, Practical Methods of Optimization, R. Fletcher, Ed. Wiley, 2000.
[8] J. D. Pinter, "Global Optimization: Software, Test Problems, and Applications," Handbook of Global Optimization, P.M. Pardalos and H.E. Romeijn (eds), vol. 2, pp. 515-569, 2002.
[9] A. Conn, N. I. M. Gould, and P. L. Toint, "Large-Scale Nonlinear Constrained Optimization: A Current Survey," Algorithms for continuous optimization: the state of the art, vol. 434, pp. 287-332, 1994.
[10] N. Gould, D. Orban, and P. Toint, "Numerical methods for large-scale nonlinear optimization," Acta Numerica, vol. 14, pp. 299-361, 2005.
[11] H.-G. Beyer and B. Sendhoff, "Robust optimization - A comprehensive survey," Computer Methods in Applied Mechanics and Engineering, vol. 196, pp. 3190-3218, 2007.
[12] M. Kieffer, M. C. Mark'ot, H. Schichl, and E. Walter, "Verified global optimization for estimating the parameters of nonlinear models," Modeling, Design, and Simulation of Systems with Uncertainties, vol. 1, pp. 129-151, 2011.
[13] R. Hammer, M. Hocks, U. Kulisch, and D. Ratz, C++ Toolbox for Verified Computing, R. Hammer, M. Hocks, U. Kulisch, and D. Ratz, Eds. Springer, 1997.
[14] M. C. Mark'ot and H. Schichl, "Comparison and Automated Selection of Local Optimization Solvers for Interval Global Optimization Methods," SIAM Journal on Optimization, vol. 21, pp. 1371-1391, 2011.
[15] N. Henze, Stochastik - Einf¨uhrung in die Wahrscheinlichkeitstheorie und Statistik (english: Stochastics - Introduction to probability calculus and statistics), N. Henze, Ed. Technische Universit¨at Karlsruhe, 1995.
[16] ÔÇöÔÇö, Stochastik f┬¿ur Einsteiger (english: Stochastics for Beginners), N. Henze, Ed. Vieweg, 1997.
[17] H. Bandemer and A. Bellmann, Statistische Versuchsplanung (english: Statistical Test Planning), H. Bandemer and A. Bellmann, Eds. Verlag H. Deutsch / BSB B. G. Teubner, 1979.
[18] E. Weisstein, MathWorld - A Wolfram Web Resource, E. Weisstein, Ed. Wolfram Research, 2009.
[19] M. P. McLaughlin, A Compendium of Common Probability Distributions, M. P. McLaughlin, Ed. Regress+, 1999.
[20] P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, "Geometric Approximations via Coresets," Combinatorial and Computational Geometry - MSRI Publications, vol. 52, pp. 1-30, 2005.
[21] G. Zachmann, "Rapid Collision Detection by Dynamically Aligned DOP-Trees," Proceedings of the Virtual Reality Annual International Symposium, vol. 1, pp. 90-97, 1998.
[22] J. D. Pinter, "Globally Optimized Spherical Point Arrangements: Model Variants and Illustrative Results," Annals of Operations Research, vol. 104, pp. 213-230, 2001.
[23] A. Katanforoush and M. Shahshahani, "Distributing Points on a Sphere," Experimental Mathematics, vol. 12, pp. 199-208, 2003.
[24] C. Schinko, T. Ullrich, and D. W. Fellner, "Simple and Efficient Normal Encoding with Error Bounds," Proceedings of Theory and Practice of Computer Graphics, vol. 29, pp. 63-66, 2011.
[25] R. Storn and K. Price, "Differential Evolution: A simple and efficient heuristic for global optimization over continuous spaces," Journal of Global Optimization, vol. 11, pp. 341-359, 1997.
[26] Z. Michalewicz and M. Schoenauer, "Evolutionary Algorithms for Constrained Parameter Optimization Problems," Evolutionary Computation, vol. 4, pp. 1-32, 1996.