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

Этапы 1 и 2

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

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

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

По итогам исследований сделаны доклады на секции международной конференции Numerical Computations: Theory and Algorithms (NUMTA2016).  Результаты  опубликованы в трудах конференции.

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

Блочная схема реализована программно в системе глобальной оптимизации ExaMin, которая для решения вложенных подзадач использует информационно-статистический алгоритм глобального поиска и его модификации. Наряду с последовательным режимом функционирования, ExaMin поддерживает работу как на системах с распределенной (используя MPI), так и с общей памятью (используя OpenMP).

Система ExaMin прошла апробацию в рамках международного конкурса солверов задач глобальной оптимизации GENeralization-based challenge in global OPTimization (GENOPT), в рамках которого реализован известный подход к исследованию и сравнению алгоритмов многоэкстремальной оптимизации на множествах тестовых задач, выбираемых случайным образом из некоторого сконструированного класса. Организаторами конкурса GENOPT были предложены 18 классов многоэкстремальных задач, в каждом классе было задано 100 функций (подробное описание конкурсных задач). Алгоритмы оптимизации сравнивались как по скорости сходимости к решению, так и по числу решенных задач. Единственное ограничение, накладываемое на работу алгоритмов: должно быть выполнено не более 1 миллиона вычислений значений функции.       По условиям конкурса при решении задач использовался только последовательный режим работы решателя.  Численные эксперименты с конкурсными задачами были выполнены на суперкомпьютере «Лобачевский» Нижегородского госуниверситета.

В финальной части конкурса решатель ExaMin занял 3-е место в общем зачете и 1-е по общему числу решенных задач.

Описание блочной схемы, системы ExaMin и принципы организации конкурса GENOPT отражены в публикациях и доложены на секции международной конференции Numerical Computations: Theory and Algorithms (NUMTA2016).

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

Результаты опубликованы в международном журнале Mathematics and Computers in Simulation.

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

Результаты исследований опубликованы в статье международного научного журнала  Automation and Remote Control .

Рассмотрена трехиндексная задача о назначениях, возникающая в области планирования, распределения ресурсов, логистики и др. , которая является известным подклассом задач дискретной оптимизации и оказывается NP-трудной уже в трехиндексном случае. Исследованы вопросы построения нижней оценки задачи, основанной на линейной релаксации. В ходе вычислительного эксперимента найдена экстремальная нижняя оценка для трехиндексной аксиальной задачи о назначениях с 1,2-декомпозицонной матрицей стоимостей в случае, когда количество значений индексов не превосходит 3. Выдвинута гипотеза об экстремальности данной оценки для всего класса задач с 1,2-декомпозицонной матрицей стоимостей.

По итогам исследований подготовлена статья, принятая к публикации в российском журнале, индексируемом в РИНЦ.

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

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

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

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

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

Сравнение алгоритмов проводилось на основе метода операционных характеристик, позволяющего наглядно представить эффективность конкурирующих методов.  В эксперименте рассматривались выборки задач класса GKLS размерностей от 2 до 4, состоящие из 100 функций для каждой размерности. Результаты сравнения показали значительное превосходство адаптивных вариантов многошаговой схемы над их классическими прототипами, которое существенно увеличивается с ростом размерности. Наконец, наибольшую эффективность среди всех конкурирующих методов продемонстрировала адаптивная многошаговая схема в сочетании с информационно-статистическим алгоритмом глобального поиска.

Результаты исследования доложены на секции международной конференции Numerical Computations: Theory and Algorithms (NUMTA2016)  и опубликованы в трудах конференции.

Авторам доклада было предложено опубликовать расширенную статью в  спецвыпуске по материалам конференции.

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

Предложен новый параллельный алгоритм решения многомерных многоэкстремальных задач, ориентированный на суперкомпьютерные системы с графическими процессорами (GPU). В основе алгоритма лежит схема редукции многомерной задачи к решению эквивалентной одномерной проблемы глобального поиска с помощью кривых, заполняющих пространство (эвольвент Пеано) и последующего применения информационно-статистического параллельного алгоритма поиска глобального экстремума гельдеровых функций. Дано теоретическое обоснование эффективности распараллеливания синхронной версии метода через установление условий безызбыточности вычислений. Предложена схема реализации с использованием графических процессоров и разработана программная система, реализующая предложенные алгоритмические  решения на суперкомпьютерных архитектурах, включающих  процессоры графического типа. Проведены представительные вычислительные эксперименты по верификации теоретических результатов и сравнению различных реализаций алгоритма на известном тестовом классе многоэкстремальных функций GKLS для задач различных размерностей. Полученные результаты продемонстрировали более высокую эффективность метода по сравнению с известным методом глобальной оптимизации DIRECT, а также существенное ускорение вычислений в случае использования графических процессоров по сравнению с реализацией алгоритма на CPU-архитектурах. Эксперименты были выполнены на суперкомпьютере “Лобачевский” Нижегородского госуниверситета.

Результаты опубликованы в журнале Journal of Global Optimization.

Выполнено обобщение на параллельный случай блочной схемы вложенной оптимизации, сочетающей многошаговую редукцию размерности исходной многоэкстремальной задачи к системе подзадач меньших размерностей, решаемых посредством их сведения к одномерным задачам через использование кривых Пеано-Гильберта. Разработана структура организации параллельных вычислений на основе блочной схемы и реализована программная система решения задач поиска глобального оптимума многомерных функций на суперкомпьютерных вычислительных установках. Проведенные  вычислительные эксперименты  на суперкомпьютере Нижегородского госуниверситета “Лобачевский” продемонстрировали эффективность использования параллельной блочной схемой  гетерогенных (CPU, GPU) ресурсов современных суперкомпьютерных систем, обеспечив значительное ускорение вычислительного процесса.

Результаты доложены на международной конференции Суперкомпьютерные дни в России 2016 (Russian Supercomputing Days 2016)  – секционный доклад, опубликованы в сборнике трудов конференции и приняты к публикации в сборнике Communications in Computer and Information Science (Springer) .

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

Результаты доложены на секции международной конференции Numerical Computations: Theory and Algorithms (NUMTA2016) и опубликованы в трудах конференции.

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

Предложены новые методы решения задачи Коши, обеспечивающие существенно более высокую точность решения по сравнению с традиционными методами за счет введения  в структуру методов бесконечно малых  параметров.  Введение таких  параметров позволяет получать точные значения  производных  без использования разностных схем аппроксимации, что значительно снижает погрешность вычислений.  Проведено сравнение с известными методами численного решения задачи Коши, продемонстрировавшее перспективность  предложенного подхода. Результаты доложены на Международной конференции NUMTA2016, опубликованы в научном журнале International Journal of Unconventional Computing и трудах конференции.

Задачи многокритериальной оптимизации являются важной прикладной областью деятельности . В проекте рассмотрены лексикографические задачи линейного программирования. Это означает, что задача содержит несколько критериев и первый критерий несравнимо более важен, чем второй критерий, который, в свою очередь, несравнимо более важен, чем третий и т.д. Традиционные методы предусматривают два подхода к решению таких задач. Первый состоит в поэтапном решении задач  линейного программирования, соответствующих каждому критерию. Естественно, такой подход является очень затратным по времени. Второй подход предлагает решить одну задачу, которая зависит от неизвестного параметра. Поскольку параметр неизвестен, проводятся множественные запуски с различными значениями параметра, что опять ведет к большим временным затратам. В проекте проведены исследования возможности работы с бесконечно большими значениями параметра в рамках теории исчисления бесконечно малых и бесконечно больших величин, разработанной Я.Д.Сергеевым. Предложен алгоритм решения линейных многокритериальных задач, в котором не требуется решать множество однокритериальных подзадач: достаточно решить одну такую задачу специального вида, используя операции компьютера бесконечности. Алгоритм, позволяющий проводить эксперименты с бесконечно большими величинами, также реализован в среде MATLAB.

Результаты исследования доложены на секции международной конференции Numerical Computations: Theory and Algorithms (NUMTA2016) и опубликованы в трудах конференции.

4. Проведение в Нижегородском госуниверситете молодежной научной школы “Высокопроизводительные вычисления, оптимизация и приложения” (ноябрь 2016 г.) с привлечением ведущих российских и зарубежных ученых.

С 7 по 11 ноября 2016 г. в Нижегородском государственном университете им. Н.И.Лобачевского проведена запланированная в проекте школа молодых ученых “Высокопроизводительные вычисления, оптимизация и приложения” с приглашением в качестве лекторов ведущих российских и зарубежных ученых по тематике проекта.

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

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

Работа школы состояла из двух частей.  В рамках первой части  в Нижегородском госуниверситете  6 иностранных и 10 российских ученых прочитали 16 лекций:

1. А. Zhigljavsky (Great Britain) Some geometrical and analytical features of problems involving big data and high dimensions
2. R. Battiti (Italy) Deep learning: dream or reality?
3. А.В. Бухановский (Россия) Вычислительные технологии трансляционной медицины: от больших данных к предсказательному моделированию
4. O.Kostyukova (Belarus) Phenomenon of Immobility  in  study  of  convex  Semiinfinite  Programming problems: General approach
5. T. Tchemisova (Portugal) Phenomenon of Immobility  in  study  of  convex  Semiinfinite Programming problems: CQ-free optimality conditions
6. Ю.Г. Евтушенко, М.А. Посыпкин (Россия) Метод неравномерных покрытий для задач глобальной оптимизации
7. И. Кузьмин (Россия) Towards new horizons with Machine Learning solutions on Intel® IA
8. J. Zilinskas (Lithuania) Simplicial global optimization
9. O.Burdakov (Sweden) Contemporary numerical methods of unconstrained optimization
10. О.В. Хамисов (Россия) Методы ветвей и отсечений в непрерывной глобальной оптимизации
11. М.В. Якобовский (Россия) Суперкомпьютерное моделирование: проблемы и возможности
12. Л.Г. Афраймович (Россия) Математические модели и методы эффективного использования распределенных вычислительных систем
13. Я.Д. Сергеев, Д.Е. Квасов (Россия) Липшицева глобальная оптимизация и приложения
14. Вл.В. Воеводин, Вад.В. Воеводин (Россия) Искусство эффективного управления суперкомпьютерной системой
15. Д.И. Крыжановский (Россия) Робототехника и компьютерное зрение
16. Н.Ю. Золотых (Россия) Введение в машинное обучение

Во второй части обучение проходило по трем направлениям (трекам). Программа по каждому треку включала  практические и лабораторные занятия на базе Нижегородского госуниверситета и Нижегородского отделения компании Интел. Полная программа школы приведена в приложении.

В работе школы принял участие 71 слушатель (студенты, аспиранты и молодые ученые) из 21 города России, которые представляли 28 университетов и институтов, в том числе ведущие ВУЗы Российской Федерации: МГУ им. М.В.Ломоносова, МФТИ, МГТУ им. Н.Э.Баумана, НИУ ВШЭ, Новосибирский госуниверситет, Уральский и Южный Федеральные университеты, Сколковский институт науки и технологий и др.

По итогам работы слушатели школы получили именные сертификаты участника.

 

Этап 3

1. Разработан новый метод глобальной оптимизации, основанный на редукции с помощью кривой Пеано многомерной задачи с липшицевой целевой функцией к решению одномерной задачи оптимизации с функцией, удовлетворяющей условию Гёльдера. Алгоритм вместо единой константы Гёльдера использует семейство оценок константы (множественные константы), что позволяет более точно оценивать поведение целевой функции. Разработана модификация метода, автоматически сочетающая в себе глобальную фазу поиска новых перспективных решений с локальной фазой уточнения текущего лучшего решения, которая также производится на кривой, что ускоряет поиск глобального решения. Дано теоретическое обоснование сходимости метода. Приведены результаты численных экспериментов по сравнению предложенного метода с рядом известных методов глобального поиска на тестовых функциях GKLS-генератора многомерных многоэкстремальных задач оптимизации.
2. Предложена новая методология сравнения детерминированных и стохастических глобальных алгоритмов оптимизации, получившая название «метод операционных зон». Данная техника является обобщением метода операционных характеристик, широко используемого  для сравнения детерминированных методов глобальной оптимизации, но неприменимого для алгоритмов  стохастической оптимизации.  Дано теоретическое описание метода операционных зон и приведены примеры его использования для сравнения детерминированных алгоритмов Липшицевой глобальной оптимизации с эвристическими популяционными методами поиска глобального минимума.
3. Проведено масштабное численное сравнение одномерных детерминированных липшицевых и стохастических популяционных методов глобальной оптимизации. Системное сравнение методов данных классов является новым элементом, поскольку ранее такого сравнения между ними не проводилось, методы сравнивались только внутри своих классов.
4. Предложены новые планарные методы, предотвращающие вырождение метода сопряженных градиентов за счет использования вычислений с бесконечно малыми величинами.
5. Для решения задач лексикографического многокритериального линейного программирования (LMOLP) предложен подход, который вместо решения семейства линейных задач или скаляризации критериев, требующей трудоемкого подбора весов свертки, конструирует однокритериальную задачу, решение которой позволяет получить решение задачи LMOLP. Теоретически доказано эквивалентность исходной многокритериальной и конструируемой однокритериальной задачи. Предложен численный алгоритм для построения оптимальной свертки, описана его реализация и приведены результаты численных экспериментов.
6. Установлено свойство строгой однородности нескольких одномерных алгоритмов глобальной оптимизации, предотвращающих плохую обусловленность масштабированной задачи при очень малых или очень больших константах масштабирования.
7. Разработан алгоритм негладкой безусловной оптимизации на основе метода переменной метрики D-Bundle, в котором в отличие от метода-прототипа матрица, определяющая метрику, всегда является хорошо обусловленной. Получены результаты численных экспериментов, иллюстрирующие преимущества предложенного подхода.
8. Предложен новый тестовый класс многомерных условных оптимизационных задач с непрерывно-дифференцируемыми многоэкстремальными целевыми функциями и нелинейными ограничениями для экспериментального анализа алгоритмов глобального поиска. Реализована программная система, обеспечивающая построение задач данного класса.
9. Построен параллельный алгоритм многомерной глобальной безусловной оптимизации на основе адаптивной многошаговой схемы редукции размерности. Разработана программная реализация параллельной адаптивной схемы, ориентированная на суперкомпьютерные вычислительные системы, в том числе системы, использующие вычислительные ускорители (типа графических процессоров общего назначения). Получены результаты экспериментального тестирования, продемонстрировавшие значительное ускорение вычислений адаптивной параллельной схемы по сравнению с ее чисто последовательной версией.
10. Предложен новый многомерный алгоритм условной оптимизации, комбинирующий адаптивную многошаговую схему с индексным методом учета ограничений. Алгоритм ориентирован на решение задач с липшицевой целевой функцией и липшицевыми ограничениями, которые могут быть нелинейными и невыпуклыми и порождать области сложной конфигурации, в том числе неодносвязные. Разработана программная система, реализующая вычислительную схему алгоритма. Получены результаты эксперимента, свидетельствующие о существенном превосходстве предложенного алгоритма по сравнению с использованием традиционного способа учета ограничений – метода штрафных функций.
11. Получены результаты сравнительной оценки эффективности методов, основанных на разных подходах к редукции размерности: классической многошаговой схемы, адаптивной схемы и редукции размерности на основе кривых Пеано. В рамках исследования предложен новый метод, сочетающий многошаговую схему редукции с известным методом ломаных, и теоретически обоснована его сходимость к глобальному минимуму многомерной задачи. По результатам эксперимента построены операционные характеристики сравниваемых методов, продемонстрировавшие эффективность методов на основе адаптивной схемы редукции.
12. Предложен новый подход рекуррентного многоуровневого разбиения графов, ориентированный на применение в сложных сетевых структурах, включая нейронные, и основанный на идеях табу-поиска. Новизна подхода состоит во включении в табу-поиск метапараметров, обеспечивающих гибкую самонастройку как элемент машинного обучения алгоритма в зависимости от индивидуальных характеристик решаемой задачи, в сочетании с рекуррентной многоуровневой процедурой разбиения графа (многоуровневый  реактивно-рандомизированный табу-поиск).  Получены результаты вычислительного эксперимента по решению задач из классического бенчмарк-репозитория, подтвердившие эффективность предложенного подхода.
13. Обобщены свойства задач низкоранговой аппроксимации в оптимизационной постановке, проведено качественное сравнение подходов к исследованию моделей низкоранговой аппроксимации как оптимизационных задач.
14. Для широкого класса алгоритмов глобального случайного поиска (ГСП) получены общие условия сходимости к глобальному оптимуму и установлена их выполнимость для различных подклассов методов ГСП. Получены оценки скорости сходимости для алгоритмов ГСП с независимыми испытаниями (вычислениями целевой функции) и вероятностным распределением проведения испытаний, одинаковом на каждом шаге поиска, а также оценки скорости сходимости для общего случая.
15. Для методов глобального случайного поиска определена точность статистических оценок глобального минимума в случае больших размерностей. Установлены асимптотические свойства оптимальных статистических оценок в алгоритмах глобального случайного поиска, когда размер допустимой области стремится к бесконечности. Проведен численный эксперимент, результаты которого подтвердили асимптотическое поведение, установленное аналитически.
16. 19-21 июня 2017 г. в Нижегородском государственном университете им. Н.И.Лобачевского проведена международная конференция “Learning and Intelligence OptimizatioN” (LION11) с участием 36 российских ученых (из них 16 молодых ученых) и 35 зарубежных ученых. В издательстве Springer издан сборник трудов конференции.
17. С 7 по 10 сентября 2017 г. в Нижегородском государственном университете им. Н.И.Лобачевского проведена школа молодых ученых “Высокопроизводительные вычисления, оптимизация и приложения” с приглашением в качестве лекторов ведущих российских и зарубежных ученых по тематике проекта. В пленарной программе школы сделано 6 докладов известными зарубежными учеными и 10 докладов российскими учеными. Наряду с лекциями проведены практические и лабораторные занятия по 3 направлениям (трекам).
18. В международном издательстве Springer опубликовано две монографии и одна монография в том же издательстве принята к опубликованию.

19. Подготовлены к изданию 17 статей, из них 16 опубликованы и 1 принята к опубликованию. 14 статей опубликованы в международных журналах, индексируемых в Web Of Science и/или Scopus. Из числа опубликованных работ 7 публикаций проиндексированы в Web of Science, 12 работ проиндексированы в базе данных Scopus. На международных конференциях было сделано 4 пленарных и 8 секционных докладов, проведен один тьюториал. На молодежной научной школе, проведенной в соответствии с планом работ 2017 года, участниками проекта прочитано 3 лекции для молодых ученых, аспирантов и студентов.

Результаты выполнения проекта в целом

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

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

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

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

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

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

8. Разработаны обобщения адаптивной многошаговой схемы редукции размерности на класс характеристических алгоритмов оптимизации. В рамках общей схемы рассмотрен многомерный алгоритм, сочетающий адаптивную схему с одним из характеристических алгоритмов – методом ломаных. Для данного метода дано теоретическое обоснование его сходимости к глобальному минимуму многомерной задачи с липшицевой целевой функцией.
9. Разработан эффективный алгоритм решения многоиндексной целочисленной транспортной задачи, основанный на редуцировании задачи к задаче поиска потока минимальной стоимости в сети древовидной структуры. Получены необходимые и достаточные условия редуцирования, оценки вычислительной сложности.
10. Предложен новый многомерный алгоритм условной оптимизации, комбинирующий адаптивную многошаговую схему редукции размерности с индексным методом учета ограничений, предназначенный для решения задач глобальной оптимизации в областях сложной конфигурации (невыпуклых, неодносвязных)
11. Предложен новый подход к решению задач лексикографического многокритериального линейного программирования, связанный с конструированием эквивалентной скалярной задачи, реализующей оптимальную свертку критериев.
12. Разработан алгоритм негладкой безусловной оптимизации на основе метода переменной метрики D-Bundle, в котором в отличие от метода-прототипа матрица, определяющая метрику, всегда является хорошо обусловленной. Получены результаты численных экспериментов, иллюстрирующие преимущества предложенного подхода.
13. Решены прикладные задачи, связанные с оптимизацией кавитационных явлений, возникающих при движении поршня в замкнутой трубе, заполненной жидкостью, и с восстановлением зашумленного сигнала набором затухающих синусоид.
14. Предложена новая схема блочной вложенной оптимизации, сочетающая идеи редукции классической многошаговой схемы оптимизации и редукции на основе кривых, заполняющих пространство. Проведено обобщение блочной схемы на параллельный случай.

15. Выполнена программная реализация блочной схемы в системе глобальной оптимизации ExaMin, которая поддерживает как режим последовательного, так и параллельного выполнения на гетерогенных суперкомпьютерных архитектурах.Система ExaMin апробирована на суперкомпьютере «Лобачевский» с использованием графических ускорителей и приняла участие в международного конкурсе солверов задач глобальной оптимизации GENeralization-based challenge in global OPTimization (GENOPT) , где заняла 1-е место по числу решенных задач и 3-е в общем зачете, что свидетельствует о высокой конкурентоспособности разработанных в рамках проекта методов глобальной оптимизации.

16. Выполнено обобщение адаптивной многошаговой схемы редукции размерности на параллельный случай и проведена экспериментальная апробация метода.
17. Разработан новый тестовый класс многомерных условных оптимизационных задач с непрерывно-дифференцируемыми многоэкстремальными целевыми функциями и нелинейными ограничениями для экспериментального анализа алгоритмов глобального поиска. Реализована программная система, обеспечивающая построение задач данного класса.
18. Предложена новая методология сравнения детерминированных и стохастических глобальных алгоритмов оптимизации, получившая название «метод операционных зон».
19. По методу операционных зон проведено представительное численное сравнение одномерных детерминированных липшицевых и стохастических популяционных методов глобальной оптимизации.
20. Для широкого класса алгоритмов глобального случайного поиска (ГСП) получены общие условия сходимости к глобальному оптимуму и установлена их выполнимость для различных подклассов методов ГСП. Определена точность статистических оценок глобального минимума в случае больших размерностей и установлены асимптотические свойства оптимальных статистических оценок.
21. В рамках спектрально-сингулярного анализа временных рядов выполнено теоретическое исследование методов аппроксимации, порождающих оптимизационные задачи на основе построения траекторных матриц с возможно более низким рангом (задачи низкоранговой аппроксимации). Для решения задач данного класса при использовании аппроксимирующих матриц Ганкеля построены методы глобального поиска с гарантированными оценками, изучено их поведение и проведено сравнение с другими оптимизационными алгоритмами.
22. Выполнен анализ методов одновременного конструирования для случая коррелированных наблюдений, в которых аппроксимируются лучшие возможные пары «проектирование плюс оценочная функция» в задаче линейной регрессии.
23. Проведено исследование алгоритмов стохастического локального поиска для обучения нейронных сетей с функциями пороговой активации. Предложен новый метод, названный Бинарным Машинным Обучением (БМО), который превосходит современные техники.
24. Разработан и исследован новый алгоритм обучения нейронных сетей (бинарной обучающей машины), основанный на многомасштабном стохастическом локальном поиске с двоичным представлением.
25. Предложен новый подход рекуррентного многоуровневого разбиения графов, ориентированный на применение в сложных сетевых структурах, включая нейронные, и основанный на идеях табу-поиска и реактивной рандомизации.
26. В рамках проекта 19-21 июня 2017 г. в Нижегородском государственном университете им. Н.И. Лобачевского проведена международная конференция “Learning and Intelligence OptimizatioN” – LION 11 (“Машинное обучение и интеллектуальная оптимизация”). Подготовлен сборник трудов конференции, опубликованный в международном издательстве Springer.
27. Проведены 3 молодежных научных школы “Высокопроизводительные вычисления, оптимизация и приложения- 2015, 2016, 2017” для аспирантов, стажеров, студентов, молодых ученых из различных университетов и научных учреждений России. На каждой конференции прочитано не менее 5 лекций известными зарубежными учеными и не менее 10 лекций ведущими российскими учеными. Наряду с пленарными заседаниями проводились практические и лабораторные занятия по нескольким направлениям (трекам).
28. В международном издательстве Springer опубликовано две монографии и одна монография принята к опубликованию в том же издательстве.
29. По результатам исследований проекта опубликовано 49 статей, одна статья принята к опубликованию. 47 статей опубликованы в международных журналах и сборниках, индексируемых в Web Of Science и/или Scopus. К моменту представления отчета проиндексировано 36 статей в Web Of Science и 44 статьи в Scopus.
30. На международных конференциях за период выполнения проекта было сделано 40 докладов. На молодежных школах члены научного коллектива проекта прочитали 11 лекций.
31. Информационные ресурсы в сети Интернет

Cайт конференции LION11:    http://intelligent-optimization.org/lion11/

Cайты молодежных школ:

        http://agora.guru.ru/display.php?conf=hpc2015

        http://agora.guru.ru/display.php?conf=hpc2016

        http://agora.guru.ru/display.php?conf=hpc2017

План работ проекта реализован полностью, все показатели, предусмотренные Соглашением, достигнуты.