КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер 21-71-30005

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

РуководительРайгородский Андрей Михайлович, Доктор физико-математических наук

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

Период выполнения при поддержке РНФ

2021 г. - 2024 г.

Конкурс№53 - Конкурс 2021 года по мероприятию «Проведение исследований научными лабораториями мирового уровня в рамках реализации приоритетов научно-технологического развития Российской Федерации» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными.

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-203 - Теория оптимизации и исследование операций

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

Код ГРНТИ27.41.00

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Подавляющее большинство практически важных задач управления, обратных задач, задач обучения являются невыпуклыми. Как следствие, с точки зрения теоретической возможности их эффективного решения в общем случае не существует более эффективных методов, чем алгоритмы переборного типа (Немировский-Юдин, 1979). Тем не менее, как правило, для каждого конкретного класса задач можно предложить что-то лучше, чем просто перебор. В частности, довольно популярное направление связано с подменой исходной сложной (например, NP-трудной) задачи оптимизации похожей, более простой (например, выпуклой), задачей, решение которой является неплохим приближением к решению исходной задачи. Особенно, это направление популярно в сообществе специалистов по Computer Science (SDP-релаксации и т.п.). Однако в последние годы предпринимаются попытки перенести эту идею и на задачи синтеза управлений (Поляк-Фатхуллин, 2020) и на классические задачи машинного обучения (кластеризация, Ю.Е. Нестеров, 2018). Другими словами, в проекте планируется уделить значительное внимание проработке вопросов, связанных с тем, как именно ставить сами задачи оптимизации, которые необходимо решать, чтобы решения этих задач были хорошим приближением к решениям исходных задач (вообще говоря, не задач оптимизации): обратных задач, задач управления, обучения и т.д. Современные требования к точности и эффективности решения задач (связанные с тиражируемостью технологий и возможностью их переноса на различные мобильные устройства/приборы) подразумевают не только принципиальную (теоретическую) возможность получить достаточно точное решение, но и задают достаточно жесткие временные (ресурсные) рамки на то, насколько это может быть затратно. Последнее обстоятельство критическим образом заставляет взглянуть на то, каким образом далее стоит решать полученную задачу оптимизации. Собственно, вторая часть направлений исследований в проекте как раз и сосредотачивается вокруг чисто вычислительных вопросов, связанных с классами задач оптимизации, возникающих при сведении исходных постановок к задачам оптимизации. Далее мы опишем немного подробнее, на каких именно вопросах планируется сосредотачиваться. Любой численный метод (например, градиентного спуска) использует информацию о целевой функции (ограничениях). Как правило, это градиент целевой функции. Философия автоматического дифференцирования (в машинном обучении “обратного распространения”) позволяет для широкого класса задач (в которых имеется “дерево вычислений” целевого функционала) вычислять градиент за время, не превышающее более чем в пять раз время вычисления значения функции. Эта философия эффективно используется сейчас в различных оптимизационных пакетах, заточенных под задачи машинного обучения (например, Pytorch или TensorFlow). В проекте планируется использовать эту философию для значительно более общего и сложного класса задач оптимизации. В частности, задач оптимизации в бесконечномерных пространствах (пространствах функций - управлений, синтеза и т.п.), возникающих при решении задач оптимального управления и обратных задач. Нетривиальность тут, в частности, в том, что не понятно в общем случае, когда лучше дискретизировать задачу (сводить ее к конечномерной задаче оптимизации) - изначально или только в момент вычисления градиента. Это фундаментальный вопрос, на который (насколько нам известно) на данный момент нет общего (универсального) ответа. Нет и теории, объясняющей в достаточной общности, как в зависимости от класса задач следует действовать. Тем не менее, есть многолетний опыт (Ю.Г. Евтушенко и др.), который планируется использовать в проработке данных вопросов. Предполагается изучить, в каких случаях удобнее и эффективнее проводить дискретизацию задачи для ее прямой или двойственной формулировки таким образом, чтобы при необходимости ветвления одной из задач на подзадачи меньшей размерности можно было использовать эффективные правила ветвления по строго положительным теневым ценам (shadow prices). Для вычислительно труднорешаемых (NP-трудных)задач будет построена теория приближения исходных данных труднорешаемой задачи ее полиномиально (эффективно) решаемыми частными случаями. Такая теория позволит прогнозировать завершение поиска решения, приближенного к оптимальному, с помощью классических алгоритмов, например, ветвей и границ, с заданными до решения задачи точностью и временем вычислений (см. B. Goldengorin, P.M. Pardalos. Data Correcting Approaches in Combinatorial Optimization. Springer, 2012). Другое важное направление связано с разработкой адаптивных (самонастраивающихся) численных методов. Самонастройка может проходить: 1) за счет вспомогательной одномерной (маломерной) минимизации, как это имеет место в методах типа наискорейшего спуска (сопряженных градиентов и их обобщений А.С. Немировским (1981), BFGS и т.п.) - в таких подходах важную роль играет эффективность и точность процедуры одномерного поиска; 2) за счет правил адаптивного выбора размера шага метода по предписанной формуле (Поляк-Шор, Барзелай-Борвейн, Мищенко-Малицкий и т.д.); 3) за счет внутреннего цикла, основанного на проверке некоторых условий типа Армихо, Вульфа, Нестерова. Общая идея таких правил (из пп. 2), 3)): связь размера шага с константами гладкости целевого функционала, оценка констант гладкости по текущей и предыдущей итерации по вычисленным значениям функций и градиента на них. В контексте рассматриваемого в проекте класса задач управления, обратных задач, насколько нам известно, системное сопоставление отмеченных адаптивных подходов, равно как и их непосредственная адаптация под возникающие задачи оптимизации, в нужном объеме пока не производилась. Более того, ряд постановок задач управления и, особенно, обучения с подкреплением, по сути своей являются задачами в условиях неопределенности шума (случайного и даже враждебного), параметры которого могут меняться (в том числе враждебным образом) по мере процесса решения задачи (онлайн оптимизация). Для решения таких задач адаптивность (понимаемая сейчас уже в более общем ключе, чем описано выше) используемого подхода обусловлена не только желанием сделать метод более эффективным, но и является требованием к возможности его практического использования. Собственно, разработка онлайн алгоритмов, способных “отслеживать” изменения самой задачи по ходу ее решения - является популярным направлением исследований у специалистов по машинному обучению. Разработано много эффективных и универсальных процедур онлайн обучения (см., например, недавние обзоры F. Orabona 2019 и E. Hazan 2016) в приложении к задачам машинного обучения. В проекте планируется распространить (адаптировать) современные достижения онлайн обучения на задачи синтеза управлений в том числе в антагонистической среде. Надо отметить, что проблемы связи идей обучения и теории управления необычайно популярны в настоящее время. Например, уже две конференции Learning for Dynamics and Control были проведены в Беркли (последняя - в июне 2020 года) и собрали сотни участников. На последнем конгрессе ИФАК в Берлине (июль 2020 г.) два из четырех пленарных докладов были посвящены этой тематике, причем характерны их названия: B.Recht, Reflections on the Learning-to-Control Renaissance и J.Lee, Reinforcement Learning for Process Control and Beyond. Кроме того, состоялся там же круглый стол на тему Adaptive control and machine learning, на нем выступила Президент ЕЕС A. Annaswamy на тему Connections Between Adaptive Control and Optimization in Machine Learning. Коллектив, собранный для реализации настоящего проекта и объединяющий лучших специалистов России по оптимизации, машинному обучению и управлению, имеет уникальные предпосылки для выполнения этой престижной и актуальной программы. Особо следует отметить фундаментальный вопрос, открыто стоящий в современном машинном обучении: как адаптивно выбирать ОДНОВРЕМЕННО размер шага и размер батча в процедурах обучения (решения задач минимизации функционала эмпирического риска). На данный момент процедуры типа AdaGrad, Adam и их современные варианты частично решают только проблему адаптивного подбора шага. У авторского коллектива имеется здесь некоторый задел (Двинских-Гасников-Двуреченский, IFAC 2020), который позволяет надеяться, что проблему хотя бы частично, но можно решить в указанной общности. Предполагается развитие современных методов оптимизации, ориентированных на решение задач оптимального управления сложными динамическими системами. Будет исследована возможность применения методологии Быстрого Автоматического Дифференцирования (БАД-методологии) для решения задач оптимального управления методами второго порядка. В качестве объектов применения разрабатываемых методов будет рассмотрен ряд обратных коэффициентных задач, в основе которых лежит первая краевая задача для нестационарного уравнения теплопроводности. Задача идентификации зависящего от температуры коэффициента теплопроводности вещества будет решена в трехмерной постановке. Также предполагается применение БАД-методологии для решения оптимизационных задач, актуальных для развития СВЧ-электроники. А именно, будет рассмотрена задача определения оптимального легирования барьерного слоя, состоящего из ряда подслоев, обеспечивающего заданную концентрацию электронов в канале проводимости в полупроводниковых гетероструктурах. Задачи конического и полуопределенного программирования являются весьма важными классами задач условной оптимизации. К их решению сводятся многие выпуклые и невыпуклые задачи, включая задачи квадратичной оптимизации с квадратичными ограничениями, задачи структурной и робастной оптимизации, определения метрик в задачах идентификации и распознавания образов, задачи машинного обучения и многие другие. Более того, к таким задачам редуцируются некоторые задачи дискретной оптимизации, позволяя тем самым находить их точное решение или некоторое приближение с помощью непрерывных методов. Поэтому разработка эффективных численных методов для решения таких задач представляется важным перспективным исследованием. Многие задачи оптимизации характеризуются различными особенностями, требующими разработки специальных методов и подходов к их решениям. К этим задачам относятся нерегулярные (вырожденные) задачи оптимизации, в которых не работают стандартные условия оптимальности. Поэтому весьма актуальным является изучение структуры вырожденности и построение на этой основе эффективных численных методов их решения.

Ожидаемые результаты
Достаточно ярким и наиболее простым (по формулировке) примером того, насколько важным является правильно ставить задачу оптимизации, являются задачи стохастической оптимизации (минимизации риска), возникающие практически в любом приложении машинного обучения. Исходная задача на практике, как правило, заменяется задачей оптимизации эмпирического риска. Под правильностью постановки задачи тут понимается выбор (связь) числа слагаемых в эмпирическом риске в зависимости от желаемой точности решения исходной задачи. Не погружаясь здесь в детали (см. https://www.youtube.com/playlist?list=PLIvQImOQgbGZH-HlEsVYddBF6EU-qrDOv - это первая лекция в рамках курса, который в этом семестре читается студентам МФТИ по тематике данного проекта в части приложений методов оптимизации к задачам обучения), обратим внимание на то, что от числа этих слагаемых, естественно, будет зависеть и сложность задачи. Поэтому выбирать это число больше, чем требуется для заданной точности, едва ли стоит. Равно как и решать очень точно задачу минимизации эмпирического риска без должной регуляризации (ранней остановки) чревато переобучением. Все это в простейших (выпуклых) случаях уже неплохо было изучено (Н. Сребро и др. 2009). Однако, несмотря на определенный прогресс в решении данной задачи важно отметить, что на основные вопросы тут по-прежнему либо нет ответов, либо они есть, но не полные. В данном проекте планируется не просто проработать ответ на конкретно поставленный вопрос (в нужной общности) о выборе числа слагаемых, а постараться ответить на более общий вопрос: как исходя из этого еще и численно решать возникшую задачу минимизации эмпирического риска в том числе на распределенных (параллельных) архитектурах? Может показаться, что в такой формулировке мы просто объединили две задачи и сделали постановку еще сложнее. На самом деле, как ни странно, именно такое объединение, позволяет по-другому (правильнее) посмотреть на исходный вопрос о выборе числа слагаемых, и более основательно на него ответить, учитывая вопросы связанные с точностью решения задачи минимизации эмпирического риска. Кажущаяся теоретичность данных исследований, в действительности, во многом мотивирована конкретными приложениями, в том числе, связанными с кооперацией с индустриальным партнером (на видео по ссылке выше об этом имеется более подробный рассказ). В проекте планируется все эти наблюдения систематизировать и оформить. Для получения ответа на вопрос о том, когда лучше дискретизировать бесконечномерную задачу (обратную задачу, задачу управления): изначально или при вычислении градиента потребуется проработка вопросов о накоплении неточности в вычислении градиента в различных численных методах оптимизации. Частично ответы на эти вопросы известны (Б.Т. Поляк, 1981; Деволдер-Глинер-Нестеров, 2013; Двуреченский-Гасников, 2016). Однако имеющиеся теоретические наработки достаточно пессимистичны, и говорят о существенном накоплении шума. Что интересно, эти оценки в общем случае являются не улучшаемыми. Тем не менее, на практике такое “плохое” поведение (накопление) не наблюдается (см., например, доклад А.В. Гасникова https://www.youtube.com/watch?v=bgLQKW7QVkU с момента 5:36:00). Связано это с разными аспектами (используемой концепцией неточности, способом агрегирования выхода алгоритма, наличием правильной регуляризации, поздней остановкой метода, отсутствием регуляризирующих свойств у выбранного метода). Планируется проработать эти аспекты и показать, что при правильной (ранней) остановке метода с правильным (робастным) способом формирования выхода алгоритма при очень широких допущениях для широкого класса важных на практике алгоритмов аддитивная ошибка в градиенте, на самом деле, не накапливается по мере роста номера итерации. В том числе для задач оптимизации на неограниченных множествах (это совершенно нетривиальное замечание, потому что много сложностей удается побороть, как раз, сделав предположение об ограниченности множества, на котором происходит оптимизация), и задач стохастической оптимизации. Ожидается, что по итогам проведенных исследований будут выработаны общие рецепты вида, что широкий класс задач оптимального управления лучше решать сразу дискретизируя постановку задачи (переходя к дискретному времени), а широкий класс некорректных обратных задач (например, восстановление коэффициентов, краевых условий и т.п. краевых задач для уравнений эллиптического и гиперболического типа по дополнительным замерам решения), наоборот, лучше дискретизировать непосредственно при приближенном вычислении градиента. Достаточно большой класс практических задач не допускает возможности доступа к точной информации о функции и ее градиенте (например, к такому классу относится задача обучения весов модели ранжирования web-страниц, которую авторский коллектив П.Е. Двуреченский, А.М. Райгородский, А.В. Гасников и др. решали в 2016 году совместно с коллегами из Яндекса (результаты опубликованы на NIPS 2016)). Как следствие, приходится довольствоваться значением функции или, того хуже, случайными реализациями значений функции. Для решения таких задач возникает естественная идея - восстановления (стохастического) градиента по конечным разностям (J.C. Spall) реализаций функций. Недавние исследования (Нестеров-Спокойный, 2017) и членов коллектива (Горбунов-Двуреченский-Безносиков-Гасников, IFAC 2020, EJOR 2020) показывают, что при определенных (дополнительных) предположениях такой подход (с восстановлением градиента) уже не будет наилучшим. В целом в данном направлении осталось намного больше открытых вопросов (особенно в части седловых задач и задач оптимизации с смешанным оракулом - по части переменных / композитов градиентным, по части безградиентным), чем для полноградиентных методов. Особо отметим фундаментальный и практически важный вопрос о накоплении шума в таких безградиентных методах. В отличие от полноградиентных постановок задач на данный момент здесь нет общепризнанных гипотез относительно того, какие правильные оценки имеют место на уровень шума в значении (реализации) функции, при котором этот шум не портит оценку скорости сходимости как функцию от желаемой точности. Имеются только различные верхние оценки (в группе А.В. Гасникова и у американских коллег из Карнеги-Меллон под рук. К. Шайнберг). В рамках работы по проекту планируется систематизировать здесь собственные наработки, полученные в различных частных случаях, и постараться выработать общие правила для широкого класса задач, прежде всего, выпуклой стохастической оптимизации и различных седловых обобщений. Планируется разработать общие способы распределенного решения задач выпуклой (стохастической) оптимизации с целевым функционалом вида суммы, в основу которых также будут положены результаты о сходимости градиентных процедур с неточным градиентом. Только на этот раз неточность в вычислении градиента будет обусловлена не приближенным решением систем дифференциальных уравнений (краевых задач), как это имело место в обратных задачах и задачах оптимального управления, а невозможностью точно найти консенсус в моделях распределенной оптимизации с децентрализованной архитектурой. Отметим, что хотя с точки зрения математики здесь во многом будет использованы те же идеи, что и для отмеченных выше обратных задачи и задач управления, сами приложения и формулировки достигаемых результатов будут совершенно отличными, поскольку акцент уже будет делаться именно на коммуникационных аспектах решения распределенными методами рассматриваемых задач. При создании новых материалов нередко некоторые характеристики этих материалов бывают неизвестными. Для их определения прибегают к решению обратных задач. Довольно часто приходится встречаться с ситуацией, когда коэффициент теплопроводности вещества зависит только от температуры и эта зависимость неизвестна. В связи с этим возникает задача определения зависимости коэффициента теплопроводности вещества от температуры по результатам экспериментального наблюдения за динамикой температурного поля в исследуемом веществе. Задача идентификации зависящего от температуры коэффициента теплопроводности вещества будет рассмотрена в трехмерной постановке. Исследование будет проводиться на основе первой краевой задачи для нестационарного уравнения теплопроводности. Рассмотренные раньше одномерный и двумерный варианты обратной задачи, безусловно, представляют большой математический, теоретический интерес. Однако на практике, при сборе экспериментальных данных, имеют дело с трехмерными объектами. Поэтому задачу идентификации коэффициента теплопроводности желательно решать в трехмерной постановке. Заявленная обратная задача актуальна, интересна и до сих пор нигде не рассматривалась. Предполагается дальнейшее усовершенствование методологии Быстрого Автоматического Дифференцирования (БАД-методологии) и ее использование для решения практически важных задач. Будет исследована возможность применения методологии Быстрого Автоматического Дифференцирования для решения задач оптимального управления методами второго порядка. В качестве объектов применения разрабатываемых методов будет рассмотрен ряд обратных коэффициентных задач на основе первой краевой задачи для нестационарного уравнения теплопроводности. Также предполагается применение этой современной и эффективной методологии для решения оптимизационных задач, актуальных для развития СВЧ-электроники. Современной тенденцией развития высокочастотной полупроводниковой техники является стремление к достижению максимальных концентраций носителей заряда при максимально возможной их подвижности. Весьма перспективными с точки зрения повышения концентрации и подвижности носителей заряда являются структуры с наличием поверхностного заряда на гетерогранице. Математическая модель, описывающая распределение электронов в таких структурах, основывается на системе уравнений Шрёдингера и Пуассона. Эта модель хорошо себя зарекомендовала и активно используется при расчете различных устройств. Что касается задач оптимизации таких устройств, то здесь публикаций практически нет. В рамках проекта будет исследована задача определения оптимального легирования барьерного слоя, состоящего из ряда подслоев, обеспечивающего заданную концентрацию электронов в канале проводимости в полупроводниковых гетероструктурах.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Аннотация результатов, полученных в 2021 году
За первый этап было опубликовано 15 Scopus работ, включающих, например, публикацию в трудах конференции ICML 2021 и NeurIPS 2021, имеющих наивысший рейтинг A*, а также 3 статей из квартиля Q1. Основные результаты были получены по направлению разработки численных методов решения седловых задач (в том числе с разными константами сильной выпуклости и вогнутости и задач со структурой, например, структурой вида суммы) полноградиентными, безградиентными (одноточечными и двухточечными в случае стохастических постановок) и смешанных оракулов. Были предложены оптимальные (с точностью до логарифмических множителей) алгоритмы, т.е. работающие по недавно полученным нижним оценкам. Например, впервые был предложен алгоритм работающий по нижним оценкам для седловых задач вида суммы с разными константами сильной выпуклости и вогнутости. Ранее такой алгоритм был известен только для случая, когда эти константы совпадают, что является заметно более узким классом задач. Примечательно, что заметная часть полученных результатов имеет общее “оболочечное” происхождение. То есть в проекте разрабатываются не только почти оптимальные алгоритмы, но и развивается философия, позволяющая получать новые оптимальные методы для более широкого класса задач из оптимальных методов для более узкого класса. В разработки численных методов решеняи бесконечномерных обратных задач также была построена общая теория, базирующаяся на недавних достижения в изучении сходимости численных методов выпуклой оптимизации с неточным градиентом. Удалось построить необходимую редукцию широкого класса линейных обратных (некорректных) задач (в этот класс, например, входят, например, начально-краевые задачи для уравнения эллиптического типа) к задачам выпуклой (квадратичной) оптимизации с неточным оракулом, выдающим градиент и значение целевой функции. Исследовались различные прямые и двойственные методы решения отмеченной задачи квадратичной оптимизации (в гильбертовом пространстве). Среди прочего изучались вопросы регуляризации, накопления неточностей и критерии останова. Полученные результаты показали эффективность ускоренным методов выпуклой оптимизации. Решена задача определения зависящего от температуры коэффициента теплопроводности вещества по экспериментальным данным в трехмерной постановке. Исследования проводились на основе первой краевой задачи для трехмерного нестационарного уравнения теплопроводности. Задача идентификации коэффициента теплопроводности была сформулирована в двух постановках. В первом случае в качестве экспериментальных данных выступает заданное температурное поле объекта, во втором случае - заданный тепловой поток на границе объекта. Рассматриваемая обратная задача сводилась к вариационной задаче и решалась с помощью градиентных методов минимизации целевого функционала. Для вычисления градиента использовалась методология Быстрого Автоматического Дифференцирования (БАД-методология). Это позволило добиться того, что градиент целевой функции в разработанном алгоритме вычислялся с машинной точностью, что увеличило скорость минимизации функционала. Сопряженные уравнения и формула для вычисления градиента целевого функционала были получены для случая, когда прямая задача решалась с помощью локально-одномерной разностной схемы. Исследована возможность применения БАД-методологии для решения обратных коэффициентных задач оптимизационными методами второго порядка сходимости. Рассмотрена линейная задача полуопределенного программирования. Для ее решения предложен допустимый прямо-двойственный метод, основанный на решении методом Ньютона системы уравнений, описывающих условия оптимальности. Обсужден вопрос, как строить ньютоновские направления перемещения в случае принадлежности текущих точек итерационного процесса границам допустимых множеств. При этом существенным образом использовалось разбиение пространства симметричных матриц на подпространства. Далее мы рассматриваем задачи линейного программирования на конусах второго порядка и предлагаем для таких задач вариант симплексного метода. Предложен новый подход для изучения устойчивости динамических систем в случае, когда традиционные функции Ляпунова не применимы или не эффективны для исследования. Основная конструкция для анализа вырожденных динамических систем - это так называемый P-фактор функции Ляпунова, которые позволяют свести исходную задачу к новой, на основе элементов теории P-регулярности. Приводятся примеры эффективного применения предложенного подхода. В последнее время стал очень популярным подход к линейным системам управления с точки зрения оптимизации, восходящий к работам Р. Калмана. В частности, существенным шагом явилось понимание, что коэффициенты обратной связи в задачах линейно-квадратичного управления могут рассматриваться как переменные, по которым может проводиться минимизация. Важным продвижением в этом направлении явилось понимание, как устроена такая оптимизационная задача. В работе И. Фатхуллин, Б.Т. Поляк, “Optimizing Static Linear Feedback: Gradient Method”, SIAM Journal on Control and Optimization, 2021, Vol. 59, No. 5, P. 3887-3911 (квартиль Q1) показано, что хотя возникающая функция невыпукла, неограничена и определена на достаточно сложном множестве стабилизирующих регуляторов, тем не менее эта функция дифференцируема и достаточно гладкая. Более того, для синтеза статической обратной связи по состоянию удалось доказать, что выполняется условие Поляка-Лоясевича, которое гарантирует сходимость градиентного метода с линейной скоростью. Предложены также более эффективные варианты алгоритма оптимизации и проведены численные эксперименты, демонстрирующие работоспособность метода в практических задачах. Также участниками проекта подготовлены эвристики для будущего построения корректирующих алгоритмов (см. статьи Boris Goldengorin, Vadim V. Romanuke. Online heuristic for the preemptive single machine scheduling problem to minimize the total weighted tardiness. Comput.& Ind. Eng. 155: 107090 (2021); Boris Goldengorin, Vadim V. Romanuke. Experimental analysis of tardiness in preemptive single machine scheduling. Expert Syst. With Appl. 186: 114947 (2021)) для приближенного решения одного класса многоэкстремальных (NP-трудных задач) по оптимизации прерываемых расписаний на одной сшироким классом целевых функций, вклучающих минимизацию суммарного взвешенного времени выполнения все работ, не обязательно равной длительности. Для случая равной длительности всех работ построен контрпример для свойства Вполне Двойственной Целочисленности (Total Dual Integrality-TDI) и соответствующая статья подана в журнал Computers & Operations Research.

Публикации

1. Dmitry Pasechnyuk, Andrei M. Raigorodskii Network Utility Maximization by Updating Individual Transmission Rates Communications in Computer and Information Science, pp 184-198 (год публикации - 2021) https://doi.org/10.1007/978-3-030-92711-0_13

2. Абдурахмон Садиев, Александр Безносиков, Павел Двуреченский, Александр Гасников Solving Smooth Min-Min and Min-Max Problems by Mixed Oracle Algorithms Communications in Computer and Information Science, pp 19 - 40 (год публикации - 2021) https://doi.org/10.1007/978-3-030-86433-0_2

3. Александр Масловский, Дмитрий Пасечнюк, Александр Гасников, Антон Аникин, Александр Рогозин, Александр Горнов, Лев Антонов, Роман Власов, Анна Николаева, Мария Бегичева Non-convex Optimization in Digital Pre-distortion of the Signal Communications in Computer and Information Science, Том 1476, Страницы 54 - 70 (год публикации - 2021) https://doi.org/10.1007/978-3-030-86433-0_4

4. Безносиков А., Новицкий В., Гасников А. One-point gradient-free methods for smooth and non-smooth saddle-point problems Lecture Notes in Computer Science, Том 12755, Страницы 144 - 158 (год публикации - 2021) https://doi.org/10.1007/978-3-030-77876-7_10

5. Безносиков А., Рогозин А., Ковалев Д., Гасников А. Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks Lecture Notes in Computer Science, Том 13078, Страницы 246 - 257 (год публикации - 2021) https://doi.org/10.1007/978-3-030-91059-4_18

6. Бирюков А., Чернов А. On Numerical Estimates of Errors in Solving Convex Optimization Problems Communications in Computer and Information Science, pp 3-18 (год публикации - 2021) https://doi.org/10.1007/978-3-030-92711-0_1

7. Гольденгорин Б.И., Романюк В. Experimental analysis of tardiness in preemptive single machine scheduling Expert Systems with Applications, Том186, Номер статьи 114947 (год публикации - 2021) https://doi.org/10.1016/j.eswa.2021.114947

8. Ковалев Д., Шульгин Э., Рихтарик П., Рогозин А., Гасников А. ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks ICML 2021, vol 139 , стр 5784-5793 (год публикации - 2021)

9. Матюхин В., Кабанихин С., Шишленин М., Новиков Н., Васин А., Гасников А. Convex optimization with inexact gradients in hilbert space and applications to elliptic inverse problems Lecture Notes in Computer Science, стр 159 - 175 (год публикации - 2021)

10. П. Щербаков, Ф. Даббене A probabilistic point of view on peak effects in linear difference equations European Journal of Control, pp 1-9 (год публикации - 2021) https://doi.org/10.1016/j.ejcon.2021.09.007

11. Садиев А., Везносиков А., Двуреченский П., Гасников А. Zeroth-order algorithms for smooth saddle-point problems Lecture Notes in Computer Science, Том 1476, Страницы 71 - 85 (год публикации - 2021) https://doi.org/10.1007/978-3-030-86433-0_5

12. Сафин К., Двуреченский П., Гасников А. Adaptive gradient-free methods for stochastic optimization Communications in Computer and Information Science, pp 95 - 110 (год публикации - 2021) https://doi.org/10.1007/978-3-030-92711-0_7

13. Фатхуллин И., Поляк Б.Т. OPTIMIZING STATIC LINEAR FEEDBACK: GRADIENT METHOD SIAM JOURNAL ON CONTROL AND OPTIMIZATION, Vol. 59, No. 5, pp. 3887–3911 (год публикации - 2021) https://doi.org/10.1137/20M1329858

14. Ю.Г.Евтушенко, А.А,Третьяков A New Class of Lyapunov Functions for Stability Analysis of Singular Dynamical Systems. Elements of p-Regularity Theory Doklady Mathematics, Vol. 104, No. 1, pp. 165–168 (год публикации - 2021) https://doi.org/10.1134/S1064562421040062

15. Ю.Г.Евтушенко, В.Малкова, А.А.Третьяков Exit from Singularity. New Optimization Methods and the p-Regularity Theory Applications Lecture Notes in Computer Science, Том 13078, Страницы 3 - 19 (год публикации - 2021) https://doi.org/10.1007/978-3-030-91059-4_1

Аннотация результатов, полученных в 2022 году
В отчетном году исследовалась скорость сходимость градиентных и безградиентных методов (и их адаптивных версий) для задач оптимизации и седловых задач в условиях шума (вообще говоря, враждебного). Были получены оценки на допустимый уровень шума, при которых возможно достичь наперед заданной (желаемой) точности решения задачи. Отметим, что полученные здесь результаты в ряде случае неулучшаемы (то есть соответствуют известным нижним оценкам) как на число вызовов оракула (градиентного / безградиентного) так и на сам уровень шума. Для задач распределенной оптимизации были получены существенные продвижения в разработке методов, использующих смещённую компрессию с ограниченной ошибкой, редукцию дисперсии и неравномерное сэмплирование стохастических градиентов. Предложен общий анализ для стохастических методов, использующих смещённую компрессию с ограниченной ошибкой. Также подробно исследовался класс задач децентрализованной выпуклой оптимизации с аффинными ограничениями. Такие задачи возникают, например, в моделировании энергетических сетей. Полученные здесь результаты оптимальны как по числу оракульных вызовов (вычислений градиентнов на узлах), так и по числу коммуникаций. Отметим, что ранее для данных задач в основном использовались методы типа ADMM, которые и сходились (во всяком случае по теоретическим оценкам) хуже и имели более дорогие итерации (приходилось отрешивать нетривиальные квадратичные задачи оптимизации). Более того, был предложен способ обобщения алгоритмов децентрализованной оптимизации на задачи группами разделенных и общих переменных. Этот подход основан на использовании новой матрицы коммуникаций, обобщающей матрицу Лапласа графа. Написан обзор по методам решения стохастических задач вариационного неравенства. В работе собраны как классические подхода, так и новые тренды в этой популярной сейчас области. Обзор представлен в виде архив препринта: Beznosikov A. et al. Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems--Survey //arXiv preprint arXiv:2208.13592. – 2022, и принят к публикации в EMS MAGAZINE (выйдет в следующем 2023 году). Проводилось численное исследование устойчивости решений обратной коэффициентной задачи для уравнения теплопроводности в трехмерной постановке. Во всех рассмотренных примерах экспериментальные данные были возмущены с помощью генератора случайных чисел. Интенсивность возмущений определялась как максимальное отклонение возмущенных данных от невозмущенных, деленное на среднее значение невозмущенных данных. Были сделаны следующие выводы: (1) Если в целевом функционале отсутствует регуляризатор, то при небольших возмущениях в экспериментальных данных предлагаемый алгоритм приводит к небольшим отклонениям в решении обратной задачи. (2) При умеренных возмущениях в экспериментальных данных (20-30%) для получения устойчивого решения в целевом функционале необходимо вводить регуляризатор. (3) Если возмущения входных данных не малы, то можно добиться сглаженного решения, выбрав небольшое количество М разбиений отрезка температур на подотрезки. (4) Для эффективной работы предлагаемого алгоритма целесообразно решать обратную задачу, начиная с малых значений М. Полученное решение используется в качестве начального приближения для больших значений М. Проведен сравнительный анализ нескольких методов численного решения спектральных задач, которые могут быть использованы при решении задач оптимизации в наноэлектронике. Одной из целей проведенного анализа является также изучение возможности использования вариационных методов при решении спектральных задач. Анализ результатов проведенных вычислительных экспериментов позволил сделать вывод о том, что в одномерном случае эффективным является предложенный авторами численно-аналитический метод, а в многомерном случае – вариационный метод. Разработан алгоритм численного решения задачи определения оптимального легирования барьерного слоя, состоящего из ряда подслоев, обеспечивающего заданную концентрацию электронов в канале проводимости в полупроводниковых гетероструктурах. Алгоритм реализован в виде программного кода на языке программирования C/C++. Разработан прямо-двойственный метод для решения линейных задач конического программирования с конусом второго порядка. Метод основан на решении методом Ньютона системы уравнений, описывающих условия оптимальности. Разработан новый подход к исследованию на сходимость непрерывных аналогов градиентного метода и метода Ньютона при решении вырожденных нелинейных систем уравнений. Предложен новый подход к решению задачи разреженной фильтрации (т.е. фильтрации, использующей пониженное число выходов) при произвольных ограниченных внешних возмущениях с использованием наблюдателя. Подход основан на методе инвариантных эллипсоидов и технике линейных матричных неравенств. Применение этой концепции позволило свести исходную проблему к задаче полуопределенного программирования, легко решающейся численно. Подход отличается простотой и легкостью реализации и в равной мере охватывает как непрерывную, так и дискретную постановки задачи. Предложен новый подход к задаче настройки и оптимизации параметров ПИД-регулятора, основанный на сведении проблемы к задаче оптимизации. При этом качество регулятора оценивается по квадратичному критерию от выхода системы: ПИД-регулятор настраивается против неопределенности в начальных условиях так, чтобы выход системы был равномерно малым; при этом дополнительно гарантируется заданная степень устойчивости замкнутой системы. Выписан градиентный метод для отыскания параметров ПИД-регулятора. Предлагаемая рекуррентная процедура приводит ко вполне удовлетворительным по инженерным критериям качества ПИД-регуляторам. Рассмотрена задача минимизации расхода топлива дозвукового турбореактивного пассажирского самолета на этапе набора высоты. Целевая функция оптимизации кроме расхода топлива включает время, затраченное на этап набора высоты, так как оптимизация набора высоты – это часть задачи оптимизации всего полета с требованием прибытия в заданную точку в заданное время. Так как в конце этапа нужно выйти на заданные значения скорости и высоты, с которых должен начинаться крейсерский полет, то в целевую функцию добавлены штрафы за недостижение этих значений. Для решения задачи применен безградиентный метод поиска с использованием точек-кандидатов и учетом ограничений. В предположении вероятностной природы коэффициентов полинома и ненулевых начальных условий показано, что для случайно сгенерированного устойчивого полинома с высокой вероятностью найдутся начальные условия, гарантирующие всплеск, причем эта вероятность очень быстро растет с ростом степени полинома, т.е. можно утверждать, что, как правило, всплеск неизбежен. Среди других результатов - оценка вероятности всплеска для случайного полинома и случайных начальных условий и оценивание ее точности; оценка доли начальных условий из единичного куба, приводящих к всплеску некоторого класса полиномов; вероятностная оценка величины всплеска и его среднего значения. Для минимизации прерываемых расписаний по критерию суммарного взвешенного времени выполненных работ на одной машине доказаны новые свойства оптимальных расписаний. На основе этих свойств построена новая Модель Булевого Линейного Программирования (МБЛП). На основе МБЛП разработан алгоритм ветвей и границ и эвристика возвращающая в более чем 99% из более чем 1 млн тестовых промеров точное оптимальное решение. В остальных случаях требуется не более чем 1-2 ветвления для доказательства оптимальности найденных прерываемых расписаний. Построенный контрпример (см. Fomin, B. Goldengorin. An exact algorithm for the preemptive single machine scheduling of equal-length jobs to minimize the Total Weighted Completion Time. Computers & Operations Research, Volume 142, June 2022, 105742) опровергает наличие свойства Вполне Двойственной Целочисленности у нашей МБЛП.

Публикации

1. B.T. Polyak, M.V. Khlebnikov Новые критерии настройки ПИД-регуляторов Автоматика и телемеханика, выпуск 11, страницы 62–82 (год публикации - 2022) https://doi.org/10.31857/S0005231022110022

2. А.Ф. Албу, Ю.Г. Евтушенко, В.И. Зубов Application of Second-Order Optimization Methods for Solving an Inverse Coefficient Problem in the Three-Dimensional Statement Proceedings of the Steklov Institute of Mathematics, Vol. 317, P. 1 - 15 (год публикации - 2022) https://doi.org/10.1134/S0081543822030014

3. Агафонов А. Д. Lower bounds for conditional gradient type methods for minimizing smooth strongly convex functions Computer Research and Modeling, Vol. 14, No, 2, P. 213 - 223 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-213-223

4. Александров В. А., Зыбин Е. Ю., Косьянчук В. В., Сельвесюк Н. И., Тремба А. А., Хлебников М. В. Оптимизация расхода топлива воздушного судна на этапе набора высоты Автоматика и телемеханика, No 11, 2022, No. 11, P. 83–102 (год публикации - 2022) https://doi.org/10.31857/S0005231022110034

5. Алпатов А. В., Петерс Е. А., Пасечнюк Д. А., Райгородский А. М. Stochastic optimization in digital pre-distortion of the signal Computer Research and Modeling, V. 14, No. 2, P. 399 - 416 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-399-416

6. Базарова А. И., Безносиков А. Н., Гасников А. В. Linearly convergent gradient-free methods for minimization of parabolic approximation Computer Research and Modeling, V. 14, No. 2, P. 239–255 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-239-255

7. Безносиков А., Скутари Г., Рогозин А., Гасников А. Distributed Saddle-Point Problems Under Similarity Advances in Neural Information Processing Systems, V. 10, P. 8172 - 8184 (год публикации - 2021)

8. В.И. Зубов, А.Ф. Албу On Solving One Spectral Problem Lecture Notes in Computer Science, Vol.13367, P. 153 - 166 (год публикации - 2022) https://doi.org/10.1007/978-3-031-09607-5_11

9. Д. Двинских, В. Томинин, Я. Томинин, А. Гасников Noisy Zeroth-Order Optimization for Non-smooth Saddle Point Problems Lecture Notes in Computer Science, Vol. 13367, P. 18 - 33 (год публикации - 2022) https://doi.org/10.1007/978-3-031-09607-5_2

10. Д. Ярмошик, А. Рогозин, О. Хамисов, П. Двуреченский, А. Гасников Decentralized Convex Optimization Under Affine Constraints for Power Systems Control Lecture Notes in Computer Science, Vol. 13367, P. 62 - 75 (год публикации - 2022) https://doi.org/10.1007/978-3-031-09607-5_5

11. Данилова М. On the Convergence Analysis of Aggregated Heavy-Ball Method Lecture Notes in Computer Science, Vol. 13367, pp. 3-17 (год публикации - 2022) https://doi.org/10.1007/978-3-031-09607-5_1

12. Данилова М. Ю., Малиновский Г. С. Averaged heavy-ball method Computer Research and Modeling, Vol. 14. No. 2. P. 277–308. (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-277-308

13. Данилова М., Горбунов Э. Distributed Methods with Absolute Compression and Error Compensation Communications in Computer and Information Science, Vol. 1661, P. 163 - 177 (год публикации - 2022) https://doi.org/10.1007/978-3-031-16224-4_11

14. Двинских Д. М., Пырэу В. В., Гасников А. В. On the relations of stochastic convex optimization problems with empirical risk minimization problems on p-norm balls Computer Research and Modeling, V. 14, No. 2, P. 309–319 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-309-319

15. Двуреченский П. Е. A gradient method with inexact oracle for composite nonconvex optimization Computer Research and Modeling, Vol. 14, No. 2, P. 321 - 334 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-321-334

16. Евтушенко Ю.Г., Е. Беднарчук, Прусинска А., Третьяков А.А. Об эквивалентности вырожденных и некорректных задач. P-фактор метод регуляризации Доклады Российской академии наук. Математика, информатика, процессы управления., T. 506, № 1, стр. 41-44 (год публикации - 2022) https://doi.org/10.31857/S2686954322050095

17. Евтушенко Ю.Г., Третьяков А.А. Convergence of Continuous Analogues of Numerical Methods for Solving Degenerate Optimization Problems and Systems of Nonlinear Equations Computational Mathematics and Mathematical Physics, Vol. 62, No. 10, P. 1602 - 1608 (год публикации - 2022) https://doi.org/10.1134/S0965542522100049

18. Ковалев Д., Безносиков А., Бородич Е., Гасников А., Сцутари Г. Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity Advances in Neural Information Processing Systems 2022, NIPS 2022 (год публикации - 2022)

19. Курузов И., Стонякин Ф. Sequential Subspace Optimization for Quasar-Convex Optimization Problems with Inexact Gradient Communications in Computer and Information Science, Vol. 1514 CCIS, P. 19 - 33 (год публикации - 2021) https://doi.org/10.1007/978-3-030-92711-0_2

20. Парсегов С., Щербаков П., Чеботарёв П., Ерофеева В., Рогозин А. Laplacian spectra of two-layer hierarchical cyclic pursuit schemes IFAC-PapersOnLine, Vol. 55, No. 13, P. 246-251. (год публикации - 2022) https://doi.org/10.1016/j.ifacol.2022.07.267

21. Плетнев Н. В., Двуреченский П. Е., Гасников А. В Application of gradient optimization methods to solve the Cauchy problem for the Helmholtz equation Computer Research and Modeling, V. 14, No. 2, P. 417–444 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-417-444

22. Поляк Б.Т., Хлебников М.В. Observer-Aided Output Feedback Synthesis as an Optimization Problem Automation and Remote Control, Vol. 83, No. 3, P. 303 - 324 (год публикации - 2022) https://doi.org/10.1134/S0005117922030018

23. Ричтарик П., Соколов И., Фаткхуллин И., Гасанов Е., Ли З., Горбунов Е. 3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation Proceedings of the 39th International Conference on Machine Learning, PMLR 162:18596-18648 (год публикации - 2022)

24. Савчук О. С., Титов А. А., Стонякин Ф. С., Алкуса М. С. Adaptive first-order methods for relatively strongly convex optimization problems Computer Research and Modeling, V. 14, No. 2, P. 445–472 (год публикации - 2022) https://doi.org/10.20537/2076-7633-2022-14-2-445-472

25. Ф. С. Стонякин, А. А. Титов, Д. В. Макаренко, М. С. Алкуса Численные методы для некоторых классов вариационных неравенств с относительно сильно монотонными операторами Математические заметки, том 112, выпуск 6, страницы 879–894 (год публикации - 2022) https://doi.org/10.4213/mzm13357

26. Фомин А., Гольденгорин Б. An exact algorithm for the preemptive single machine scheduling of equal-length jobs Computers and Operations Research, Vol. 142, No. 105742 (год публикации - 2022) https://doi.org/10.1016/j.cor.2022.105742

27. Хлебников М.В, Sparse Filtering Under Norm-Bounded Exogenous Disturbances Using Observers SYSTEM THEORY, CONTROL AND COMPUTING JOURNAL, VOL. 2, NO. 1, pp. 1-7 (год публикации - 2022) https://doi.org/10.52846/stccj.2022.2.1.29

28. Чежегов С., Новицкий А., Рогозин А., Парсегов С., Двуреченский П., Гасников А. A General Framework for Distributed Partitioned Optimization IFAC-PapersOnLine, Vol. 55, No. 13, P. 139 - 144 (год публикации - 2022) https://doi.org/10.1016/j.ifacol.2022.07.249

29. Шатов Д.В. Analysis of Stability and Dwell Time of a Certain Class of Switched Systems with Second Order Subsystems 2022 16th International Conference on Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy's Conference), No. 180536 (год публикации - 2022) https://doi.org/10.1109/STAB54858.2022.9807515

30. Шатов Д.В. Синтез параметров пропорционально-интегрирующих и пропорционально-интегрально-дифференцирующих регуляторов для стационарных линейных объектов с ненулевыми начальными условиями Известия РАН. Теория и системы управления, No. 1 (год публикации - 2022)

31. Ю.Г. Евтушенко, В.И. Зубов, А.Ф. Албу Numerical Study of Stability of an Algorithm for Identifying the Thermal Conductivity in the Three-Dimensional Case Journal of Mathematical Sciences, Vol. 267, No. 4, P. 474 - 482 (год публикации - 2022) https://doi.org/10.1007/s10958-022-06152-9

Аннотация результатов, полученных в 2023 году
Проведен анализ современных работ по теме многокритериальной оптимизации и построения моделей для решения задачи предискажения сигнала при помощи метода добавления нелинейных искажений. Показано, что возможно найти структуру (сохранив производительность) и имеющую меньшее количество используемых ресурсов, быстрее, чем полный перебор по всему словарю из заданных параметров (софинансирование проекта). Предложен алгоритм численного решения обратной начально-краевой задачи для гиперболического уравнения с малым параметром перед второй производной по времени, которая состоит в нахождении начального распределения по заданному конечному. Данный алгоритм позволяет для заданной наперед точности получить решение задачи (в допустимых пределах точности). Данный алгоритм позволяет избежать сложностей, аналогичных случаю с уравнением теплопроводности с обращенным временем. Предложенный алгоритм позволяет подобрать оптимальный размер конечно-разностной схемы путем обучения на относительно больших разбиениях сетки и малом числе итераций градиентного метода. Предложенный алгоритм позволяет получить оценку для константы Липшица градиента целевого функционала. Также представлен способ оптимального выбора малого параметра при второй производной для ускорения решения задачи. Данный подход может быть применен и в других задачах с похожей структурой, например в решении уравнений состояния плазмы, в социальных процессах или в различных биологических задачах. Новизна данной работы заключается в разработке оптимальной процедуры выбора размера шага путем применения экстраполяции Ричардсона и обучения на малых размерах сетки для решения задач оптимизации с неточным градиентом в обратных задачах. Предложен алгоритм для получения численного решения задачи одновременной идентификации зависящих от температуры объемной теплоемкости и коэффициента теплопроводности исследуемого вещества. Исследование осуществлялось на основе первой краевой задачи для одномерного нестационарного уравнения теплопроводности. Исследовался вопрос единственности получаемого решения, сформулированной выше обратной задачи. Установлено, что для некоторых рассмотренных задач решение единственно, а для некоторых нет. Найден класс температурных полей из области достижимости, для которых обратная задача имеет неединственное решение. Разработан алгоритм численного решения одномерной задачи определения оптимального легирования барьерного слоя, состоящего из ряда подслоев, обеспечивающего заданную концентрацию электронов в канале проводимости в полупроводниковых гетероструктурах. Проводились исследования, связанные с развитием теории р-регулярности и аппарата р-фактор анализа и применения его в различных областях математики и приложениях. Предложен новый подход к задаче подавления ограниченных внешних возмущений в линейных системах управления при помощи ПИ-регулятора. Подход основан на сведении проблемы к задаче невыпуклой матричной оптимизации. Выписан градиентный метод для отыскания параметров ПИ-регулятора и дано его обоснование. Разработан конструктивный алгоритм решения задачи синтеза ПИ- и ПИД-регуляторов для следящих систем для SISO-объекта управления. В качестве показателя качества работы регулятора был выбран квадратичный критерий по ошибке. Решение исходной задачи сведено к задаче оптимизации и для ее решения предложен метод, подобный методу сопряженных градиентов. Предложен новый подход к задаче синтеза гарантирующего фильтра, основанный на сведении проблемы к задаче матричной оптимизации, где переменной является матрица фильтра. Далее эта задача решается градиентным методом; его сходимость теоретически обосновывается для ряда важных частных случаев. Решена задача оптимизации высотно-скоростного профиля крейсерского полета воздушного судна, обеспечивающего прибытие в точку назначения в заданное время, с использованием данных реальной атмосферы на протяжении маршрута. При этом удалось получить заметное снижение расхода топлива (более 1 %) для дозвукового турбореактивного пассажирского самолета. Показано, что учет скорости ветра существенно влияет на выбор экономичного эшелона полета, в том числе учитывая зависимость скорости ветра от высоты. Предложен регулярный подход к синтезу стабилизирующей статической обратной связи, минимизирующей величину отклонения траекторий линейной системы управления, подверженной воздействию неслучайных ограниченных внешних возмущений и системных неопределенностей. Подход основан на технике линейных матричных неравенств и предполагает сведение исходной задачи к параметрической задаче полуопределенного программирования, легко решающейся численно. Предложен робастный (надежный) контроллер слежения неопределённого динамического объекта с заданными ограничениями на переменные состояния, предполагая, что текущие переменные состояния и их производные по времени наблюдаемы (измеряемы). Показано, что "желаемый режим" – нестационарный аналог поверхности скольжения – может быть достигнут с самого начала процесса управления; также получена явная верхняя граница убывания функции стоимости. Рассмотрен класс разностных уравнений высокого порядка, моделирующих процессы популяционной динамики. Показано, что вероятность всплеска их решений (при случайном равномерном генерировании коэффициентов в области устойчивости) стремится к нулю с ростом порядка уравнения. С другой стороны, для некоторых специальных подклассов таких уравнений получены явные нижние оценки величины всплеска, которые показывают, что он может принимать очень большие значения. Для решения подкласса стохастической невыпукло-невогнутой задачи оптимизации черного ящика с седловой точкой, которая удовлетворяет условию Поляка–Лоясиевича исследован впервые, насколько нам известно, безградиентный алгоритм, подход к созданию которого основывается на применении градиентной аппроксимации (ядерной аппроксимации) к алгоритму стохастического градиентного спуска подъема со смещенным оракулом. Полyчены теоретические оценки, гарантирующие глобальную линейную скорость сходимости к желаемой точности. Теоретические результаты мы проверили на модельном примере, сравнивая с алгоритмом, использующую Гауссовскую аппроксимацию. Рассмотрены два способа, сводящие задачу поиска вектора PageRank к задаче поиска равновесия в антагонистической матричной игре, которая затем решается с помощью алгоритма Григориадиса – Хачияна. При этом данная реализация эффективно работает в предположении о разреженности матрицы, подаваемой на вход. Рассмотрен вероятностный метод поиска вектора PageRank, а именно Markov chain Monte Carlo (MCMC), с целью сравнения результатов работы указанных алгоритмов на матрицах с различными значениями спектральной щели. Последнее представляет особый интерес, поскольку значение спектральной щели сильно влияет на скорость сходимости MCMC, и не оказывает никакого влияния на два других подхода. Сравнение проводилось на сгенерированных графах двух видов: цепочках и d-мерных кубах. Проведены эксперименты, которые продемонстрировали эффективность алгоритма Григориадиса – Хачияна по сравнению с MCMC для разреженных графов с маленьким значением спектральной щели.

Публикации

1. Айвазян Г.В., Стонякин Ф.С., Пасечнюк Д.А., Алкоуса М.С., Райгородский А.М. Adaptive Variant of the Frank-Wolfe Algorithm for Convex Optimization Problems Programming and Computer Software, Vol. 49, No. 6, pp. 493–504 (год публикации - 2023) https://doi.org/10.1134/S0361768823060038

2. Акиндинов Г.Д., Матюхин В.В., Криворотько О.И. Numerical solving of an inverse problem of a hyperbolic heat equation with small parameter Computer Research and Modeling, VOL. 15 NO. 2 P. 245–258 (год публикации - 2023) https://doi.org/10.20537/2076-7633-2023-15-2-245-258

3. Албу А. Ф., Горчаковa А. Ю. , Зубовa В. И. FAD Technique and Differentiation of a Composite Function Computational Mathematics and Mathematical Physics, vol. 63, 57–68 (год публикации - 2023) https://doi.org/10.1134/S0965542523010037

4. Александров В.А., Зыбин Е.Ю., Косьянчук В.В., Сельвесюк Н.И., Стефанюк Е.А., Тремба А.А., Хлебников М.В. Aircraft Cruise Altitude and Speed Profile Optimization in a Real Atmosphere Automation and Remote Control, том 84, 327–336 (год публикации - 2023) https://doi.org/10.1134/S0005117923040021

5. Брежнева О., Евтушенко Ю., Малькова В., Третьяков А. Degenerate Equality Constrained Optimization Problems and P-Regularity Theory Lecture Notes in Computer Science, volume 13781, pp 18–33 (год публикации - 2023) https://doi.org/10.1007/978-3-031-22543-7_2

6. Евтушенко Ю. Г. , Медак Б. , Третьяков А. А. p-Regularity Theory and the Existence of a Solution to a Boundary Value Problem Continuously Dependent on Boundary Conditions Computational Mathematics and Mathematical Physics, 63, 957–972 (год публикации - 2023) https://doi.org/10.1134/S0965542523060076

7. Евтушенко Ю. Г. , Третьяков А. А. Method for False Extrema Localization in Global Optimization Doklady Mathematics, Vol. 108, No. 1, pp. 309–311 (год публикации - 2023) https://doi.org/10.1134/S1064562423700850

8. Лобанов А. Stochastic Adversarial Noise in the “Black Box” Optimization Problem Lecture Notes in Computer Science, volume 14395, p 60–71 (год публикации - 2023) https://doi.org/10.1007/978-3-031-47859-8_5

9. Лобанов А., Гасников А. Accelerated Zero-Order SGD Method for Solving the Black Box Optimization Problem Under “Overparametrization” Condition Lecture Notes in Computer Science, volume 14395, p 72–83 (год публикации - 2023) https://doi.org/10.1007/978-3-031-47859-8_6

10. Масловский А.Ю., Суменков О.Ю., Воркутов Д.А., Чуканов С.В. Application of discrete multicriteria optimization methods for the digital predistortion model design Computer Research and Modeling, vol. 15, no. 2, pp. 281-300 (год публикации - 2023) https://doi.org/10.20537/2076-7633-2023-15-2-281-300

11. Назин А.В., Позняк А.С. Non-quadratic proxy functions in Mirror Descent Method applied to designing of robust controllers for nonlinear dynamic systems with uncertainty Computational Mathematics and Mathematical Physics, № 4, т.64 (год публикации - 2024)

12. Плетнев Н.В., Матюхин В.В. On the modification of the method of component descent for solving some inverse problems of mathematical physics Computer Research and Modeling, VOL. 15 NO. 2 P. 301–316 (год публикации - 2023) https://doi.org/10.20537/2076-7633-2023-15-2-301-316

13. Рогозин А., Ярмошик Д., Копылова К., Гасников А. Decentralized Strongly-Convex Optimization with Affine Constraints: Primal and Dual Approaches Communications in Computer and Information Science, volume 1739, pp 93–105 (год публикации - 2023) https://doi.org/10.1007/978-3-031-22990-9_7

14. Руденко В.Д., Юдин Н.Е., Васин А.А. Survey of convex optimization of Markov decision processes Computer Research and Modeling, vol. 15, no. 2, pp. 329–353 (год публикации - 2023) https://doi.org/10.20537/2076-7633-2023-15-2-329-353

15. Савчук О., Стонякин Ф., Алкоуса М., Забирова Р., Титов А., Гасников А. Online Optimization Problems with Functional Constraints Under Relative Lipschitz Continuity and Relative Strong Convexity Conditions Communications in Computer and Information Science, volume 1881, pp 29–43 (год публикации - 2023) https://doi.org/10.1007/978-3-031-43257-6_3

16. Садыков С. И., Лобанов А. В., Райгородский А. М. Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition Programming and Computer Software, Vol. 49, p. 535–547 (год публикации - 2023) https://doi.org/10.31857/S0132347423060079

17. Скачков Д.А., Гладышев С.И., Райгородский А.М. Experimental comparison of PageRank vector calculation algorithms Computer Research and Modeling, vol. 15, no. 2, pp. 369-379 (год публикации - 2023) https://doi.org/10.20537/2076-7633-2023-15-2-369-379

18. Скорик С.Н., Пырэу В.В., Седов С.А., Двинских Д.М. Comparsion of stochastic approximation and sample average approximation for saddle point problem with bilinear coupling term Computer Research and Modeling, vol. 15, no. 2, pp. 381–391 (год публикации - 2023) https://doi.org/10.20537/2076-7633-2023-15-2-381-391

19. Стонякин Ф., Курузов И., Поляк Б. Stopping Rules for Gradient Methods for Non-convex Problems with Additive Noise in Gradient Journal of Optimization Theory and Applications, 198, 531–551 (год публикации - 2023) https://doi.org/10.1007/s10957-023-02245-w

20. Хлебников М.В. PI Controller Design for Suppressing Exogenous Disturbances Automation and Remote Control, Volume 84, Issue 8, Pages 901–917 (год публикации - 2023) https://doi.org/10.25728/arcRAS.2023.38.46.002

21. Хлебников М.В. A Comparison of Guaranteeing and Kalman Filters Automation and Remote Control, том 84, 389–411 (год публикации - 2023) https://doi.org/10.1134/S0005117923040094

22. Хлебников М.В., Стефанюк Е.А. Peak-Minimizing Design for Linear Control Systems with Exogenous Disturbances and Structured Matrix Uncertainties Control Sciences, Issue 3, Pages 9–14 (год публикации - 2023) https://doi.org/10.25728/cs.2023.3.2

23. Чернов А., Лисаченко А. Convergence Rate of Gradient-Concordant Methods for Smooth Unconstrained Optimization Lecture Notes in Computer Science, volume 14395, p 33–44 (год публикации - 2023) https://doi.org/10.1007/978-3-031-47859-8_3

24. Чернов А., Флерова А., Жукова А. Application of Optimization Methods in Solving the Problem of Optimal Control of Assets and Liabilities by a Bank Lecture Notes in Computer Science, volume 14395, p. 235–250 (год публикации - 2023) https://doi.org/10.1007/978-3-031-47859-8_17

25. Чернов А.В., Жукова А.А. Numerical Analysis of the Model of Optimal Savings and Borrowing Lecture Notes in Computer Science, volume 13781, стр. 165-176 (год публикации - 2023) https://doi.org/10.1007/978-3-031-22543-7_12

26. Чикаке Т., Гольденгорин Б. Dimensionality reduction using pseudo-Boolean polynomials for cluster analysis Springer Optimization and Its Applications, volume 202,pp 59–72 (год публикации - 2023) https://doi.org/10.1007/978-3-031-31654-8_4

27. Чикаке Т., Гольденгорин Б., Самосюк А. Pseudo-Boolean Polynomials Approach to Edge Detection and Image Segmentation Springer Optimization and Its Applications, volume 202, pp 73–87 (год публикации - 2023) https://doi.org/10.1007/978-3-031-31654-8_5

28. Шатов Д.В. PI and PID Controllers Design for Tracking Systems via LQ Criterion IEEEXplore, - (год публикации - 2024)

29. Зубов Владимир Иванович, Албу Алла Филипповна Программа определения зависимости коэффициента теплопроводности вещества от температуры -, 2023661763 (год публикации - )