Все выпуски

Около года назад в журнале был собран первый специальный выпуск, всецело посвященный численным методам оптимизации. Как уже отмечалась в первом выпуске, в школе ФПМИ МФТИ сформировался коллектив, который достаточно активно пишет статьи по численным методам оптимизации и их приложениям (в том числе в анализе данных) на разные ведущие научные конференции, в ведущие журналы. В 2022 году коллектив был оформлен как научная лаборатория математических методов оптимизации в МФТИ (https://labmmo.ru/). Вся эта активность предполагает ежегодное вовлечение молодежи, которая готовит свои первые научные работы. Такое вовлечение традиционно происходит на проектных сменах в Научно-технологическом университете «Сириус», а также на курсах, которые сотрудники лаборатории читают в МФТИ. Стоит отметить, что с одной проектной смены может быть подготовлены десятки статей, как это было, например, на проектной смене 2020 года (http://dmivilensky.ru/opt/2020.html). Обычно с одного курса лекций, на котором также предлагаются проекты, статей получается поменьше, но в итоге с курса лекций появляется 3–4 статьи. В данный специальный выпуск в основном вошли статьи, которые были выполнены молодыми учеными (как правило, студентами/аспирантами школы ФПМИ МФТИ) в рамках проектной смены «Современные методы теории информации и оптимизации» (рук. А.С. Ненашев, даты проведения — октябрь–ноябрь 2022 года) и в рамках курса «Математика больших данных» (лектор А.В. Гасников, курс читался в осеннем семестре 2022/2023 учебного года; видео к курсу доступны на YouTube).

За прошедшие два года российское (советское) оптимизационное сообщество потеряло несколько ярких специалистов: А.И. Голиков, В.Г. Жадан, Ю.М. Ермольев, Ф.П. Васильев, . . . . Но особо хотелось бы обратить внимание на то, что 3 февраля 2023 года не стало Бориса Теодоровича Поляка. Без преувеличения можно сказать, что это был один из ведущих в мире специалистов в области численных методов оптимизации и оптимального управления. Его уход — это, безусловно, невосполнимая потеря для мировой науки. В память о Борисе Теодоровиче мы начинаем этот специальный выпуск статьей, посвященной его научному пути. Уверены, что еще будет написано много статей и воспоминаний об этом выдающемся человеке. Надеемся, что данная статья сподвигнет коллег оставить свои воспоминания о Борисе Теодоровиче.

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

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

В статье Александра Масловского с соавторами произведен анализ современных работ по теме многокритериальной оптимизации и построения моделей для решения задачи предискажения сигнала усилителя мощности базовой станции сотовой связи. В статье показывается, что возможно найти структуру (сохранив производительность), имеющую меньшее количество используемых ресурсов, быстрее, чем полный перебор по всему словарю из заданных параметров. Статья была выполнена в рамках проектной смены в «Сириусе». Отметим, что с 2022 года в наших проектных сменах, проводимых в «Сириусе», участвуют студенты магистратуры Университета «Сириус». Этот проект был предложен компаний «Хуавей» (лекции прочитал Андрей Воробьев, а проект вел Александр Масловский) и вызывал интерес как раз у студентов «Сириуса». По результатам выполнения проекта появилась статья.

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

В статье Ирины Подлипновой с соавторами рассмотрены способы расчета усредненных ценовых матриц при наличии нескольких способов передвижения в улично-дорожной сети. Предложен способ расчета усредненной матрицы цен на основе модели дискретного выбора. Для указанного способа выведены ограничения на калибровочные параметры, необходимые для соблюдения условия неотрицательности цены при любых заданных полезностях каждого из отдельно взятого способа передвижения. Также рассмотрен перенос понятия усредненной полезности из модели модального расщепления в гравитационную модель и показана необходимость перекалибровки гравитационной функции при применении logsum-усреднения. Статья содержит демонстрационные расчеты, выполненные в программе для транспортного моделирования TransNet (написанной одним из соавторов статьи В.И. Швецовым) для упрощенной модели федеральной территории «Сириус». Приведенный пример отражает, что представленный в работе способ усреднения ценовых матриц более правдоподобно описывает реальность, чем классические подходы. Статья была выполнена в рамках проектной смены в «Сириусе».

В статье Варвары Руденко с соавторами рассмотрен обзор исторических достижений и современных результатов в области марковских процессов принятия решений (Markov Decision Process, MDP) и выпуклой оптимизации. Представлены классические теоретические результаты, такие как фундаментальное уравнение Беллмана и построенные на его основе критерии оптимальности политики, основные итеративные алгоритмы оптимизации политики, построенные на решении уравнений Беллмана. Представлена альтернатива к подходу Q-обучения — метод прямой максимизации средней награды агента для избранной стратегии от взаимодействия со средой. Таким образом, решение данной задачи выпуклой оптимизации представимо в виде задачи линейного программирования. В работе демонстрируется, как аппарат выпуклой оптимизации применяется для решения задачи обучения с подкреплением (Reinforcement Learning, RL). В работе также рассматривается вопрос сложности оптимизации MDP относительно количества троек «состояние–действие–награда», получаемых в результате взаимодействия со средой. Представлены оптимальные границы сложности решения MDP в случае эргодического процесса с бесконечным горизонтом, а также в случае нестационарного процесса с конечным горизонтом, который можно перезапускать несколько раз подряд или сразу запускать параллельно в нескольких потоках, и рассмотрены последние результаты по уменьшению зазора нижней и верхней оценки сложности оптимизации MDP с усредненным вознаграждением (Averaged MDP, AMDP). А также рассматриваются вещественнозначная параметризация политики агента и класс градиентных методов оптимизации через максимизацию Q-функции ценности. В частности, представлен специальный класс MDP с ограничениями на ценность политики (Constrained Markov Decision Process, CMDP), для которых предложен общий прямодвойственный подход к оптимизации, обладающий сильной двойственностью. Статья была выполнена в рамках проектной смены в «Сириусе».

В статье Ивана Самойленко с соавторами представлена теоретико-игровая модель межгрупповой конкуренции, в которой эгоистичные агенты в некоторых ситуациях действуют кооперативно. Хотя связанные с такой ситуацией явления (в частности, то, что рост межвидовой конкуренции ведет также к росту уровня внутривидовой кооперации) ранее наблюдались эмпирически, до сих пор не было математической модели, в рамках которой эти наблюдения были бы верными. Авторы ввели параметры, которые, во-первых, имеют физическую интерпретацию в рамках эволюционной модели (родство и уровень дефицитности ресурса), а во-вторых, позволяют показать, что равновесные состояния в такой модели удовлетворяют биологическим законам. Также было продемонстрировано соответствие ранее полученным экономическим результатам в области изучения явления coopetition. Также в рамках численного моделирования авторами показано существование фазового перехода при увеличении неопределенности (при отсутствии знания агентов о текущих стратегиях нескольких других участников системы). Незначительный рост приводит к тому, что система перестает быть стабильной и показывает некоторую хаотическую динамику около равновесия. Статья была выполнена в рамках курса «Математика больших данных».

В статье Даниеля Скачкова с соавторами приводятся детали реализаций алгоритма Markov Chain Monte Carlo (MCMC) и двух версий алгоритма Григориадиса – Хачияна, адаптированных для задачи поиска вектора PageRank. В статье проводится ряд численных экспериментов на сгенерированных графах, которые имеют различные значения спектральной щели. Эксперименты подтверждают преимущество методов, использующих алгоритм Григориадиса – Хачияна, на графах с малыми значениями спектральной щели по сравнению с MCMC, как и предсказывает теория. Таким образом, авторам впервые удалось реализовать алгоритм Григориадиса – Хачияна эффективно с точки зрения практики. Статья была выполнена в рамках курса «Математика больших данных».

В статье Сергея Скорика с соавторами был проведен сравнительный анализ онлайн- и офлайн-методов решения задачи стохастической оптимизации на примере выпуклой и седловой задач. Такое сравнение имело цель выявить общие закономерности в оценках вычислительной сложности соответствующих алгоритмов, а также найти пробелы в результатах для седловой постановки в сравнении с соответствующей выпуклой задачей стохастической оптимизации. В частности, в данной работе были проработаны вопросы сопоставления алгоритмической сложности передовых онлайн-алгоритмов с существующим офлайн-алгоритмом и точности его решения вспомогательной задачи. Также рассмотрение седловой задачи как обобщение выпуклой позволило перенести на седловую задачу результаты онлайн-алгоритма, который работает в выпуклом случае, когда целевая функция удовлетворяет условию $\gamma$-роста. Статья была выполнена в рамках проектной смены в «Сириусе».

В статье Федора Стонякина и Сейдамета Аблаева с соавторами получены новые результаты о сходимости субградиентных методов на классе слабовыпуклых липшицевых задач с острым минимумом. Доказан вариант оценки скорости сходимости субградиентного метода со скоростью геометрической прогрессии, учитывающий приближение итеративной последовательности ко множеству точных решений. Этот результат обобщен на класс задач с ограничениями-неравенствами, для чего авторами предложены оригинальный вариант условия острого минимума и соответствующие схемы с переключениями по продуктивным и непродуктивным шагам. Наконец, для предложенного в 2018 г. D. Davis с соавторами класса относительно слабовыпуклых задач при дополнительных предположениях об относительной липшицевости и относительном остром минимуме доказана сходимость сyбградиентного метода со скоростью геометрической прогрессии. Результаты во многом основаны на известной идее Б.Т. Поляка о выборе шага cyбградиентного метода с учетом оптимального значения функции $f^*$. Авторами детально исследован вариант такого подхода для относительно липшицевых задач, включая теоретический результат об описании влияния погрешностей доступной методу информации о целевой функции и/или субградиента на качество выдаваемого решения.

Статья Федора Стонякина и Олега Савчука с соавторами посвящена исследованию адаптивных методов градиентного типа для задач с аналогами предложенного несколько лет назад Ю.Е. Нестеровым с соавторами условия сильной выпуклости относительно дивергенции Брэгмана. Рассмотрен класс выпуклых оптимизационных задач с аналогом условия квадратичного роста относительно дивергенции Брэгмана (относительный функциональный рост), который позволяет предложить схему рестартов адаптивных методов для выпуклых задач по параметру роста, что позволяет существенно повысить гарантии скорости сходимости. Так, для выпуклых относительно гладких задач можно обосновать линейную скорость сходимости. Предложен вариант универсального градиентного метода для классов относительно гладких и относительно липшицевых задач с относительным функциональным ростом. Предложен аналог условия Поляка – Лоясиевича относительно дивергенции Брэгмана, который позволяет обосновать сходимость со скоростью геометрической прогрессии на классе относительно гладких задач. Доказана оценка скорости сходимости метода градиентного типа с адаптивно подбираемыми параметрами. Проведенные эксперименты показали примечательный факт: относительно сильно выпуклая функция может не удовлетворять относительному варианту условия градиентного доминирования, что довольно контрастирует с классической ситуацией.

В статье Ярослава Томинина и соавторов рассматриваются сильновыпукло-сильновогнутые небилинейные седловые задачи с разными числами обусловленности по прямым и двойственным переменным. Для задачи с гладкими композитами, один из которых имеет структуру с конечной суммой, предлагается алгоритм уменьшения дисперсии с оценками сложности, превосходящими существующие ограничения в литературе. Также в данной работе рассматриваются седловые задачи конечной суммы с композитами, и авторы предлагают несколько алгоритмов в зависимости от свойств составных членов. Когда составные члены являются гладкими, авторы также получают лучшие оценки сложности, чем существуют в литературе. Предложенные алгоритмы позволяют разделить сложность, т. е. оценить для каждой функции в задаче количество вызовов оракула, достаточное для достижения заданной точности. Это важно, так как разные функции могут иметь разную арифметическую сложность оракула, а дорогие оракулы желательно вызывать реже, чем дешевые. Статья была выполнена в рамках проектной смены в «Сириусе».

В статье Цзявэй Чэнь с соавторами изучен вопрос решения негладкой седловой задачи в распределенной настройке, где последнее означает, что целевая функция представляется в виде суммы нескольких слагаемых, распределенных между группой вычислительных узлов. Каждый узел имеет доступ к локально хранимой функции. Узлы, или агенты, обмениваются информацией через некоторую коммуникационную сеть, которая может быть централизованной или децентрализованной. В статье обобщена техника сглаживания на седловые задачи. Разработаны алгоритмы для централизованной и децентрализованной оптимизации, а также получены оптимальные оценки (по числу итераций и оракульной сложности) для выпуклоогнутого и сильновыпукло-сильновогнутого случаев. Статья была выполнена в рамках курса «Математика больших данных».

А.В. Гасников, А.И. Лобанов