Аннотация.

Предлагается новый метод решения задач глобальной оптимизации на компактных множествах, описываемых непрерывными функциями гельдеровского класса, которые заданы алгоритмически. Метод основан на пакетных итерациях Монте-Карло для построения последовательностей «квази-глобальных» минимумов и их декрементов. Последняя используется для оценивания констант Гельдера минимизируемой функции. Исследованы вероятностные свойства указанных последовательностей, и доказана сходимость метода и экспоненциальная скорость сходимости с вероятностью 1. Получены оценки расстояния при конечном числе итераций до точного значения глобального минимума и его вероятности. Работоспособность метода подтверждены на многочисленных тестовых задачах.

Ключевые слова:

глобальная минимизация, каноническая форма задач глобальной оптимизации, преобразование  к  единичному неотрицательному кубу,  константы Гельдера, модуль  непрерывности, метод  Монте-Карло, пакетные итерации, вероятностная сходимость, последовательность «квази-глобальных» минимумов, последовательность декрементов, МНК-оценки.

Стр. 39-52.

B.S. Darkhovskii, A.Yu. Popkov, Yu.S. Popkov

"Method of Monte Carlo batch iteration to solving by global optimization problems."

This paper proposes a new solution method for global optimization problems involving Holder-functions defined on compact sets that are defined by algorithmically. The method is based on Monte Carlo batch iteration and constructing the sequences of “quasiglobal” minima and the sequence of their decrements. The latter serves for estimating the Holder constants of a goal function. We explore the probabilistic properties of the above sequences and demonstrate that this method possesses exponential convergence with the probability of 1 (almost sure). Under a finite number of iterations, we obtain the upper estimates for the distance between “quasiglobal” and exact solutions of the global minimization problem, as well as the lower estimates for the associated probability. And finally, a series of test problems illustrate the operability of the suggested technique.

Keywords: global optimization, canonical-form global optimization problems, transformation to unit nonnegative cube, Holder constants, module of continuity, Monte Carlo method, burst iterations, probabilistic convergence, the sequence of “quasiglobal” minima, the sequence of decrements, Monte Carlo estimates.

Полная версия статьи в формате pdf.

REFERENCES

1    Horst R., Pardalos P. M., and Thoai N. V. Introduction to Global Optimization. Kluwer Academic, 1996.
2    Strekalovskiy A. S.  Elementy  nevypukloy  optimizatsii. Novosibirsk: Nauka, 2003.
3    Rubinov A. M. Abstact Convexity and Global Optimization, Dordrecht: Kluwer, 2000.
4.   Strongin R. G., Sergeyev Ya. D. Global Optimization with Non-Convex  Constraints.  Sequential  and  Parallel  Algorithms. Dordrecht: Kluwer Academic Publishers, 2000.
5.   Sergeev Ya. D., Kvasov D. Ye. Diagonalnye metody globalnoy optimizatsii. M.: Fizmatlit, 2008. 351 s.
6.   Sergeev Y. D.,  Strongin R. G.,  Lera D.  Introduction  to Global Optimization Exploiting Space-Filling Curves. Springer Briefs in Optimization, 2013.
7.   Tikhonova M. V., Ryabov V. V., Spivak S. I., Gibaydullin I. M. Parallelnaya uslovnaya globalnaya optimizatsiya pri matematicheskom modelirovanii kinetiki khimicheskikh reaktsiy // Vychislitelnye metody i programmirovanie. 2013. T. 14. S. 262–268.
8.   Caflisch R. E. Monte Carlo and quasi-Monte Carlo methods // Acta Numerica. 1998. P. 1–49.
9.   Rubinstein R. Y., Kroese D. P. Simulation and the Monte Carlo Method. 2008, John Wiley & Sons.
10. Strongin R. G., Gergel V. P., Grishagin V. A., Barkalov K. A.  Parallelnye  vychisleniya  v  zadachakh  globalnoy optimizatsii. M.: izd. Moskovskogo universiteta, 2012. 276 s.
11. Zabinsky Z. B.,  Smith R. L.,  McDonald  F.,  Romeijn H. E., Kaufman D. E. Impruving Hit-and-Run for Global Optimization // Journal of Global Optimization. 1993. V. 3. P. 171–192.
12. Polyak B., Gryasina E. Hit-and-Run: New design technique for stabilization, robusness and optimization of linear systems. In: Proc. of the IFAC World Congress. 2008. P. 376–380.
13. Hastings W. K.  Mante  Carlo  sampling  methods  using Marcov chains and its applications // Biometrika. 1970. v. 57. P. 92–109.
14. Borovkov K. A. Ob odnom novom variante metoda Monte-Karlo  //  Teoriya  veroyatnostey  i  ee  primeneniya. 1991. T. 36. Vyp. 2. S. 342–346.
15. Rubinstein R. Y., Kroese D. P. The Cross-Entropy Methods. A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Mashine Learning. Springer, Information Science and Statistics, 2004. 300 p.
16. Zorin A. V.,   Fedotkin M. A.   Metody   Monte-Karlo dlya parallelnykh vychisleniy. M.: izd. Moskovskogo universiteta, 2013. 187 s.
17. Feller W. An Introduction to Probability Theory and  its Applications. V. 1, 2. London, New York: John Wiley & Sons, Inc., 1957.
18. Kolmogorov A. N.,    Fomin S. V.    Elementy    teorii funktsiy i funktsionalnogo analiza.
19. Fu M. C., Hu J., Marcus S. I. Model-Based Randomized Methods for Global Optimization. Proc. of the 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, July 24–28, 2006.
20. Virtual Library of Simulation Experiments: Test Functions and Datasets      [Elektronnyy resurs]. URL: http://www.sfu.ca/ ssurjano/optimization.html  (Data obrashcheniya: 31.07.2014)
21. Test functions for optimization [Elektronnyy resurs].
URL:  http://en.wikipedia.org/wiki/Test _functions_for_o ptimization (Data obrashcheniya: 31.07.2014).