Аннотация результатов, полученных в 2016 году
Для линейных задач управления исследованы эффекты "всплеска" для ненулевых начальных условий. Для систем в канонической форме, у которых все собственные числа действительные, отрицательные и равные, отклонения траекторий (для некоторых начальных условий) определены в явном виде. Показано, что большие отклонения наблюдаются как для больших, так и для малых скоростей затухания. Получены оценки всплеска снизу для наихудшего случая для систем в канонической форме. Полученные результаты обобщены на системы общего вида. Предложены оценки сверху для эффекта всплеска, основанные на построении инвариантного эллипсоида для замкнутой системы. Предложены новые подходы к построению функций Ляпунова для общих нелинейных систем. Они позволяют упростить обоснование асимптотической устойчивости и построение области притяжения точки равновесия. В качестве примеров рассмотрено движение физического маятника с возмущающей силой и синхронизация пары нелинейных осцилляторов. Обоснована также локальная асимптотическая устойчивость нелинейной системы с электромагнитным тормозом. Для нелинейных задач управления изучались проблемы стабилизации билинейной системы. На основе техники линейных матричных неравенств и квадратичных функций Ляпунова предложен подход к построению так называемого эллипсоида стабилизируемости такого, что траектории замкнутой системы, начинаясь внутри эллипсоида, асимптотически стремятся к нулю. Предложенный подход позволяет эффективно строить невыпуклые аппроксимации областей стабилизируемости билинейных систем управления. Разрабатывались новые подходы к компактному представлению больших массивов данных. В этом направлении предложены два робастных варианта метода главных компонент, основанные на хуберовском статистическом подходе. Оба они сводятся к невыпуклым задачам оптимизации с векторными или матричными переменными. Для численного решения задач оптимизации применяется метод итеративной квадратичной аппроксимации. Численная проверка методов демонстрирует их быструю сходимость и преимущества по сравнению с классическим методом главных компонент. Проводилось исследование квадратичных отображений, которые играют большую роль в ряде практических задач (например, электроэнергетике). Оно основывается на анализе выпуклости/невыпуклости образа при таком отображении. Построен критерий выпуклости и алгоритм поиска невыпуклостей в многомерном образе. Используемые результаты выпуклого анализа (в частности, теория двойственности) и техника линейных матричных неравенств позволили сформулировать достаточное условие неразрешимости системы квадратичных уравнений. Этот результат нашел свое применение при проверки существования равновесия в DC системах с постоянным нагрузками. Изучались задачи безусловной минимизации для выпуклых и невыпуклых функций. Получены новые результаты для обоснования метода тяжелого шарика с помощью новых функций Ляпунова. Предложены подходы, позволяющие обобщить идеологию зеркального спуска на метод тяжелого шарика.

Аннотация результатов, полученных в 2017 году
В отчетном году работа коллектива продолжалась по нескольким запланированным направлениям и дополнительно по ряду вновь возникших задач. 1. Разработка новых подходов к анализу и стабилизации нелинейных систем управления, основанная на использовании нестандартных функций Ляпунова Основные исследования были направлены на проблемы анализа и синтеза нелинейных систем управления. Прежде всего, оказались очень полезными параллели между задачами оптимизации и условиями асимптотической устойчивости, обнаруженные в прошлом году (см. пункт 1 отчета прошлого года и статью Polyak B.T., Shcherbakov P.S. "Optimization and Asymptotic Stability’’ // International Journal of Control (published on-line November 2016). На их основе удалось построить новые функции Ляпунова, которые позволяют обосновывать не только факт асимптотической устойчивости ряда нелинейных систем (что удавалось сделать раньше только на основе достаточно сложного исследования с использованием теоремы Барбашина-Красовского), но и доказать экспоненциальную скорость сходимости к точке равновесия. В частности, такой подход дал возможность обосновать эффект синхронизации системы двух связанных осцилляторов . Кроме того, на этом пути удается получить оценки области притяжения точек равновесия, которые оказываются заметно более широкими, чем имевшиеся ранее . Это направление исследований весьма перспективно и будет продолжено далее. В частности, аналогичная техника позволяет исследовать поведение алгоритмов оптимизации, содержащих инерционные члены. Такие алгоритмы (метод "тяжелого шарика" и ускоренный метод Нестерова) получили сейчас огромное распространение как наиболее эффективные методы оптимизации для задач очень большой размерности, примерами которых являются алгоритмы настройки многослойных нейронных сетей. Успехи современных методов "глубокого обучения" (deep learning) во многом опирается именно на использование таких алгоритмов минимизации. Первые результаты подобного типа относительно метода "тяжелого шарика" получены в наших публикациях, они будут обобщены в исследованиях следующего года. 2. Разработка критериев робастной устойчивости билинейных систем управления Это направление также связано с нелинейными системами управления, с их важным классом - билинейными системами. В прошлом году была развита техника конструирования эллипсоидов стабилизируемости для билинейных систем, основанная на методе инвариантных эллипсоидов и аппарате линейных матричных неравенств. Она позволяет получать простые оценки областей стабилизируемости билинейных систем. При этом система замыкалась при помощи линейной статической обратной связи по состоянию. В отчетном году была решена более общая сложная задача, предполагающая стабилизацию билинейной системы при помощи линейного динамического регулятора по выходу системы. Для этого пришлось прибегнуть к использованию специально разработанного итерационного метода, позволившего свети поставленную задачу к серии задач полуопределенного программирования и одномерной минимизации, легко решающихся численно. Численное моделирование демонстрирует работоспособность и эффективность предложенного подхода, который в полной мере может быть обобщен на различные робастные постановки задач (в частности - со структурированной неопределенностью в матрице системы), на задачи в дискретном времени и другие. 3. Условия разрешимости и новые методы решения для недоопределенных систем нелинейных уравнений Этот цикл исследований относится к решению систем нелинейных алгебраических уравнений, причем число уравнений может быть меньше числа переменных. Такие ситуации часто возникают как в практических задачах (см. приложения к электроэнергетике ниже), так и при теоретических исследованиях. Для недоопределенных систем нелинейных уравнений получены условия существования решений, существенно расширяющие известные границы сходимости. Предложено обобщение классического метода Ньютона на случай недоопределенных уравнений. Исследованы две модификации метода Ньютона, объединяющие метод Ньютона и демпфированный метод Ньютона. Первая модификация использует константы регулярности нелинейного уравнения и константу Липшица производной функций, входящих в нелинейные уравнения. Вторая модификация использует только константу Липшица. Существенно, что сначала методы выполняют конечное число шагов с линейной скоростью сходимости (для число таких шагов получена явная оценка), а только потом скорость сходимости становится явно квадратичной. В результате скорость сходимости обоих методов является квадратичной, но полученная декомпозиция на два этапа позволяет точнее оценить качество работы методов. Важным результатом стала обнаруженная связь между параметрами задачи и радиусом области сходимости. Для предлагаемых методов размер области сходимости удалось значительно увеличить. При определенном соотношении параметров задачи доказана глобальная сходимость предложенных методов. Предложенные модификации метода Ньютона позволяют решать невыпуклые задачи безусловной минимизации специального вида как частный случай нелинейных уравнений. Кроме того, они с успехом применимы к вполне определенным системам нелинейных уравнений, с числом переменных равным числу неизвестных. Все полученные результаты являются новыми, в том числе и для вполне определенных систем нелинейных уравнений. 4. Приложения к электроэнергетике Эти приложения базировались на двух направлениях исследований, описанных выше. Первая группа работ относилась к разрешимости уравнений, описывающих статические режимы в энергетических системах (так называемые power flow equations). Дело в том, что в современных электрических сетях мощности как источников энергии, так и потребителей могут сильно меняться как вследствие наличия нетрадиционных источников (ветрогенераторы, солнечные батареи) так и вследствие возможных аварий. Поэтому важно знать возможные интервалы мощностей, гарантирующие нормальную работу сети. С математической точки зрения речь идет о разрешимости нелинейных (а именно, квадратических) уравнений при различных правых частях в окрестности номинального режима. Это именно та задача, которая описывалась выше в разделе 3. Полученные на этом пути оценки области допустимых режимов оказываются более широкими, чем даваемые традиционными методами. Другое направление приложений связано с анализом динамической устойчивости систем, что является одной из самых вычислительно сложных задач в электроэнергетике. В тоже время возможность быстрого анализа необходима для обеспечения надежной работы Централизованных Систем Противоаварийной Автоматики. Представлены новые подходы к быстрому анализу устойчивости, основанные на методах построения функций Ляпунова, описанных в разделе 1. Мы проводим сравнение с более известным методом энергетических функций и представлен ряд стратегий для использования функций Ляпунова для вычисления оптимальных управляющих воздействий. Для анализа динамической устойчивости существуют две группы методов. Одна основана на прямом расчете послеаварийной динамики, прогонке большого количества сценариев и подготовке таблиц противоаварийных действий. Рост вычислительных мощностей и совершенствование программного обеспечения для подобных расчетов обеспечивают их широкое распространение в практике системных операторов. Ко второй группе относятся прямые или качественные методы анализа устойчивости. В большинстве своем эти методы основаны на выборе энергетического функционала для анализа устойчивости траекторий динамической системы. Ключевым этапом применения энергетического метода является поиск ближайшего неустойчивого равновесия (седловой точки) в многомерном пространстве, что само по себе нетривиально, а подбор функции Ляпунова для конкретной системы при хорошо разработанной теории все еще считается скорее искусством, чем технологией. 5. Методы зеркального спуска для выпуклой оптимизации В 2017 г. продолжена работа по распространению и обоснованию метода зеркального спуска с оракулом первого порядка для задач стохастической выпуклой оптимизации как в непрерывном, так и дискретном времени. Существенно новым является то, что техника зеркального спуска распространена теперь на методы с инерцией (примером которых является метод тяжелого шарика, упоминаемый в разделе 1). Поскольку целевая функция рассматривается как математическое ожидание случайной функции потерь, то в частном случае, когда функция потерь неслучайная, получены и исследованы соответствующие методы детерминированной выпуклой оптимизации. Отметим, что полученные алгоритмы зеркального спуска с инерцией можно рассматривать как нетривиальное обобщение стандартного метода градиента, объединенного с методом тяжелого шарика. 6. При изучении задач оптимизации часто применяются рандомизированные алгоритмы. Простейшим из них является метод Монте-Карло. Вопрос о его эффективности при решении задач оптими​зации является открытым, и было проведено исследование этого вопроса. В простейшей задачи минимизации линейной функции, заданной на многомерном шаре, получены явные выражения для минимального количества точек, равномерно гене​рируемых на шаре, такого, которое гарантирует заданную точность выборочного мини​мума функции с заданной вероятностью при данной размерности шара. Приводятся ана​логичные выражения для оценивания среднего и медианы. Схожие результаты получены для схемы многокритериальной оптимизации на шаре. Аналогичные оценки получены для равномерного распределения на гиперкубе; проведено сравнение с регулярной сеткой и с lp-tau последовательностями. Результаты подтверждают ограничительность применения методов Монте-Карло в задачах минимизации при больших размерностях вследствие чрезвычайной трудоемкости даже для "хороших" классов задач. 7. Изучалось явление всплеска - больших уклонений решений устойчивых систем от положения равновесия. Ранее этот важный эффект в работах нашего коллектива исследовался для систем линейных дифференциальных уравнений. Теперь сделана попытка обобщить эти результаты для скалярных линейных разностных уравнений с ненулевыми начальными условиями на конечных моментах времени. Для некоторых общих классов распределения корней характеристического уравнения и ряда специальных начальных условий получены точные аналитические выражения для момента и величины максимального уклонения. В других ситуациях получены нижние оценки величины всплеска. Получены нижние оценки (или точные выражения) для величины максимума норм степеней специальных классов устойчивых по Шуру матриц; эта задача тесно связана с поведением решений устойчивых векторных разностных уравнений. В такой схеме для шуровских матриц общего вида предложены процедуры получения верхних оценок величины всплеска; численное решение получено с использованием аппарата линейных матричных неравенств. Предполагается продолжить эти исследования в следующем году и связать их с поведением ускоренных методов оптимизации (см. раздел 1 выше). 8. Социальные сети и связанный с ними круг проблем являются особым случаем в общей теории сетевых динамических систем. В отличие многих от моделей и задач в области мультиагентных систем, в социальных сетях редко можно наблюдать такое явление как консенсус мнений, скорее оно является вырожденным случаем. В результате взаимодействия и общения мнения людей и социальных подгрупп как правило образуют кластеры разного размера, а не приходят к единодушию. Линейная дискретная модель Фридкина-Джонсена обобщает идею консенсусной модели ДеГроота и, учитывая предубеждения агентов, позволяет описать поведение с рассогласованием/кластеризацией мнений. Было получено обобщение модели Фридкина-Джонсена на случай агентов с многомерными взаимосвязанными мнениями: агенты обсуждают одновременно несколько тем, в определенном смысле связанных друг с другом. Введено новое понятие матрицы зависимостей между темами обсуждения, являющееся математическим представления такого понятия социальной психологии как «система убеждений», введено понятие «забывчивого», т.е. агента, не являющегося «упертым» (в терминологии Фридкина-Джонсена) и не подверженного влиянию других упертых агентов. Для предложенной модели сетевой системы сформулированы необходимые и достаточные критерии сходимости и устойчивости, доказаны соответствующие теоремы. На примере с близкой к единичной матрицей зависимостей между темами показано, на сколько существенно отличается динамика такой системы от системы с независимыми темами обсуждения (единичной матрицей зависимостей). Полученная в работе модель является централизованной: на каждом шаге вся социальная сеть меняет свое состояние, что является довольно сильным упрощением реальных процессов взаимодействия в социальных группах. В связи с этим также была предложена версия модели с асинхронным случайным взаимодействием агентов в сети, состояния которой в среднем сходятся положению равновесия централизованной модели. Результаты анализа поведения такой системы сопровождаются строгими доказательствами. Результаты моделирования, проведенные на сетевых системах большой размерности, подтверждают корректность сделанных теоретических выводов.

Аннотация результатов, полученных в 2018 году
Продолжались исследования поведения траекторий систем, описываемых дифференциальными или разностными уравнениями, при ненулевых начальных условиях. В прошлые годы основные усилия были сосредоточены на получении оценок для непрерывных систем, в текущем году они были обобщены на дискретный случай. Найдены верхние и нижние границы отклонений при различных предположениях о собственных значениях характеристических уравнений. Оказалось, что поведение траекторий даже для случая систем второго порядка отнюдь не тривиально. В частности, возможны большие уклонения и немонотонное поведение решений. Приложение этих результатов к исследованию ускоренных методов оптимизации оказалось чрезвычайно плодотворным. Оно объяснило эффект немонотонной сходимости ускоренных алгоритмов типа "тяжелого шарика" в задачах безусловной оптимизации, а построенные новые функции Ляпунова позволили контролировать сходимость таких методов и настраивать параметры в них. В упомянутых исследованиях делался акцент на нижние границы уклонений (т.е. на неизбежные большие уклонения при "плохих" начальных условиях). С другой стороны, получены эффективные оценки верхних границ (которые не могут быть превзойдены при любых ограниченных начальных условиях). Начат большой цикл исследований по применению методов градиентного типа при оптимизации с ограничениями в форме равенств. Здесь принципиальным фактом является невыпуклость подобных задач. Имевшиеся ранее результаты давали лишь локальные условия сходимости методов. В проведенных работах удалось существенно расширить эти результаты. В частности, предложены варианты метода проекции градиента и условного градиента для невыпуклых ограничений, удалось доказать их сходимость и оценить скорость сходимости. Для обобщенного метода Ньютона, который был введен нами ранее, продолжались исследования и обобщения. Они включали новые варианты выбора длины шага, точные оценки числа итераций и области сходимости, использование различных норм. Выяснилась возможность применения метода для задач оптимального управления. Предложены инерционные варианты метода зеркального спуска для стохастических задач выпуклой оптимизации. Эти методы обладают рядом преимуществ; никаких аналогов таких методов ранее не было известно. В области нелинейного управления велись исследования, посвященные стабилизации и робастному управлению для билинейных систем. В частности, рассмотрена проблема стабилизации дискретной билинейной системы управления. На основе техники линейных матричных неравенств и квадратичных функций Ляпунова предложен регулярный подход к построению так называемого эллипсоида стабилизируемости такого, что траектории замкнутой системы, начинаясь внутри эллипсоида, асимптотически стремятся к нулю. Предложенный подход позволяет эффективно строить невыпуклые области стабилизируемости непрерывных и дискретных билинейных систем управления. Полученные результаты распространены на робастную постановку задачи -- со структурированной неопределенностью в матрице системы.