Анализ методов первого порядка для оптимизационных задач с относительными аналогами гладкости, липшицевости и сильной выпуклости тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Савчук Олег Сергеевич

• Савчук Олег Сергеевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Савчук Олег Сергеевич

Введение

Глава 1. Методы зеркального спуска для относительно липшицевых и относительно сильно выпуклых задач оптимизации с ограничениями-неравенствами

1.1 Методы зеркального спуска для задач онлайн-оптимизации с функциональными ограничениями в условиях относительной липшицевости и относительной сильной выпуклости

1.1.1 Зеркальный спуск для относительно липшицевых и относительно сильно выпуклых задач онлайн-оптимизации

с ограничениями-неравенствами

1.1.2 Онлайн-зеркальный спуск с регуляризацией

1.1.3 Случай задач онлайн-оптимизации с функциональными ограничениями типа неравенств

1.2 Аналоги метода зеркального спуска для задач сильно выпуклого программирования с липшицевыми функциональными ограничениями

1.2.1 Субградиентная схема с переключениями для задач сильно выпуклого программирования с липшицевыми функционалами

1.2.2 Субградиентный метод для задач сильно выпуклого программирования с использованием 6-субградиентов

1.2.3 Зеркальный спуск для задач сильно выпуклой минимизации с ограничениями в условиях относительной липшицевости и относительной сильной выпуклости

Глава 2. Адаптивные методы первого порядка для относительно

липшицевых задач оптимизации

2.1 Адаптивные алгоритмы для относительно липшицевых задач выпуклой оптимизации

2.2 Адаптивные алгоритмы для относительно липшицевых задач относительно сильно выпуклой оптимизации

Стр.

Глава 3. Адаптивные и универсальные методы градиентного типа для относительно гладких и относительно липшицевых задач оптимизации

3.1 Универсальные методы первого порядка для относительно

гладких и относительно липшицевых задач выпуклой оптимизации

3.2 Универсальные методы градиентного типа для относительно гладких и относительно липшицевых задач относительно сильно выпуклой оптимизации

3.3 Адаптивный и универсальный варианты метода подобных треугольников для относительно гладких задач оптимизации

3.4 Аналоги условия относительной сильной выпуклости для относительно гладких задач и рестарты адаптивных и универсальных методов градиентного типа

3.4.1 Условие относительного функционального роста и

рестарты адаптивных методов градиентного типа

3.4.2 Аналог условия градиентного доминирования для относительно гладких задач оптимизации

Глава 4. Адаптивные прямо-двойственные методы с неточным

оракулом для относительно гладких задач оптимизации

4.1 Прямая и двойственная задачи

4.2 Прямо-двойственный градиентный метод для относительно

гладких задач оптимизации с неточным оракулом

4.3 Прямо-двойственный метод подобных треугольников для относительно гладких задач оптимизации с неточным оракулом

Заключение

Благодарности

Список сокращений и условных обозначений

Список литературы

Список рисунков

Введение диссертации (часть автореферата) на тему «Анализ методов первого порядка для оптимизационных задач с относительными аналогами гладкости, липшицевости и сильной выпуклости»

Введение

Актуальность темы исследования. Стремительное развитие различных отраслей науки в последнее время привело к необходимости разработки численных методов оптимизации в пространствах больших и сверхбольших размерностей. В связи с увеличением числа приложений, которые могут быть смоделированы в качестве задач large-scale оптимизации (в том числе возникающих в машинном обучении, оптимальном управлении, обработке сигналов, статистике и т. д.), методы первого порядка вызвали большой интерес при решении задач как гладкой, так и негладкой оптимизации [1; 2]. При этом особое место в современной теории оптимизации занимают градиентные методы [3]. Это объясняется низким объёмом потребляемой памяти и низкой стоимостью итераций, а также возможностью обоснования приемлемых оценок скорости сходимости, которые не содержат параметров размерности пространства. Однако, при этом необходимы некоторые предположения о функциональных свойствах таких задач (гладкость, липшицевость, сильная выпуклость и т.д.).

Несмотря на то, что классическое условие гладкости (условие Липшица градиента)

l|V f (х )-Vf (y)\U ^ L У х - у у Wx,y е Q

(здесь У • У* - норма в сопряженном пространстве Е* к конечномерному нормированному векторному пространству (Е,|| • ||), Q с Е - замкнутое выпуклое подмножество) является одним из ключевых при анализе методов первого порядка, существует множество приложений, в которых целевая функция (даже выпуклая и дифференцируемая) не обладает этим свойством, потому не может считаться достаточно гладкой в стандартном смысле, чтобы гарантировать приемлемую скорость сходимости вычислительных процедур. Например, это относится к обратной задаче Пуассона [4; 5] или задаче D-оптимального проектирования [6; 7], целевые функции которых включают в себя логарифм в виде логарифмического определителя или относительной энтропии. Значения градиента таких функций могут резко возрастать при приближении траектории метода к границе допустимой области.

В связи с этим относительно недавно появилось новое направление исследований, связанное с разработкой численных методов градиентного типа для задач оптимизации с относительно гладкими [8] и относительно сильно

выпуклыми [9; 10] функциями, для которых оценки скорости сходимости для неускоренных методов являются оптимальными с точностью до умножения на константу, не зависящую от параметров размерности задачи. Условие относительной гладкости [8; 9] предполагает замену условия липшицевости градиента на обобщенный вариант

/(У) < /(х) + (V/(х)- х> + ЬУ(),

где V(у,х) — широко используемый в оптимизации аналог расстояния между точками х и у, который называют дивергенцией Брэгмана [3; 11]. Обычно дивергенция Брэгмана вводится на базе вспомогательной выпуклой функции й (прокс-функции) [3], непрерывно дифференцируемой во всех точках выпуклого замкнутого множества Q:

V(у,х) = й(у) - й(х) - (х), у - X> Ух, у е й,

где (•, •> — скалярное произведение в К.и.

Понятие относительной сильной выпуклости [9; 10] обобщает обычную сильную выпуклость путём замены в соответствующем неравенстве выражения

2 У* - У У 2 на V(у,х):

/(х) + (V/(Х), у - х> + »У(у, х) ^ /(у) Ух, у е й,

где У • У 2 - евклидова норма.

Вышеописанные подходы позволили обобщить класс задач со стандартным условием Липшица градиента и проанализировать сходимость градиентных методов для более широкого класса функций, что обеспечивает их эффективное применение во многих приложениях. Вышеупомянутые обратная задача Пуассона и задача Б-оптимального проектирования также оказались относительно гладкими [9; 12]. Таким образом, был расширен класс задач выпуклой оптимизации, для которых имеет место линейная скорость сходимости методов градиентного типа (сходимость со скоростью геометрической прогрессии).

Также несколько лет назад для негладких оптимизационных задач был предложен подход, связанный с обобщением условия Липшица, которое предполагает замену ограниченности нормы субградиента IV/(х)||* ^ М так называемой относительной липшицевостью [10; 13]:

Мл/2У (у,х) IV/(х)||* < ; ,. ) Ух,у е й,у ф х у У - ху

или

(V/(х)- X> + М^IV(у,х) ^ 0 Ух,^ е <2.

Условие относительной липшицевости существенно обобщает классическое условие Липшица и охватывает множество довольно важных прикладных задач, включая задачу нахождения общей точки системы эллипсоидов (IEP) [10], а также задачу бинарной классификации методом опорных векторов (SVM) [10; 14].

Степень разработанности темы. Понятия относительной гладкости, относительной липшицевости и относительной сильной выпуклости позволили значительно расширить класс задач, к которым применимы методы градиентного типа с сохранением оптимальной скорости сходимости. Например [15; 16], для относительно липшицевых задач выпуклой оптимизации можно гарантировать оценку сложности вида -2 ), а для относительно гладких задач в выпуклом

случае имеет место оценка О^ , где - - точность по функции решения задачи оптимизации. Кроме того, авторы [15] показали, что для класса относительно гладких задач такая оценка в общем случае является неулучшаемой.

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

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

Разработка численных методов для решения задач негладкой онлайн-оптимизации в настоящее время представляет большой интерес в связи с появлением множества прикладных задач с соответствующей постановкой [17; 18]. Онлайн-оптимизация играет ключевую роль в решении многих задач машинного обучения, финансов, сетей и др [19—21]. Что касается второго вышеупомянутого класса задач, то задачи выпуклого программирования с

несколькими ограничениями типа неравенств также часто встречаются в различных приложениях, в связи с чем им посвящаются всё новые исследования, в том числе и в области субградиентных методов (см., например, [22] и имеющиеся там ссылки). Первый субградиентный метод, как известно, был предложен в [23] и обобщён для задач с ограничениями-неравенствами в [24], где и была предложена идея пошагового переключения между направлением субградиента целевого функционала и направлением субградиента функционала ограничения.

Для решения как задач онлайн-оптимизации, так и задач выпуклого программирования с ограничениями существует множество методов, одним из которых, в частности, является метод зеркального спуска [16; 25—27]. Действительно, обычное условие Липшица относительно евклидовой нормы может быть не очень удобным, а использование других прокс-структур приводит к необходимости использования вместо обычного субградиентного метода

1 2

хк+i := argmm{y<V/(хк),х - хк) + -||х - хк У2}

х eQ 2

метода зеркального спуска

хк+i := argmin{y<Vf (хк),х - хк) + V(х,хк)}. * eQ

Недавно в [28] для задач выпуклого программирования были предложены алгоритмы зеркального спуска как с адаптивным выбором шага, так и с адаптивным критерием остановки. Кроме того, в [29] также предложены адаптивные методы зеркального спуска для задач с липшицевым (вообще говоря, негладким) целевым функционалом и задач с липшицевым градиентом целевого функционала в случае, когда имеется несколько функциональных ограничений, а также рассматривается случай негладкого целевого функционала, равного максимуму нескольких гладких функционалов с липшицевым градиентом.

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

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

Для задач сильно выпуклого программирования с множеством ограничений в диссертации также предложен аналогичный подход к построению субградиентных методов первого порядка. Особенность предложенной методики — возможность использования в теоретических оценках качества выдаваемого решения параметров сильной выпуклости именно тех функционалов-ограничений, для которых нарушается условие продуктивности итерации. Ключевая идея заключается в объединении двух подходов: вышеописанной схемы с переключениями по продуктивным и непродуктивным шагам для онлайн-оптимизации и недавно предложенных в [29] модификаций зеркального спуска для задач выпуклого программирования, позволяющих игнорировать часть функциональных ограничений на непродуктивных шагах алгоритма.

Второе направление исследований связано с разработкой адаптивных градиентных методов первого порядка для относительно липшицевых и относительно гладких задач и с идеологией универсальных градиентных методов, предложенных Ю.Е. Нестеровым [30]. Особенность универсального метода, как известно, заключается в том, что в процессе работы метод сам настраивается на гладкость задачи и при этом не требует никакой информации о гладкости на входе [3]. Отметим, что отличие универсального метода от адаптивного в том, что настройка идёт не только на константу гладкости, но и на уровень гладкости функции [3].

Данное направление исследований вызвало интерес в связи с тем, что если вопрос с построением универсальных методов градиентного типа и обоснованием их вычислительных гарантий на классе обычных L-гладких и М-липшицевых задач на сегодняшний день не стоит [3; 30], то аналогичные результаты для универсальных методов на классе относительно L-гладких и относительно М-липшицевых задач не были получены вплоть до выхода нашего препринта [31]. Также стоит отметить, что через 4 дня после опубликования [31] появился препринт [32], авторы которого предложили несколько иной подход, использующий метод Adaptive mirror descent (AdaMir), и получили несколько иные теоретические результаты для относительно липшицевых и относительно гладких задач оптимизации.

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

Как известно [15], в отличие от обычныго гладкого случая, для класса выпуклых относительно гладких задач, вообще говоря, отсутствует возможность построения ускоренных методов с оптимальными оценками сложности ,

и потому в данном случае оценка сложности неускоренного метода

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

V ((1 - 9)х + 9г, (1 - 6)х + 0г) ^ (г, г) У0 е [0,1].

Данное свойство интересно тем, что для указанного класса задач обоснована возможность построения ускоренных методов первого поряка с оптимальными оценками скорости сходимости при у е (1;2] [12; 33]. Предложенный

в данной диссертационной работе подход является вполне целесообразным и обоснованным, поскольку широкое семейство дивергенций Брэгмана имеет внутренний (т.е. на всяком ограниченном множестве) коэффициент треугольного шкалирования уги = 2 [12]. В связи с этим для относительно гладких задач с треугольным шкалированным свойством дивергенции Брэгмана с у = 2 предложен универсальный вариант метода подобных треугольников [34] с аналогом неточного оракула О. Деволдера - Ф. Глинера - Ю.Е. Нестерова [34—38]

0 ^ /(х) - (/б(у) + (V/ь(у),х - у>) ^ ЬУ(х,у) + 6 Ух е й.

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

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

Важно отметить, что во многих случаях решение различных оптимизационных задач с ограничениями выполняется с помощью перехода к так называемой двойственной задаче [39]. При этом важным свойством некоторых методов оптимизации является прямо-двойственность [39—42]: это возможность восстанавливать достаточно эффективно решение двойственной задачи по прямой (или наоборот). Данный подход хорошо себя зарекомендовал в транспортных задачах [43—45], задаче бинарной классификации методом опорных векторов (SVM) [10; 14] и многих других [3]. В связи с этим в данной диссертационной работе предложены адаптивные (ускоренный и неускоренный) прямо-двойственные методы градиентного типа с неточным оракулом для относительно гладких задач выпуклой оптимизации. Получены теоретические результаты, описывающие влияние неточностей оракула и решения вспомогательных подзадач на качество выдаваемого решения.

Диссертационная работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Крымский федеральный университет им. В.И. Вернадского» и в федеральном государственном автономном образовательном учреждении высшего образования «Московский физико-технический институт (национальный исследовательский университет)».

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

Для достижения цели были поставлены следующие задачи диссертации:

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

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

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

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

Научная новизна работы.

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

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

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

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

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

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

Положения, выносимые на защиту.

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

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

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

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

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

1. 65-я и 66-я конференции МФТИ, 2023, 2024, Долгопрудный, Россия.

2. 22-я и 23-я Международные конференции «Mathematical optimization theory and operations research (MOTOR)», 2023, 2024, Екатеринбург, Омск, Россия.

3. IX Международная конференция «Quasilinear Equations, Inverse Problems and Their Applications (QIPA)», 2023, Долгопрудный, Россия.

4. Международная конференция «Наукоёмкие технологии - основа современного цифрового промышленного производства» в рамках VII Международного научного Форума профессорско-преподавательского состава и молодых учёных«ЦИФРОВЫЕ ТЕХНОЛОГИИ: НАУКА, ОБРАЗОВАНИЕ, ИННОВАЦИИ», 2024, Симферополь, Россия.

5. 14-я и 15-я Международные молодежные научно-практические конференции «Прикладная математика и фундаментальная информатика» (ПМиФИ), 2024, 2025, Омск, Россия.

Основные научные результаты были опубликованы в рецензируемых изданиях, индексируемых в базах данных Scopus и RSCI. Всего автором опубликовано 6 работ по теме диссертации в изданиях, индексируемых в базе данных Scopus, из которых 4 статьи в журналах, включенных в перечень научных журналов, рекомендованных Московским физико-техническим институтом (МФТИ, Физтех) и имеющих в нём категорию К1. Список всех публикаций автора по теме диссертации:

1. Савчук О. С., Титов А. А., Стонякин Ф. С., Алкуса М. С. Адаптивные методы первого порядка для относительно сильно выпуклых задач оптимизации // Компьютерные исследования и моделирование. — 2022. — Т. 14, No 2. — С. 445-472.

2. Стонякин Ф. С., Савчyк О. С., Баран И. В., Алкуса М. С., Титов А. А. Аналоги условия относительной сильной выпуклости для относительно гладких задач и адаптивные методы градиентного типа // Компьютерные исследования и моделирование. — 2023. — Т. 15, No 2. — С. 413-432.

3. Stonyakin F. S., Alkousa M. S., Titov A. A., Savchuk O. S., Gasnikov A. V. Adaptive Algorithms for Relatively Lipschitz Continuous Convex Optimization Problems // Pure and Applied Functional Analysis. — 2023.— V. 8, No. 5. —P. 1505- 1526.

4. Savchuk O. S, Stonyakin, F. S., Alkousa, M. S., Zabirova, R. R., Titov, A. A., Gasnikov, A. V. Online Optimization Problems with Functional Constraints Under Relative Lipschitz Continuity and Relative Strong Convexity Conditions // Communications in Computer and Information Science. — 2023. — V. 1881 CCIS. — P. 29-43.

5. Савчук О. С., Алкуса М. С., Стонякин Ф. С. О некоторых методах зеркального спуска для задач сильно выпуклого программирования с липшицевыми функциональными ограничениями // Компьютерные исследования и моделирование. — 2024. — Т. 16, No 7. — С. 1727-1746.

6. Савчук О. С., Стонякин Ф. С., Выгузов А. А., Алкуса М. С., Гасников А. В. Адаптивные прямо-двойственные методы с неточным оракулом для относительно гладких оптимизационных задач и их приложения

к задачам восстановления малоранговых матриц // Журн. вычисл. математики и мат. физики. — 2025.— Т. 65, N0 7. — С. 1156-1177. Личный вклад. Все приведенные в диссертации результаты из совместных публикаций, за исключением численных экспериментов, получены автором лично. Проведение и анализ вычислительных экспериментов выполнены совместно с соавтором Мохаммадом Соуд Алкуса.

Структура и объем диссертации. Диссертация состоит из введения,

4 глав и заключения. Полный объём диссертации составляет 150 страниц, включая

5 рисунков. Список литературы содержит 74 наименования.

Глава 1. Методы зеркального спуска для относительно липшицевых и относительно сильно выпуклых задач оптимизации с ограничениями-неравенствами

Первая глава диссертации посвящена исследованию численных методов первого порядка для относительно липшицевых и относительно сильно выпуклых задач оптимизации с несколькими функциональными ограничениями. Если точнее, рассматриваются два класса задач: задачи онлайн-оптимизации [17—21] с функциональными ограничениями и задачи выпуклого программирования [22; 28; 29] с несколькими ограничениями в условиях относительной липшицевости и относительной сильной выпуклости.

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

Список литературы диссертационного исследования кандидат наук Савчук Олег Сергеевич, 2026 год

Список литературы

1. Nesterov Y. Lectures on Convex Optimization. — Springer International Publishing, 2018.—P. 589.

2. Beck A. First-Order Methods in Optimization. — Society for Industrial, Applied Mathematics, 2017. — P. 487.

3. Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. — М.: МЦНМО, 2021. — С. 272.

4. Image deblurring with Poisson data: from cells to galaxies / M. Bertero [et al.] // Inverse Problems. — 2009. — Vol. 25, no. 12. — P. 123006.

5. Csiszar I. Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems // Annals of Statistics. — 1991. — Vol. 19, no. 4. — P. 2032-2066.

6. Kiefer J., Wolfowitz J. Optimum Designs in Regression Problems // The Annals of Mathematical Statistics. — 1959. — Vol. 30, no. 2. — P. 271-294.

7. Atwood C. L. Optimal and efficient designs of experiments // The Annals of Mathematical Statistics. — 1969. — Vol. 40, no. 5. — P. 1570-1602.

8. Bauschke H., Bolte J., Teboulle M. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications // Mathematics of Operations Research. — 2017. — Vol. 42, no. 2. — P. 330-348.

9. Lu H., Freund R. M., Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications // SIAM Journal on Optimization. — 2018. — Vol. 28, no. 1. — P. 333-354.

10. Lu H. Relative-Continuity for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent // INFORMS Journal on Optimization. — 2019. — Vol. 1, no. 4. — P. 288-303.

11. Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования // Журн. вычисл. математики и мат. физики. — 1967. — Т. 7, №3. —С. 200—217.

12. Hanzely F., Richtarik P., Xiao L. Accelerated Bregman proximal gradient methods for relatively smooth convex optimization // Computational Optimization and Applications. — 2021. — Vol. 79. — P. 405-440.

13. Nesterov Y. Relative Smoothness: New Paradigm in Convex Optimization // Conference report, EUSIPCO-2019, A Coruna, Spain. — 2019. — URL: http: / / eusipco2019 . org / wp - content / uploads / 2019 / 10 / °/„20Relative -

.

14. Shalev-Shwartz S., Singer Y., Srebro N. Pegasos: Primal estimated sub-gradient solver for SVM // Mathematical Programming. — 2011. — Vol. 127, no. 1. — P. 3-30.

15. Optimal complexity and certification of Bregman first-order methods / R.-A. Dragomir [et al.] // Mathematical Programming. — 2022. — Vol. 194, no. 1. — P. 41-83.

16. Немировский А., Юдин Д. Сложность задач и эффективность методов оптимизации. — М.:Наука, Главная редакция физико-математической литературы, 1979. — С. 384.

17. Bubeck S., Cesa-Bianchi N. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems // Foundations and Trends in Machine Learning. — 2012. — Vol. 5, no. 1. — P. 1-122.

18. Bartlett P., Hazan E., Rakhlin A. Adaptive Online Gradient Descent // Advances in Neural Information Processing Systems. Vol. 20. — Curran Associates, Inc., 2007. —URL: https://proceedings.neurips.cc/paper_files/paper/

.

19. Hazan E., Kale S. Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization // Journal of Machine Learning Research - Proceedings Track. — 2011. — Vol. 19. — P. 421-436.

20. Hazan E. Introduction to Online Convex Optimization // Foundations and Trends in Optimization. — 2016. — Vol. 2. — P. 157-325.

21. Cesa-Bianchi N., Lugosi G. Prediction, Learning, and Games. — Cambridge University Press, 2006. — P. 406.

22. Advances in Low-Memory Subgradient Optimization / P. E. Dvurechensky [et al.] // Numerical Nonsmooth Optimization: State of the Art Algorithms. — Springer International Publishing, 2020. — P. 19-59.

23. Shor N. Z. Generalized gradient descent with application to block programming // Cybernetics. — 1967. — Vol. 3, no. 3. — P. 43-45.

24. Поляк Б. Т. Один общий метод решения экстремальных задач // Докл. АН СССР. — 1967. — Т. 174, № 1. — С. 33—36.

25. Orabona F., Crammer K., Cesa-Bianchi N. A Generalized Online Mirror Descent with Applications to Classification and Regression // Machine Learning. — 2015. — Vol. 99. — P. 411-435.

26. Немировский А. С., Юдин Д. Б. Эффективные методы решения задач выпуклого программирования большой размерности // Экономика и математические методы. — 1979. — Т. 15, № 1. — С. 135—152.

27. Beck A., Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization // Operations Research Letters. — 2003. — Vol. 31, no. 3. — P. 167-175.

28. Mirror Descent and Convex Optimization Problems with Non-smooth Inequality Constraints / A. Bayandina [et al.] // Large-Scale and Distributed Optimization. — Springer International Publishing, 2018. — P. 181-213.

29. Адаптивные алгоритмы зеркального спуска в задачах выпуклого программирования с липшицевыми ограничениями / Ф. С. Стонякин [и др.] // Тр. ИММ УрО РАН. — 2018. — Т. 24, № 2. — С. 266—279.

30. Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming. — 2015. — Vol. 152. — P. 381-404.

31. Gradient-Type Adaptive Methods for Relatively Lipschitz Convex Optimization Problems / F. S. Stonyakin [et al.] // arXiv preprint. — 2021. — URL: https :

.

32. Antonakopoulos K., Mertikopoulos P. Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements // arXiv preprint. — 2021. —URL: https://arxiv.org/pdf/2107.08011.

33. Accelerated Bregman gradient methods for relatively smooth and relatively Lipschitz continuous minimization problems / O. S. Savchuk [et al.] // arXiv preprint. — 2024. — URL: https://arxiv.org/pdf/2411.16743.

34. Inexact model: a framework for optimization and variational inequalities / F. Stonyakin [et al.] // Optimization Methods and Software. — 2021. — Vol. 36, no. 6. — P. 1155-1201.

35. Devolder O., Glineur F., Nesterov Y. First-order methods of Smooth Convex Optimization with Inexact Oracle // Mathematical Programming. — 2014. — Vol. 146, no. 1.—P. 37-75.

36. Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization: PhD Thesis. — CORE UCL, 2013. — P. 320.

37. First-order methods with inexact oracle: the strongly convex case / O. Devolder, F. Glineur, [et al.] // CORE Discussion Papers. — 2013. — Vol. 2013016. — P. 32.

38. Intermediate gradient methods for smooth convex problems with inexact oracle / O. Devolder, F. Glineur, [et al.] // CORE Discussion Papers. — 2013. — Vol. 2013017. — P. 47.

39. Boyd S., Vandenberghe L. Convex Optimization. — Cambridge University Press, 2004.—P. 716.

40. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях / А. С. Аникин [и др.] // Журн. вычисл. математики и мат. физики. — 2017. — Т. 57, № 8. — С. 1270—1284.

41. Nesterov Y. Complexity bounds for primal-dual methods minimizing the model of objective function // Mathematical Programming. — 2018. — Vol. 171. — P. 311-330.

42. Nesterov Y. Primal-dual Subgradient Methods for Convex Problems // Mathematical Programming. — 2009. — Vol. 120. — P. 221-259.

43. Универсальный метод поиска равновесий и стохастических равновесий в транспортных сетях / Д. Р. Баймурзина [и др.] // Журн. вычисл. математики и мат. физики. — 2019. — Т. 59, № 1. — С. 21—36.

44. Гасников А. В., Гасникова Е. В., Нестеров Ю. Е. Двойственные методы поиска равновесий в смешанных моделях распределения потоков в больших транспортных сетях // Журн. вычисл. математики и мат. физики. — 2018. — Т. 58, № 9. — С. 1447—1454.

45. Гасников А. В. Эффективные численные методы поиска равновесий в больших транспортных сетях: дис. ... д. физ. мат. наук. — Моск. физ.-техн. ин-т., 2020. — С. 487.

46. Jenatton R., Huang J., Archambeau C. Adaptive Algorithms for Online Convex Optimization with Long-term Constraints // Proceedings of The 33rd International Conference on Machine Learning. Vol. 48. — PMLR, 2016. — P. 402-411.

47. Mirror Descent and Constrained Online Optimization Problems / A. Tytov [et al.] // Optimization and Applications. — Springer International Publishing, 2019. — P. 64-78.

48. Поляк Б. Т. Введение в оптимизацию. — М.: Наука, 1983. — С. 384.

49. Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model / F. Stonyakin [et al.] // arXiv preprint. —2021. —URL: https://arxiv.org/pdf/2001.09013.

50. Adaptive Algorithms for Relatively Lipschitz Continuous Convex Optimization Problems / F. Stonyakin [et al.] // Pure and Applied Functional Analysis. — 2023. — Vol. 8, no. 5. — P. 1505-1526.

51. Nesterov Y. Implementable tensor methods in unconstrained convex optimization // Mathematical Programming. — 2019. — Vol. 186, no. 2. — P. 1-27.

52. Dragomir R.-A., d'Aspremont A., Bolte J. Quartic First-Order Methods for Low-Rank Minimization // Journal of Optimization Theory and Applications. — 2021. — Vol. 189. — P. 341-363.

53. Candes E., Recht B. Exact matrix completion via convex optimization // Commun. ACM. — 2012. — Vol. 55, no. 6. — P. 111-119.

54. Cai J.-F., Candes E. J., Shen Z. A singular value thresholding algorithm for matrix completion // SIAM Journal on optimization. — 2010. — Vol. 20, no. 4. — P. 1956-1982.

55. Jain P., Netrapalli P., Sanghavi S. Low-rank matrix completion using alternating minimization // Proceedings of the forty-fifth annual ACM symposium on Theory of computing. — 2013. — P. 665-674.

56. Recht B., Fazel M., Parrilo P. A. Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization // SIAM Review. — 2010. — Vol. 52, no. 3.—P. 471-501.

57. Mishra B., Meyer G., Sepulchre R. Low-rank optimization for distance matrix completion // 50th IEEE Conference on Decision and Control and European Control Conference. — 2011. — P. 4455-4460.

58. Fang H.-R., O'Leary D. P. Euclidean distance matrix completion problems // Optimization Methods and Software. — 2012. — Vol. 27, no. 4/5. — P. 695-717.

59. Burer S., Monteiro R. D. Local minima and convergence in low-rank semidefinite programming // Mathematical programming. — 2005. — Vol. 103, no. 3. — P. 427-444.

60. Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods / L. Bogolubsky [et al.] // Advances in Neural Information Processing Systems. Vol. 29. — Curran Associates, Inc., 2016. — URL: https : //proceedings . neurips . cc/paper_files/paper/2016/file/

.

61. Bottou L., Curtis F. E., Nocedal J. Optimization methods for large-scale machine learning // SIAM Review. — 2018. — Vol. 60, no. 2. — P. 223-311.

62. Bergstra J., Bengio Y. Random search for hyper-parameter optimization // The journal of machine learning research. — 2012. — Vol. 13, no. 1. — P. 281-305.

63. Dvurechensky P., Gasnikov A., Kamzolov D. Universal intermediate gradient method for convex problems with inexact oracle // Optimization Methods and Software. — 2021. — Vol. 36, no. 6. — P. 1289-1316.

64. Ben-Tal A., Nemirovski A. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. — Society for Industrial, Applied Mathematics, 2001. — P. 504.

65. Тюрин А. И., Гасников А. В. Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим ( 5, L )-модель функции в запрошенной точке // Журн. вычисл. математики и мат. физики. — 2019. — Т. 59, № 7. — С. 1137—1150.

66. Выпуклая оптимизация: учебное пособие / Е. А. Воронцова [и др.]. — М.:МФТИ, 2021. — С. 364.

67. Jaggi M. Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization // Proceedings of the 30th International Conference on Machine Learning, Cycle 1. Vol. 28. — JMLR.org, 2013. — P. 427-435.

68. Harchaoui Z., Juditsky A., Nemirovski A. Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization // Mathematical Programming. — 2013. — Vol. 152. — P. 75-112.

69. Gutman D., Pena J. A unified framework for Bregman proximal methods: subgradient, gradient, and accelerated gradient schemes // arXiv preprint. — 2018. — URL: https://arxiv.org/pdf/1812.10198v3.

70. Поляк Б. Т. Градиентные методы минимизации функционалов // Журн. вычисл. математики и мат. физики. — 1963. — Т. 3, № 4. — С. 643—653.

71. Belkin M. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation // Acta Numerica. — 2021. — Vol. 30. — P. 203-248.

72. Karimi H., Nutini J., Schmidt M. Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition // Machine Learning and Knowledge Discovery in Databases. — Springer International Publishing, 2016. — P. 795-811.

73. Yue P., Fang C., Lin Z. On the Lower Bound of Minimizing Polyak-Lojasiewicz functions // Proceedings of Thirty Sixth Conference on Learning Theory. Vol. 195. — 2023. — P. 2948-2968.

74. Тюрин А. И. Прямо-двойственный быстрый градиентный метод с моделью // Компьютерные исследования и моделирование. — 2020. — Т. 12, № 2. — С. 263—274.

Список рисунков

Рисунок 1.1 Результаты алгоритма 6 и Mod.AMD-L (алгоритм 3 из [29])

для задачи (1.22) с (1.40) и (1.41), п = 500, т = 50, Г = 10........48

Рисунок 3.1 Результаты алгоритмов: ускоренный алгоритм 14 и неускоренный адаптивный алгоритм 1 (Algorithm 1) из [34] для задачи (3.52)..................................101

Рисунок 3.2 Результаты алгоритмов: неадаптивный (3.85) и адаптивный

(3.87) для задачи (3.92) с т = 200, п = 100 и ^ = 0............125

Рисунок 3.3 Результаты алгоритмов: неадаптивный (3.85) и адаптивный (3.87) для задачи (3.92) с т = 200, п = 100 и ^ = 0.001 - динамика f(xk)......................................126

Рисунок 3.4 Результаты алгоритмов: неадаптивный (3.85) и адаптивный

(3.87) для задачи (3.92) с т = 200, п = 100 и ^ = 0.001 - значения щ+1. 127