AN ALGORITHM FOR FINDING A ROOT OF A NONNEGATIVE MULTIMODAL FUNCTION

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

A new algorithm for finding the global minimizer of a one-dimensional multimodal function satisfying the Lipschitz condition with an unknown constant is considered and justified. It is assumed that the value of the function at the global minimizer is known (as is typical, e.g., in problems of minimizing the discrepancy between computed and experimental data). The convergence of the new algorithm is proved without using estimates of the Lipschitz constant, which are required in other Lipschitz optimization methods. Results of a numerical comparison of the efficiency of the proposed method with three well-known Lipschitz minimization algorithms are presented for functions from large random samples generated by two test problem generators widely used in such studies.

About the authors

K. A Barkalov

Lobachevsky State University of Nizhny Novgorod

Email: konstantin.barkalov@itmm.unn.ru
Nizhny Novgorod, Russia

A. S Zaitsev

Lobachevsky State University of Nizhny Novgorod

Nizhny Novgorod, Russia

R. G Strongin

Lobachevsky State University of Nizhny Novgorod

Nizhny Novgorod, Russia

References

  1. Квасов Д.Е., Сергеев Я.Д. Методы липшицевой глобальной оптимизации в задачах управления // Автомат. и телемехан. 2013. №9. C. 3–19.
  2. Kvasov D.E. et al. Tuning fuzzy power-system stabilizers in multi-machine systems by global optimization algorithms based on efficient domain partitions // Electr. Power Syst. Res. 2008. V. 78. №7. P. 1217–1229.
  3. Cavoretto R. et al. On the search of the shape parameter in radial basis functions using univariate global optimization methods // J. Global. Optim. 2021. V. 79. №2. P. 305–327.
  4. Васильев Ф.П. Методы оптимизации: В 2-х кн: Кн. 1 – М.: МЦНМО, 2011.
  5. Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. М.: Физматлит, 2008.
  6. Paulavicius R., ˇZilinskas J. Simplicial Global Optimization. Springer Briefs in Optimization. N.Y.: Springer, 2014.
  7. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.
  8. Grishagin V.A., Israfilov R., Sergeyev Ya.D. Convergence conditions and numerical comparison of global optimization methods based on dimensionality reduction schemes // Appl. Math. and Comput. 2018. V. 318. P. 270–280.
  9. Пиявский С.А. Один алгоритм отыскания абсолютного экстремума функции // Ж. вычисл. матем. и матем. физ. 1972. Т. 12. №4. С. 888–896.
  10. Стронгин Р.Г. Об одном алгоритме глобальной минимизации // Изв. ВУЗов. Радиофизика. 1970. Т. 13. № 4. С. 539–595.
  11. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Dordrecht: Kluwer Acad. Publ., 2000.
  12. Норкин В.И. О методе Пиявского для решения общей задачи глобальной оптимизации // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. № 7. С. 992–1006.
  13. Гергель В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функций // Ж. вычисл. матем. и матем. физ. 1996. Т. 36. № 6. С. 51–57.
  14. Lera D., Sergeyev Ya.D. Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives // SIAM J. Optim. 2013. V. 23. № 1. P. 508–529.
  15. Sergeyev Ya.D., Mukhametzhanov M.S., Kvasov D.E., Lera D. Derivative-free local tuning and local improvement techniques embedded in the univariate global optimization // J. Optim. Theor. and Appl. 2016. V. 171. № 1. P. 186–208.
  16. Евтушенко Ю.Г., Малкова В.У., Станевичюс А.А. Распараллеливание процесса поиска глобального экстремума // Автомат. и телемех. 2007. № 5. С. 46–58.
  17. Евтушенко Ю.Г., Посыпкин М.А. Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач // Ж. вычисл. матем. и матем. физ. 2011. Т. 51. № 8. С. 1376–1389.
  18. Jones D.R., Martins J.R.R.A. The DIRECT algorithm: 25 years Later // J. Global. Optim. 2021. V. 79. P. 521–566.
  19. Paulavicius R., Žilinskas J. Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints // Optim. Lett. 2016. V. 10. № 2. P. 237–246.
  20. Stripinis R., Paulavicius R., Žilinskas J. Penalty functions and two-step selection procedure based DIRECT-type algorithm for constrained global optimization // J. Struct. Multidisc. Optim. 2019. V. 59. № 6. P. 2155–2175.
  21. Grishagin V.A., Sergeyev Y.D., Strongin R.G. Parallel characteristical algorithms for solving problems of global optimization // J. Global. Optim. 1997. V. 10. № 2. P. 185–206.
  22. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация. Н. Новгород: Изд-во ННГУ, 2007.
  23. Shubert B.O. A sequential method seeking the global maximum of a function // SIAM J. Numer. Anal. 1972. V. 9. № 3. P. 379–388.
  24. Barkalov K.A., Strongin R.G., Bevzyuk S.A. Acceleration of global search by implementing dual estimates for Lipschitz constant // Lect. Not. Comput. Sci. 2020. V. 11974. P. 478–486.
  25. Barkalov K.A., Strongin R.G., Bevzyuk S.A. Global optimization method with dual Lipschitz constant estimates for problems with non-convex constraints // Soft Comput. 2020. V. 24. P. 11853–11865.
  26. Barkalov K.A., Usova M.A. A search algorithm for the global extremum of a discontinuous function // Comm. Comput. and Inform. Sci. 2021. V. 1514. P. 37–49.
  27. Barkalov K.A., Usova M.A. An algorithm for finding the global extremum of a partially defined function // Comm. Comput. and Inform. Sci. 2024. V. 1914. P. 147–161.
  28. Hill J.D. A search technique for multimodal surfaces // IEEE Transact. System Sci. and Cybernet. 1969. V. 5. № 1. P. 2–8.
  29. Shekel J. Test functions for multimodal search technique. In: Proceedings of the 5th Princeton Conference on Information Science Systems. Princeton Univ. Press, 1971. P. 354–359.
  30. Casado L.G., Garcia I.F., Sergeyev Y.D. Interval branch and bound algorithm for finding the first-zero-crossing-point in one-dimensional functions // Reliable Comput. 2000. V. 6. P. 179–191.
  31. Sergeyev Y.D., Daponte P., Grimaldi D., Molinaro A. Two methods for solving optimization problems arising in electronic measurements and electrical engineering // SIAM J. Optim. 1999. V. 10. № 1. P. 1–21.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2026 Russian Academy of Sciences

✱ All the metadata of this work are dedicated to being read, copied, modified, distributed, and used for any purpose (even commercial), without asking permission.