Приволжский научно-образовательный центр суперкомпьютерных технологий
Исследования
  • Основные направления
  • Гранты, проекты, договора

    • Высокопроизводительные вычисления в задачах глобальной оптимизации

    Краткое описание

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

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

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

    Исследования в области параллельной глобальной оптимизации ведутся в ННГУ им. Н.И. Лобачевского на протяжении последних 25 лет; за это время сформировалась признанная в стране и за рубежом Нижегородская школа глобальной оптимизации.

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

    Основные результаты отражены в 8 монографиях и более чем в 300 работах, опубликованных в стране и за рубежом. Здесь же отметим, что в рамках направления разработаны:

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

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

    Эффективные параллельные алгоритмы глобального поиска, в т.ч.

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

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

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

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

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

    Коллектив

    Научный руководитель Нижегородской школы глобальной оптимизации — Стронгин Роман Григорьевич, президент ННГУ им. Н.И. Лобачевского, заведующий кафедрой математического обеспечения ЭВМ факультета ВМК, д.ф.-м.н., проф., заслуженный деятель науки Российской Федерации, Лауреат премии Президента Российской Федерации в области образования, Лауреат премии г. Нижнего Новгорода в области высшей школы

    Коллектив научной школы:

    • Гергель Виктор Павлович, д.т.н., проф., декан факультета ВМК ННГУ,
    • Сергеев Ярослав Дмитриевич, д.ф.-м.н., проф., факультет ВМК ННГУ
    • Баркалов Александр Валентинович, к.ф.-м.н., доц., факультет ВМК ННГУ
    • Гришагин Владимир Александрович, к.ф.-м.н., доц., факультет ВМК ННГУ
    • Баркалов Константин Александрович, к.ф.-м.н., доц., факультет ВМК ННГУ
    • Сысоев Александр Владимирович, к.т.н., ст.преп., факультет ВМК ННГУ
    • Квасов Дмитрий Евгеньевич, к.ф.-м.н., н.с., факультет ВМК ННГУ
    • Гергель Александр Викторович, к.т.н., инженер-программист, факультет ВМК ННГУ
    • Сидоров Сергей Владимирович, к.т.н, инженер-программист, факультет ВМК ННГУ
    • Рябов Василий Владимирович, м.н.с., факультет ВМК ННГУ

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

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

    1. Стронгин Р. Г., Гергель В. П., Гришагин В. А., Баркалов К. А. Параллельные вычисления в задачах глобальной оптимизации: Монография / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2013. – 280 с. – ISBN 978-5-211-06479-9
    2. Sergeyev Ya.D., Strongin R.G., Lera D. Introduction to global optimization exploiting space-filling curves. – Springer, NY, 2013. – 133 pp. – ISBN 978-1-4614-8042-6
    3. Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. – М.: Физматлит, 2008. – 352 с. – ISBN 978-5-9221-1032-7
    4. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация: учебное пособие. – Н.Новгород: Изд-во Нижегор. гос. ун-та, 2007. – 489 с. – ISBN 978-5-85746-987-3
    5. Стронгин Р.Г., Гергель В.П., Городецкий С.Ю., Гришагин В.А., Маркина М.В. Современные методы принятия оптимальных решений: учебник. Изд-во Нижегор. гос. ун-та, 2002. – 199 с. – ISBN 5-85746-697-0
    6. Strongin R.G., Sergeyev Ya.D. Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms . – Kluwer Academic Publishers. Dordrecht. The Netherlands, 2000. – 728 pp. – ISBN 978-1-4615-4677-1
    7. Стронгин Р.Г. Поиск глобального оптимума. – М.: Знание, 1990. – 48 с.
    8. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. Информационно- статистический подход. – М.: Наука, 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. Гергель В.П., Гришагин В.А., Гергель А.В. Многомерная многоэкстремальная оптимизация на основе адаптивной многошаговой редукции размерности // Вестник Нижегородского университета им. Н.И. Лобачевского. – № 1, 2010. – С. 163–170.
    7. Стронгин Р.Г., Гергель В.П., Баркалов К.А. Параллельные методы решения задач глобальной оптимизации // Известия высших учебных заведений. Приборостроение. – Т. 52, № 10, 2009. – С. 25–33.
    8. 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.
    9. Стронгин Р.Г., Баркалов К.А. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем. физ. – Т. 42, №9, 2002. – С. 1338–1350.
    10. 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.
    11. 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.
    12. Gergel V.P. A Global Optimization Algorithm for Multivariate Functions with Lipschitzian First Derivatives // Journal of Global Optimization. – vol.10, 1997. – pp. 257–281.
    13. Гергель В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функции // Ж. вычисл. матем. и матем. физ. – Т. 36, № 6, 1996. – С. 51–67.
    14. Стронгин Р.Г., Маркин Д.Л. О равномерной оценке множества слабоэффективных точек в многоэкстремальных многокритериальных задачах оптимизации // Ж. вычисл. матем. и матем. физ. – Т. 33, №2, 1993. – С. 195–205.
    15. Gergel V.P. A software system for multiextremal optimization // European Journal of Operation Research. – vol. 65(3), 1993. – pp. 305–313.

     Разработанное программное обеспечение

    1. Программная система Globalizer для параллельного параллельного поиска глобально-оптимальных решений (2013-~)
    2. Программная система GlobalExpert для решения задач многомерной многоэкстремальной оптимизации (2001-2013)
    3. Программная система для исследования и изучения методов глобальной оптимизации АБСОЛЮТ (1992-~)
    4. Система многоэкстремальной оптимизации в научных исследованиях и проектировании СИМОП-НИПР (1989-1992)
    5. Система оптимизации технологических процессов СО ТП (1986-1991)
    6. Система СИМОП автоматизации выбора рациональных решений в комплексах САПР и АСНИ (1981-1985)

     Конкурсы, проекты и гранты

    • Грант РНФ «Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности», 2016-2018 гг.
    • Грант РНФ «Глобальная оптимизация, суперкомпьютерные вычисления и приложения», 2015-2017 гг.
    • Проект ФЦП «Научные и научно-педагогические кадры инновационной России», проект № 14.B37.21.0393 «Модели, методы и программные средства для решения задач непрерывной и дискретной оптимизации» (2012-2013)
    • Грант Совета Президента № НШ-1960.2012.9 «Модели и методы параллельных вычислений для многопроцессорных систем» (2008-2009, 2010-2011, 2012-2013)
    • Грант Совета Президента № МК-1536.2009.9 «Разработка параллельных алгоритмов глобальной оптимизации и их реализация на многопроцессорных вычислительных системах» (2009 – 2010)
    • Грант РФФИ  № 11-01-00682 «Эффективные параллельные методы исследования сложных многоэкстремальных оптимизационных моделей» (2011–2013)
    • Грант РФФИ  №  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 гг.