Аннотация результатов, полученных в 2016 году
Целью выполнения проекта «Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности» является разработка интегрированной системы моделей, методов и программных средств для исследования сложных проблем рационального выбора, формулируемых как задачи многокритериальной многоэкстремальной оптимизации. Указанные задачи имеют общий характер и широко распространены в приложениях (оптимальное проектирование, идентификация параметров и др.) и обладают высокой вычислительной трудоемкостью. Новизна проводимых исследований определяется: • ориентированностью на наиболее сложные задачи оптимального выбора и разработкой общей математической модели задач поиска оптимальных (наилучших) вариантов для подобных задач, • включением в модель выбора принципиально важной возможности изменения постановки задачи в процессе вычислений, • разработкой схем параллельных вычислений, эффективно масштабируемых вплоть до использования сотен тысяч вычислительных ядер, • расширением класса решаемых задач за основе использования вычислительного потенциала современных суперкомпьютерных систем. В 2016 г. при выполнении первого этапа проекта были получены следующие научные результаты. 1. Разработана общая модель выбора наилучших вариантов в задачах принятия решений, которая: a. объединяет различные постановки оптимизационных задач (с линейными, выпуклыми и невыпуклыми функционалами, многокритериальные задачи, задачи многопараметрической оптимизации), b. обеспечивает более адекватное моделирование процессов принятия решений для сложных задач выбора оптимальных вариантов, допуская возможность корректировки постановки решаемых задач при изменении представлений об оптимальности. Подобное расширение общности модели оптимального выбора приводит к значительному повышению ее вычислительной сложности. 2. Сформулирован новый класс задач многократного глобального поиска, порождаемых при решении проблем оптимального выбора. Множество задач глобального поиска возникают в силу необходимости поиска нескольких различных вариантов, при изменении постановок решаемых задач. 3. Определены необходимые требования к методам и программным системам решения задач многократного глобального поиска для обеспечения возможности практического применения разработанной общей модели оптимального выбора. 4. Предложен новый метод для решения задач многократного глобального поиска как развитие многомерного обобщенного алгоритма глобального поиска, разработанного ранее Р.Г. Стронгиным. Решающие правила метода были модифицированы таким образом, чтобы сохранились все его ранее доказанные свойства, и метод можно было бы применять для решения нескольких задач одновременно. 5. Доказана равномерная сходимость предложенного алгоритма решения задач многократного глобального поиска. Одновременно с этим установлено свойство равномерного распределения вычислительной нагрузки между отдельными процессорами/ядрами вычислительной системы при параллельном решении серии задач оптимизации. 6. Разработана вычислительная схема повторного использования поисковой информации, получаемой в ходе вычислений при решении серии задач глобальной оптимизации. Как показали результаты выполненных экспериментов, использование поисковой информации может существенно сократить объем требуемых вычислений для решения задач многокритериальной оптимизации. 7. В процессе выполнения первого этапа проекта был разработана параллельная система Globalizer Lite, которая предназначена для решения задач многомерной глобальной оптимизации. Метод решения основан на редукции размерности с использованием разверток многомерной области поиска на одномерный отрезок. Указанная редукция выполняется с использованием взаимно-однозначных отображений типа кривой Пеано. Система ориентирована на системы с распределенной памятью (реализация выполнена с использованием библиотеки MPI). Постановка задачи оптимизации с точки зрения пользователя системы состоит в подключении динамической библиотеки, в которой должна быть реализована оптимизируемая функция. В целом система представляет собой кроссплатформенное (Windows, Linux) консольное приложение. Система Globalizer использовалась для практической оценки эффективности параллельного решения оптимизационных задач с использованием аппарата операционных характеристик. 8. Предложен и реализован метод решения задач оптимизации, основанный на построении поверхностей отклика. В методе используются метамодели, построенные по подпространствам меньшей размерности (по сравнению с исходной задачей). Размерности подпространств, в которых строятся метамодели, являются разными для разных вычислительных моделей и основаны на разбиении множества варьируемых параметров. Выбор конкретного подмножества зависит от варьируемых параметров, являющихся определяющими для отклика модели. Достоинством метода является то, что уменьшается размерность подзадач, в которых строится аппроксимация, и общие вычислительные затраты для построения аппроксимации также уменьшаются. Метод использует локальную зависимость переменных для каждой оптимизационной подзадачи. Полученные результаты являются основой для проведения дальнейших исследований: (1) решение сложных задач оптимального проектирования (2) обобщение метода для многокритериальных задач. Результаты выполнения проекта отражены в 10 публикациях, из которых: - 7 работ в изданиях, индексируемых в Web of Science и/или Scopus (5 опубликованы и 2 приняты к публикации). - 3 работы в изданиях, индексируемых РИНЦ. Информация о проекте представлена на сайте http://hpc-education.unn.ru/исследования/гранты/принятие-решений

Аннотация результатов, полученных в 2017 году
Целью выполнения проекта «Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности» является разработка интегрированной системы моделей, методов и программных средств для исследования сложных проблем рационального выбора, формулируемых как задачи многокритериальной многоэкстремальной оптимизации. Указанные задачи имеют общий характер и широко распространены в приложениях (оптимальное проектирование, идентификация параметров и др.) и обладают высокой вычислительной трудоемкостью. Новизна проводимых исследований определяется: • ориентированностью на наиболее сложные задачи оптимального выбора и разработкой общей математической модели задач поиска оптимальных (наилучших) вариантов для подобных задач, • включением в модель выбора принципиально важной возможности изменения постановки задачи в процессе вычислений, • разработкой схем параллельных вычислений, эффективно масштабируемых вплоть до использования сотен тысяч вычислительных ядер, • расширением класса решаемых задач на основе использования вычислительного потенциала современных суперкомпьютерных систем. В 2017 г. при выполнении второго этапа проекта были получены следующие научные результаты. 1. Предложен подход к решению задач многокритериальной оптимизации, обеспечивающий снижение вычислительных затрат за счет повторного использования всей поисковой информации, получаемой в процессе решения задачи. В рамках данного подхода разработан параллельный алгоритм, основанный на свертке критериев и приведении всей имеющейся поисковой информации (т.е. точек итераций и значений частных критериев, вычисленных в них) к значениям скалярного критерия очередной решаемой скалярной задачи нелинейного программирования. В результате подобного пересчета величин, без каких-либо трудоемких вычислений при переходе к решению очередной скалярной подзадачи уже будет иметься накопленная ранее поисковая информация, которую может использовать алгоритм, решающий скалярную задачу. Доказано, что построенный алгоритм является устойчивым; дана верхняя оценка числа итераций, требующихся для решения очередной скалярной подзадачи. Проведены вычислительные эксперименты на суперкомпьютере «Лобачевский», подтверждающие теоретические положения. 2. Разработана эффективная структура хранения поисковой информации, основанная на страничном принципе организации памяти. При таком подходе используемая оперативная память (ОП) и внешняя память (ВП) разделяются на непрерывные участки (страницы) фиксированного (одинакового) размера. Обработка поисковой информации выполняется только для тех блоков, которые располагаются в страницах ОП. Если блок, требующий обработки, располагается в ВП, то он сначала перемещается в ОП. При этом ОП может быть переполнена (все страницы ОП заняты), и в этом случае часть блоков из ОП должна быть переписана обратно в ВП. Разработана стратегия замещения, ориентированная на минимизацию обменов блоков между ВП и ОП. Введение блочного представления накопленной поисковой информации позволяет свести глобальные операции по ее обработке к локальной обработке отдельных блоков. 3. Разработана схема эффективного использования гетерогенных вычислительных ресурсов современных суперкомпьютеров для решения задач глобальной оптимизации. Предложенный подход основан на блочно-рекурсивной схеме редукции размерности, сочетающей использование кривых Пеано и схему вложенной оптимизации. Блочно-рекурсивная схема является весьма гибкой: можно варьировать количество процессоров, применять различные параллельные методы поиска, а также использовать различные виды вычислительных устройств на различных уровнях рекурсии. 4. Проведено теоретическое исследование разработанной схемы использования поисковой информации при решении задач многокритериальной оптимизации, получена верхняя оценка числа итераций, требующихся для решения очередной скалярной подзадачи, которая показывает, что при достижении достаточно высокой плотности испытаний в интервалах области поиска за счет повторного использования поисковой информации при решении очередных подзадач количество дополнительных итераций будет постоянно уменьшаться. 5. Разработан прототип параллельной программной системы Globalizer, предназначенной для решения задач глобальной оптимизации на суперкомпьютерных системах. Реализованы следующие основные блоки системы Globalizer: - Блок вычисления значений функционалов (критериев и ограничений) решаемой задачи оптимизации (осуществляет взаимодействие между внешним вычислителем и Globalizer в соответствии с установленным интерфейсом); - Подсистема оптимизации, которая обеспечивает решение задач глобального поиска, нелинейного программирования, многокритериальной оптимизации и общих задач оптимального выбора (обеспечивает последовательную схему взаимодействия реализованных в ней компонент – задачи оптимального выбора решаются с использованием блока многокритериальной оптимизации, который, в свою очередь, использует блок нелинейного программирования, и т.д.) - Блок накопления и обработки поисковой информации; - Блок редукции размерности (использует комбинированную схему, сочетающую редукцию размерности с использованием кривых, заполняющих пространство, и редукцию по схеме вложенной оптимизации); - Блок управления параллельными процессами при выполнении глобального поиска (обеспечивает, в том числе, распределение процессов между вычислительными элементами, проводит балансировку вычислительной нагрузки, и т.п.); - Набор средств для визуальной демонстрации результатов глобального поиска. 6. Проведена экспериментальная оценка эффективности разработанных алгоритмов глобального поиска с использованием системы Globalizer (указанные методы вошли в ее алгоритмическое наполнение). При проведении экспериментов было одновременно задействовано 32 узла кластера, на каждом из которых установлено по 3 ускорителя NVIDIA Kepler K20Х (2688 потоковых процессора). Таким образом, всего было задействовано более 250 тысяч вычислительных ядер с суммарной производительностью 115.8 TFlop/s. 7. Разработан параллельный алгоритм для решения задач оптимизации большой размерности, основанный на построении метамоделей критериев и ограничений. Данный метод является итерационным и основан на решении серии вспомогательных задач, аппроксимирующих исходную задачу. Аппроксимированная задача формируется на основе метамоделей критериев и ограничений, построенных в доверительной области, т.е. подобласти исходной области изменения параметров, в которой построенные метамодели считаются корректными. Были разработаны новые способы построения метамоделей, основанные на идеях кригинга. Также была предложена стратегия изменения доверительной области, которая может учитывать численные погрешности и случайные сбои в процессе моделирования, необходимого для вычисления значений критериев и ограничений. Проведено исследование эффективности программной реализации построения метамоделей и решения аппроксимированных задач, выделены (с использованием инструмента анализа Intel VTune Amplifier XE) и распараллелены наиболее трудоемкие операции алгоритма. Эффективность параллельного алгоритма была оценена на классической тестовой задаче оптимального проектирования – минимизации объема балки, состоящей из набора прямоугольных элементов. Число параметров варьировалось от 100 до 1000, число ограничений – от 200 до 2000. Результаты выполнения проекта отражены в 20 публикациях, из которых: - 17 работ в изданиях, индексируемых в Web of Science и/или Scopus. - 3 работы в изданиях, индексируемых РИНЦ. Информация о проекте представлена на сайте http://hpc-education.unn.ru/исследования/гранты/принятие-решений

Аннотация результатов, полученных в 2018 году
Целью выполнения проекта «Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности» является разработка интегрированной системы моделей, методов и программных средств для исследования сложных проблем рационального выбора, формулируемых как задачи многокритериальной многоэкстремальной оптимизации. Указанные задачи имеют общий характер и широко распространены в приложениях (оптимальное проектирование, идентификация параметров и др.) и обладают высокой вычислительной трудоемкостью. Новизна проводимых исследований определяется: - ориентированностью на наиболее сложные задачи оптимального выбора и разработкой общей математической модели задач поиска оптимальных (наилучших) вариантов для подобных задач, - включением в модель выбора принципиально важной возможности изменения постановки задачи в процессе вычислений, - разработкой схем параллельных вычислений, эффективно масштабируемых вплоть до использования сотен тысяч вычислительных ядер, - расширением класса решаемых задач на основе использования вычислительного потенциала современных суперкомпьютерных систем. В 2018 г. при выполнении третьего этапа проекта были получены следующие научные результаты. 1. Разработана математическая модель задач принятия решений, которая охватывает многие существующие постановки оптимизационных задач, включая задачи глобальной оптимизации, задачи нелинейного программирования, задачи многокритериальной оптимизации с ограничениями. В рамках разработанной модели выбранная постановка задачи принятия решений может быть уточнена при изменении требований к оптимальности. Например, в случае избыточности набора частных критериев может оказаться целесообразным перевод части критериев в ограничения. Или, наоборот, при получении малой допустимой области может потребоваться ослабление допусков или перевод части ограничений в критерии и т.д. При выполнении работ по проекту в 2018 г. разработанная модель расширена возможностью одновременного формулирования и решения множества задач многокритериальной оптимизации, которое может меняться в ходе вычислений за счет добавления новых или удаления уже существующих задач. Решение сформированного множества задач может выполняться последовательно либо одновременно в режиме разделения времени или параллельно при наличии нескольких вычислительных устройств. Разработанный в рамках проекта подход – общая модель задач принятия решений, возможность изменения постановки задачи в ходе вычислений, формирование множества одновременно решаемых задач – является новым и позволяет адекватно моделировать процессы выбора оптимальных вариантов в разных областях приложений науки и техники. 2. Исследован параллельный алгоритм построения равномерной аппроксимации множества слабоэффективных точек в задачах многокритериальной оптимизации. Основной проблемой при использовании известных методов скаляризации (основанных на идее свертки критериев) является отсутствие гарантии полного покрытия множества эффективных (множества Парето) или же множества слабо-эффективных (множества Слейтера) вариантов на широком классе задач, в том числе с многоэкстремальными критериями. Метод, обладающий равномерной сходимостью к множеству Слейтера для задач липшицевой многокритериальной оптимизации, был разработан Р.Г. Стронгиным на основе информационно-статистического подхода. Была обоснована схема скаляризации многокритериальной задачи, при использовании которой множество слабо-эффективных решений исходной задачи будет совпадать с множеством глобально-оптимальных решений редуцированной скалярной задачи. Метод решения возникающей скалярной задачи основан на информационно-статистическом алгоритме глобального поиска (при решении задач без ограничений) или индексном алгоритме (при решении задач с ограничениями). Указанные методы принадлежат классу характеристических алгоритмов, что позволяет применить технику распараллеливания, основанную на выборе наиболее перспективных подмножеств области поиска и параллельном проведении очередных итераций в данных подмножествах. Вычислительные эксперименты с параллельным алгоритмом, проведенные на наборах тестовых задач многокритериальной оптимизации, показали ускорение, близкое к линейному (по числу вычислений значений оптимизируемых критериев). 3. Детально проработана модель информационного сопровождения процесса решения задач многокритериальной оптимизации. Разработанная модель ориентирована на повторное использование и оптимальное хранение поисковой информации, получаемой в процессе вычислений. При решении сложных задач выбора оптимальных вариантов объем поисковой информации является значительным (сотни гигабайт). Для обеспечения эффективного хранения и обработки данных такого объема разработан блочный способ представления поисковой информации. Такой подход позволяет свести глобальные процедуры анализа данных к локальным операциям обработки отдельных небольших блоков поисковой информации. Блочное представление позволяет использовать для хранения поисковой информации внешнюю память практически неограниченного объема, а в оперативной памяти размещать только небольшое число блоков, которые необходимы для выполнения обработки поисковой информации в каждый текущий момент времени. Хранение поисковой информации с использованием внешней памяти повышает надежность вычислений и позволяет организовать приостановку вычислений с возможностью последующего продолжения. Проведены вычислительные эксперименты на суперкомпьютере «Лобачевский», подтверждающие высокую эффективность предложенной модели обработки поисковой информации. 4. Продолжено развитие семейства методов решения задач многократного многокритериального глобального поиска. Используемые алгоритмы разработаны в рамках информационно-статистической теории глобального поиска и обеспечивают эффективное решение всего спектра задач, рассматриваемых в рамках проекта (задачи многокритериальной оптимизации, нелинейного программирования с невыпуклыми ограничениями, глобальной оптимизации). Семейство алгоритмов образует единую вычислительную схему решения задач многократного многокритериального глобального поиска, что позволяет организовать эффективное повторное использование всей поисковой информации, получаемой в процессе вычислений. Повторное использование поисковой информации дает основу для преодоления существенного возрастания вычислительной сложности при вариации постановок решаемых задач за счет продолжения глобального поиска с учетом всех предыдущих вычислений. Разработанные вычислительные схемы повторного использования поисковой информации теоретически обоснованы. Построены оценки сокращения объема вычислений при многократном решении задач многокритериальной оптимизации. Показаны условия достаточности поисковой информации, когда при смене постановок решаемых задач объема поисковой информации оказывается достаточно для получения оценок оптимальных вариантов без проведения каких-либо дополнительных вычислений. Результаты опубликованы в Journal of Global Optimization (doi: 10.1007/s10898-018-0624-3). 5. В рамках проекта рассматриваются задачи принятия решений, математическими моделями которых являются вычислительно-трудоемкие задачи глобальной оптимизации. Для численного решения задач указанного класса объем необходимых вычислений достигает петафлопсного уровня даже при сравнительно небольшом количестве варьируемых переменных. Для решения подобных задач на суперкомпьютерных системах рекордной производительности предложены обобщенные вычислительные схемы, в рамках которых могут быть использованы многие эффективные параллельные алгоритмы глобальной оптимизации. Разработанные схемы включают различные способы многоуровневой декомпозиции параллельных вычислений, что обеспечивает возможность эффективного применения для решения задач глобальной оптимизации систем с общей и распределенной памятью, а также с использованием ускорителей вычислений, с большим количеством (десятки и сотни тысяч) ядер/процессоров. Описание вычислительных схем параллельных алгоритмов для трудоемких задач глобальной оптимизации представлено в Lobachevskii Journal of Mathematics (doi: 10.1134/S1995080218040133). Для апробации разработанного подхода проведены масштабные вычислительные эксперименты на высокопроизводительных суперкомпьютерных системах (с использованием более 250 тысяч вычислительных ядер). 6. Разработана параллельная программная система Globalizer, предназначенная для решения задач глобальной оптимизации на современных суперкомпьютерах с гетерогенной архитектурой. Система Globalizer реализует предложенную в рамках проекта общую схему параллельного решения задач глобально-оптимального выбора с использованием широкого спектра вычислительных систем: с общей и распределенной памятью, графическими процессорами NVIDIA и сопроцессорами Intel Xeon Phi. Система Globalizer может использоваться в двух разных вариантах: - Вариант GlobalizerPro является исследовательской версией системы, обеспечивает полный набор возможностей и ориентирован на решение наиболее сложных задач оптимального выбора. - Вариант GlobalizerLite представляет собой ограниченную версию системы, доступен для свободного использования для решения задач среднего уровня сложности. Описание программной системы представлено в журнале Numerical Algebra, Control and Optimization (doi: 10.3934/naco.2018003). Результаты выполнения проекта отражены в 12 публикациях, индексируемых в Web of Science и/или Scopus, и 1 публикации, индексируемой РИНЦ. Информация о проекте представлена на сайте http://hpc-education.unn.ru/исследования/гранты/принятие-решений.