Основные научные результаты

В рамках направления разработаны:

Теоретические основы для разработки и исследования методов глобальной оптимизации, в том числе:

• информационно-статистический подход к построению оптимизационных алгоритмов;
• характеристическая теории сходимости и оценки эффективности методов поиска экстремума;
• общая методология редукции сложности исследуемых оптимизационных моделей.

Эффективные параллельные алгоритмы глобального поиска, использующие

• способы сведения многомерных задач к одномерным (редукция размерности) с помощью разверток типа кривых Пеано, передающих свойство близости в многомерном пространстве на одномерные шкалы и нашедших применение в оптимизации, распознавании образов, интегрировании и при создании баз данных;
• схемы раздельного учета ограничений (без использования штрафов), сокращающие вычислительные затраты и допускающие частичную определенность и вычислимость функционалов, характерную для приложений;
• способы ускорения сходимости методов глобальной оптимизации путем учета степени регулярности задачи, определяемой на основе введенного понятия eps-резервированных решений, а также путем использования адаптивно изменяемого порядка проверки ограничений.

Масштабируемая схема параллельных вычислений, позволяющая в полной мере использовать потенциал современных суперкомпьютерных систем (вплоть до петафлопсного уровня). Разработанный подход включает:

• схему распараллеливания для вычислительных систем с распределенной памятью на основе применения множественных разверток типа кривой Пеано;
• асинхронные параллельные алгоритмы глобальной оптимизации для систем с общей разделяемой памятью;
• способы управления параллельными вычислениями на основе блочной многошаговой схемы редукции размерности.

Параллельные программные системы глобальной оптимизации, среди которых:

• программная система Globalizer, предназначенная для решения многомерных многоэкстремальных задач оптимизации со сложными нелинейными ограничениями;
• программная система Globalizer Lab (Абсолют), ориентированная на изучение и исследование алгоритмов глобального поиска.

С использованием разработанных в рамках данного направления методов и программных систем выполнено решение широкого спектра научно-технических задач из разных областей приложений (проектирование систем цифровой передачи, силовых конструкций, летательных аппаратов, электронной аппаратуры, идентификации моделей в физике, экономике, медицине и др.).

В целом, полученные результаты составляют новое направление в области теории и методов выбора решений на основе сложных оптимизационных моделей (многоэкстремальных и многокритериальных с существенно невыпуклыми ограничениями и особенностями). Сформированное направление отличается всесторонним охватом проблемы глобальной оптимизации, воплощено в программных средствах и апробированно на большом числе приложений.

Избранные публикации

Монографии, учебники

1. Sergeyev Ya.D., Kvasov D.E. Deterministic Global Optimization. An Introduction to the Diagonal Approach. – Springer, NY, 2017. – 136 p. – ISBN 978-1-4939-7199-2
2. Стронгин Р. Г., Гергель В. П., Гришагин В. А., Баркалов К. А. Параллельные вычисления в задачах глобальной оптимизации: Монография / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2013. – 280 с. – ISBN 978-5-211-06479-9
3. Sergeyev Ya.D., Strongin R.G., Lera D. Introduction to global optimization exploiting space-filling curves. – Springer, NY, 2013. – 133 p. – ISBN 978-1-4614-8042-6
4. Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. – М.: Физматлит, 2008. – 352 с. – ISBN 978-5-9221-1032-7
5. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация: учебное пособие. – Н.Новгород: Изд-во Нижегор. гос. ун-та, 2007. – 489 с. – ISBN 978-5-85746-987-3
6. Стронгин Р.Г., Гергель В.П., Городецкий С.Ю., Гришагин В.А., Маркина М.В. Современные методы принятия оптимальных решений: учебник. Изд-во Нижегор. гос. ун-та, 2002. – 199 с. – ISBN 5-85746-697-0
7. Strongin R.G., Sergeyev Ya.D. Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms . – Kluwer Academic Publishers. Dordrecht. The Netherlands, 2000. – 728 p. – ISBN 978-1-4615-4677-1
8. Стронгин Р.Г. Поиск глобального оптимума. – М.: Знание, 1990. – 48 с.
9. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. Информационно- статистический подход. – М.: Наука, 1978. – 240 стр.

 Статьи

1. Grishagin V.A., Israfilov R., Sergeyev Ya.D. Convergence conditions and numerical comparison of global optimization methods based on dimensionality reduction schemes // Applied Mathematics and Computation. – vol. 318, 2018. – pp. 270–280.
2. Barkalov K.A., Gergel V.P.  Parallel global optimization on GPU // Journal of Global Optimization. – vol. 66(1), 2016. –pp. 3–20.
3. Gergel V.P., Grishagin V.A., Gergel A.V. Adaptive nested optimization scheme for multidimensional global search // Journal of Global Optimization. – vol. 66(1), 2016. –pp 35–51.
4. Sergeyev Ya.D., Kvasov D.E.  A deterministic global optimization using smooth diagonal auxiliary functions // Communications in Nonlinear Science and Numerical Simulation. – vol. 21, 2015. – pp. 99–111.
5. Kvasov D.E., Sergeyev Ya.D. Lipschitz gradients for global optimization in a one-point-based partitioning scheme // Journal of Computational and Applied Mathematics. – vol. 236(16), 2012. – pp. 4042–4054.
6. Сысоев А.В. Об одной информационно-алгоритмической модели процесса параллельного глобального поиска // Вестник Нижегородского университета им. Н.И. Лобачевского. – № 3(2), 2011. – С. 293–300.
7. Гергель В.П., Гришагин В.А., Гергель А.В. Многомерная многоэкстремальная оптимизация на основе адаптивной многошаговой редукции размерности // Вестник Нижегородского университета им. Н.И. Лобачевского. – № 1, 2010. – С. 163–170.
8. Стронгин Р.Г., Гергель В.П., Баркалов К.А. Параллельные методы решения задач глобальной оптимизации // Известия высших учебных заведений. Приборостроение. – Т. 52, № 10, 2009. – С. 25–33.
9. Gergel V.P., Strongin R.G. Parallel Computing for Globally Optimal Decision Making on Cluster Systems // Future Generation Computer Systems. – vol. 21(5), 2005. – pp. 673–678.
10. Стронгин Р.Г., Баркалов К.А. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем. физ. – Т. 42, №9, 2002. – С. 1338–1350.
11. Ya.D. Sergeyev, V.A. Grishagin. Parallel Asynchronous Global Search ant the Nested Optimization Scheme // Journal of Computational Analysis and Applications. – vol. 3(2), 2001. pp. 123–245.
12. Gergel V.P., Sergeyev Ya.D. Sequential and parallel global optimization algorithms using derivatives // Computers & Mathematics with Applications. – vol. 37(4/5), 1999. – pp. 163–180.
13. Gergel V.P. A Global Optimization Algorithm for Multivariate Functions with Lipschitzian First Derivatives // Journal of Global Optimization. – vol.10, 1997. – pp. 257–281.
14. Гергель В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функции // Ж. вычисл. матем. и матем. физ. – Т. 36, № 6, 1996. – С. 51–67.
15. Стронгин Р.Г., Маркин Д.Л. О равномерной оценке множества слабоэффективных точек в многоэкстремальных многокритериальных задачах оптимизации // Ж. вычисл. матем. и матем. физ. – Т. 33, №2, 1993. – С. 195–205.
16. Gergel V.P. A software system for multiextremal optimization // European Journal of Operation Research. – vol. 65(3), 1993. – pp. 305–313.

Гранты, проекты, договора

• Грант РНФ № 16-11-10150 «Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности» (2016-2018)
• Грант РНФ № 15-11-30022 «Глобальная оптимизация, суперкомпьютерные вычисления и приложения» (2015-2017)
• ФЦП «Научные и научно-педагогические кадры инновационной России», проект № 14.B37.21.0393 «Модели, методы и программные средства для решения задач непрерывной и дискретной оптимизации» (2012-2013)
• Гранты Совета Президента № НШ-4694.2008.9, НШ-64729.2010.9, НШ-1960.2012 «Модели и методы параллельных вычислений для многопроцессорных систем» (2008-2009, 2010-2011, 2012-2013)
• Грант Совета Президента № МК-1536.2009.9 «Разработка параллельных алгоритмов глобальной оптимизации и их реализация на многопроцессорных вычислительных системах» (2009 – 2010)
• Грант РФФИ № 11-01-00682 «Эффективные параллельные методы исследования сложных многоэкстремальных оптимизационных моделей» (2011–2013)
• Грант РФФИ № 11-07-97017 «Параллельные методы глобальной оптимизации в идентификации динамических балансовых нормативных моделей региональной экономики» (2011-2012)
• Грант РФФИ № 07-01-00467 «Многоэкстремальные модели оптимального выбора и эффективные методы их анализа» (2007–2009)
• Грант РФФИ № 04-01-00455 «Теория и методы анализа многоэкстремальных моделей оптимального выбора» (2004–2006)
• Грант РФФИ № 01-01-00587 «Многоэкстремальные модели выбора и параллельные методы их анализа» (2001–2003)
• Грант РФФИ № 95-01-01073 «Многоэкстремальные модели принятия решений и методы их анализа» (1995–1997)
• ФЦП «Интеграция», проект № К0392 «Учебно-научный Центр «Информатика. Распознавание образов. Анализ изображений. Интеллектуальные информационные технологии» (1998–2000)
• ФЦП «Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения», проект № 0201.03.287 «Разработка методов, программных комплексов и инструментальных средств поддержки процессов принятия проектных решений в задачах автоматизации проектирования» (1996-2000)

Достижения

Разработанная в ННГУ им. Н.И. Лобачевского система глобальной оптимизации ExaMin заняла 1-е место в номинации Target Shooting (число решенных задач) на международном конкурсе солверов для задач глобальной оптимизации GENeralization-based challenge in global OPTimization (GENOPT) (и 3-е место в общем зачете конкурса).

В рамках конкурса GENOPT  солверы соревновались при решении множества тестовых задач, выбираемых случайным образом из некоторого сконструированного класса. Организаторами конкурса были предложены 18 классов многоэкстремальных задач, в каждом классе было задано 100 функций  (см. подробное описание конкурсных задач). Алгоритмы оптимизации сравнивались как по скорости сходимости к решению, так и по числу решенных задач при заданном числе итераций. Численные эксперименты с конкурсными задачами были выполнены на суперкомпьютере «Лобачевский».