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

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

    Проект Российского Фонда Фундаментальных Исследований «Высокоэффективные параллельные методы глобальной оптимизации для задач суперкомпьютерного моделирования».

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

    При выполнении проекта «Высокоэффективные параллельные методы глобальной оптимизации для задач суперкомпьютерного моделирования» в 2019 году был разработан новый алгоритм глобального поиска. Отличительной особенностью разработанного алгоритма является использование численных оценок значений производных, построенных на основе накопленной поисковой информации; дополнительных испытаний для вычисления производных не требуется. Использование в алгоритме оценок значений производных позволяет значительно повысить эффективность его работы. На основе разработанных алгоритмов подготовлены пилотные варианты программ, а также проведены вычислительные эксперименты. Результаты выполненных экспериментов подтверждают, что разработанный подход является перспективным. Для разработанного алгоритма проведено теоретическое обоснование. Результаты исследований опубликованы в статье [Gergel, V., Goryachih, A. Multidimensional global optimization using numerical estimates of objective function derivatives // Optimization Methods and Software. doi: 10.1080/10556788.2019.1630624].

    Цели и задачи проекта на 2019 год

    1. Разработка алгоритмов глобального поиска, использующих численные оценки значений производных оптимизируемых задач, и обеспечивающих существенное повышение эффективности глобального поиска (не менее чем в 5-10 раз).
    2. Проведение теоретического обоснования сходимости разработанных алгоритмов.
    3. Разработка пилотных вариантов программ, реализующих алгоритмы с численными оценками производных.
    4. Получение результатов вычислительных экспериментов с разработанными алгоритмами и программами.

    Результаты 2019 года

    1. Разработка алгоритмов глобального поиска, использующих численные оценки значений производных оптимизируемых задач

    В 2019 году в рамках проекта был разработан новый адаптивный метод глобального поиска с использованием численных оценок значений производных (AGMND) [1]. При разработке метода использовался информационно-статистический подход к глобальному поиску, предложенный Стронгиным Р.Г. [8]. На основе базового алгоритма глобального поиска с использованием значений производных минимизируемой функции (алгоритм представлен в [2, 3]), был разработан метод, в котором значения производных оцениваются численно путем обработки доступной поисковой информации.

    2. Проведение теоретического обоснования сходимости разработанных алгоритмов

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

    3. Разработка пилотных вариантов программ, реализующих алгоритмы с численными оценками производных. Результаты вычислительных экспериментов.

    Для разработанного метода была выполнена пилотная программная реализация. С использованием разработанного программного обеспечения было выполнено сравнение метода AGMND с известными алгоритмами аналогичного назначения. В экспериментах сравнивались известные методы: метод Гальперина (GM) [6], метод Пиявского (PM) [7], алгоритм Стронгина (GSA)[8], алгоритм Брента (BA) [9] и разработанный метод AGMND. Эффективность разработанных методов оценивалась путем решения набора из 20 одномерных тестовых задач глобальной оптимизации. Отметим, что среди выбранного множества алгоритмов, алгоритм Брента использует оценку вторых производных в качестве параметра. В серии экспериментов в алгоритме Брента была использована точная верхняя оценка.

    Среднее количество проведенных испытаний, выполненное каждым из методов:

    1. GM – 720.75;
    2. PM – 314.60;
    3. GSA – 244.15;
    4. BA – 61.9;
    5. AGMND – 23.95.

    Результаты выполненных экспериментов подтверждают, что разработанный подход является перспективным.

    4. Апробация результатов проекта на научных мероприятиях

    Международная конференция, «Numerical Computations: Theory And Algorithms 2019 (NUMTA2019)», Изола Капо Риццуто, Кротоне, Италия, 15-21 июня 2019г.

    Международная конференция, «Суперкомпьютерные дни в России», Москва, 23-24 сентября 2019 г.

    Литература

    1. Gergel, V., Goryachih, A. Multidimensional global optimization using numerical estimates of objective function derivatives // Optimization Methods and Software (статья в печати)
    2. В.П. Гергель. Об одном способе учета значений производных при минимизации многоэкстремальных функций // Ж. вычисл. матем. и матем. физ. 1996. Т.36, №6. с. 51–67.
    3. P. Gergel, A global optimization algorithm for multivariate function with Lipschitzian first derivatives // J. Global Optim. 1997. vol. 10. pp. 257–281.
    4. К.А. Баркалов, М.А. Кочеганова, С.А. Бевзюк, А.А. Федюков Эффективные методы глобальной оптимизациидля решения задач оптимального управления // Суперкомпьютерные дни в России: Труды международной конференции. 23-24 сентября 2019 г., г. Москва / Под. ред. Вл.В. Воеводина – Москва : МАКС Пресс, 2019, С.235-236
    5. Gergel, V., Goryachih, A. Multidimensional global search using numerical estimations of minimized function derivatives and adaptive nested optimization scheme // LNCS (принято в печать)
    6. A. Galperin The cubic algorithm // Journal of Mathematical Analysis and Applications 112 (1985), pp. 635-640.
    7. O. Shubert A sequential method seeking the global maximum of a function // SIAM Journal on Numerical Analysis 9 (1972), pp. 379-388.
    8. G. Strongin and Y.D. Sergeyev Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms // Kluwer Academic Publishers, 2000, 2nd ed 2013, 3rd ed 2014.
    9. P. Brent, Algorithms for Minimization Without Derivatives // Englewood Cliffs NJ: Prentice-Hall, 1973.
    10. Баландин Д.В., Коган М.М. Синтез законов управления на основе линейных матричных неравенств. М.: Физматлит, 2007. 281 с.

    Цели и задачи проекта на 2020 год

    1. Анализ возможных схем редукции размерности для сведения многомерных оптимизационных задач к одномерным задачам глобального поиска при использовании алгоритмов, использующих оценки частных производных.
    2. Разработка алгоритмов глобального поиска, использующие численные оценки значений производных для задач многомерной глобальной оптимизации.
    3. Исследование условий сходимости разработанных алгоритмов.
    4. Разработка пилотных программ, реализующих предложенные алгоритмы решения многомерных задач глобальной оптимизации.
    5. Анализ теоретических и экспериментальных результатов для оценки эффективности разработанных алгоритмов для решения многомерных многоэкстремальных задач.
    6. Подготовка статьи для публикации в рецензируемых научных изданиях.

    Результаты 2020 года

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

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

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

    Разработка алгоритмов выполнялась в два этапа.

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

    На втором этапе была разработана общая вычислительная схема, которая позволяет применять алгоритмы одномерной оптимизации для решения многомерных задач глобального поиска. Для оценки применимости одномерных алгоритмов в рамках такого подхода были выполнены вычислительные эксперименты, в каждом из которых проводилось решение серии двумерных задач глобальной оптимизации. При выполнении вычислительных алгоритмов рассматривались несколько различных вариантов сочетания одномерных алгоритмов на разных уровнях рекурсивной схемы редукции размерности. Из результатов выполненных вычислительных экспериментов следует, что использование метода AGMND на каждом уровне рекурсии позволяет достичь наилучшей производительности (наименьшего количества поисковых испытаний) [2].

    3. Исследование условий сходимости разработанных алгоритмов

    За основу были взяты теоретические условия сходимости алгоритма с использованием «точных» производных, процедуры вычисления значений которых заданы априори. Сформулированы условия сходимости новых разработанных алгоритмов, в которых значения производных вычисляются численно с использованием поисковой информации, получаемой в процессе глобального поиска.

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

    На основе предложенных алгоритмов многомерного глобального поиска разработаны пилотные варианты программных реализаций, которые использовались для проведения вычислительных экспериментов.

    5. Анализ теоретических и экспериментальных результатов для оценки эффективности разработанных алгоритмов для решения многомерных многоэкстремальных задач

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

    6. Подготовка статьи для публикации в рецензируемых научных изданиях

    По результатам исследований в 2020 г. опубликована статья в рецензируемом научном журнале [1] и еще одна работа принята к опубликованию [2]. Результаты выполнения проекта в 2020 г. были представлены на научных конференциях [3-5].

    Литература

    1. Sysoyev A., Kocheganova M., Gergel V., Kozinov E. (2020) A Visual-Based Approach for Evaluating Global Optimization Methods // Communications in Computer and Information Science. vol 1331, pp. 137-149 https://doi.org/10.1007/978-3-030-64616-5_12.
    2. Sysoyev A., Gergel V. Global optimization method with numerically calculated function derivatives // Communications in Computer and Information Science (принята в печать).
    3. Баркалов К.А., Усова М.А. Решение задач глобальной оптимизации с учетом возможных разрывов целевой функции // Математическое моделирование, численные методы и комплексы программ: Сборник материалов IX Международной научной молодежной школы-семинара имени Е. В. Воскресенского (Саранск, 8-11 октября 2020 г.) / Отв. ред. В.Ф. Тишкин. – Саранск: СВМО, 2020. C. 32-35.
    4. Баркалов К. А., Сысоев А. В., Ямщиков И. С. Алгоритм глобальной оптимизации с использованием численных оценок производной минимизируемой функции // Математическое моделирование, численные методы и комплексы программ: Сборник материалов IX Международной научной молодежной школы-семинара имени Е. В. Воскресенского (Саранск, 8-11 октября 2020 г.) / Отв. ред. В.Ф. Тишкин. – Саранск: СВМО, 2020. C. 28-31.
    5. Баркалов К.А., Усова М.А. Сравнение методов решения задач глобальной оптимизации с разрывными функциями // Труды XX Международной конференции (Н. Новгород, 23–27 ноября 2020 г.) / Под ред. проф. В.П. Гергеля. – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2020. C. 48-50.

    Цели и задачи проекта на 2021 год

    1. Анализ возможных схем параллельных вычислений для алгоритмов многомерной оптимизации с использованием численных значений производных.
    2. Разработка пилотных вариантов параллельных программ, реализующих разработанные алгоритмы алгоритмов.
    3. Проведение вычислительных экспериментов на суперкомпьютерных системах для оценки эффективности предложенных схем организации параллельных вычислений.
    4. Обобщение результатов исследований и определение направлений будущих исследований.

    Результаты 2021 года

    В соответствии с поставленными задачами при выполнении проекта были получены следующие результаты.

    1. Новые методы использования численных оценок значений производных для решения вычислительно-трудоемких задач глобальной оптимизации

    В результате выполнения проекта разработан новый адаптивный метод глобального поиска с использованием численных оценок значений производных (AGMND) [1]. При разработке метода использовался информационно-статистический подход к глобальному поиску [6]. На основе базового алгоритма глобального поиска с использованием значений производных минимизируемой функции (алгоритм представлен в [2, 3]), был разработан метод, в котором значения производных оцениваются численно путем обработки доступной поисковой информации.

    2. Развитие математического аппарата исследования предлагаемых алгоритмов в рамках единой информационно-статистической теории глобальной оптимизации

    Разработка новых алгоритмов (AGMND и его модификаций) сопровождалась их теоретическим обоснованием. Для всех алгоритмов были сформулированы и доказаны теоремы, гарантирующие сходимость последовательности точек испытаний, порождаемой новым алгоритмом, к точке глобального минимума. Формулировки теорем и доказательства опубликованы в [1].

    3. Разработка многомерных вариантов предлагаемых методов с использованием различных схем редукции размерности

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

    Уменьшить сложность анализа поисковой информации можно за счет редукции решаемых задач оптимизации с использованием кривых или разверток Пеано, однозначно и непрерывно отображающих отрезок [0,1] на N-мерный гиперкуб. В результате такой редукции многомерная задача глобальной оптимизации сводится к одномерной задаче. Данный подход в случае алгоритма с использованием производных имеет ограниченное применение, так как редуцированная одномерная функция удовлетворяет условию Гельдера и не является гладкой.

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

    На основе проведенного анализа возможных схем редукции размерности в ходе исследований выбран второй подход, так как при реализации алгоритмов можно задействовать результаты, полученные при выполнении первого этапа исследований. Вместе с тем стоит отметить, что одномерные функции на верхнем уровне рекурсии, возникающие при использовании многошаговой схемы, могут также не обладать свойством гладкости, т.е. иметь разрывы производной типа конечного скачка. Для преодоления указанной проблемы в рамках исследований реализован подход к учету возникающих разрывов [11-12].

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

    4. Анализ возможных схем параллельных вычислений для алгоритмов многомерной оптимизации с использованием численных значений производных

    Рассмотрены возможные схемы распараллеливания разработанного алгоритма глобального поиска. На основе проведенного исследования предложен параллельный алгоритм решения вычислительно трудоемких многомерных задач глобальной оптимизации, сочетающий использование схемы вложенной редукции размерности и численных оценок производных целевой функции. Результаты численных экспериментов демонстрируют значительное сокращение времени решения задач в параллельном варианте алгоритма [15].

    В качестве задела для реализации будущих проектов рассмотрена возможность использования набора инструментов Intel OneApi для реализации алгоритмов глобального поиска. Intel OneApi позволяет разрабатывать единый код для разных вычислительных устройств. Результаты исследований представлены на международной конференции [14].

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

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

    Апробация разработанных программ была проведена при решении серий тестовых задач глобальной оптимизации, а также – вычислительно-трудоемких прикладных задач оптимального выбора на суперкомпьютерных системах [4,13].

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

    Разработанные методы были апробированы при решении вычислительно-трудоемких прикладных задач оптимального выбора.

    В качестве примера одной из прикладных задач рассматривается задача поиска -динамического регулятора для обратного маятника с подвижным основанием. Известно [7], что решение данной задачи сводится к разрешимости системы матричных неравенств, часть из которых являются невыпуклыми. В качестве численного примера построен регулятор первого порядка для перевернутого маятника на тележке [4]. Найдены параметры регулятора и соответствующее им минимальное значение уровня гашения возмущений. Время решения данной задачи составило 125 сек (CPU Intel Core i7, 3.6 GHz).

    Еще одним примером являлась задача выбора параметров модели турбулентного течения; исследуемая модель формировалась при участии сотрудников ИСП РАН [13]. В исследовании рассматривались математические модели таких опасных природных явлений, как сход оползней, селей и лавин. Проблема прогноза данных явлений является актуальной задачей, т.к. моделирование позволяет прогнозировать разрушения, правильно располагать защитные сооружения и жизненно важные объекты. В модель склоновых потоков, как правило, входят несколько параметров (коэффициенты модели турбулентности), значения которых нельзя указать заранее, но можно выбрать, исходя из соответствия расчета по модели и имеющихся экспериментальных данных. Подобная задача является задачей глобальной оптимизации.

    Процесс выбора оптимального набора параметров модели склоновых потоков соответствует задаче глобальной оптимизации с целевой функцией вида «черный ящик». В качестве целевой функции в задаче глобальной оптимизации рассматривалась функция потерь, представляющая собой среднеквадратическую ошибку рассчитанного профиля скорости потока по отношению к экспериментальному профилю на выходной плоскости. Для ускорения процедуры оптимизации использовалась аппроксимация целевой функции при помощи нейросетевой регрессии (NNR). На первом этапе поиска алгоритм работал с целевой функцией напрямую (этап накопления информации). Затем на основе поисковой информации строилась аппроксимация целевой функции, которая использовалось на втором этапе поиска.

    Моделирование проводилось на суперкомпьютере ННГУ им. Н.И. Лобачевского (операционная система Linux CentOS 7.2). Каждый узел кластера включает в себя два процессора Intel Sandy Bridge E5-2660 2.2 ГГц, 64 ГБ ОЗУ; центральный процессор имеет 8 ядер. Для вычисления значения целевой функции использовалось программное обеспечение CFD с открытым исходным кодом OpenFOAM v2012. Одно вычисление оптимизируемой функции при заданных значениях параметров занимало в среднем 15 минут с использованием 8 MPI-процессов на узел. Общее время расчетов составило более 20 часов на суперкомпьютере ННГУ им. Н.И. Лобачевского. Результаты проведенных экспериментов позволили найти оптимальные значения шести параметров модели турбулентности, что обеспечило хорошее соответствие модели экспериментальным данным.

    Результаты, полученные при выполнении проекта, отражены в 10 публикациях, 3 из которых – в рецензируемых изданиях, индексируемых WebOfScience/Scopus (в том числе статья в журнале Optimization Methods and Software, Q1), 7 публикаций индексируются РИНЦ.

    Литература

    1. Gergel, V., Goryachih, A. Multidimensional global optimization using numerical estimates of objective function derivatives // Optimization Methods and Software, 2019.   https://doi.org/10.1080/10556788.2019.1630624
    2. Гергель, В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функций // Ж. вычисл. матем. и матем. физ. 1996. Т.36, №6. C. 51–67.
    3. Gergel, V.P. A global optimization algorithm for multivariate function with Lipschitzian first derivatives // J. Global Optim. 1997. vol. 10. pp. 257–281.
    4. Баркалов, К.А., Кочеганова, М.А., Бевзюк С.А., Федюков А.А. Эффективные методы глобальной оптимизациидля решения задач оптимального управления // Суперкомпьютерные дни в России: Труды международной конференции. 23-24 сентября 2019 г., г. Москва / Под. ред. Вл.В. Воеводина – Москва : МАКС Пресс, 2019, С.235-236
    5. Gergel, V., Goryachih, A. Multidimensional global search using numerical estimations of minimized function derivatives and adaptive nested optimization scheme //  Lecture Notes in Computer Science, 2020. vol. 11974, pp. 378-385, https://doi.org/10.1007/978-3-030-40616-5_33
    6. Strongin, R.G., Sergeyev, Y.D. Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms // Kluwer Academic Publishers, 2000, 2nd ed 2013, 3rd ed 2014.
    7. Баландин, Д.В., Коган, М.М. Синтез законов управления на основе линейных матричных неравенств // М.: Физматлит, 2007. 281 с.
    8. Sysoyev, A., Kocheganova, M., Gergel, V., Kozinov, E. A Visual-Based Approach for Evaluating Global Optimization Methods // Communications in Computer and Information Science, 2020. vol 1331. pp 137-149. https://doi.org/10.1007/978-3-030-64616-5_12
    9. Sysoyev, A., Gergel, V. Global optimization method with numerically calculated function derivatives // Communications in Computer and Information Science, 2020. vol. 1340, pp 3-14. https://doi.org/10.1007/978-3-030-65739-0_1
    10. Баркалов, К.А., Сысоев, А.В., Ямщиков, И.С. Алгоритм глобальной оптимизации с использованием численных оценок производной минимизируемой функции // IX Международная научная молодежная школа-семинар ”Математическое моделирование, численные методы и комплексы программ” имени Е.В. Воскресенского, 2020. C. 28-31
    11. Баркалов, К.А., Усова, М.А. Решение задач глобальной оптимизации с учетом возможных разрывов целевой функции //IX Международная научная молодежная школа-семинар ”Математическое моделирование, численные методы и комплексы программ” имени Е.В. Воскресенского, 2020. C. 32-35
    12. Баркалов, К.А., Усова, М.А. Сравнение методов решения задач глобальной оптимизации с разрывными функциями // Труды XX Международной конференции (Н. Новгород, 23–27 ноября 2020 г.) / Под ред. проф. В.П. Гергеля. – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2020. C. 48-50
    13. Баркалов, К.А., Лебедев, И.Г., Усова, М.А., Романова, Д.И., Рязанов, Д.А., Стрижак. С.В. Оптимизация параметров модели турбулентности с помощью метода глобального поиска на параллельной вычислительной системе // Математическое моделирование и суперкомпьютерные технологии. Труды XXI Международной конференции (Н. Новгород, 22–26 ноября 2021 г.) – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2021. С. 47-50.
    14. Кольтюшкина, Я.В., Лебедев И.Г. Реализация параллельного алгоритма глобального поиска с использованием набора инструментов Intel oneAPI // Математическое моделирование и суперкомпьютерные технологии. Труды XXI Международной конференции (Н. Новгород, 22–26 ноября 2021 г.) – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2021. С. 165-168.
    15. Ямщиков, И.С., Сысоев, А.В. Параллельный алгоритм глобальной оптимизации с использованием численных оценок производных минимизируемой функции // Тезисы XXII Всероссийской конференции молодых учёных по математическому моделированию и информационным технологиям. г. Новосибирск, Россия, 25–29 октября 2021 г. — Новосибирск: ФИЦ ИВТ, 2021. C. 60-61