Homogeneous algorithms of multiextremal optimization for time-consuming objective functions

Authors

  • S.M. Elsakov South Ural State University
  • V.I. Shiryaev South Ural State University

Keywords:

global optimization, multiextremal optimization, homogeneous algorithms, response surface models, models of objective functions

Abstract

A number of ways to accelerate homogeneous algorithms for global optimization are proposed. Theorems on the possibilities of acceleration without loss of convergence to the global minimum are proved. Models of objective functions are considered. It is proved that the use of these models ensures a convergence to the global minimum of the objective function. A model to determine the application field of the algorithm is constructed. Some numerical results of testing the proposed algorithm are discussed.

Author Biographies

S.M. Elsakov

V.I. Shiryaev

References

  1. Ананченко А.Г. Разработка алгоритмов и программных комплексов для глобальной оптимизации химико-технологических систем. Дисс. … канд. техн. наук. Санкт-Петербург, 2004.
  2. Антонов М.О., Елсаков С.М., Ширяев В.И. Нахождение оптимального расположения радиомаяков в разностно-дальномерной системе посадки летательного аппарата // Авиакосмическое приборостроение. 2005. N 11. 41-45.
  3. Гришагин В.А. Исследование одного класса численных методов решения задач многоэкстремальной оптимизации. Дисс. … канд. физ.-мат. наук. Горький, 1983.
  4. Гришагин В.А. Операционные характеристики некоторых алгоритмов глобального поиска // Проблемы случайного поиска. Рига: Зинатне, 1978. N 7. 198-206.
  5. Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Журн. вычисл. матем. и матем. физ. 1971. 11, N 6. 1390-1400.
  6. Елсаков С.М., Ширяев В.И. Однородные алгоритмы многоэкстремальной оптимизации // Журн. вычисл. матем. и матем. физ. 2010. 50, N 10. 1-14.
  7. Квасов Д.Е., Сергеев Я.Д. Многомерный алгоритм глобальной оптимизации на основе адаптивных диагональных кривых // Журн. вычисл. матем. и матем. физ. 2003. 43, N 1. 42-59.
  8. Пиявский С.А. Один алгоритм отыскания абсолютного экстремума функции // Журн. вычисл. матем. и матем. физ. 1972. 12, N 12. 57-67.
  9. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  10. Роженко А.И. Теория и алгоритмы вариационной сплайн-аппроксимации. Новосибирск: ИВМиМГ, 2005.
  11. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.
  12. Björkman M., Holmström K. Global optimization of costly nonconvex functions using radial basis functions // Optimization and Engineering. 2000. N 4. 373-397.
  13. Egorov I.N., Kretinin G.V., Leshchenko I.A. Robust design optimization strategy of IOSO technology // Proc. Fifth World Congress on Computational Mechanics. Vienna, Austria. 2002. 1-8.
  14. Elsakov S.M., Shiryaev V.I. Linear homogeneous algorithms of global optimization // Global Optimization: Theory, Methods &; Applications. Series Lecture Notes in Decision Science. Vol. 12. Hong Kong, London, Tokyo: Global-Link Publisher, 2009. 241-247.
  15. Finkel D.E. Global optimization with the direct algorithm. PhD thesis. Raleigh, NC, 2005.
  16. Floudas C.A. Deterministic global optimization: theory, methods and its applications. New York: Springer, 1999.
  17. Floudas C.A., Gounaris C.E. A review of recent advances in global optimization // J. of Global Optimization. 2009. N 1. 3-38.
  18. Gablonsky J.M., Kelley C.T. A locally-biased form of the direct algorithm // J. of Global Optimization. 2001. N 1. 27-37.
  19. Gaviano M., Kvasov D.E., Lera D., Sergeyev Ya.D. Generation of classes of test functions with known local minima // ACM Trans. Math. Soft. 2003. N 4. 469-480.
  20. Holmström K. An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization // J. of Global Optimization. 2008. N 3. 447-464.
  21. Holmström K., Göran A.O., Edvall M.M. User’s guide for TOMLAB 7 // (http://tomopt.com/docs/TOMLAB.pdf).
  22. Jones D.R. A taxonomy of global optimization methods based on response surfaces // J. of Global Optimization. 2001. N 4. 345-383.
  23. Jones D.R., Perttunen C.D., Stuckman B.E. Lipschitzian optimization without the Lipschitz constant // J. Optim. Theory Appl. 1993. N 1. 157-181.
  24. Jones D.R., Schonlau M., Welch W.J. Efficient global optimization of expensive black-box functions // J. of Global Optimization. 1998. N 4. 455-492.
  25. Pintér J.D. Nonlinear optimization with GAMS/LGO // J. of Global Optimization. 2007. N 1. 79-101.
  26. Sergeyev Y.D., Kvasov D.E. Global search based on efficient diagonal partitions and a set of Lipschitz constants // SIAM J. on Optimization. 2006. N 3. 910-937.
  27. Towards global optimization 2 / Eds. G.P. Szego, L.C.W. Dixon. New York : North-Holland Pub., 1978.
  28. Xiaojun W., Yu M., Xia W.Q. Implicit fitting and smoothing using radial basis functions with partition of unity // Proc. Ninth Int. Conf. on Computer Aided Design and Computer Graphics. Washington: IEEE Computer Society, 2005. 139-148.

Published

28-01-2011

How to Cite

Елсаков С., Ширяев В. Homogeneous Algorithms of Multiextremal Optimization for Time-Consuming Objective Functions // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2011. 12. 48-69

Issue

Section

Section 1. Numerical methods and applications