Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математический сборник, 2023, том 214, номер 3, страницы 3–53
DOI: https://doi.org/10.4213/sm9700
(Mi sm9700)
 

Решение сильно выпукло-вогнутых композитных седловых задач с небольшой размерностью одной из групп переменных

М. С. Алкусаa, А. В. Гасниковabcd, Е. Л. Гладинe, И. А. Курузовa, Д. А. Пасечнюкa, Ф. С. Стонякинaf

a Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл.
b Исследовательский центр доверенного искусственного интеллекта, Институт системного программирования им. В. П. Иванникова Российской академии наук, г. Москва
c Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, г. Москва
d Кавказский математический центр, Адыгейский государственный университет, г. Майкоп
e Humboldt-Universität, Berlin, Germany
f Крымский федеральный университет имени В. И. Вернадского, г. Симферополь
Список литературы:
Аннотация: Разработаны алгоритмические методы, гарантирующие эффективные оценки сложности для сильно выпукло-вогнутых седловых задач в случае, когда одна из групп переменных имеет большую размерность, а другая – достаточно малую (до сотни). Предлагаемая методика основана на сведении задач такого типа к задаче минимизации выпуклого (максимизации вогнутого) функционала по одной из переменных, для которого можно найти приближенное значение градиента в произвольной точке с необходимой точностью с помощью вспомогательной оптимизационной подзадачи по другой переменной. При этом для маломерных задач предлагается использовать методы эллипсоидов и Вайды, а для многомерных – ускоренные градиентные методы с неточной информацией о градиенте или субградиенте. Для случая очень малой размерности задачи одной из групп переменных (до 5) на гиперкубе достаточно эффективным будет иной предлагаемый подход к сильно выпукло-вогнутым седловым задачам на базе нового варианта многомерного аналога метода Ю. Е. Нестерова на квадрате (метод многомерной дихотомии) с возможностью использования неточных значений градиента целевого функционала.
Библиография: 28 названий.
Ключевые слова: седловая задача, метод эллипсоидов, метод Вайды, неточный субградиент, гиперкуб, многомерная дихотомия.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации 0714-2020-0005
075-02-2021-1316
Исследование А. В. Гасникова в п. 2.2 и § 3 подготовлено в рамках выполнения государственного задания Министерства науки и высшего образования Российской Федерации (проект № 0714-2020-0005). Исследование Ф. С. Стонякина в пп. 2.1 и 2.3 выполнено при поддержке программы стратегического академического лидерства “Приоритет-2030” (соглашение № 075-02-2021-1316 от 30.09.2021).
Поступила в редакцию: 26.11.2021 и 24.10.2022
Англоязычная версия:
Sbornik: Mathematics, 2023, Volume 214, Issue 3, Pages 285–333
DOI: https://doi.org/10.4213/sm9700e
Реферативные базы данных:
Тип публикации: Статья
MSC: Primary 90C47; Secondary 68Q25, 90C06

§ 1. Введение

Седловые задачи весьма актуальны, поскольку возникают в реальных проблемах машинного обучения, компьютерной графики, теории игр, а также теории оптимального транспорта. Ввиду важности таких задач известно немало работ, посвященных различным алгоритмам их решения и теоретическим результатам о скорости их сходимости (сложности); см. [1]–[8].

В настоящей статье рассматриваются выпукло-вогнутые седловые задачи вида

$$ \begin{equation} \min_{x \in Q_{x}}\max_{y \in Q_y} \bigl\{\widehat{S}(x, y) :=r(x)+F(x, y)-h(y) \bigr\}, \end{equation} \tag{1.1} $$
где $Q_x\subseteq \mathbb{R}^n$, $Q_y\subseteq \mathbb{R}^m$ – непустые выпуклые компактные множества, $r$: $Q_x \to \mathbb{R}$ и $h\colon Q_y \to \mathbb{R}$ есть $\mu_{x}$-сильно выпуклая и $\mu_y$-сильно выпуклая функции соответственно. Функционал $F\colon Q_x \times Q_y \to \mathbb{R}$ выпуклый по $x$ и вогнутый по $y$ и задан в некоторой окрестности множества $Q_x \times Q_y$. Если задача не сильно выпукла (случай $\mu_x=0$ или $\mu_y=0$), то ее можно свести к сильно выпуклой применением техники регуляризации (см. [9; замечание 4.1]).

Класс задач (1.1) уже некоторое время назад достаточно подробно изучен в билинейном случае, т.е. когда $F(x,y)=\langle Ax,y \rangle$ для некоторого линейного оператора $A$ (см., например, обзор [6]). Также известны работы, нацеленные на обобщение известных в билинейном случае результатов на общую ситуацию; см. [3], [5], [10], [11].

В статье [12] рассматривалась постановка, когда $Q_x \equiv \mathbb R^n$, $Q_y \equiv \mathbb R^m$, причем для произвольных $x$ и $y$ функция $\widehat{S}(x, y)=F(x, y)$ – это $\mu_x$-сильно выпуклая по $x$, $\mu_y$-сильно вогнутая по $y$ и $(L_{xx}, L_{xy}, L_{yy})$-гладкая функция. Последнее означает, что для любого фиксированного $x$ отображения $\nabla_y F(x, \cdot)$ и $\nabla_x F(x, \cdot)$ являются липшицевыми с некоторыми неотрицательным константами $L_{yy}$ и $ L_{xy}$, а для любого фиксированного $y$ отображения $\nabla_x F(\cdot, y)$ и $\nabla_y F(\cdot, y)$ – с константами $L_{xx}$ и $L_{xy}$. В [12] для выделенного класса задач обоснована нижняя оценка сложности вида

$$ \begin{equation*} N(\varepsilon)= \Omega\biggl(\sqrt{\frac{L_{xx}}{\mu_{x}}+\frac{L_{xy}^{2}}{\mu_x \mu_y}+\frac{L_{yy}}{\mu_y}} \ln\biggl(\frac{1}{\varepsilon}\biggr) \biggr), \end{equation*} \notag $$
где $N(\varepsilon)=\Omega (f(\varepsilon))$ означает, что существуют $C>0$ и $\varepsilon_0>0$ такие, что $|N(\varepsilon)| > C|f(\varepsilon)|$ для любого $\varepsilon < \varepsilon_0$. В [1] был представлен подход на основе ускоренных методов с оценкой сложности, наиболее близкой к оптимальной на тот момент. Далее были предприняты попытки получить оптимальный алгоритм; см. [4], [7]. Так, в [13] предложен метод с верхней оценкой на количество итераций $\widetilde{O}\bigl(\sqrt{{L_{xx}}/{\mu_x}+{ L \cdot L_{xy}}/(\mu_x \mu_y)+{L_{yy}}/{\mu_y}} \bigr)$, где $L=\max \bigl\{L_{xx}, L_{xy}, L_{yy}\bigr\}$ (обозначение $\widetilde{O}(\cdot)$ означает $O(\cdot)$ с точностью до логарифмического по $\varepsilon^{-1}$ множителя в степени $1$ или $2$). Таким образом, вопрос о почти оптимальном алгоритме для сильно выпукло-вогнутой седловой задачи большой размерности с гладкой целевой функцией был решен.

В табл. 1 приведены наилучшие известные на данный момент результаты (см. [1]–[7] и ссылки в них) об оценках сложности решения задачи (1.1).

Для каждого из случаев $\varepsilon$-решение задачи (1.1) может быть достигнуто за указанные в первом столбце $\widetilde{O}(\cdot)$ вычислений величины из второго столбца. Константа Липшица $\nabla F$ (градиента по $x$ и по $y$) обозначается как $L_F$. Далее, когда говорится, что функция $r\colon Q_x \to \mathbb{R}$ проксимально дружественна, то имеется в виду возможность явно решить задачу вида

$$ \begin{equation} \min _{x \in Q_{x}}\bigl\{\langle c_{1}, x\rangle+r(x)+ c_{2}\|x\|_{2}^{2}\bigr\}, \qquad c_1 \in Q_x, \quad c_2 > 0. \end{equation} \tag{1.2} $$
Аналогичным образом определяется и проксимальная дружественность $h$: $Q_y \to \mathbb{R}$ для задач вида
$$ \begin{equation} \min_{y \in Q_y}\bigl\{\langle c_{3}, y\rangle+ h(y)+ c_{4}\|y\|_{2}^{2}\bigr\}, \qquad c_3 \in Q_y, \quad c_4 > 0. \end{equation} \tag{1.3} $$

Таблица 1.Наилучшие известные результаты о сложности методов для задачи (1.1)

ОценкаОбращение к подпрограммам
Случай 1: обе функции $r$ и $h$ проксимально дружественны
$\widetilde{O}\biggl(\dfrac{L_{F}}{\sqrt{\mu_x \mu_y}} \biggr)$вычислений $\nabla_{x}F(x,y)$, $\nabla_{y}F(x,y)$ и решений задач (1.2), (1.3)
Случай 2: $r$ – $L_x$-гладкая и не проксимально дружественная функция
$\widetilde{O}\biggl(\sqrt{\dfrac{L_{x} L_F}{\mu_x \mu_y}}\biggr)$вычислений $\nabla r(x)$
$\widetilde{O}\biggl(\dfrac{L_{F}}{\sqrt{\mu_x \mu_y}} \biggr)$вычислений $\nabla_{x}F(x,y)$, $\nabla_{y}F(x,y)$ и решений задачи (1.3)
Случай 3: $h$ – $L_y$-гладкая и не проксимально дружественная функция
$\widetilde{O}\biggl(\sqrt{\dfrac{L_{y} L_F}{\mu_x \mu_y}}\biggr)$вычислений $\nabla h(y)$
$\widetilde{O}\biggl(\dfrac{L_{F}}{\sqrt{\mu_x \mu_y}} \biggr)$вычислений $\nabla_{x}F(x,y)$, $\nabla_{y}F(x,y)$ и решений задачи (1.2)
Случай 4: $r$ и $h$ – $L_x$- и $L_y$-гладкие не проксимально дружественные функции
$\widetilde{O}\biggl(\sqrt{\dfrac{L_x L_F}{\mu_x \mu_y}}\biggr)$вычислений $\nabla r(x)$
$\widetilde{O}\biggl(\sqrt{\dfrac{L_y L_F}{\mu_x \mu_y}}\biggr)$вычислений $\nabla h(y)$
$\widetilde{O}\biggl(\dfrac{L_{F}}{\sqrt{\mu_x \mu_y}} \biggr)$вычислений $\nabla_{x}F(x,y)$ и $\nabla_{y}F(x,y)$

Отметим, что седловую задачу можно сводить и к вариационному неравенству (далее – ВН) с монотонным оператором. Напомним, что оператор $G\colon \operatorname{dom} G \to \mathbb{R}^k$, заданный на выпуклом множестве $\operatorname{dom} G \subseteq \mathbb{R}^k$, называется монотонным, если

$$ \begin{equation*} \langle G(z)-G(z'),\ z-z' \rangle \geqslant 0 \quad \forall\, z, z' \in Q, \end{equation*} \notag $$
где $Q$ – выпуклое компактное множество с непустой внутренностью и $\operatorname{int} Q \subseteq \operatorname{dom} G$. Решением вариационного неравенства называется точка $z_* \in \operatorname{dom} G \cap Q$, удовлетворяющая соотношению
$$ \begin{equation*} \langle G(z_*),\ z-z_* \rangle \geqslant 0 \quad \forall\, z \in Q. \end{equation*} \notag $$

Выпукло-вогнутые седловые задачи вида (1.2) с дифференцируемой функцией $S(\cdot, \cdot)$ при $r$ и $h$, равных тождественно $0$, сводятся к ВН с оператором $G(x, y)=[\nabla_x S(x, y), -\nabla_y S(x, y)]^\top$, который является монотонным в силу выпуклости $S$ по $x$ и вогнутости по $y$. Такое ВН можно решать, например, с помощью метода эллипсоидов из [14], что приводит к скорости сходимости $O \biggl( \exp \biggl\{-\dfrac{N}{2 d(d+1)}\biggr\} \biggr)$, где $d=n+m$ – размерность задачи, $N$ – число итераций. Такой подход к решению задачи (1.2) не требует ни гладкости, ни сильной выпуклости (вогнутости) целевой функции $S(\cdot, \cdot)$ и может считаться вполне эффективным в случае малой размерности задачи $d=n+m$. Более того, базируясь на методах типа метода центров тяжести, оценку $O \biggl( \exp \biggl\{-\dfrac{N}{2 d(d+1)}\biggr\} \biggr)$ можно улучшить до оценки $O \biggl( \exp \biggr\{-\dfrac{N}{O(d)}\biggr\} \biggr)$; см. [15; лекция 5]. Отметим, что первый из указанных выше подходов к задаче (1.1) достаточно эффективен в случае большой размерности обеих переменных задачи (1.1), а второй – в случае малой размерности переменных задачи.

В настоящей статье рассматривается ситуация, когда одна из групп переменных ($x$ или $y$) имеет большую размерность, а другая – небольшую (несколько десятков). Задача (1.1) представляется в виде задачи минимизации по “внешней” переменной выпуклой функции, информация о которой (значение функции, градиента) доступна только с некоторой точностью. Эта точность в свою очередь регулируется с помощью вспомогательной оптимизационной подзадачи по “внутренней” переменной. Соответственно в зависимости от размерности (малая или большая) внешней переменной $x$ естественно выделить два таких подхода. Если размерность внешней переменной $x$ велика (п. 2.2), то для решения задачи (1.1) предлагается использовать ускоренный градиентный метод с неточным оракулом, а для вспомогательной максимизационной подзадачи – метод секущей гиперплоскости (метод эллипсоидов или метод Вайды). Если же размерность внешней переменной $x$ мала, то для (1.1) используются предложенные в настоящей работе вариации методов секущей гиперплоскости (методы эллипсоидов и Вайды) с использованием на итерациях неточного аналога градиента целевой функции ($\delta$-субградиент или градиент с $\delta$-аддитивной неточностью), а для внутренней оптимизационной подзадачи – ускоренные градиентные методы. С целью вывода оценок достаточного количества итераций (обращений к подпрограмме нахождения (суб)градиента функционала или его “неточного аналога”) для достижения нужного качества решений седловой задачи (1.1) при указанном подходе получены важные теоретические результаты, описывающие влияние параметра $\delta$ на качество точки выхода метода эллипсоидов или метода Вайды, которые вместо градиента целевой функции используют на итерациях $\delta$-субградиент или $\delta$-аддитивно неточный градиент. Отметим при этом, что метод Вайды по сравнению с методом эллипсоидов приводит к лучшей оценке достаточного для достижения нужного качества приближенного решения количества итераций, но итерация метода эллипсоидов менее затратна. Далее детально рассматривается ситуация, когда размерность одной из групп переменных седловой задачи (1.1) очень мала, а допустимое множество значений этой переменной есть гиперкуб. В этом случае вместо метода эллипсоидов можно использовать аналог метода дихотомии, что может оказаться в случае очень малой размерности (до 5) выгоднее методов секущей гиперплоскости. Точнее говоря, в работе предлагается метод минимизации выпуклой дифференцируемой функции с липшицевым градиентом на многомерном гиперкубе для малых размерностей пространства, который является аналогом метода Ю. Е. Нестерова минимизации выпуклой липшицевой функции двух переменных на квадрате с фиксированной стороной (см. [9], [16]). Далее условимся этот метод называть методом многомерной дихотомией. Идея метода – деление квадрата на меньшие части и постепенное их удаление так, чтобы в оставшейся достаточно малой области все значения целевой функции были достаточно близки к оптимальному. При этом метод заключается в решении вспомогательных задач одномерной минимизации вдоль разделяющих отрезков и не предполагает вычисления точного значения градиента целевого функционала (т.е. метод можно считать неполноградиентным). Данный метод в двумерном случае на квадрате рассматривался в работе [16]. В настоящей статье предложен новый вариант критерия остановки для вспомогательных подзадач, а также аналог метода Ю. Е. Нестерова для произвольной размерности. Полученные результаты применимы и к седловым задачам с небольшой размерностью одной из групп переменных на гиперкубе. Приведены оценки сложности такого подхода для сильно выпукло-вогнутых седловых задач вида (1.1) с достаточно гладкими функционалами в случае, если маломерная задача решается методом дихотомии с неточным градиентом, и на каждой итерации решается многомерная вспомогательная задача с использованием быстрого градиентного метода для всех вспомогательных задач. Найденные оценки скорости сходимости представляются приемлемыми в случае, если размерность одной из групп переменных достаточно мала (до 5).

Для сравнения предложенных подходов к задаче (1.1) между собой, а также с некоторыми известными аналогами выполнены вычислительные эксперименты для некоторых типов лагранжевых седловых задач к задачам минимизации сильно выпуклых функционалов при наличии небольшого количества выпуклых функциональных ограничений-неравенств. В частности, проведены численные эксперименты для задачи, двойственной к задаче LogSumExp с линейными ограничениями (приложения задач такого типа описаны, например, в работе [2]). Нами проведено сравнение скорости работы подхода к (1.1) как к системе подзадач в случаях, когда основная маломерная задача решается быстрым градиентным методом с $(\delta,L)$-оракулом или методом эллипсоидов с $\delta$-субградиентом. Проведенные вычислительные эксперименты показали, что использование рассмотренных методов секущей гиперплоскости для задач небольшой размерности приводит к более удачной работе с достаточно высокой требуемой точностью по сравнению с методами, использующими только градиентные подходы. Кроме того, в ряде случаев метод многомерной дихотомии показал себя эффективнее методов секущей гиперплоскости, что указывает на целесообразность и такого предлагаемого нами подхода. Для случая, когда маломерная подзадача решается методом эллипсоидов, был дополнительно проведен эксперимент по сравнению методик учета неточностей при использовании аддитивно зашумленного градиента (п. 3.4): предложенный подход со значением неточности, изменяющимся вместе с диаметром текущего эллипсоида, позволяет с использованием (1.1) как системы подзадач быстрее достигать условия останова и, следовательно, заданной точности. Проведен также эксперимент по сравнению эффективности предложенных подходов с известным аналогом [8] применительно к задаче проектирования точки на множество, заданное набором (небольшого числа) гладких ограничений (п. 3.5). Сравнение показало, что подход с применением метода эллипсоидов для маломерной задачи при использовании предложенного условия останова и новых оценок на достаточное число итераций для внутреннего метода оказывается существенно эффективнее аналогичного подхода, предложенного в работе [8]. Отметим, что для применяемых в настоящей работе к подзадачам небольшой размерности методов секущей гиперплоскости или многомерного аналога дихотомии сильная выпуклость важна лишь для теоретических оценок. Для реализации таких методов предполагать сильную выпуклость целевой функции не обязательно, и поэтому мы не проводим регуляризацию лагранжевых седловых задач по двойственным переменным.

Работа состоит из введения, заключения и двух основных параграфов. В § 2 приводятся основные результаты, подходы к рассматриваемой задаче для различных случаев малой размерности внешних и внутренних переменных. В п. 2.1 описана общая схема рассуждений, используемых для анализа рассматриваемых в настоящей работе задач, которая связана с рассмотрением семейства вспомогательных подзадач оптимизации. Следующий п. 2.2 является ключевым и содержит вывод оценок для задачи (1.1) в случае относительно небольшой размерности одной из групп переменных на базе использования новых вариаций методов эллипсоидов и Вайды к соответствующим вспомогательным подзадачам. В п. 2.3 рассмотрен специальный случай очень малой (до 5) размерности одной из групп переменных седловой задачи и описаны оценки сложности подхода к задаче (1.1), основанного на предлагаемом многомерном аналоге дихотомии с аддитивно неточным градиентом. В § 3 приводятся результаты некоторых вычислительных экспериментов и сравнение скорости работы предложенных подходов. Полные доказательства некоторых результатов (теорем 3, 69 и леммы 4) приводятся в § 4.

§ 2. Основные результаты

2.1. Схема вывода оценок сложности для рассматриваемого класса седловых задач

2.1.1. Постановка задачи

Перепишем задачу (1.1) в виде

$$ \begin{equation} \min_{x \in Q_{x}} \Bigl\{ g(x):=r(x)+\max_{y \in Q_y} S(x, y) \Bigr\}, \end{equation} \tag{2.1} $$
где $Q_x \subseteq \mathbb{R}^n, Q_y \subseteq \mathbb{R}^m$ – выпуклые замкнутые множества, $Q_x$ ограничено, $S(x, y)=F(x, y)-h(y)$ – непрерывная функция из (1.1), сильно выпуклая по $x$ и сильно вогнутая по $y$.

Определение 1. Пару точек $(\widetilde{x},\widetilde{y}) \in Q_x \times Q_y$ будем называть $\varepsilon$-решением задачи (1.1) (или (2.1)), если

$$ \begin{equation} \max\{\|\widetilde{x}-x_*\|_2, \, \|\widetilde{y}-y_*\|_2\} \leqslant \varepsilon, \end{equation} \tag{2.2} $$
где $(x_*, y_*)$ – точное решение сильно выпукло-вогнутой седловой задачи (1.1).

Замечание 1. Ввиду сильной выпуклости функции $g$ для выполнения неравенства (2.2) достаточно находить для задачи (2.1) такое $\widetilde{x}$, что $g(\widetilde{x})-\min_{x \in Q_{x}} g(x) \leqslant C\varepsilon^2$ (при подходящем выборе константы $C>0$, зависящей от параметра сильной выпуклости $\mu_x$), а также с аналогичной точностью $O(\varepsilon^2)$ решать вспомогательные подзадачи. Поскольку мы используем методы с гарантией линейной скорости сходимости, то в итоговые оценки сложности для задачи (1.1) величины типа $C\varepsilon^2$ будут входить под логарифмами. Это означает, что для вывода асимптотических оценок сложности седловых задач вида (1.1) достаточно находить такое $\widetilde{x}$, что $g(\widetilde{x})-\min_{x \in Q_{x}} g(x) \leqslant \varepsilon$, что мы и будем использовать в рассуждениях.

Будем рассматривать задачу (2.1) как композицию внутренней задачи максимизации

$$ \begin{equation} \widehat{g}(x):=\max_{y \in Q_y} S(x, y) \end{equation} \tag{2.3} $$
и внешней задачи минимизации
$$ \begin{equation} \min_{x \in Q_x} g(x). \end{equation} \tag{2.4} $$
Итерационный метод для внешней задачи (2.4) будет на каждом шаге использовать градиент целевой функции, который может быть вычислен с некоторой точностью на основе приближенного решения внутренней задачи (2.3). В связи с этим возникает необходимость в четких оценках качества выдаваемого методом решения в случае использования на его итерациях неточной информации о градиенте или субградиенте целевой функции. Оказывается, что для седловых задач в качестве подходящего неточного аналога субградиента целевой функции можно рассматривать $\delta$-субградиент (см. определение 2), $(\delta, L)$-субградиент (см. (2.5) ниже, а также [1]) или $\delta$-неточный субградиент (см. определение 3 ниже).

Определение 2. Пусть $\delta \geqslant 0$. Вектор $\nu(\widehat{x}) \in \mathbb{R}^n$ называется $\delta$-субградиентом выпуклой функции $g\colon Q_x \to \mathbb{R}$ в точке $\widehat{x}$, если $g(x) \,{\geqslant}\, g(\widehat{x})\,{+}\,\langle \nu(\widehat{x}), x\,{-}\,\widehat{x} \rangle\,{-}\,\delta$ для всякого $x \in Q_x$. Множество $\delta$-субградиентов $g$ в $\widehat{x}$ обозначается $\partial_{\delta} g(\widehat{x})$.

Заметим, что $\delta$-субградиент совпадает с обычным субградиентом при $\delta=0$.

Определение 3. Пусть $\delta \geqslant 0$. Вектор $\nu(\widehat{x}) \in \mathbb{R}^n$ будем называть $\delta$-неточным субградиентом выпуклой функции $g\colon Q_x \to \mathbb{R}$ в точке $\widehat{x}$, если для некоторого субградиента $\nabla g(\widehat{x}) \in \partial g(\widehat{x})$ выполнено $\| \nabla g(\widehat{x})-\nu(\widehat{x})\|_2 \leqslant \delta$. Если известно, что функция $g$ дифференцируема в точке $\widehat{x}$, то будем говорить, что $\nu(\widehat{x})$ – $\delta$-неточный градиент.

2.1.2. Вычисление неточного аналога градиента целевой функции основной подзадачи

В качестве приближенного субградиента целевой функции $g$ задачи (2.4) в точке $x \in Q_x$ предлагается использовать субградиент $\nabla r(x)+\nabla_x S(x, \widetilde{y})$, где $\widetilde{y}$ – $\widetilde{\varepsilon}$-решение вспомогательной подзадачи (2.3) при данном $x$, $\nabla r(x) \in \partial r(x)$ и $\nabla_x S(x, \widetilde{y}) \in \partial_x S(x, \widetilde{y})$ – произвольные конечные субградиенты в точке $x$ функций $r$ и $S(\cdot, \widetilde{y})$ соответственно. Оказывается, что такой неточный субградиент может быть $\delta$-субградиентом целевой функции $g$ в точке $x$, если выбрать точность $\widetilde{\varepsilon}$ для вспомогательной подзадачи согласно следующей лемме.

Лемма 1 (см. [17; с. 123, 124]). Пусть в условиях задачи (2.1) для фиксированного $x$ точка $\widetilde{y} \in Q_y$ такова, что $\widehat{g}(x)-S(x, \widetilde{y}) \leqslant \delta$. Тогда $\partial_x S(x, \widetilde{y}) \subseteq \partial_{\delta} (\widehat{g}(x))$.

Приведенная лемма говорит, что для отыскания $\delta$-субградиента функции $g$ достаточно решить задачу максимизации (2.3) с точностью $\widetilde{\varepsilon}=\delta$.

Оказывается (см. [1]), что для седловых задач типа (2.1) при соответствующих предположениях и точности решения вспомогательной подзадачи можно гарантировать при подходящем $L>0$ и сколь угодно малом $\delta > 0$ доступность $(\delta, L)$-субградиента $\nabla_{\delta, L} g(x)$ функции $g$ в произвольной точке $x \in Q_x$:

$$ \begin{equation} \begin{aligned} \, g(x)+\langle \nabla_{\delta, L} g(x), y-x \rangle-\delta &\leqslant g(y) \nonumber \\ &\leqslant g(x)+ \langle \nabla_{\delta, L} g(x), y-x \rangle+\frac{L}{2}\|y-x\|_2^2+\delta. \end{aligned} \end{equation} \tag{2.5} $$
Ясно, что $(\delta, L)$-субградиент $\nabla_{\delta, L} g(x)$ есть некоторый $\delta$-субградиент функции $g$ в точке $x$ с дополнительным условием вида (2.5).

Следующий известный результат непосредственно вытекает из аналогичного результата [18] для известного понятия ($\delta, L$)-оракула и поясняет связь между двумя используемыми далее аналогами градиента ($\delta$-субградиент и $\delta$-неточный субградиент) выпуклой функции $g$, допускающей ($\delta, L$)-липшицев субградиент в каждой точке $x \in Q_x$.

Теорема 1. Пусть $g\colon Q_x \to \mathbb{R}$ – выпуклая функция, $\nu(x)=\nabla_{\delta, L} g(x)$ – ее $(\delta, L)$-субградиент в точке $x \in \operatorname{int} Q_x$. В таком случае, если $\rho (x, \partial Q_x)$ – евклидово расстояние от точки $x$ до границы множества $Q_x$, при $\rho (x, \partial Q_x) \geqslant 2\sqrt{\delta/L}$ для всякого субградиента $\nabla g(x)$ верно неравенство

$$ \begin{equation*} \| \nu(x)-\nabla g(x) \|_2 \leqslant 2\sqrt{\delta L}. \end{equation*} \notag $$

На базе леммы 1 и теоремы 1 можно заключить, что при достаточно малом $\delta > 0$ для отыскания $\delta$-неточного субградиента функции $g$ в точке $x \in \operatorname{int} Q_x$ достаточно решить задачу максимизации (2.3) с точностью $\widetilde{\varepsilon}=\delta^2/(4L)$.

Еще один способ нахождения $\delta$-неточного субградиента (в данном случае уже $\delta$-неточного градиента, поскольку дополнительно предполагается дифференцируемость) может быть использован при следующем дополнительном предположении.

Предположение 1. Функция $S(\cdot, y)$ дифференцируема для всех $y \in Q_y$ и удовлетворяет для некоторого $L_{xy} \geqslant 0$ условию

$$ \begin{equation} \|\nabla_x S (x, y)-\nabla_x S(x, y')\|_2\leqslant L_{xy} \|y-y' \|_2 \quad \forall\, x \in Q_x, \quad y,y' \in Q_y. \end{equation} \tag{2.6} $$

Лемма 2. Пусть в условиях задачи (2.1) и предположения 1 для любого фиксированного $x\in Q_x$ точка $\widetilde{y} \in Q_y$ такова, что $\widehat{g}(x)- S(x, \widetilde{y}) \leqslant \widetilde{\varepsilon}$. Тогда $\widehat{g}$ дифференцируема в точке $x$ и выполняется неравенство

$$ \begin{equation*} \|\nabla_x S (x, \widetilde{y})-\nabla \widehat{g}(x)\|_2 \leqslant L_{xy} \sqrt{\frac{2 \widetilde{\varepsilon}}{\mu_y}}. \end{equation*} \notag $$

Таким образом, для отыскания $\delta$-неточного градиента функции $g$ достаточно решить задачу максимизации (2.3) с точностью

$$ \begin{equation*} \widetilde{\varepsilon}=\frac{\mu_y}{2 L_{xy}^2} \delta^2, \end{equation*} \notag $$
если $L_{xy} >0$, и с любой конечной точностью $\widetilde{\varepsilon}$, если $L_{xy}=0$.

Приведем еще одну лемму о связи двух аналогов градиента ($\delta$-субградиента и $\delta$-неточного субградиента), которые далее встречаются в статье.

Лемма 3. Пусть $g\colon Q \to \mathbb{R}$ – выпуклая функция на выпуклом множестве $Q$. Тогда:

1) если множество $Q$ ограничено, то $\delta_1$-неточный субградиент функции $g$ является ее $\delta_2$-субградиентом с

$$ \begin{equation*} \delta_2=\delta_1 \operatorname{diam} Q, \quad\textit{где }\ \operatorname{diam} Q=\sup_{x, x' \in Q} \|x-x'\|_2; \end{equation*} \notag $$

2) если функция $g$ $\mu$-сильно выпуклая, то ее $\delta_1$-неточный субградиент является $\delta_2$-субградиентом с $\delta_2=\delta_1^2/(2\mu)$.

Методику исследований и результаты статьи можно условно подразделить на две части, первая из которых (п. 2.2) связана c использованием методов секущей гиперплоскости (методы эллипсоидов и Вайды) для подзадач небольшой размерности, а вторая (п. 2.3) использует авторский многомерный вариант дихотомии с адаптивными правилами остановки для подзадач малой размерности (примерно до 5). Для результатов, основанных на использовании для основных подзадач методов секущей гиперплоскости, приведенные выше утверждения позволяют обосновать возможность использования на итерациях как $\delta$-субградиента, так и $\delta$-неточного субградиента целевой функции $g$. Оценки сложности для седловых задач при этом будут асимптотически совпадать. Что же касается второй части результатов, связанных с использованием многомерной дихотомии, то для них существенно используется допущение о гладкости функции и $\delta$-неточного градиента (именно уже градиента, поскольку в этой части рассматриваются только гладкие задачи).

2.1.3. Общая схема (алгоритм) подхода к выделенному классу задач

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

Сложность алгоритма 1 будем определять согласно следующему очевидному принципу.

Предложение. Пусть метод $\mathcal{M}_1$ для решения задачи (2.4) с использованием $\delta$-субградиента или $\delta$-неточного градиента находит $\varepsilon$-решение не более чем за $N_1(\varepsilon, \delta)$ шагов1, и пусть метод $\mathcal{M}_2$ для решения задачи (2.3) находит $\widetilde{\varepsilon}$-решение не более чем за $N_2(\widetilde{\varepsilon})$ шагов. Если точность $\delta$ оракула для задачи (2.4) зависит от $\widetilde{\varepsilon}$ как $\delta(\widetilde{\varepsilon})$, то алгоритм 1 находит $\varepsilon$-решение задачи (2.1) после $N_1(\varepsilon, \delta(\widetilde{\varepsilon}))$ вычислений $\nabla_x S$ и $N_1(\varepsilon, \delta(\widetilde{\varepsilon})) \cdot N_2(\widetilde{\varepsilon})$ вычислений $\nabla_y S$.

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

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

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

Пусть для задачи (2.1) выполнено следующее

Предположение 2. Множество $Q_x$ имеет непустую внутренность, размерность $n$ относительно мала (не более 100), $Q_y \equiv \mathbb{R}^m$, функция $S$ имеет вид

$$ \begin{equation*} S(x, y) :=F(x,y)-h(y), \end{equation*} \notag $$
где $\mu_y$-сильно выпуклая функция $h$ непрерывна, выпукло-вогнутая функция $F$ дифференцируема по $y$ и удовлетворяет для некоторого $L_{yy} \geqslant 0$ условию
$$ \begin{equation*} \|\nabla_y F(x, y)-\nabla_y F(x, y')\|_2 \leqslant L_{yy}\|y-y'\|_2 \quad \forall\, x \in Q_x, \quad y,y' \in Q_y. \end{equation*} \notag $$

Пусть также выполнено одно из условий:

Теорема 2. $\varepsilon$-решение задачи (2.1) может быть достигнуто:

$\bullet$ в предположении 2 за

$$ \begin{equation*} O \biggl( n \ln \frac{n}{\varepsilon} \biggr)\quad \textit{вычислений } \nabla_x F,\ \nabla r; \end{equation*} \notag $$

$\bullet$ в предположении 2, a) за

$$ \begin{equation*} O \biggl( n \sqrt{\frac{L_{yy}}{\mu_y}} \ln \frac{n}{\varepsilon} \ln \frac{1}{\varepsilon} \biggr) \quad \textit{вычислений } \nabla_y F \textit{ и решений задачи } (2.7); \end{equation*} \notag $$

$\bullet$ в предположении 2, b) за

$$ \begin{equation*} \begin{gathered} \, O \biggl( n \sqrt{\frac{L_{yy}}{\mu_y}} \ln \frac{n}{\varepsilon} \ln \frac{1}{\varepsilon} \biggr) \quad \textit{вычислений } \nabla_y F\textit{ и} \\ O \biggl( n \sqrt{\frac{L_h}{\mu_y}} \ln \frac{n}{\varepsilon} \ln \frac{1}{\varepsilon} \biggr) \quad \textit{вычислений } \nabla h. \end{gathered} \end{equation*} \notag $$

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

2.2.1. Методы секущей плоскости с использованием $\delta$-субградиентов

Рассмотрим задачу вида

$$ \begin{equation} \min_{x \in Q} g(x), \end{equation} \tag{2.8} $$
где $Q \subset \mathbb R^n$ – выпуклое компактное множество, которое содержится в некотором евклидовом шаре радиуса $\mathcal{R}$ и включает некоторый евклидов шар радиуса $\rho>0$, $g$ – непрерывная выпуклая функция, число $B>0$ таково, что
$$ \begin{equation*} |g(x)-g(x')| \leqslant B \quad \forall\, x, x' \in Q. \end{equation*} \notag $$

Мы предлагаем обобщение метода эллипсоидов (алгоритм 2) для задачи (2.8), на итерациях которого используется $\delta$-субградиент целевой функции.

Теорема 3 (оценка качества приближенного решения для метода эллипсоидов с использованием $\delta$-субградиентов). Точка $x^N \in Q$, полученная после $N \geqslant 2n^2 \ln(\mathcal{R}/\rho)$ итераций алгоритма 2 для задачи (2.8), удовлетворяет неравенству

$$ \begin{equation} g(x^N)-\min_{x \in Q} g(x) \leqslant \frac{B \mathcal{R}}{\rho} \exp \biggl(-\frac{N}{2n^2} \biggr)+\delta. \end{equation} \tag{2.9} $$

Следствие 1. Если дополнительно к условиям теоремы 3 допустить, что $g$ $\mu_x$-сильно выпукла, то точка выхода $x^N$ алгоритма 2 удовлетворяет неравенству

$$ \begin{equation} \| x^N-x_* \|_2^2 \leqslant \frac{2}{\mu_x} \biggl( \frac{B \mathcal{R}}{\rho} \exp \biggl(-\frac{N}{2n^2} \biggr)+\delta \biggr), \end{equation} \tag{2.10} $$
где $x_*$ – искомая точка минимума $g$.

Замечание 2. Условие $\mu_x$-сильной выпуклости $g$ и оценка (2.10) существенны для обоснования достижимости требуемого качества решения седловой задачи (1.1) согласно определению 1.

Замечание 3. Метод эллипсоидов с $\delta$-субградиентом может быть использован и в том случае, когда у нас есть доступ к $\delta$-неточному градиенту вместо точного градиента или $\delta$-субградиента (см. лемму 3).

Теперь напомним метод секущей плоскости, который был предложен Вайдой (см. [19]) для решения задачи (2.8). Сначала введем необходимые обозначения. Для матрицы $A$ и вектора $b$ будем рассматривать вспомогательный ограниченный $n$-мерный многогранник $P(A, b)$ вида

$$ \begin{equation*} P(A, b)=\{x \in \mathbb R^n\colon Ax\geqslant b\}, \quad\text{где }\ A \in \mathbb R^{m\times n}, \quad b \in \mathbb R^m, \end{equation*} \notag $$
где неравенство $Ax\geqslant b$ понимается как покомпонентное (каждая координата вектора $Ax$ не меньше соответствующей координаты вектора $b$).

Для множества $P(A, b)$ можно ввести следующий логарифмический барьер:

$$ \begin{equation*} L(x; A,b)=-\sum_{i=1}^{m} \ln (a_{i}^{\top} x-b_{i}), \qquad x \in \operatorname{int} P(A,b), \end{equation*} \notag $$
где $a_{i}^{\top}$ – $i$-я строка матрицы $A$, $\operatorname{int} P(A,b)$ – внутренность $P(A,b)$. Гессиан $H$ функции $L$ есть
$$ \begin{equation} H(x; A,b)=\sum_{i=1}^{m} \frac{a_{i} a_{i}^{\top}}{(a_{i}^{\top} x-b_{i})^{2}}, \qquad x \in \operatorname{int} P(A,b). \end{equation} \tag{2.11} $$
Матрица $H(x; A,b)$ положительно определена для всех $x \in \operatorname{int} P(A,b)$. Также для множества $P(A, b)$ можно ввести волюметрический барьер (volumetric barrier) вида
$$ \begin{equation} V(x; A,b)=\frac{1}{2} \ln (\operatorname{det}H(x; A,b)), \qquad x \in \operatorname{int} P(A,b), \end{equation} \tag{2.12} $$
где $\operatorname{det}H(x; A,b)$ обозначает определитель $H(x; A,b)$. Обозначим
$$ \begin{equation} \sigma_{i}(x; A,b)=\frac{a_{i}^{\top} (H(x; A,b))^{-1} a_{i}}{(a_{i}^{\top} x-b_{i})^{2}}, \qquad x \in \operatorname{int} P(A,b), \quad 1 \leqslant i \leqslant m. \end{equation} \tag{2.13} $$

Волюметрическим центром множества $P(A, b)$ называют точку минимума волюметрического барьера

$$ \begin{equation} x_c=\operatorname{arg}\min_{x \in \operatorname{int} P(A, b)} V(x; A,b). \end{equation} \tag{2.14} $$

Волюметрический барьер $V$ является самосогласованной функцией, поэтому может быть эффективно минимизирован методом Ньютона. Подробный теоретический анализ для метода Вайды можно найти в статье [19] и книге [20]. Ранее в [21] было доказано, что в методе Вайды можно использовать $\delta$-субградиент вместо точного субградиента. Ниже приводится вариант метода с использованием $\delta$-субградиента (алгоритм 3).

Этот алгоритм образует последовательность пар $(A_k, b_k) \in \mathbb R^{m_k\times n}\times \mathbb R^{m_k}$ таких, что соответствующие многогранники содержат искомое решение задачи. В качестве исходного многогранника, задаваемого парой $(A_0, b_0)$, можно выбрать, например, симплекс

$$ \begin{equation*} P_0=\biggl\{x \in \mathbb{R}^n\colon x_{j} \geqslant-\mathcal{R}, j=1,\dots,n,\ \sum_{j=1}^{n} x_{j} \leqslant n \mathcal{R} \biggr\} \supseteq \mathcal{B}_{\mathcal{R}} \supseteq \mathcal{X}, \end{equation*} \notag $$
т.е.
$$ \begin{equation} b_0=- \mathcal{R}\begin{bmatrix} \mathbf{1}_n \\ n \end{bmatrix}, \qquad A_0=\begin{bmatrix} I_n \\ -\mathbf{1}_n^{\top} \end{bmatrix}, \end{equation} \tag{2.15} $$
где $I_n$ обозначает единичную матрицу размера $n \times n$, $\mathbf{1}_n$ обозначает вектор из единиц $(1, \dots, 1)^{\top} \in \mathbb{R}^n$. В таком случае $m_0$ будет равно $n+1$.

Теорема 4 (см. [21]). После

$$ \begin{equation*} N \geqslant \frac{2n}{\gamma} \ln \biggl( \frac{n^{1.5} \mathcal{R}}{\gamma \rho} \biggr)+ \frac{1}{\gamma} \ln \pi \end{equation*} \notag $$
итераций метод Вайды с $\delta$-субградиентом для задачи (2.8) возвращает такую точку $x^N$, что
$$ \begin{equation} g(x^N)-\min_{x \in Q} g(x) \leqslant \frac{n^{1.5} B \mathcal{R}}{\gamma \rho} \exp \biggl( \frac{\ln \pi -\gamma N}{2n} \biggr)+\delta, \end{equation} \tag{2.16} $$
где $\gamma>0$ – параметр алгоритма 3.

Следствие 2. Если к условиям теоремы 4 добавить $\mu_x$-сильную выпуклость $g$, то точка выхода $x^N$ алгоритма 3 удовлетворяет неравенству

$$ \begin{equation*} \| x^N-x_* \|_2^2 \leqslant \frac{2}{\mu_x} \biggl( \frac{n^{1.5} B \mathcal{R}}{\gamma \rho} \exp \biggl( \frac{\ln \pi -\gamma N}{2n} \biggr)+\delta \biggr), \end{equation*} \notag $$
где $x_*$ – точка минимума $g$.

Замечание 4 (учет неточной информации о значении целевой функции). Как метод эллипсоидов, так и метод Вайды используют значения целевой функции при определении выходов алгоритмов ($x^N$). Однако по смыслу рассматриваемой в настоящей статье постановки седловой задачи естественна ситуация, когда значение целевой функции вспомогательной подзадачи доступно лишь с некоторой точностью $\widetilde{\delta}$. В таком случае выписанные оценки качества выдаваемых методами приближенных решений (2.9) и (2.16) необходимо уточнить, добавив в правые части неравенств слагаемые $\widetilde{\delta}$. Действительно, если функция $g_{\widetilde{\delta}}$ отличается от $g$ не больше, чем на $\widetilde{\delta}$, то для

$$ \begin{equation*} \widetilde{x}^N :=\operatorname*{arg\,min}_{x \in \{x_0, \dots, x_{N-1}\}} g_{\widetilde{\delta}}(x), \qquad x^N :=\operatorname*{arg\,min}_{x \in \{x_0, \dots, x_{N-1}\}} g(x) \end{equation*} \notag $$
верно неравенство $g(\widetilde{x}^N) \leqslant g(x^N)+\widetilde{\delta}$.

Замечание 5. Метод Вайды с использованием $\delta$-субградиентов может быть использован и в том случае, когда доступна информация о $\delta$-неточном субградиенте вместо точного или $\delta$-субградиента (см. лемму 3).

Замечание 6 (сравнение результатов о сложности для метода эллипсоидов и метода Вайды). По числу итераций, требуемых для достижения заданной точности решения минимизационной задачи по функции, метод эллипсоидов проигрывает методу Вайды. Действительно, для метода эллипсоидов оценка количества итераций квадратично зависит от размерности пространства, а для метода Вайды эта оценка пропорциональна $n \ln n$.

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

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

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

$$ \begin{equation} \min_{y \in \mathbb{R}^m} \bigl\{ U(y) :=u(y)+v(y) \bigr\}, \end{equation} \tag{2.17} $$
где $u$ – $\mu$-сильно выпуклая функция с $L_u$-липшицевым градиентом, $v$ – выпуклая функция.

Теорема 5 (оценка сложности рестартованного ускоренного метаалгоритма; см. [4]). Пусть $z_N$ – выход алгоритма 5 после $N$ итераций. Тогда если $H \geqslant 2 L_u$, то общее число вычислений (2.18) для достижения $\displaystyle U(z_N)- U(y_*) \leqslant \varepsilon$ будет равно

$$ \begin{equation} N=O \biggl( \sqrt{\frac{H}{\mu}} \ln \biggl(\frac{\mu R_y^2}{\varepsilon}\biggr) \biggr), \end{equation} \tag{2.19} $$
где $R_y=\| y^0-y_* \|_2$, а $y_*$ – точное решение задачи (2.17).

Замечание 7 (разделение оракульных сложностей). Если $v$ имеет $L_v$-липшицев градиент, то можно смотреть на вспомогательную задачу (2.18) как на гладкую сильно выпуклую задачу. Для ее решения можно также использовать рестартованный ускоренный метаалгоритм (УМ), положив

$$ \begin{equation*} \begin{gathered} \, u^{\mathrm{new}} :=v,\qquad v^{\mathrm{new}}(y) :=u(\widetilde{z}_k)+\langle \nabla u(\widetilde{z}_k), y-\widetilde{z}_k\rangle +\frac{H}{2}\|y-\widetilde{z}_k\|_2^{2}, \\ \mu^{\mathrm{new}} :=\frac{H}{2}, \qquad H^{\mathrm{new}} :=2 L_v \end{gathered} \end{equation*} \notag $$
и применяя технику рестартов подобно тому, как это сделано в [4]. При условии $L_u \leqslant L_v$ это позволяет получить $\varepsilon$-решение задачи (2.17) за
$$ \begin{equation} \begin{gathered} \, O \biggl( \sqrt{\frac{H}{\mu}} \ln \biggl(\frac{\mu R_y^2}{\varepsilon}\biggr) \biggr) \quad \text{вычислений } \nabla u \text{ и } \\ O \biggl( \sqrt{\frac{L_v}{\mu}} \ln \biggl(\frac{\mu R_y^2}{\varepsilon}\biggr) \biggr) \quad \text{вычислений } \nabla v. \end{gathered} \end{equation} \tag{2.20} $$

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

Для того чтобы найти $\varepsilon$-решение задачи (2.1) в предположении 2, предлагается использовать следующий подход.

Подход 1 (случай малой размерности $x$). Алгоритм 1 применяется к задаче (2.1) с параметрами $\widetilde{\varepsilon}:=\varepsilon/2$, $\mathcal{M}_1$ – метод Вайды (алгоритм 3), $\mathcal{M}_2$ – рестартованный УМ (алгоритм 5).

Воспользуемся предложением из п. 2.1, чтобы установить сложность подхода 1. Для этого требуется, используя обозначения из формулировки упомянутого предложения, выписать зависимости $N_1(\varepsilon, \delta)$, $\delta(\widetilde{\varepsilon})$ и $N_2(\widetilde{\varepsilon})$. Согласно лемме 1 точность $\widetilde{\varepsilon}={\varepsilon}/{2}$ решения внутренней задачи приводит к точности $\delta$-субградиента, равной $\delta= {\varepsilon}/{2}$. Как видно из теоремы 4, количество итераций метода Вайды составляет

$$ \begin{equation*} N_1 \biggl( \varepsilon, \frac{\varepsilon}{2} \biggr)=\biggl\lceil \frac{2 n}{\gamma} \ln \biggl(\frac{2 n^{1.5} B \mathcal{R}}{\gamma \rho \varepsilon} \biggr)+\frac{\ln \pi}{\gamma} \biggr\rceil. \end{equation*} \notag $$
Рестартованный УМ (алгоритм 5) применяется к функциям $u(\cdot) :=-F(x, \cdot)$ и $v(\cdot) :=h(\cdot)$ (если в предположении 2, b) $L_{yy} > L_h$, то нужно поменять $u$ и $v$). Прежде чем выписать его сложность, заметим, что отображение $y^*(x):=\operatorname{arg}\max_{y \in Q_y} S(x, y)$ непрерывно в силу непрерывности $S$ и ее сильной выпуклости по $y$. Следовательно, множество $\{ y^*(x)\mid x \in Q_x \}$ ограничено как образ компактного множества. Обозначим его диаметр через $R_y$.

Если $h$ является проксимально-дружественной (случай 1), то согласно формуле (2.19) ${\varepsilon}/{2}$-решение внутренней задачи может быть найдено за

$$ \begin{equation*} N_2 \biggl( \frac{\varepsilon}{2} \biggr)=O \biggl( \sqrt{\frac{L_{yy}}{\mu_y}} \ln \biggl(\frac{\mu_y R_y^2}{\varepsilon}\biggr) \biggr) \quad\text{вычислений }\ \nabla_y F \text{ и решений задачи } (2.7). \end{equation*} \notag $$
Если же $h$ имеет $L_h$-липшицев градиент (случай 2), то согласно формулам (2.20) ${\varepsilon}/{2}$-решение внутренней задачи может быть найдено за
$$ \begin{equation*} \begin{gathered} \, N_2^F \biggl( \frac{\varepsilon}{2} \biggr)=O \biggl( \sqrt{\frac{L_{yy}}{\mu_y}} \ln \biggl(\frac{\mu_y R_y^2}{\varepsilon}\biggr) \biggr) \quad \text{вычислений }\ \nabla_y F\text{ и} \\ N_2^h \biggl( \frac{\varepsilon}{2} \biggr)=O \biggl( \sqrt{\frac{L_h}{\mu_y}} \ln \biggl(\frac{\mu_y R_y^2}{\varepsilon}\biggr) \biggr) \quad \text{вычислений }\ \nabla h. \end{gathered} \end{equation*} \notag $$

Из выписанных оценок сложности и предложения из 2.1 следует результат, сформулированный в теореме 2. Вместо метода Вайды можно использовать в качестве $\mathcal{M}_1$ метод эллипсоидов. Согласно теореме 3 его сложность составляет

$$ \begin{equation*} N_1 \biggl( \varepsilon, \frac{\varepsilon}{2} \biggr)=\biggl\lceil 2 n^2 \ln \biggl( \frac{2 B \mathcal{R}}{\rho \varepsilon} \biggr) \biggr\rceil. \end{equation*} \notag $$
В этом случае получаются похожие оценки сложности, а именно, $\varepsilon$-решение задачи (2.1) может быть достигнуто:

$\bullet$ в предположении 2 за

$$ \begin{equation*} O \biggl( n^2 \ln \frac{1}{\varepsilon} \biggr) \quad \text{вычислений }\nabla_x F,\ \nabla r; \end{equation*} \notag $$

$\bullet$ в предположении 2, a) за

$$ \begin{equation*} O \biggl( n^2 \sqrt{\frac{L_{yy}}{\mu_y}} \ln^2 \frac{1}{\varepsilon} \biggr)\quad\text{вычислений }\nabla_y F\text{ и решений задачи }(2.7); \end{equation*} \notag $$

$\bullet$ в предположении 2, b) за

$$ \begin{equation*} \begin{gathered} \, O \biggl( n^2 \sqrt{\frac{L_{yy}}{\mu_y}} \ln^2 \frac{1}{\varepsilon} \biggr)\quad \text{вычислений }\nabla_y F\text{ и } \\ O \biggl( n^2 \sqrt{\frac{L_h}{\mu_y}} \ln^2 \frac{1}{\varepsilon} \biggr)\quad \text{вычислений }\nabla h. \end{gathered} \end{equation*} \notag $$

Отметим, что когда функция $h$ является проксимально-дружественной (предположение 2, a), то в подходе 1 можно использовать в качестве метода $\mathcal{M}_2$, например, метод подобных треугольников (см. [22]), который позволяет убрать из предположения 2 требование $Q_y \equiv \mathbb{R}^m$, сохранив те же оценки сложности.

Другой интересный случай возникает, когда $Q_y=[a_1, b_1] \times \dots \times [a_m, b_m]$ – гиперпрямоугольник и $S$ сепарабельна по $y$, т.е. для $y=(y_1, y_2, \dots, y_m) \in Q_y$ верно $S(x, y)=\sum_{i=1}^m S_i(x, y_i)$, где для любого $x \in Q_x$ функции $S_i(x, y_i)$ аргумента $y_i$ являются непрерывными и унимодальными. Тогда из предположения 2 можно убрать требование о гладкости и сильной вогнутости функции $S$ по $y$ и свести вспомогательную задачу (2.3) к $m$ задачам одномерной максимизации

$$ \begin{equation*} \max_{y_i \in [a_i, b_i]} S_i(x, y_i), \qquad i=1,\dots, m. \end{equation*} \notag $$
Эти задачи можно решать с помощью метода дихотомии (деления отрезка пополам) с точностью $\varepsilon/(2m)$, что гарантирует точность ${\varepsilon}/{2}$ решения вспомогательной задачи (2.3). Такой подход позволяет получить $\varepsilon$-решение задачи (2.1) за $O \biggl( n \ln \dfrac{n}{\varepsilon} \biggr)$ вычислений $\nabla_x F$ и $O \biggl( mn \ln \dfrac{n}{\varepsilon} \ln \dfrac{m}{\varepsilon} \biggr)$ вычислений $S(x, y)$.

Наконец, рассмотрим случай, когда малую размерность имеют не внешние переменные $x$, а внутренние $y$. Пусть $F$ является выпуклой по $x$ и $\mu_y$-сильно вогнутой по $y$, а также для любых $x \in Q_x$ и $y,y' \in Q_y$ верны неравенства

$$ \begin{equation*} \begin{gathered} \, \|\nabla_x F(x, y)-\nabla_x F(x', y)\|_2 \leqslant L_{xx}\|x-x'\|_2, \\ \|\nabla_x F(x, y)-\nabla_x F(x, y')\|_2 \leqslant L_{xy}\|y-y'\|_2, \\ \|\nabla_y F(x, y)-\nabla_y F(x', y)\|_2 \leqslant L_{xy}\|x-x'\|_2, \end{gathered} \end{equation*} \notag $$
где $L_{xx}, L_{xy} < \infty$. Пусть также функция $r$ является $\mu_x$-сильно выпуклой и проксимально-дружественной. В такой постановке внешняя задача (2.4) (минимизация функции $g$) является многомерной. Как показано в [1], для минимизации функции $g$ можно использовать быстрый градиентный метод с аналогом неточного оракула – $(\delta, L)$-моделью целевой функции в произвольной запрашиваемой точке $Q_x$. Поэтому для решения задачи (2.1) предлагается использовать следующий подход.

Подход 2 (малая размерность $y$). Ко внешней задаче (2.4) применяется быстрый градиентный метод с $(\delta, L)$-оракулом для задач сильно выпуклой композитной оптимизации (см. [1], алгоритм 4). Для внутренней задачи (2.3) используется метод Вайды (алгоритм 3 с $\delta=0$).

Можно доказать, что такой подход позволяет получить $\varepsilon$-решение задачи (2.1) за

$$ \begin{equation*} \begin{gathered} \, O \biggl( \sqrt{\frac{L}{\mu_x}} \ln \dfrac{1}{\varepsilon} \biggr) \quad \text{вычислений }\nabla_x F\text{ и решений задачи }(1.2)\text{ и} \\ O \biggl( m \sqrt{\frac{L}{\mu_x}} \ln \frac{1}{\varepsilon} \ln \frac{m}{\varepsilon} \biggr)\quad\text{вычислений }\nabla_y F,\ \nabla h, \end{gathered} \end{equation*} \notag $$
где $L=L_{xx}+ {2L_{xy}^2}/{\mu_y}$.

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

В этом пункте мы рассмотрим выпукло-вогнутую седловую задачу (полагаем одно из композитных слагаемых $r$ в задаче (1.1) тождественно равным 0)

$$ \begin{equation} \max_{y \in Q_{y}} \Bigl\{ \min_{x \in Q_{x}} S(x, y) := F(x,y)-h(y) \Bigr\}. \end{equation} \tag{2.21} $$

Пусть для задачи (2.21) выполнено следующее

Предположение 3. $Q_x\subseteq \mathbb{R}^n$ – гиперкуб с конечной стороной, $Q_y\subseteq \mathbb{R}^m$ – непустое выпуклое компактное множество, размерность $n$ очень мала (менее $5$), функция $\widehat{S}$ имеет вид

$$ \begin{equation*} \widehat{S}(x, y)=S(x, y)=F(x,y)-h(y), \end{equation*} \notag $$
где $\mu_y$-сильно выпуклая функция $h$ непрерывна, функционал $F$, заданный в некоторой окрестности множества $Q_x \times Q_y$, является выпуклым по $x$ и вогнутым по $y$. Допустим, что $F$ является достаточно гладким, а именно для произвольных $x, x' \in Q_x$ и $y, y' \in Q_y$ верны неравенства
$$ \begin{equation} \begin{gathered} \, \|\nabla_x F(x, y)-\nabla_x F(x', y)\|_2 \leqslant L_{xx}\|x-x'\|_2, \\ \|\nabla_x F(x, y)-\nabla_x F(x, y')\|_2 \leqslant L_{xy}\|y-y'\|_2, \end{gathered} \end{equation} \tag{2.22} $$
$$ \begin{equation} \begin{gathered} \, \|\nabla_y F(x, y)-\nabla_y F(x', y)\|_2 \leqslant L_{xy}\|x-x'\|_2, \\ \|\nabla_y F(x, y)-\nabla_y F(x, y')\|_2 \leqslant L_{yy}\|y-y'\|_2, \end{gathered} \end{equation} \tag{2.23} $$
где $L_{xx}, L_{xy}, L_{yy} <+\infty$. Пусть, как и ранее (см. предположение 2), выполнено одно из условий, a (случай 1) или b (случай 2).

Введем для задачи (2.21) функцию

$$ \begin{equation*} f:=\max_{y\in Q_y} S(x,y). \end{equation*} \notag $$
Обозначим диаметр множества $Q_x$ через $R=\max_{x_1,x_2\in Q_x}\|x_1-x_2\|$. Если размер каждой стороны гиперкуба равен $a$, то $R=a\sqrt{n}$.

Как и в пп. 2.1, 2.3, будем рассматривать подходы к (2.21) на базе системы вспомогательных минимизационных задач. Однако для решения маломерных (внешних) подзадач на гиперкубе уже будем использовать некоторый аналог метода дихотомии. Поэтому сначала опишем этот подход к решению задач выпуклой минимизации на многомерном гиперкубе с использованием неточного градиента на итерациях.

Рассмотрим задачу оптимизации вида

$$ \begin{equation} \min_{x \in Q_x} f(x), \end{equation} \tag{2.24} $$
где функция $f$ является липшицевой с константой $M_f$, имеет липшицев градиент с константой $L_f$ и является $\mu_f$-сильно выпуклой, $Q_x$ – конечный гиперкуб. Далее в этом пункте будет описан и проанализирован алгоритм 6 (метод многомерной дихотомии), являющийся аналогом предложенного Ю. Е. Нестеровым метода двумерной минимизации на квадрате (см. [22; упр. 4.2]), – метод многомерной дихотомии на гиперкубе размерности $n\geqslant 2$.

Для алгоритма 6 получен следующий результат.

Теорема 6. Пусть для задачи (2.24) функция $f$ является $M_f$-липшицевой $\mu_f$-сильно выпуклой и имеет $L_f$-липшицев градиент. Для достижения точности $\varepsilon$ по функции точки выхода алгоритма 6 достаточно

$$ \begin{equation} O\biggl(2^{n^2} \log_2^n\biggl(\frac{C R}{\varepsilon}\biggr)\biggr), \quad\textit{где }\ C= \max\biggl(M_f,\frac{4(M_f+2L_fR)}{L_f}, \frac{128L_f^2}{\mu_f}\biggr), \end{equation} \tag{2.25} $$
обращений к подпрограмме для вычисления $\nu(\mathbf{x})$, где $\nu(\mathbf{x})$ есть приближение градиента $\nabla f$ такое, что $\|\nabla f(\mathbf{x})-\nu(\mathbf{x})\|_2\leqslant \widetilde{\delta}(\mathbf{x})$ для всякой текущей точки $\mathbf{x}$. Точность $\widetilde{\delta}(x)$ определяется из условия (2.28), точность решения вспомогательных задач определяется согласно (2.26).

Используя этот результат и методы вспомогательной минимизации, описанные в п. 2.2, можно прийти к следующим выводам. Пусть решение по малоразмерной переменной находится при помощи метода многомерной дихотомии. Тогда точность $\varepsilon$ будет достигнута в смысле определения 1 для седловой задачи (2.21) за следующее число операций:

$$ \begin{equation*} O\biggl(2^{n^2} \log_2^n\biggl(\frac{C R}{\varepsilon}\biggr)\biggr) \quad\text{обращений к подпрограмме вычисления }\ \nabla_x S(x, y); \end{equation*} \notag $$

  • • в случае 1
    $$ \begin{equation*} \begin{gathered} \, O \biggl( 2^{n^2} \sqrt{\frac{L_{yy}}{\mu_y}} \log_2^{n+1} \biggl(\frac{CR}{\varepsilon}\biggr) \biggr)\quad\text{вычислений }\nabla_y F(x, y) \\ \text{ и решений подзадачи }(2.7); \end{gathered} \end{equation*} \notag $$
  • • в случае 2
    $$ \begin{equation*} \begin{gathered} \, O \biggl( \sqrt{\frac{L_h}{\mu_y}} \log_2^{n+1}\biggl(\frac{CR}{\varepsilon}\biggr) \biggr) \quad\text{вычислений }\ \nabla h(y)\text{ и} \\ O \biggl( 2^{n^2} \biggl( \sqrt{\frac{L_h}{\mu_y}}+\sqrt{\frac{L_{yy}}{\mu_y}} \biggr) \log_2^{n+1}\bigl(\frac{CR}{\varepsilon}\biggr) \biggr) \quad\text{вычислений }\ \nabla_y F(x, y). \end{gathered} \end{equation*} \notag $$

2.3.1. Описание метода многомерной дихотомии

Метод многомерной дихотомии предполагает проведение через центр гиперкуба разделяющей гиперплоскости параллельно одной из его граней и рекурсивное решение вспомогательной задачи оптимизации с некоторой точностью $\widetilde{\varepsilon}$, выбор которой мы обсудим ниже. В точке приближенного решения вычисляется неточный градиент $\nu(x)$ такой, что $\|\nu(x)\,{-}\,\nabla f(x)\|_2 \,{\leqslant}\, \widetilde{\delta}$ для подходящего $\widetilde{\delta}$, и выбирается та его компонента в текущей точке, которая соответствует зафиксированному измерению выбранной гиперплоскости, и в зависимости от ее знака выбирается та часть гиперкуба, в которой не лежит неточный градиент. На одной итерации метода описанная процедура выполняется для каждой грани гиперкуба. Итерации метода выполняются для основного гиперкуба до тех пор, пока размер $R$ оставшейся области не станет меньше ${\varepsilon}/{M_f}$, что гарантирует сходимость по функции с точностью $\varepsilon$. Условие останова для вспомогательной подзадачи, гарантирующее достижение приемлемой точности исходной задачи, будет подробнее описано ниже (теорема 10).

Обсудим корректность алгоритма 6. Далее будем использовать следующие обозначения. Пусть на текущем уровне рекурсии рассматривается множество $Q\subset \mathbb{R}^n$ и некоторое его сечение вида $Q_k=\{x \in Q\mid x_k=c\}$ для некоторого $c\in \mathbb{R}$ и $k=1,\dots, n$. Пусть $\nu$ есть вектор в $\mathbb{R}^n$. Тогда определим $\nu_{\parallel Q_k}$, $\nu_{\perp Q_k}$ – проекции вектора $\nu$ на $Q_k$ и его ортогональное дополнение в пространстве $\mathbb{R}^{n}$ соответственно. Заметим, что $\nu_{\perp Q_k}$ есть скаляр.

Сформулируем следующий вспомогательный результат.

Лемма 4. Пусть $f$ – непрерывно дифференцируемая выпуклая функция и рассматривается задача ее минимизации на множестве $Q_k \subset Q$. Если $\mathbf{x}_*$ – решение этой задачи, то существует условный субградиент функции $f$ на множестве $Q_x$ $g \in \partial_Q f(\mathbf{x}_*)$ такой, что $g_\parallel=0.$

Отметим, что алгоритм 6 сходится не для всех выпуклых функций, даже если допустить, что все вспомогательные подзадачи одномерной минимизации решаются точно. Отметим в этой связи пример негладкой выпуклой функции из [16], для которой теряется сходимость многомерной дихотомии.

Следующий результат – обобщение на многомерный случай утверждений (см. [16]) о сходимости метода Ю. Е. Нестерова на квадрате.

Теорема 7. Пусть функция $f$ выпукла, имеет $L_{f}$-липшицев градиент при некотором $L_{f} > 0$. Пусть $\nu(\mathbf{x})=\nabla f(\mathbf{x})$ и $\nu_{\perp Q_k}(\mathbf{x})= \bigl(\nu(\mathbf{x})\bigr)_{\perp Q_k}$ для всякой текущей точки $\mathbf{x}$. Если все вспомогательные подзадачи решаются со следующей точностью по функции:

$$ \begin{equation} \widetilde{\varepsilon} \leqslant \frac{\mu_f \varepsilon^2}{128 L_f^2 R^2}, \end{equation} \tag{2.26} $$
то после каждого удаления некоторой части (согласно пп. 11–14 алгоритма 6) допустимого множества оставшаяся его часть содержит решение исходной задачи $\mathbf{x}_*$ на гиперкубе $Q_x$.

Данная оценка требует точности решения вспомогательной задачи по функции порядка $\varepsilon^{2k}$ на $k$-м уровне рекурсии. Таким образом, с учетом максимальной глубины рекурсии $n-1$ получаем, что в худшем случае на каждом шаге алгоритма потребуется решать задачу с точностью $\varepsilon^{2n-2}$ по функции.

Замечание 8. Условие $\mu_f$-сильной выпуклости $f$ нужно лишь для теоретической оценки достаточной точности решения вспомогательных подзадач на итерациях алгоритма 6, которая бы позволила гарантировать достижение требуемого качества решения задачи (2.24) за линейное время. Для практической реализации метода многомерной дихотомии ни знать константу $\mu_f$, ни требовать выполнения условия $\mu_f > 0$ нет необходимости, что существенно использовано при постановке экспериментов.

Интуитивно понятно, что для функции с липшицевым градиентом “большая” величина ортогональной компоненты при близости к точному решению (вспомогательной подзадачи) не сможет сильно уменьшиться, а следовательно, и изменить направление. С другой стороны, если эта компонента мала и решается вспомогательная задача на многомерном параллелепипеде $Q_k$, то можно выбрать эту точку в качестве искомого решения задачи на $Q_k$. Предложим некоторый подход к выбору точности для вспомогательных подзадач на базе отмеченной выше идеи.

Начнем с результата о необходимой точности для решения вспомогательных подзадач, гарантирующей сохранение искомого точного решения в допустимой области после удаления ее частей на итерациях метода. Будем обозначать далее через $\Delta$ точность решения вспомогательных подзадач (п. 9 алгоритма 6) по аргументу (п. 10 алгоритма 6).

Теорема 8. Пусть функция $f$ выпукла и имеет $L_f$-липшицев градиент при $L_f > 0$, $\mathbf{x}$ – приближенное решение вспомогательной подзадачи на некоторой итерации метода. Пусть на каждой итерации $\nu(\mathbf{x})=\nabla f(\mathbf{x})$ и $\nu_{\perp Q_k}(\mathbf{x})= \bigl(\nu(\mathbf{x})\bigr)_\perp$, а также приближение $\mathbf{x}$ удовлетворяет условию

$$ \begin{equation*} \Delta \leqslant \frac{|\nu_{\perp Q_k}(\mathbf{x})|}{L_f}. \end{equation*} \notag $$
Тогда после каждого удаления части допустимого множества оставшаяся его часть содержит решение исходной задачи $\mathbf{x}_*$ на гиперкубе.

Полученная в теореме 8 оценка может привести к крайне медленной скорости сходимости алгоритма 6, если проекция вектора-градиента во всякой текущей точке на ортогональное дополнение к рассматриваемому подпространству стремительно убывает при приближении к точке-решению. Поэтому сформулируем результат с альтернативным условием останова для вспомогательных задач. Обозначим через $Q_k$ некоторое подмножество (отрезок, часть плоскости или гиперплоскости) исходного гиперкуба $Q$, на котором решается вспомогательная подзадача.

Теорема 9. Пусть функция $f$ выпукла, $M_f$-липшицева и имеет $L_f$-липшицев градиент ($M_f> 0$, $L_f > 0$). Тогда для достижения точности $\varepsilon$ по функции решения задачи (2.24) на множестве $Q_x$ достаточно выполнения следующего условия для всякого приближенного решения $\mathbf{x}\in Q_k\subset Q$:

$$ \begin{equation*} \Delta \leqslant \frac{\varepsilon- R|\nu_{\perp Q_k}(\mathbf{x})|}{L_f+M_f R}, \end{equation*} \notag $$
где $R=a\sqrt{n}$ – длина диагонали в исходном гиперкубе $Q_x$.

Здесь под $\varepsilon$ подразумевается точность по функции, с которой нужно решить задачу оптимизации на $Q_k$ при условии, что алгоритм находится на $k$-м уровне рекурсии, т.е. решает вспомогательную задачу на множестве $Q_k\subset Q$.

Объединяя полученные оценки, получаем следующую теорему для случая $n=2$.

Теорема 10. Пусть функция $f$ выпукла, $M_f$-липшицева и имеет $L_f$-липшицев градиент ($M_f > 0$, $L_f >0$), а также в произвольной текущей точке $x$ при реализации метода мы используем неточный градиент $\nu(x)$, удовлетворяющий условию

$$ \begin{equation} \|\nabla f(\mathbf{x})-\nu(\mathbf{x})\|_2 \leqslant \widetilde{\delta}(\mathbf{x}). \end{equation} \tag{2.27} $$
Тогда для того чтобы после каждого удаления части допустимого множества оставшаяся его часть содержала решение исходной задачи $\mathbf{x}_*$ на множестве $Q$, достаточно выполнения следующего условия для решения $\mathbf{x}$ вспомогательной задачи минимизации $f$ на $Q_k$:
$$ \begin{equation} C_f\widetilde{\delta}(\mathbf{x})+\Delta \leqslant \max\biggl\{ \frac{|\nu_{\perp Q_k}(\mathbf{x})|}{L_f}, \frac{\varepsilon-R |\nu_{\perp Q_k}(\mathbf{x})|}{M_f+L_f R} \biggr\}, \end{equation} \tag{2.28} $$
где $C_f=\max\biggl(\dfrac{1}{L_f}, \dfrac{R}{M_f+L_f R}\biggr).$ В таком случае приближение искомого минимума с точностью $\varepsilon$ будет достигнуто не более чем за
$$ \begin{equation} N^* :=\biggl\lceil\log_2 \biggl(\frac{4R(M_f+2L_f R)}{L_f\varepsilon}\biggr)\biggr\rceil \end{equation} \tag{2.29} $$
итераций алгоритма 6.

Отметим, что критерий останова (2.28) применим ко внутренним подзадачам. Для внешних подзадач остановка определяется требуемым количеством итераций (2.29).

Кроме того, заметим, что с учетом требований малости диаметра оставшейся части допустимой области после удаления гиперпрямоугольников (согласно алгоритму 6) оценка количества итераций, гарантирующих достижение $\varepsilon$-точности по функции, принимает следующий вид:

$$ \begin{equation} O\biggl(\log_2\biggl(\varepsilon^{-1}\max\biggl(M_f, \frac{4(M_f +2L_f R)}{L_f}\biggr)\biggr)\biggr). \end{equation} \tag{2.30} $$

Таким образом, на каждом уровне рекурсии (для гиперпрямоугольника $Q$) вспомогательная задача решается до тех пор, пока не будет выполнено условие (2.28). Причем в случае, если для некоторой точки условие (2.28) выполняется и для второго аргумента максимума, то эта точка будет решением задачи на $Q$. При этом если задача на $Q$ есть вспомогательная задача для некоторого гиперпрямоугольника $Q_1$ в более высокой размерности, то на более высоких уровнях рекурсии решение задачи тем не менее не останавливается.

Переходим теперь к описанию теоретических результатов об оценках скорости сходимости предложенной методики для сильно выпукло-вогнутых седловых задач вида (2.21) с достаточно малой размерностью (до 5) одной из групп переменных. Напомним, что мы рассматриваем исходную задачу (2.21) как задачу минимизации вспомогательного выпуклого функционала max-типа с использованием неточного градиента на каждой итерации (точность его нахождения регулируется за счет решения вспомогательных минимизационных подзадач по другой группе переменных). Отметим, что поскольку множества $Q_x$ и $Q_y$ компактны, то $f$ удовлетворяет условию Липшица в силу предположений (2.22), (2.23).

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

Для минимизации по переменной малой размерности $x$ в задаче (2.21) будем использовать метод многомерной дихотомии (алгоритм 6) с неточным (аддитивно зашумленным) градиентом. Опишем необходимые условия на точность градиента целевого функционала, который будет использоваться на каждой итерации. Заметим, что согласно теореме Демьянова–Данскина (см. [23]) имеем

$$ \begin{equation*} \nabla f(\mathbf{x})=\nabla_x S(\mathbf{x}, \mathbf{y}(\mathbf{x})). \end{equation*} \notag $$
Здесь и далее будем считать, что $\nu(\mathbf{x})=\nabla_x S(\mathbf{x}, \mathbf{y}_{\widetilde{\delta}}),$ где $\mathbf{y}_{\widetilde{\delta}}$ есть приближение $\mathbf{y}(\mathbf{x})$ такое, что выполнено условие (2.27). Рассмотрим два возможных условия для вычисления $\mathbf{y}_{\widetilde{\delta}}$.

1. В силу сделанных выше предположений для $S$

$$ \begin{equation*} \|\nu (\mathbf{x})- \nabla f(\mathbf{x})\|_2\leqslant L_{yx} \|\mathbf{y}(\mathbf{x})- \mathbf{y}_\delta\|_2. \end{equation*} \notag $$

Таким образом, для того чтобы правильно определить оставшееся множество, достаточно выполнения неравенства (2.28), где $\widetilde{\delta}(\mathbf{x})=L_{yx} \|\mathbf{y}(\mathbf{x})-\mathbf{y}_\delta\|_2$.

Указанный выше способ предполагает возможность решения с линейной скоростью внутренней подзадачи задачи с любой точностью по аргументу. Однако если $S(\mathbf{x}, \mathbf{y})$ $\mu_y$-сильно вогнута по $\mathbf{y}$, то эти условия можно заменить на условия сходимости по функции. В таком случае получаем, что вспомогательную задачу по $y$ нужно решать с точностью по функции $\delta$, удовлетворяющей условию

$$ \begin{equation} \delta \leqslant \frac{\mu_y}{2L_{yx}^2} \widetilde{\delta}^2. \end{equation} \tag{2.31} $$

2. Можно получить другую оценку для необходимой точности решения вспомогательных подзадач. Заметим, что если $y_{\widetilde{\delta}}$ есть решение задачи максимизации вида

$$ \begin{equation*} f(x)=\max_{\mathbf{y}\in Q_y}S(\mathbf{x}, \mathbf{y}) \end{equation*} \notag $$
при фиксированном $x$ с точностью ${\delta}$ по функции, то $\nu(\mathbf{x})$ есть ${\delta}$-градиент функции $f$ в точке $\mathbf{x}$. Тогда по теореме 1 в случае, если расстояние от текущей точки $x$ до границы допустимого множества $Q_x$ достаточно велико, т.е. $\rho(\mathbf{x}, \partial Q)\geqslant 2\sqrt{{\delta}/{L_f}}$, то верно следующее неравенство:
$$ \begin{equation*} \|\nu(\mathbf{x})-\nabla f(\mathbf{x})\|_2\leqslant 2\sqrt{{L_f\delta}}. \end{equation*} \notag $$

В таком случае для того, чтобы правильно определить оставшееся множество, достаточно выполнения неравенства (2.28) для $\widetilde{\delta}(\mathbf{x})=2\sqrt{{L_f\delta}}$, где $\delta$ – точность по функции решения вспомогательной подзадачи $y_{\widetilde{\delta}}$.

В данном случае получаем, что вспомогательную задачу по $y$ нужно решать с точностью по функции, удовлетворяющей условию

$$ \begin{equation} \delta \leqslant \frac{2}{L_{f}} \widetilde{\delta}^2. \end{equation} \tag{2.32} $$

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

Далее, рассмотрим вспомогательную внутреннюю задачу минимизации по многомерной переменной. Стратегия решения вспомогательной задачи минимизации по многомерной переменной описана в п. 2.2.3. Точнее говоря, для вспомогательных подзадач максимизации по $y$ большой размерности будем использовать следующие методы в зависимости от выделенного класса задач (условий на $h$ или $S$).

В таких случаях получаем следующие оценки достаточного для достижения $\varepsilon$-точного решения задачи (2.21) согласно определению 1 количества обращений к соответствующим вспомогательным подзадачам:

  • • в случае 1
    $$ \begin{equation*} \begin{gathered} \, O \biggl( 2^{n^2} \sqrt{\frac{L_{yy}}{\mu_y}} \log_2^{n+1} \biggl(\frac{CR}{\varepsilon}\biggr) \biggr) \quad\text{вычислений } \nabla_y F(x, y) \\ \text{и решений подзадачи } (2.7); \end{gathered} \end{equation*} \notag $$
  • • в случае 2
    $$ \begin{equation*} \begin{gathered} \, O \biggl( \sqrt{\frac{L_h}{\mu_y}} \log_2^{n+1}\biggl(\frac{CR}{\varepsilon}\biggr) \biggr) \quad\text{вычислений } \nabla h(y) \text{ и} \\ O \biggl( 2^{n^2} \biggl( \sqrt{\frac{L_h}{\mu_y}}+\sqrt{\frac{L_{yy}}{\mu_y}} \biggr) \log_2^{n+1}\biggl(\frac{CR}{\varepsilon}\biggr) \biggr) \quad\text{вычислений } \nabla_y F(x, y). \end{gathered} \end{equation*} \notag $$

Отметим, что условиями останова для решения вспомогательной задачи являются условия (2.31) и (2.32).

Также заметим, что в случае сепарабельной функции, как и в п. 2.2.3, можно гарантировать достижение $\varepsilon$-решения задачи (2.21) за $O \biggl( n \ln \dfrac{n}{\varepsilon} \biggr)$ вычислений $\nabla_x F$ и $O \biggl( mn \ln \dfrac{n}{\varepsilon} \ln \dfrac{m}{\varepsilon} \biggr)$ вычислений $S(x, y)$ при ослабленных условиях на гладкость.

§ 3. Результаты вычислительных экспериментов

3.1. Постановка задач, для которых проводится сравнение вычислительной эффективности предложенных методов

В качестве важного класса седловых задач можно выделить лагранжевы седловые задачи, связанные с задачами выпуклого программирования. Если у такой задачи два функционала ограничения и выполнено условие Слейтера, то двойственная задача максимизации двумерна и к ней вполне возможно применить метод многомерной дихотомии (двумерный случай) после локализации допустимой области значений двойственных переменных. Более того, полученные нами результаты теоретически обосновывают линейную скорость сходимости для случая гладкого сильно выпуклого функционала и выпуклого гладкого функционала ограничения. Похожее верно, если, например, применять метод эллипсоидов для двойственной задачи. Однако возможна ситуация, когда за счет отсутствия необходимости на итерациях находить точное значение градиента целевой функции метод Ю. Е. Нестерова (см. [16]) работает быстрее, причем даже в случае негладких функционалов ограничений max-типа.

Рассмотрим задачу вида

$$ \begin{equation} \max_\lambda \Bigl\{ \phi(\lambda)=\min_x F(x, \lambda)\Bigr\}. \end{equation} \tag{3.1} $$
Оптимальную точку $\lambda_*$ будем находить, используя метод многомерной дихотомии и решая на каждом шаге вспомогательную задачу минимизации по $x$ быстрым градиентным методом. Подробно об этом сказано в п. 2.3.1.

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

Во-первых, можно решить основную задачу при помощи метода эллипсоидов, а вспомогательную задачу – быстрым градиентным методом (см. п. 2.2, случай 2).

Во-вторых, можно решить поставленную задачу при помощи быстрого градиентного метода с $(\delta, L)$-оракулом (см. [18], [24], [25]), при этом решая вспомогательную задачу при помощи метода эллипсоидов (алгоритм 2).

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

Наконец, в четвертом способе применения методики не будет учитываться малая размерность одной из переменных, а будет использоваться вариант быстрого градиентного метода с $(\delta,L)$-оракулом (см. [18], [24], [25]) целевой функции для внешней задачи и обычный быстрый градиентный метод (БГМ) для внутренней подзадачи.

Стоит заметить, что в § 2 мы рассматривали сильно выпукло-вогнутые седловые задачи вида (1.1). Тем не менее сильная выпуклость оптимизационных подзадач небольшой размерности (к которым мы применяем методы секущей гиперплоскости или авторский вариант многомерной дихотомии) существенна лишь для вывода теоретических оценок сложности.

Практическая же реализация алгоритмов 2, 3 и 6 возможна и без предположения о сильной выпуклости. В проведенных нами экспериментах удается без этих предположений подобрать вспомогательные параметры указанных методов и без использования сильной выпуклости задачи (1.1) по переменным небольшой размерности (в нашем случае это двойственные переменные лагранжевых седловых задач) достигнуть желаемого качества приближенного решения. Этим объясняется корректность приведенных в п. 3.1 результатов экспериментов несмотря на то, что рассматриваемые задачи не сильно выпуклы (вогнуты) по одной из групп переменных (а только выпуклы или вогнуты).

3.2. Лагранжева седловая задача к задаче квадратичной оптимизации

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

$$ \begin{equation} \min_{\substack{x \in Q_r \subset \mathbb{R}^n \\ g^i(x) \leqslant 0, \, i=1,\dots,m}} \biggl\{ f(x) :=\frac{1}{2} \|Ax-b\|_2^2 \biggr\}, \end{equation} \tag{3.2} $$
где $A \in \mathbb{R}^{n \times n}$, $b \in \mathbb{R}^n$ и $Q_r=\{x\mid \|x\|_2 \leqslant r\}$ – евклидов шар, а каждое из ограничений $g^i(x)$ является линейным:
$$ \begin{equation*} g^i(x)={c^i}^\top x+d^i, \qquad c^i \in \mathbb{R}^n, \quad d^i \in \mathbb{R}. \end{equation*} \notag $$

В дальнейшем для возможности использования метода оптимизации на квадрате или треугольнике мы будем работать с двумя выпуклыми негладкими ограничениями $g_1$ и $g_2$, $\max$-агрегирующими исходные ограничения:

$$ \begin{equation*} \begin{gathered} \, g_1(x)=\max \biggl\{ g^i(x)\biggm| i=1, \dots, \biggl\lfloor\frac{m}{2}\biggr\rfloor \biggr\}, \\ g_2(x)=\max \biggl\{ g^i(x)\biggm| i=\biggl\lfloor\frac{m}{2}\biggr\rfloor+1, \dots, m\biggr\}. \end{gathered} \end{equation*} \notag $$

В такой постановке с двумя ограничениями исходная задача (3.2) будет иметь двойственную задачу вида

$$ \begin{equation*} \max_{\lambda_1+\lambda_2 \leqslant \Omega_\lambda} \Bigl\{ \varphi(\lambda_1, \lambda_2) := \min_{x \in Q_r} \bigl\{f(x)+\lambda_1 g_1(x)+\lambda_2 g_2(x) \bigr\} \Bigr\}, \end{equation*} \notag $$
где константа $\Omega_\lambda$ оценивается из условия Слейтера следующим образом:
$$ \begin{equation*} \Omega_\lambda=\frac{1}{\gamma} f(\widehat{x}), \end{equation*} \notag $$
где $\gamma=- \max\bigl\{g_1(\widehat{x}), g_2(\widehat{x})\bigr\} > 0$, а $\widehat{x}$ – внутренняя точка множества, задаваемого исходными ограничениями. Таким образом, вместе с условием неотрицательности двойственных переменных мы получаем, что множество, на котором решается двойственная задача, представляет собой прямоугольный треугольник с катетами длины $\Omega_\lambda$, лежащими на осях координат.

Пусть $A$ – разреженная матрица с долей ненулевых элементов $\sigma$, со случайными положительными диагональными элементами из равномерного распределения $A_{ii} \propto \mathcal{U}(0, 1.1)$ и ненулевыми недиагональными элементами также из равномерного распределения $A_{ij} \neq 0, A_{ij} \propto \mathcal{U}(0, 1)$; элементы вектора $b$ – независимые равномерно распределенные случайные величины $b_i \propto \mathcal{U}(0, 0.5)$; вектор $c^i$ и скаляр $d^i$, задающие $i$-е ограничение, также генерируются случайно из равномерного распределения $\mathcal{U}(0, 0.1)$.

Сравним скорости работы метода двумерной дихотомии (далее – метод оптимизации на квадрате), метода оптимизации на (равнобедренном прямоугольном) треугольнике (который аналогичен методу двумерной дихотомии) на множестве $Q=\bigl\{x \in \mathbb{R}_{++}^2 \mid x_1+x_2 \leqslant \Omega_\lambda\bigr\}$, метода эллипсоидов и быстрого градиентного метода (БГМ). Приведем здесь описание используемого далее варианта метода дихотомии на равнобедренном прямоугольном треугольнике. Каждая его итерация осуществляется в соответствии со следующими шагами.

В качестве критерия останова для всех сравниваемых в настоящем пункте методов будем использовать условие

$$ \begin{equation*} |\lambda_1 g_1(x_\delta(\lambda))+\lambda_2 g_2(x_\delta(\lambda))| < \varepsilon, \end{equation*} \notag $$
где $x_\delta(\lambda)$ – приближенное с точностью $\delta$ по функции решение вспомогательной задачи $\min_{x \in Q} \bigl\{f(x)+\lambda_1 g_1(x)+\lambda_2 g_2(x) \bigr\}$. Выполнение данного условия гарантирует достижение точности по функции решения исходной задачи
$$ \begin{equation*} f(x_\delta(\lambda))-\min_{\substack{x \in Q \\ g_1(x), g_2(x) \leqslant 0}} f(x) \leqslant \varepsilon+\delta. \end{equation*} \notag $$
При этом на каждой итерации метода двойственные множители положительны в силу выбранной области их локализации (треугольник в положительном ортанте), что исключает возможность преждевременного выполнения этого условия в точке 0.

Вспомогательная задача минимизации решается с помощью субградиентного метода (метода СубГМ); см. [26]. Число итераций субградиентного метода определяется экспериментально таким образом, чтобы в точке решения задачи достигалась точность по функции $\delta=0.005$ (при сравнении с решением, полученным на большом числе итераций метода), а также чтобы значения ограничений $g_1$ и $g_2$ в данных точках были неположительными. Для $n=400$ при $r=5$ и $\sigma=0.005$ оказалось достаточно $800$ итераций субградиентного метода, а для $n=1000$, $r=2$ и $\sigma=0.001$ достаточно $2500$ итераций.

Как можно видеть из табл. 2, где для различных значений $\varepsilon$ сравнивается работа методов для $n=400$ при значениях $m=10$, $m=20$, предложенный метод оптимизации на треугольнике достигает выполнения критерия останова, а значит, и заданной точности по функции за меньшее по сравнению с методом эллипсоидов число итераций и время работы.

Таблица 2.Сравнение работы методов при $n=400$

$\varepsilon$ $m$ Метод на треугольникеМетод эллипсоидов
ИтерацииВремя, мсИтерацииВремя, мс
0.51046878820
20481881170
0.1108810141300
2081020141390
0.0510121160161460
20141840182140
0.0110223170363530
20263260383770

Из табл. 3 сравнения методов для $n=1000$ и $m=10$ видно, что предложенный метод на треугольнике эффективнее метода эллипсоидов. При этом время работы метода оптимизации на треугольнике несколько меньше, чем время работы метода оптимизации на квадрате, что достигается благодаря локализации двойственных множителей на прямоугольном треугольнике и вследствие этого меньшей длине отрезков, на которых необходимо решать дополнительные одномерные оптимизационные задачи на первых итерациях методов. Кроме того, значительно больших в сравнении с прочими методами числа итераций и времени работы требует метод эллипсоидов для задачи с $m$ ограничениями (не агрегированными в два ограничения вида $\max$) ввиду увеличения размерности задачи и больших временных затрат на выполнение матрично-векторных операций. При этом, как видно из табл. 3, замена субградиентного метода (СyбГМ) на быстрый градиентный метод (БГМ) для вспомогательной многомерной подзадачи не меняет ситуацию.

Таблица 3.Сравнение работы методов при $n=1000$, $m=10$

$\varepsilon$Метод на квадратеМетод на треугольникеМетод эллипсоидов
ИтерацииВремя, сИтерацииВремя, сИтерацииВремя, с
$0.5$66.1065.4146.12
$0.1$128.92128.251612.7
$0.05$1812.61611.22423.8
$0.01$2425.32224.13032.5
$\varepsilon$Метод эллипсоидов ($m\,{=}\,10$, СубГМ)Метод эллипсоидов ($m\,{=}\,10$, БГМ)
ИтерацииВремя, сИтерацииВремя, с
$0.5$815.366.27
$0.1$2026.21017.6
$0.05$3238.73438.8
$0.01$4049.54050.2

Таблица 4.Работа быстрого градиентного метода при $n=1000$, $m=10$

$\varepsilon$ БГМ БГМ ($m=10$)
ИтерацииВремя, сИтерацииВремя, с
$0.5$1010.81212.3
$0.1$1620.61622.9
$0.05$2234.12234.8
$0.01$2836.93237.3

Сравним работу метода на треугольнике для решения внешней задачи с быстрым градиентным методом (БГМ) при двух $\max$-агрегированных ограничениях и при $m=10$ исходных ограничениях (табл. 4). В обоих вариантах быстрый градиентный метод требует для достижения одной и той же точности большего числа итераций и времени работы, чем метод на треугольнике.

3.3. Лагранжева седловая задача к задаче LogSumExp с линейными функционалами ограничений

Рассмотрим задачу LogSumExp с $\ell_2$-регуляризацией и линейными ограничениями

$$ \begin{equation*} \begin{gathered} \, \min_{x \in \mathbb{R}^m} \biggl\{\log_2 \biggl(1+\sum_{k=1}^m e^{\alpha x_k}\biggr)+ \frac{\mu_x}{2} \| x \|_2^2 \biggr\}, \\ Bx \leqslant c, \qquad B \in \mathbb{R}^{n \times m}, \qquad c \in \mathbb{R}^{n}, \qquad \alpha \in \mathbb{R}. \end{gathered} \end{equation*} \notag $$

Далее введем обозначение $\mathrm{LSE}(x)=\log_2\bigl(1+\sum_{k=1}me^{\alpha x_k}\bigr)$.

Лагранжиан этой задачи можно записать в следующей форме:

$$ \begin{equation*} r(x)+F(x, y)-h(y), \end{equation*} \notag $$
где
$$ \begin{equation*} r(x)=\frac{\mu_x}{2} \| x \|_2^2, \qquad F(x, y)=\log_2 \biggl(1+\sum_{k=1}^m e^{\alpha x_k}\biggr)+y^\top Bx, \qquad h(y)=y^\top c. \end{equation*} \notag $$
Тогда двойственная задача является выпукло-вогнутой седловой задачей
$$ \begin{equation} \max_{y \in \mathbb{R}_+^n} \min_{x \in \mathbb{R}^m} \bigl\{r(x)+F(x, y)-h(y)\bigr\}. \end{equation} \tag{3.3} $$

Заметим, что в приведенной постановке задачи функция $r(x)$ является проксимально-дружественной.

Согласно теореме 11 (см. п. 4.12) выполняется

$$ \begin{equation*} y_* \in Q_y=\biggl\{y \in \mathbb{R}_+^n\biggm| y_k \leqslant \frac{f(x_0)}{\gamma}\biggr\}, \end{equation*} \notag $$
где $x_0$ есть внутренняя точка полиэдра $Bx \leqslant c$, а $\gamma=\min_k\bigl\{c_k- [Bx]_k\bigr\} > 0$. Также легко видеть, что $x$ должно лежать внутри шара $Q_x=B_{R_x}(0)$ с центром в нуле и некоторым конечным радиусом $R_x$. Действительно, значение функции в нуле есть $s_0=S(0, y)=\log_2(m+1)-y^\top c$ для любого $y\in Q_y$ и можно найти такое $x$, что квадратичная часть по $x$ будет больше данного значения для любого $y \in Q_y$.

Обсудим параметры, связанные с константами Липшица градиентов рассматриваемых функций. Для функций $r$ и $h$ они очевидны:

$$ \begin{equation*} L_r=\mu_x, \qquad L_h=0. \end{equation*} \notag $$
Также очевидно, что для функции $F$
$$ \begin{equation*} L_{x y}=\|B\|_2 R_y, \qquad L_{y x}=\|B\|_2 R_x, \qquad L_{y y}=0. \end{equation*} \notag $$
Константа $L_{xx}$ (которую мы сейчас вычислим) есть сумма констант для задачи LogSumExp и линейной функции по $x$, которая есть нуль. Константа Липшица для градиента задачи LogSumExp есть максимальное собственное число ее гессиана, которое равно $\alpha$. Таким образом,
$$ \begin{equation*} L_{xx}=L_{\mathrm{LSE}}=\max_{x} \lambda_1 \nabla^2 \mathrm{LSE}(x)=\alpha, \end{equation*} \notag $$
где $\mathrm{LSE}(x)=\log_2 \bigl(1+\sum_{k=1}^m e^{\alpha x_k}\bigr)$.

Параметры $\alpha_k$ генерируются из равномерного распределения $\mathcal{U} (-\alpha_0, \alpha_0)$, $\alpha_0=0.001$. Элементы матрицы $B$ генерируются из равномерного распределения $\mathcal{U} (-k, k)$, $k=10^3$. Параметр $\mu_x$ равен $0.001$, элементы вектора $c$ равны 1.

Уточним использованное при проведении экспериментов условие останова сравниваемых методов. Заметим, что если $x_\delta(\lambda)$ есть решение с точностью $\delta$ по функции задачи

$$ \begin{equation*} \min_{x\in Q_x} \bigl\{ f(x)+\lambda^\top g(x) \bigr\} \end{equation*} \notag $$
и при этом выполняется дополнительное условие
$$ \begin{equation} |\lambda^\top g(x_\delta(\lambda))| \leqslant \varepsilon, \end{equation} \tag{3.4} $$
то $x_\delta(\lambda)$ – приближенное решение задачи минимизации $f$ с точностью $\delta+ \varepsilon$ по функции, т.е.
$$ \begin{equation*} f(x_\delta(\lambda))-\min_{x\in Q_x} f(x) \leqslant \delta+\varepsilon. \end{equation*} \notag $$
Действительно,
$$ \begin{equation*} \begin{aligned} \, f(x_\delta(\lambda))+\lambda^\top g(x_\delta(\lambda)) & \leqslant f(x(\lambda))+\lambda^\top g(x(\lambda))+\delta \\ & \leqslant \phi(\lambda_*)+\delta=f(x_*)+\lambda_*^\top g(x_*) +\delta=f(x_*). \end{aligned} \end{equation*} \notag $$
Последний переход совершен в силу условия Каруша–Куна–Таккера, утверждающего, что в точке $(\lambda_*, x(\lambda_*))$ должно быть выполнено условие дополняющей нежесткости $\lambda_i g_i(x)=0$ для любого $i$.

Итак, можно выбрать следующие условия останова:

$$ \begin{equation*} \begin{cases} |\lambda^\top g(x_{\delta}(\lambda))| \leqslant \dfrac{\varepsilon}{2}, \\ g_i(x) \leqslant 0\quad \forall\, i\colon \lambda_i=0. \end{cases} \end{equation*} \notag $$

Первое условие гарантирует точность $\varepsilon$ по функции $f$, как уже выше было указано. Второе условие добавлено в силу того, что при $\lambda_i=0$ величина несоответствия условию $g_i(x)$ может быть сколь угодно большой.

Применяя условие (3.4) для останова метода при решении задачи (3.3), сравним описанные выше методы. Кроме того, будет поставлено дополнительное ограничение на время выполнения метода. Если предел времени превышен до того, как выполнено условие останова, то выполнение метода прерывается и возвращается текущий результат. В наших задачах мы установили этот предел равным $100$ с. Прочерк в соответствующих таблицах означает, что данный метод не успел завершиться за выделенное время при данных параметрах.

Для расчетов был использован язык программирования Python версии 3.7.3 с устанавливаемой библиотекой numpy версии 1.18.3. Весь код выложен в репозиторий на платформе GitHub (см. [27]).

Результаты экспериментов для размерностей $n=2, 3, 4$ по двойственной переменной представлены в табл. 57. В этих таблицах указано время работы для случая, когда маломерная задача решается быстрым градиентным методом (БГМ) или маломерными методами (такими, как метод эллипсоидов с $\delta$-субградиентом или метод многомерной дихотомии, представленный в настоящей работе), а вспомогательная многомерная задача решается при помощи быстрого градиентного метода. Жирным шрифтом отмечено наилучшее (наименьшее) значение в строке (при заданных $\varepsilon$, $m$).

Таблица 5.Сравнение работы методов при $n=2$

$\varepsilon$ $m$ Время работы, c
БГММетод эллипсоидовМетод дихотомииМетод Вайды
$10^{-3}$$10^2$ 0.020.270.140.39
$10^3$ 0.030.530.270.56
$10^4$ 0.459.864.336.98
$10^{-6}$$10^2$3.480.45 0.220.50
$10^3$0.470.85 0.450.79
$10^4$ 0.6316.726.1611.10
$10^{-9}$$10^2$-0.79 0.670.71
$10^3$-1.45 1.121.24
$10^4$-26.23 16.0916.82

Таблица 6.Сравнение работы методов при $n=3$

$\varepsilon$ $m$ Время работы, c
БГММетод эллипсоидовМетод дихотомииМетод Вайды
$10^{-3}$$10^2$ 0.050.650.880.71
$10^3$ 0.031.301.560.91
$10^4$ 0.3622.0520.5210.92
$10^{-6}$$10^2$2.461.07- 0.79
$10^3$ 0.532.06-1.27
$10^4$ 0.6137.64-17.66
$10^{-9}$$10^2$-1.89- 1.17
$10^3$-3.63- 1.64
$10^4$-59.71- 25.41

Таблица 7.Сравнение работы методов при $n=4$

$\varepsilon$ $m$ Время работы, c
БГММетод эллипсоидовМетод дихотомииМетод Вайды
$10^{-3}$$10^2$ 0.061.087.060.9
$10^3$ 0.032.2212.241.38
$10^4$ 0.3740.37-16.06
$10^{-6}$$10^2$3.101.86- 1.15
$10^3$ 0.563.82-1.90
$10^4$ 0.67--25.03
$10^{-9}$$10^2$-3.42- 2.01
$10^3$-6.20- 2.83
$10^4$--- 33.12

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

Обсудим полученные результаты. Во-первых, для всех $n=2, 3, 4$ (табл. 5, 6 и 7 соответственно) видно, что при не очень высокой требуемой точности $\varepsilon\,{=}\, 10^{-3}$ быстрый градиентный метод показывает наилучший результат. Действительно, при данном значении точности он быстрее, как минимум, на порядок в сравнении с маломерными методами (методом эллипсоидов и методом дихотомии). С другой стороны, при повышении требуемой точности маломерные методы становятся быстрее градиентного метода. Так, например, для $n=2$ (см. табл. 5) мы видим, что для точности $\varepsilon=10^{-9}$ маломерные методы быстрее многомерных для всех размерностей исходной задачи $m$.

Во-вторых, заметим, что при $n=2$ предложенный метод многомерной дихотомии сходится быстрее, чем метод эллипсоидов и метод Вайды для всех $\varepsilon$ и $m$. Однако сложность этого метода очень быстро растет с размерностью (см. оценку сложности (2.25)), что проявляется и в экспериментах. Так, уже для $n=3$, т.е. при повышении размерности на $1$ он перестает быть эффективным по сравнению с другими методами. При $m>2$ и $\varepsilon=10^{-9}$ в большинстве тестов метод Вайды показывает себя лучше, чем остальные методы.

В-третьих, отметим характер зависимости времени работы от размерности прямой задачи $m$. Время работы при повышении $m$ и при фиксированных $n$ и $\varepsilon$ растет быстрее для маломерных методов, чем для многомерных. Следствием этого является то, что рассмотренные в работе методы маломерной минимизации работают эффективнее по сравнению с быстрым градиентным методом в наших экспериментах при $\varepsilon=10^{-6}$ только при малой размерности $m=100$.

3.4. Лагранжева седловая задача к задаче LogSumExp с линейными функционалами ограничений при аддитивно зашумленном градиенте

В условиях предыдущего примера из п. 3.3 рассмотрим аналогичную постановку задачи (3.3) и применим для ее решения метод эллипсоидов для внешней $\max$-задачи вместе с быстрым градиентным методом для внутренней $\min$-задачи при дополнительном условии, что получение градиента по переменной $y$ внешней задачи при вызове соответствующего оракула в алгоритме 2 происходит с некоторой аддитивной ошибкой. То есть если точное значение градиента функции под оператором $\min$ есть $\nabla_y f(y)$, то вместо него доступен вектор $v$ такой, что

$$ \begin{equation*} \|\nabla_y f(y)-v\|_2 \leqslant \Delta. \end{equation*} \notag $$
В соответствии с замечанием 3 $\Delta$-аддитивную неточность градиента можно учитывать как дополнительную $\delta$-неточность оракула двумя способами: равномерно, используя $\mu$-сильную выпуклость (имеющую место для рассматриваемой задачи), или же динамически, изменяя $\delta$ в зависимости от диаметра текущего эллипсоида, равного (в обозначениях алгоритма 2)
$$ \begin{equation*} \text{diam}_k=2 \cdot \lambda_{\max}^{1/2}(H_k), \end{equation*} \notag $$
где $\lambda_{\max}$ обозначает наибольшее собственное значение матрицы.

Другая неточность оракула в методе решения внешней задачи порождается приближенностью решения внутренней задачи, в данном случае быстрым градиентным методом. Пусть внутренний метод настроен на точность $\delta_{\text{БГМ}}$ и выполняет число итераций, достаточное для достижения этой точности в соответствии с теоретическими оценками.

Пусть метод решения внешней задачи, т.е. метод эллипсоида, работает до выполнения условия останова (3.4). Будем полагать целью метода достижение им в итоге $\varepsilon$-решения общей седловой задачи. Тогда, следуя рассуждениям из прошлого примера, необходимо настроить условие останова метода эллипсоидов на точность $\varepsilon-\delta_{\text{БГМ}}- \delta$, где $\delta_{\text{БГМ}}$ – точность для метода $\text{БГМ}$. Причем эта величина зависит от способа учета аддитивной неточности градиента так же, как и практическое время выполнения методом условия останова. Исследуем эту практическую зависимость.

На рис. 2 представлены графики значений левой части выражения из условия (3.4) и значений $\varepsilon\,{-}\,\delta_{\text{БГМ}}\,{-}\,\delta$ для двух способов учета неточности градиента для частного случая задачи при $n=3$, $m=10$, $\varepsilon=0.1$, $\delta=0.05$, $\Delta=0.001$, $\mu=0.0001$. Как можно видеть, на практике происходит уменьшение диаметра эллипсоидов, и при динамическом учете неточности градиента граница из условия останова увеличивается заметно в сравнении с ростом значений, достигаемых в генерируемых методом точках, что может позволить уменьшить число итераций и время работы метода до выполнения этого условия при сохранении гарантий на точность получаемого решения.

3.5. Задача проектирования точки на множество, определенное набором гладких ограничений

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

$$ \begin{equation*} \begin{gathered} \, \min_{x \in \mathbb{R}^n} \|x_0-x\|_2^2, \\ g_i(x) \leqslant 0, \qquad g_i\ \ L\text{-гладкая} \quad \forall\, i=1,\dots,m, \end{gathered} \end{equation*} \notag $$
лагранжевой седловой задачей к которой является следующая:
$$ \begin{equation*} \max_{\lambda \in \mathbb{R}_{+}^m} \min_{x \in \mathbb{R}^n} \biggl\{ \|x_0-x\|_2^2+ \sum_{i=1}^m \lambda_i g_i(x)\biggr\}. \end{equation*} \notag $$
Для случая малого числа ограничений $m$ в работе [8] был предложен эффективный подход, алгоритмическая сложность которого линейно зависит от размерности $n$, основанный на совместном применении метода эллипсоидов (или метода Вайды) и быстрого градиентного метода. Аналогичный подход, описанный в настоящей работе, имеет значимые отличия, с одной стороны, в требованиях к точности решения вспомогательной $\min$-задачи (которая в соответствии с предлагаемым анализом может быть выбрана равной $\varepsilon/2$, тогда как в подходе [8] она необходимо $\sim \varepsilon^4$) и, с другой стороны, в применяемом условии останова (3.4) (гарантирующее достижение заданной точности исходной прямой задачи, которое может оказаться выполненным прежде теоретически достаточного числа итераций, что дает существенное удобство для приложений).

Таблица 8.Сравнение работы методов для набора из $m=3$ квадратичных ограничений

$\varepsilon$Время работы, c
$n=200$$n=300$
Метод эллипсоидовМетод FPMМетод эллипсоидовМетод FPM
$10^{-1}$213215
$10^{-2}$3541270
$10^{-4}$1611929178
$10^{-5}$3017145271
$10^{-6}$3321047336

В табл. 8 указано время выполнения предлагаемого в настоящей статье подхода (алгоритм 2) и подхода работы [8] (алгоритм 4, Fast Projection Method – FPM) для случая $m=3$ ограничений вида

$$ \begin{equation*} g_i(x)=(x-x_i)^\top A_i (x-x_i)-r_i\leqslant 0, \end{equation*} \notag $$
где матрицы $A_i$ положительно определенны и генерируются случайно с элементами из $\mathcal{U}(0, 0.05)$, центральные точки $x_i$ имеют независимые случайные компоненты из $\mathcal{U}(-1, 1)$, значения $r_i$ равномерно и независимо случайно сгенерированы из $\mathcal{U}(0, 0.1)$. Проверка итоговой точности осуществляется в сравнении с решением, полученным одним из методов, настроенным на точность $\varepsilon=10^{-10}$ (как по прямой функции $\|x_0-x\|^2_2 \leqslant \|x_0-x^*\|^2_2+ \varepsilon$, так и по ограничениям $g_i(x) \leqslant \varepsilon$ для любого $i$). Как можно видеть, описанный в настоящей статье подход за счет используемого условия останова и уменьшенной трудоемкости вспомогательных задач на практике оказывается существенно более эффективным в смысле времени выполнения.

§ 4. Доказательства и используемые результаты

4.1. Доказательство леммы 1

Приведем доказательство из [17; с. 123, 124], где вместо сильной вогнутости $S$ по $y$ используется предположение о компактности $Q_y$.

Пусть $\nu \in \partial_x S(x, \widetilde{y})$. Для любого $x' \in Q_x$

$$ \begin{equation*} \widehat{g}(x')=\max_{y \in Q_y} S(x', y) \geqslant S(x', \widetilde{y}) \geqslant S(x, \widetilde{y})+ \langle \nu, x'-x \rangle \geqslant \widehat{g}(x)+\langle \nu, x'-x \rangle-\delta. \end{equation*} \notag $$
Таким образом, $\nu \in \partial_{\delta} \widehat{g}(x)$, что и требовалось доказать.

4.2. Доказательство теоремы 1

Заметим, что $(\delta,L)$-субградиент $\nabla_{\delta, L} g(x)$ в определении (2.5) соответствует $(2\delta,L)$-оракулу вида $(g(x)-\delta, \nabla_{\delta, L} g(x))$ в определении 1 из работы [18], т.е. выполнено неравенство

$$ \begin{equation*} 0 \leqslant g(y) -\bigl(g(x)-\delta+\langle \nabla_{\delta, L} g(x), y-x \rangle\bigr)\leqslant \frac{L}{2}\|y-x\|_2^2+2\delta. \end{equation*} \notag $$
В [18; п. 2.2] было показано, что если $\rho(x,\partial Q_x)\geqslant 2\sqrt{{\delta}/{L}}$, то для любого субградиента $\nabla g(x)$ верно следующее утверждение:
$$ \begin{equation*} \|\nabla_{\delta, L} g(x)-\nabla g(x)\|\leqslant 2\sqrt{\delta L}, \end{equation*} \notag $$
что и требовалось доказать.

4.3. Доказательство леммы 2

Из сильной вогнутости $S$ по $y$ следует, что для любого $x$ задача максимизации (2.3) имеет единственное решение, которое мы будем обозначать $y(x)$, а также что для любого $y \in Q_y$ выполняется неравенство

$$ \begin{equation*} S(x, y) \leqslant {\underbrace{S(x, y(x))}_{\widehat{g}(x)}}-\frac{\mu_y}{2} \|y-y(x) \|_2^2. \end{equation*} \notag $$
В частности, если $\widetilde{y}$ – это $\widetilde{\varepsilon}$-решение внутренней задачи (2.3), то
$$ \begin{equation} \|\widetilde{y}-y(x) \|_2^2 \leqslant \frac{2}{\mu_y} \widetilde{\varepsilon}. \end{equation} \tag{4.1} $$
Согласно теореме Демьянова–Данскина (см. [23], [28]) в любой точке $x \in Q_x$ функция $\widehat{g}$ дифференцируема и ее градиент равен
$$ \begin{equation} \nabla \widehat{g}(x)=\nabla_x S(x, y(x)). \end{equation} \tag{4.2} $$
Используя (2.6), (4.1) и (4.2), получим
$$ \begin{equation*} \|\nabla_x S (x, \widetilde{y})-\nabla \widehat{g}(x)\|_2 \leqslant L_{xy} \sqrt{\frac{2 \widetilde{\varepsilon}}{\mu_y}}, \end{equation*} \notag $$
что и требовалось доказать.

4.4. Доказательство леммы 3

1. Для любых $x,x' \in Q$, $\nabla g(x) \in \partial g(x)$ и $\delta_1$-неточного субградиента $\nu$ в точке $x$

$$ \begin{equation*} \begin{aligned} \, g(x') &\geqslant g(x)+\bigl\langle \nabla g(x), x'-x \bigr\rangle \\ & =g(x)+\bigl\langle \nu, x'-x \bigr\rangle+\bigl\langle \nabla g(x) -\nu, x'-x \bigr\rangle \\ & \geqslant g(x)+\bigl\langle \nu, x'-x \bigr\rangle-\delta_1 \operatorname{diam} Q. \end{aligned} \end{equation*} \notag $$
Таким образом, $\delta_1$-неточный градиент $\nu$ является $\delta_2$-субградиентом $g$ в точке $x$ с $\delta_2=\delta_1 \operatorname{diam} Q$.

2. Для любых $x,x' \in Q$, $\nabla g(x) \in \partial g(x)$ и $\delta_1$-неточного субградиента $\nu$ в точке $x$

$$ \begin{equation*} \begin{aligned} \, g(x') &\geqslant g(x)+\bigl\langle \nabla g(x), x'-x \bigr\rangle +\frac{\mu}{2}\|x'-x\|_2^2 \\ & =g(x)+\bigl\langle \nu, x'-x \bigr\rangle+\bigl\langle \nabla g(x) -\nu, x'-x \bigr\rangle +\frac{\mu}{2}\|x'-x\|_2^2 \\ & \geqslant g(x)+\bigl\langle \nu, x'-x \bigr\rangle-\delta_1 \|x'-x\|_2 +\frac{\mu}{2}\|x'-x\|_2^2. \end{aligned} \end{equation*} \notag $$
Учитывая, что
$$ \begin{equation*} \delta_1 \|x'-x\|_2 \leqslant \frac{\mu}{2}\|x'-x\|_2^2+ \frac{\delta_1^2}{2\mu}, \end{equation*} \notag $$
получим
$$ \begin{equation*} g(x') \geqslant g(x)+\langle \nu, x'-x \rangle- \frac{\delta_1^2}{2\mu}. \end{equation*} \notag $$
Таким образом, $\delta_1$-неточный градиент $\nu$ является $\delta_2$-субградиентом $g$ в точке $x$ с $\delta_2={\delta_1^2}/({2\mu})$.

4.5. Доказательство леммы 4

Если $\mathbf{x}_*$ есть внутренняя точка, то градиент по нефиксированным переменным равен нулю в силу того, что $\mathbf{x}_*$ – минимум. Тогда с учетом того, что $\nabla f(\mathbf{x}_*)\in\partial f(\mathbf{x}_*)$, получаем утверждение леммы.

Допустим, что $\mathbf{x}_*$ – граничная точка. Тогда множество условного субдифференциала на гиперкубе $Q$ определяется следующим образом:

$$ \begin{equation*} \partial_Q f(\mathbf{x})=\partial f(\mathbf{x})+N(\mathbf{x}\mid Q), \end{equation*} \notag $$
где $N(\mathbf{x}\mid Q)=\bigl\{\mathbf{a}\mid \langle\mathbf{a}, \mathbf{y}- \mathbf{x}\rangle\leqslant 0\ \forall\, \mathbf{y} \in Q\bigr\}$.

В случае дифференцируемой функции имеем

$$ \begin{equation*} \partial f(\mathbf{x}_*)=\{\nabla f(\mathbf{x}_*)\}. \end{equation*} \notag $$

Из того, что $\mathbf{x}_*$ есть граничная точка, следует, что существует непустой набор координат $\{x_j\}_j$ такой, что $x_j= \max_{\mathbf{y}\in Q_k}y_j$ или $x_j=\min_{\mathbf{y}\in Q_k}y_j$. Введем обозначения

$$ \begin{equation*} J_+=\Bigl\{j\in \mathbb{N}\Bigm| x_j=\max_{\mathbf{y}\in Q_k}y_j\Bigr\}, \qquad J_-=\Bigl\{j\in \mathbb{N}\Bigm| x_j=\min_{\mathbf{y}\in Q_k}y_j\Bigr\}. \end{equation*} \notag $$
В таком случае заметим, что любой вектор $a$ такой, что $a_j \geqslant 0$ для любого $j \in J_+$, $a_j \leqslant 0$ для любого $ j \in J_-$ и $a_j=0$ в противном случае, принадлежит нормальному конусу.

Также заметим, что $(\nabla f(\mathbf{x}_*))_j \leqslant 0$ для любого $ j \in J_+$, $(\nabla f(\mathbf{x}_*))_j\geqslant 0$ для любого $ j \in J_-$ и $(\nabla f(\mathbf{x}_*))_j=0$ в противном случае. Действительно, если $(\nabla f(\mathbf{x}_*))_j > 0$ для некоторого $j\in J_+$, то существует вектор $\mathbf{x}=\mathbf{x}_*+\alpha \mathbf{e}_k \in Q$ для некоторого $\alpha<0$ и вектора $e_k^j=\delta_{kj}$, где $\delta_{kj}=1$ для $k=j$ и $\delta_{kj}=0$ в противном случае. Причем значение функции в этой точке будет

$$ \begin{equation*} f(\mathbf{x})=f(\mathbf{x}_*)+\alpha (\nabla f(\mathbf{x}_*))_j+o(\alpha) < f(\mathbf{x}_*) \end{equation*} \notag $$
для достаточно малого $\alpha$, что противоречит тому, что $\mathbf{x}_*$ – решение.

Тогда, выбрав $\mathbf{a}$ такой, что $\mathbf{a}_\parallel=-\bigl(\nabla f(\mathbf{x}_*)\bigr)_\parallel$, получаем субградиент из условия

$$ \begin{equation*} \mathbf{g}=\nabla f(\mathbf{x}_*)+\mathbf{a}, \qquad \mathbf{g}_\parallel=0. \end{equation*} \notag $$

4.6. Доказательство теоремы 3

В нашем методе, как и в обычном методе эллипсоидов, на каждом шаге эллипсоид рассекается плоскостью, проходящей через его центр, а затем рассматривается эллипсоид наименьшего объема, содержащий одну из частей. Можно доказать (см., например, [20]), что на каждом шаге выполняется неравенство

$$ \begin{equation} \frac{\operatorname{vol} (\mathcal{E}_{k+1})}{\operatorname{vol}(\mathcal{E}_k)} \leqslant e^{-1/(2n)} \quad \Longrightarrow\quad \operatorname{vol}(\mathcal{E}_N) \leqslant e^{-N/(2n)} \operatorname{vol}(\mathcal{B}_{\mathcal{R}}). \end{equation} \tag{4.3} $$
Если $w_k=0$, то по определению $\delta$-субградиента
$$ \begin{equation*} g(x) \geqslant g(c_k)-\delta \quad \forall\, x \in Q_x \quad\Longrightarrow\quad g(c_k)-g(x_*) \leqslant \delta, \end{equation*} \notag $$
и условие теоремы выполнено. Далее, считаем, что вектор $w_k$ ненулевой. Если $c_k \in Q_x$, то в силу определения $\delta$-субградиента справедливо включение
$$ \begin{equation} (\mathcal{E}_k \setminus \mathcal{E}_{k+1}) \,{\cap}\, Q_x \subseteq \bigl\{ x \in Q_x \colon \langle w_k, x\,{-}\, c_k \rangle > 0\bigr\} \subseteq \bigl\{ x \in Q_x \colon g(x) > g(c_k)\,{-}\,\delta \bigr\}. \end{equation} \tag{4.4} $$
Для $\varepsilon \in [0,1] $ рассмотрим множество $Q_x^{\varepsilon} :=\{(1-\varepsilon)x_*+ \varepsilon x, x \in Q_x \}$. Заметим, что $Q_x^{\varepsilon} \subseteq \mathcal{E}_0$ и
$$ \begin{equation*} \operatorname{vol}(Q_x^{\varepsilon})=\varepsilon^n \operatorname{vol}(Q_x) \geqslant \varepsilon^n \operatorname{vol}(\mathcal{B}_{\rho})= \biggl(\frac{\varepsilon \rho}{\mathcal{R}} \biggr)^n \operatorname{vol}(\mathcal{B}_{\mathcal{R}}). \end{equation*} \notag $$
Для $\varepsilon > e^{-N/(2n^2)}\dfrac{\mathcal{R}}{\rho}$ получаем, что из (4.3) следует $\operatorname{vol}(Q_x^{\varepsilon}) > \operatorname{vol}(\mathcal{E}_N)$. Следовательно, найдутся шаг $j \in \{0, \dots, N-1 \}$ и значение $x_{\varepsilon} \in Q_x^{\varepsilon}$ такие, что $x_{\varepsilon} \in \mathcal{E}_j$ и $x_{\varepsilon} \notin \mathcal{E}_{j+1}$. Если бы при этом точка $c_j$ лежала вне $Q_x$, то мы бы отсекли часть эллипсоида $\mathcal{E}_j$, не пересекающуюся с $Q_x$, что привело бы к противоречию с $x_{\varepsilon} \in Q_x$. Значит, $c_j \in Q_x$. Тогда, воспользовавшись (4.4), получим $g(x_{\varepsilon}) > g(c_j)-\delta$. Поскольку найдется $x \in Q_x$ такое, что $x_{\varepsilon}=(1-\varepsilon)x_*+\varepsilon x$, то в силу выпуклости $g$ имеем
$$ \begin{equation*} g(x_{\varepsilon}) \leqslant (1-\varepsilon) g(x_*)+\varepsilon g(x) \leqslant (1-\varepsilon) g(x_*)+\varepsilon \bigl((g(x_*)+B \bigr)=g(x_*)+B\varepsilon. \end{equation*} \notag $$

Получаем, что

$$ \begin{equation} \begin{aligned} \, \notag & g(c_j) < g(x_*)+B\varepsilon+\delta\quad \forall\, \varepsilon > e^{-N/(2n^2)}\frac{\mathcal{R}}{\rho} \\ &\quad\Longrightarrow\quad g(c_j)-g(x_*) \leqslant e^{-N/(2n^2)}\frac{B\mathcal{R}}{\rho}+\delta, \end{aligned} \end{equation} \tag{4.5} $$
откуда следует (2.9). Если дополнительно $g$ является $\mu$-сильно выпуклой, т.е.
$$ \begin{equation*} g(x)-g(x')-\langle \nabla g(x'), x-x' \rangle \geqslant \frac{\mu}{2} \| x-x' \|_2^2 \quad \forall\, x, x' \in Q_x, \end{equation*} \notag $$
то, подставив $x=c_j$, $x'=x_*$ и использовав $\langle \nabla g(x_*), x-x_*' \rangle$ для любого $x \in Q_x$, получим
$$ \begin{equation*} g(c_j)-g(x_*) \geqslant \frac{\mu}{2} \| c_j-x_* \|_2^2. \end{equation*} \notag $$
Отсюда с учетом (4.5) получаем второе доказываемое утверждение (2.10).

4.7. Доказательство теоремы 6

Пусть мы решаем задачу вида

$$ \begin{equation} \min_x f(x). \end{equation} \tag{4.6} $$

Оценим сложность метода многомерной дихотомии (т.е. количество обращений к подпрограмме вычисления градиента $\nabla f$, достаточное для достижения $\varepsilon$-точного решения по функции).

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

$$ \begin{equation*} N=\biggl\lceil\log_2 \biggl(\frac{4R(M_f+2L_f R)}{L_f\varepsilon}\biggr)\biggr\rceil. \end{equation*} \notag $$

Пусть $T(n, R, \varepsilon)$ – количество вспомогательных задач минимизации соответствующей функции размерности $n-1$, которых достаточно для решения задачи в размерности $n$ на гиперкубе диаметра $R$ с точностью $\varepsilon$. Для $n=0$ положим $T(0, R, \varepsilon)$. Заметим, что одна итерация требует решения $n$ вспомогательных задач. С учетом этого получаем следующую рекуррентную формулу для основной задачи:

$$ \begin{equation*} T(n,R,\varepsilon)=\sum_{k=0}^{\lceil\log_2 ({M_f R}/{\varepsilon})\rceil}n T(n-1,R \cdot 2^{-k},\widetilde{\varepsilon}), \end{equation*} \notag $$
и аналогичное выражение уже с учетом всех необходимых вспомогательных подзадач
$$ \begin{equation*} T(n,R,\varepsilon)=\sum_{k=0}^{\lceil\log_2 ({C_1 R}/{\varepsilon})\rceil}n T(n-1,R\cdot 2^{-k}, \widetilde{\varepsilon}), \end{equation*} \notag $$
где $\widetilde{\varepsilon}$ определяется согласно (2.30), а
$$ \begin{equation*} C_1= \max\biggl(M_f, \frac{4(M_f +2L_f R)}{L_f}\biggr). \end{equation*} \notag $$
Пусть $C_\varepsilon={128 L_f^2}/{\mu_f}$. Докажем индукцией по $n$ следующую оценку:
$$ \begin{equation} T(n, R, \varepsilon) \leqslant 2^{({n^2+n})/{2}}\log^n_2 \biggl(\frac{CR}{\varepsilon}\biggr)+O\biggl(\log_2^n \biggl(\frac{C R}{\varepsilon}\biggr)\biggr), \quad \text{где }\ C=2\max(C_1, C_\varepsilon). \end{equation} \tag{4.7} $$
Во введенных выше обозначениях коэффициент 2 в выражении для $C$ позволяет избежать записи округления вверх в дальнейшем.

Базис индукции очевиден:

$$ \begin{equation*} T(1, R, \varepsilon)=\log_2\frac{C_1}{\varepsilon} \leqslant \log_2\biggl(\frac{CR}{\varepsilon}\biggr). \end{equation*} \notag $$

Пусть справедливо неравенство (4.7) для некоторой размерности $n$. Докажем, что (4.7) верно и для размерности $n+1$:

$$ \begin{equation*} \begin{aligned} \, T(n+1,R,\varepsilon) &=\sum_{k=0}^{\lceil \log_2({C_1 R}/{\varepsilon})\rceil}(n+1)T(n,R\cdot2^{-k}, \widetilde{\varepsilon}) \\ &\leqslant (n+1) \cdot 2^{(n^2+n)/2} \sum_{k=0}^{\lceil\log_2({C_1 R}/{\varepsilon})\rceil} \log^n_2 \biggl(\frac{CC_\varepsilon R^2}{2^{2k} \varepsilon^2}\biggr)+O\biggl(\log_2^n \biggl(\frac{C R}{\varepsilon}\biggr)\biggr). \end{aligned} \end{equation*} \notag $$
Оценим сумму:
$$ \begin{equation*} \begin{aligned} \, &\sum_{k=0}^{\lceil\log_2 ({C_1 R}/{\varepsilon})\rceil} \log^n_2 \biggl(\frac{CC_\varepsilon R^2}{2^{2k} \varepsilon^2}\biggr) \leqslant \sum_{k=0}^{\lceil\log_2 ({C R}/{\varepsilon})\rceil} \log^n_2 \biggl(\frac{C^2 R^2}{2^{2k} \varepsilon^2}\biggr) \\ &\qquad \leqslant 2^n \cdot \int_{0}^{\log_2 ({C R}/{\varepsilon})+1} \biggl(\log_2 \biggl(\frac{C R}{\varepsilon}\biggr)-k\biggr)^n dk+\log_2^n \biggl(\frac{C R}{\varepsilon}\biggr) \\ &\qquad=\frac{2^n}{n+1}\biggl(\log_2^{n+1} \biggl(\frac{C R}{\varepsilon}\biggr)+1\biggr) +\log_2^n \biggl(\frac{C R}{\varepsilon}\biggr). \end{aligned} \end{equation*} \notag $$
Поэтому верно неравенство
$$ \begin{equation*} T(n+1,R,\varepsilon) \leqslant 2^{((n+1)^2+(n+1))/{2}} \log_2^{n+1} \biggl(\frac{C R}{\varepsilon}\biggr)+O\biggl(\log_2^n \biggl(\frac{C R}{\varepsilon}\biggr)\biggr), \end{equation*} \notag $$
откуда получаем доказываемую оценку (4.7). Окончательно получаем, что для решения задачи (4.6) достаточно следующего числа вычислений неточного градиента $\nu(\mathbf{x})$:
$$ \begin{equation*} O\biggl(2^{n^2} \log_2^n \biggl(\frac{C R}{\varepsilon}\biggr)\biggr), \quad\text{где }\ C= \max\biggl(M_f,\frac{4(M_f+2L_fR)}{L_f}, \frac{128L_f^2}{\mu_f}\biggr). \end{equation*} \notag $$
При этом любую вспомогательную задачу для текущего уровня рекурсии мы решаем с точностью по аргументу (см. (2.27))
$$ \begin{equation*} \widetilde{\delta}=\frac{\Delta}{C_f}\geqslant 2^{-N}, \end{equation*} \notag $$
где $N$ определяется в утверждении теоремы 10.

4.8. Доказательство теоремы 7

В работе [16] было доказано, что если задан гиперкуб $Q$ с максимальным расстоянием между точками $R$ и требуется минимизировать на нем функцию с точностью $\varepsilon$, то для этого в методе достаточно решить вспомогательную задачу с точностью по аргументу

$$ \begin{equation*} \Delta \leqslant \frac{\varepsilon}{8L_f R}, \end{equation*} \notag $$
где $R$ – размер начального гиперкуба. Данная теорема доказана для размерности $n=2$ в работе [16], однако она легко обобщается на большие размерности. Если $f$ есть $\mu_f$-сильно выпуклая функция, то, используя записанное выше условие останова, получаем, что достаточно решить вспомогательную задачу со следующей точностью по функции:
$$ \begin{equation*} \widetilde{\varepsilon} \leqslant \frac{\mu_f \varepsilon^2}{128 L_f^2 R^2}. \end{equation*} \notag $$

4.9. Доказательство теоремы 8

Далее нам понадобится следующее очевидное соотношение:

$$ \begin{equation} \forall\, a,b\in\mathbb{R} \quad |a-b|\leqslant |b| \quad\Longrightarrow\quad ab \geqslant 0. \end{equation} \tag{4.8} $$

Заметим, что множество $Q_k$ на $k$-й итерации выбирается правильно, если знак производной в решении вспомогательной задачи по фиксированной переменной совпадает со знаком производной в приближении решения.

Пусть $\nu(\mathbf{x})=\nabla f(\mathbf{x})$. Из (4.8) следует, что для того, чтобы совпали знаки $\nu_{\perp Q_k}(\mathbf{x}_*)$ и $\nu_{\perp Q_k}(\mathbf{x})$, достаточно потребовать выполнения неравенства

$$ \begin{equation*} \bigl|\nu_{\perp Q_k}(\mathbf{x}_*)-\nu_{\perp Q_k}(\mathbf{x})\bigr| \leqslant |\nu_{\perp Q_k}(\mathbf{x})|, \end{equation*} \notag $$
где $\nu_{\perp Q_k}(\mathbf{x})$ – проекция вектора $\nu(\mathbf{x})$ на ортогональное дополнение к множеству, на котором решается вспомогательная задача.

Используя липшицевость градиента целевого функционала $f$, получаем утверждение теоремы.

4.10. Доказательство теоремы 9

Из леммы 4 имеем

$$ \begin{equation*} \mathbf{g} \in \partial_Q f(\mathbf{x}_*)\colon \mathbf{g}_\parallel=0. \end{equation*} \notag $$
Тогда по определению субградиента $f$ в точке $\mathbf{x}_*$
$$ \begin{equation*} f(\mathbf{x}^*)-f(\mathbf{x}_*) \geqslant \langle\mathbf{g}, \mathbf{x}^*-\mathbf{x}_*\rangle. \end{equation*} \notag $$
Используем неравенство Коши–Буняковского–Шварца и получим
$$ \begin{equation*} f(\mathbf{x}_*)-f(\mathbf{x}^*) \leqslant \|\mathbf{g}\|_2a\sqrt{n}. \end{equation*} \notag $$

С другой стороны, из условия Липшица $f$ для любой точки $\mathbf{x}$ из $\Delta$-окрестности точки $\mathbf{x}_*$ имеем

$$ \begin{equation*} \begin{gathered} \, f(\mathbf{x})-f(\mathbf{x}_*)\leqslant M_f \Delta, \\ f(\mathbf{x})-f(\mathbf{x}^*) \leqslant M_f \Delta +\|\mathbf{g}\|_2a\sqrt{n}=M_f \Delta+ |\nu_{\perp Q_k}(\mathbf{x}_*)|R. \end{gathered} \end{equation*} \notag $$
Ввиду липшицевости градиента $f$ имеем
$$ \begin{equation*} f(\mathbf{x})-f(\mathbf{x}^*) \leqslant M_f\Delta+\bigl(|\nu_{\perp Q_k}(\mathbf{x})|+L_f\Delta\bigr)R. \end{equation*} \notag $$

Пусть после шагов 11–15 алгоритма 6 осталось множество с диаметром $\Delta$ во вспомогательной задаче. Тогда для достижения точности $\varepsilon$ по функции в исходной задаче в некоторой точке $\mathbf{x}$ из этого множества достаточно следующего условия:

$$ \begin{equation*} \begin{gathered} \, M_f\Delta +\|\mathbf{g}\|_2a\sqrt{n}=M_f\Delta+\bigl(|f_\perp'(\mathbf{x})|+L_f\Delta\bigr)R \leqslant \varepsilon, \\ \Delta(M_f+L_f R) \leqslant \varepsilon-|f_\perp'(\mathbf{x})|R. \end{gathered} \end{equation*} \notag $$

Окончательно получаем

$$ \begin{equation*} \Delta \leqslant \frac{\varepsilon-R |f_\perp'(\mathbf{x})|}{M_f+L_f R}. \end{equation*} \notag $$

4.11. Доказательство теоремы 10

Объединяя оценки из теорем 8 и 9, получаем, что для того, чтобы достигнуть точность $\varepsilon$ по функции при решении задачи минимизации на гиперкубе $Q$, каждую вспомогательную задачу нужно решать до тех пор, пока не будет выполнено следующее условие на расстояние от приближенного решения до истинного решения этой задачи:

$$ \begin{equation} \Delta \leqslant \max\biggl\{ \frac{|\nu_{\perp Q_k}(\mathbf{x})|}{L_f}, \frac{\varepsilon-R |\nu_{\perp Q_k}(\mathbf{x})|}{M_f+L_f R} \biggr\}. \end{equation} \tag{4.9} $$

Это условие верно для $\nu(\mathbf{x})=\nabla f(\mathbf{x})$. Пусть $\nu(\mathbf{x})$ есть такой вектор, что

$$ \begin{equation*} \|\nabla f(\mathbf{x})-\nu(\mathbf{x})\|_2 \leqslant \widetilde{\delta}(\mathbf{x}). \end{equation*} \notag $$
В таком случае очевидно, что условие (4.9) будет выполнено, если
$$ \begin{equation*} C_f\widetilde{\delta}(\mathbf{x})+\Delta \leqslant \max\biggl\{ \frac{|\nu_{\perp Q_k}(\mathbf{x})|}{L_f}, \frac{\varepsilon-R |\nu_{\perp Q_k}(\mathbf{x})|}{M_f+L_f R} \biggr\}, \end{equation*} \notag $$
где
$$ \begin{equation*} C_f=\max\biggl(\frac{1}{L_f}, \frac{R}{M_f+L_f R}\biggr). \end{equation*} \notag $$

Оценим необходимое число итераций. Если решать вспомогательную задачу текущего уровня рекурсии с точностью $\widetilde{\delta}=\dfrac{1}{C_f}\Delta,$ то получаем следующее условие:

$$ \begin{equation*} \Delta \leqslant \frac{1}{2}\max\biggl\{ \frac{|\nu_{\perp Q_k}(\mathbf{x})|}{L_f}, \frac{\varepsilon-R |\nu_{\perp Q_k}(\mathbf{x})|}{M_f+L_f R} \biggr\}. \end{equation*} \notag $$

Пусть модуль ортогональной компоненты приближения градиента $|\nu_{\perp Q_k}(\mathbf{x}_*)|$ равен $q$. Обозначим ее приближение с точностью $\Delta$ по аргументу $\mathbf{x}_\Delta$.

После $N$ итераций метода многомерной дихотомии для вспомогательной задачи, используя липшицевость градиента с константой $L_f$, можем получить следующую оценку градиента в точке $\mathbf{x}_\Delta$:

$$ \begin{equation*} q-2L_f R\cdot 2^{-N} \leqslant |\nu_{\perp Q_k}(\mathbf{x})|\leqslant q+2L_f R\cdot 2^{-N}. \end{equation*} \notag $$
В этом неравенстве учитывалось, что размер множества уменьшится в $2^{N}$ раз после $N$ итераций дихотомии, т.е. $\Delta\leqslant 2^{-N}R$ после $N$ итераций.

Значит, для выполнения условия $\Delta \leqslant \dfrac{1}{2} \dfrac{|\nu_{\perp Q_k}(\mathbf{x})|}{L_f}$ достаточно выполнения следующего условия:

$$ \begin{equation*} R\cdot 2^{-N} \leqslant \frac{q-2L_f R\cdot 2^{-N}}{2L_f }. \end{equation*} \notag $$
Для второго неравенства $\Delta \leqslant \dfrac{1}{2} \dfrac{\varepsilon-R |\nu_{\perp Q_k}(\mathbf{x})|}{M_f+L_f R}$ получаем аналогичное условие
$$ \begin{equation*} R\cdot 2^{-N} \leqslant \frac{1}{2}\frac{\varepsilon-qR}{M_f+L_f R}-R\cdot 2^{-N}. \end{equation*} \notag $$
Тогда получаем следующую оценку на $N$:
$$ \begin{equation*} R\cdot 2^{-N} \leqslant \frac{1}{4}\min_{q\geqslant 0}\max\biggl(\frac{q}{L_f}, \frac{\varepsilon-q R}{M_f+L_f R}\biggr)=\frac{1}{4}\frac{L_f}{M_f+2L_f R}\cdot\varepsilon. \end{equation*} \notag $$

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

$$ \begin{equation*} N=\biggl\lceil\log_2 \biggl(\frac{4R(M_f+2L_f R)}{L_f\varepsilon}\biggr)\biggr\rceil. \end{equation*} \notag $$

4.12. Формулировки некоторых известных используемых результатов

Теорема 11 (см. [22; упражнение 4.1]). Рассмотрим задачу

$$ \begin{equation*} \min_{x\in\mathbb{R}^m} f(x) \quad \textit{при }\ g(x)\leqslant 0, \quad g \colon \mathbb{R}^m \to \mathbb{R}^n, \end{equation*} \notag $$
где $f$ и $g_i$ – выпуклые функции. Лагранжиан этой задачи имеет вид
$$ \begin{equation*} \phi(y)=\min_x \bigl\{f(x)+y^\top g(x)\bigr\}. \end{equation*} \notag $$
Пусть $x_0$ есть такая точка, что $g(x_0) < 0.$ Тогда для решения $y_*$ задачи $\max_y \phi(y)$ верно следующее неравенство:
$$ \begin{equation*} \|y_*\|_2 \leqslant \frac{1}{\gamma}\bigl(f(x_0)-\min_x f(x)\bigr), \end{equation*} \notag $$
где $\gamma=\min_k \{-g_k(x_0)\}$.

§ 5. Заключение

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

$$ \begin{equation} \min_{x \in Q_{x}}\max_{y \in Q_y} \bigl\{ S(x, y) :=r(x)+F(x, y)-h(y) \bigr\} \end{equation} \tag{5.1} $$
в случае, когда одна из групп переменных ($x$ или $y$) имеет большую размерность, а другая – малую (несколько десятков).

Первые два предлагаемых подхода к такого типа задачам основаны на использовании для подзадачи выпуклой минимизации (вогнутой максимизации) для группы переменных малой размерности методов секущей гиперплоскости (метод эллипсоидов или метод Вайды). Мы приводим оба варианта как с методом эллипсоидов, так и с методом Вайды, поскольку каждый из них имеет свои преимущества: метод Вайды приводит к лучшей оценке числа итераций, а метод эллипсоидов – к меньшей сложности итераций. При этом в случае внешней подзадачи небольшой размерности важно использовать эти методы уже в авторском варианте с заменой обычного субградиента на $\delta$-субградиент (отметим, что тут можно использовать и $\delta$-неточный субградиент, причем оценки сложности асимптотически при $\varepsilon \to 0$ будут теми же). Вспомогательные подзадачи оптимизации по группе переменных большой размерности при этом предлагалось решать с помощью ускоренных градиентных методов. Такая схема позволила вывести приемлемые оценки сложности, зависящие как от обусловленности целевой функции, так и от размерности пространства (см. теорему 2 и п. 2.2.3).

Заметим, что первый подход (малая размерность $x$) можно применить и в случае малой размерности $y$, записав аналог задачи (5.1) следующим образом:

$$ \begin{equation} \min_{y \in Q_{y}}\max_{x \in Q_{x}} \bigl\{h(y)-F(x,y)-r(x) \bigr\}. \end{equation} \tag{5.2} $$

Напомним, что функция $r$ предполагается проксимально-дружественной, что означает возможность в явном виде решить подзадачу

$$ \begin{equation} \min_{x \in Q_{x}}\bigl\{\langle c_{1}, x\rangle+r(x)+ c_{2}\|x\|_{2}^{2}\bigr\}, \qquad c_1 \in Q_x, \quad c_2 > 0. \end{equation} \tag{5.3} $$
В табл. 9 указано количество операций, необходимых для того, чтобы решить задачу (5.2) с точностью $\varepsilon$ по $y$ (подход 1) или решить аналогичную задачу (5.1) с точностью $\varepsilon$ по $x$ (подход 2).

Таблица 9.Сравнение числа различных операций для подходов 1 и 2

Подход 1Подход 2Операция
$O \Bigl( m \ln \dfrac{m}{\varepsilon} \Bigr)$$O \biggl( m \sqrt{\dfrac{L_{xx}}{\mu_x}+\dfrac{2L_{xy}^2}{\mu_x\mu_y}} \ln \dfrac{m}{\varepsilon} \ln \dfrac{1}{\varepsilon} \biggr)$вычислений $\nabla_y F$, $\nabla h$
$O \biggl( m \sqrt{\dfrac{L_{xx}}{\mu_x}} \ln \dfrac{m}{\varepsilon} \ln \dfrac{1}{\varepsilon} \biggr)$$O \biggl( \sqrt{\dfrac{L_{xx}}{\mu_x}+\dfrac{2L_{xy}^2}{\mu_x\mu_y}} \ln \dfrac{1}{\varepsilon} \biggr)$$\begin{gathered} \text{вычислений }\nabla_x F \\ \text{и решений задачи }(5.3)\end{gathered}$

Согласно табл. 9 в большинстве случаев второй подход проигрывает первому. Тем не менее если

$$ \begin{equation*} m \ln m \gg \sqrt{\frac{L_{xx}}{\mu_x}+\frac{2L_{xy}^2}{\mu_x\mu_y}} \end{equation*} \notag $$
и вычисление $\nabla_x F$ и решение задачи (5.3) является трудоемким, то второй подход может оказаться эффективнее.

Помимо методов секущей гиперплоскости с неточным $\delta$-субградиентом в настоящей работе предложен также некоторый аналог метода дихотомии для решения маломерных задач выпуклой оптимизации с использованием неточных градиентов на итерациях. Этот метод назван методом многомерной дихотомии. По сути он есть обобщение обычной (одномерной) дихотомии на задачи минимизации функций $n$ переменных. Оказалось, что для задач очень малой размерности использование указанного подхода вполне оправдано. Были представлены условия для решения вспомогательной задачи и доказана сходимость метода при выполнении этих условий на каждом шаге. Кроме того, была получена оценка на достаточное количество итераций для достижения искомой точности по функции (теорема 6). Данная оценка зависит от размерности пространства (эта зависимость сопоставима с $O(2^{n^2})$), а также от требуемой точности решения (эта зависимость имеет вид $O(\log_2^n (1/\varepsilon))$). Полученный результат выглядит значительно хуже, чем описанные оценки для метода эллипсоидов с $\delta$-субградиентом. Однако проведенные численные эксперименты показали, что предложенный метод многомерной дихотомии может работать эффективнее метода эллипсоидов при $n=2$, что соответствует случаю двух ограничений в прямой задаче.

В ходе экспериментов была сопоставлена работа метода дихотомии, быстрого градиентного метода с $(\delta, L)$-оракулом, а также метода эллипсоидов или метода Вайды с использованием $\delta$-субградиентов для седловых задач с малой размерностью по одной из переменных. Точнее говоря, выполнены эксперименты на двойственной задаче для задачи LogSumExp минимизации функции с $\ell_2$-регуляризацией в размерности $m$ и с $n$ линейными ограничениями. В ходе этих экспериментов было установлено следующее.

Во-первых, маломерные методы быстрее быстрого градиентного метода при высокой требуемой точности. В наших условиях таковой точностью является $\varepsilon=10^{-9}$.

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

В-третьих, было установлено, что время работы быстрого градиентного метода для данной задачи увеличивается не так существенно при увеличении $m$, как для метода эллипсоидов или многомерной дихотомии.

Кроме того, была сопоставлена работа метода многомерной дихотомии, рассматриваемых в работе методов секущей гиперплоскости (методы эллипсоидов и Вайды), а также быстрого градиентного метода для задачи минимизации квадратичной функции (для $n=400$ и $n=1000$) с двумя негладкими ограничениями, $\max$-агрегирующими несколько ($m=10, 20$) линейных ограничений. Для данной задачи время работы метода дихотомии и его вариантов (метод на треугольнике) оказалось меньше времени работы метода эллипсоидов (как для всех исходных, так и для агрегированных ограничений) и быстрого градиентного метода. Было произведено сравнение способов учета неточностей, возникающих при наличии аддитивного шума в значениях градиента, для случая применения к задаче малой размерности метода эллипсоидов. При значении неточности, изменяющемся вместе с диаметром текущего эллипсоида, применяемый метод достигает выполнения условия останова быстрее, чем при постоянной оценке неточности. Сравнение работы методов было произведено также для задачи проектирования точки на множество, заданное набором гладких функционалов ограничений (см. [8]). Предлагаемый нами подход применения метода эллипсоидов для подзадач небольшой размерности при использовании предложенного условия останова оказывается эффективнее по сравнению с алгоритмом, предложенным в работе [8] для аналогичной постановки задачи. В рамках поставленных численных экспериментов рассматривались постановки задач, для которых задача малой размерности (в данном случае по двойственным переменным лагранжевой седловой задачи) не является сильно выпуклой (вогнутой). Несмотря на то, что теоретический анализ оценок скорости методов в настоящей статье приводится для случая сильно выпукло-вогнутых задач, правильная настройка методов на практике позволяет с тем же успехом применять предложенные схемы и для просто выпуклых (или вогнутых) маломерных подзадач с обеспечением достижения желаемого качества решения задачи. Это объясняется отсутствием необходимости требовать сильную выпуклость (вогнутость) целевой функции (она важна лишь для теоретических оценок) для реализации всех применяемых в работе к подзадачам небольшой размерности методов.

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

1. М. С. Алкуса, А. В. Гасников, Д. М. Двинских, Д. А. Ковалев, Ф. С. Стонякин, “Ускоренные методы для седловых задач”, Ж. вычисл. матем. и матем. физ., 60:11 (2020), 1843–1866  mathnet  crossref  mathscinet  zmath; англ. пер.: M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev, F. S. Stonyakin, “Accelerated methods for saddle-point problem”, Comput. Math. Math. Phys., 60:11 (2020), 1787–1809  crossref  adsnasa
2. W. Azizian, I. Mitliagkas, S. Lacoste-Julien, G. Gidel, “A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games”, Proceedings of the twenty third international conference on artificial intelligence and statistics, Proceedings of Machine Learning Research (PMLR), 108, 2020, 2863–2873 https://proceedings.mlr.press/v108/azizian20b.html
3. А. В. Гасников, П. Е. Двуреченский, Ю. Е. Нестеров, “Стохастические градиентные методы с неточным оракулом”, Труды МФТИ, 8:1 (2016), 41–91
4. А. В. Гасников, Д. М. Двинских, П. Е. Двуреченский, Д. И. Камзолов, В. В. Матюхин, Д. А. Пасечнюк, Н. К. Тупица, А. В. Чернов, “Ускоренный метаалгоритм для задач выпуклой оптимизации”, Ж. вычисл. матем. и матем. физ., 61:1 (2021), 20–31  mathnet  crossref  crossref  mathscinet  zmath  adsnasa
5. Le Thi Khanh Hien, Renbo Zhao, W. B. Haskell, An inexact primal-dual framework for large-scale non-bilinear saddle point problem, arXiv: 1711.03669
6. Guanghui Lan, First-order and stochastic optimization methods for machine learning, Springer Ser. Data Sci., Springer, Cham, 2020, xiii+582 pp.  crossref  mathscinet  zmath
7. Tianyi Lin, Chi Jin, M. I. Jordan, “Near-optimal algorithms for minimax optimization”, Proceedings of thirty third conference on learning theory, Proceedings of Machine Learning Research (PMLR), 125, 2020, 2738–2779 https://proceedings.mlr.press/v125/lin20a.html
8. I. Usmanova, M. Kamgarpour, A. Krause, K. Levy, “Fast projection onto convex smooth constraints”, Proceedings of the 38th international conference on machine learning, Proceedings of Machine Learning Research (PMLR), 139, 2021, 10476–10486 http://proceedings.mlr.press/v139/usmanova21a.html
9. А. В. Гасников, Современные численные методы оптимизации. Метод универсального градиентного спуска, 2-е испр. изд., МЦНМО, М., 2021, 272 с.
10. B. Cox, A. Juditsky, A. Nemirovski, “Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators”, J. Optim. Theory Appl., 172:2 (2017), 402–435  crossref  mathscinet  zmath
11. Yu. Nesterov, “Excessive gap technique in nonsmooth convex minimization”, SIAM J. Optim., 16:1 (2005), 235–249  crossref  mathscinet  zmath
12. Junyu Zhang, Mingyi Hong, Shuzhong Zhang, “On lower iteration complexity bounds for the convex concave saddle point problems”, Math. Program., 194:1-2, Ser. A (2022), 901–935  crossref  mathscinet  zmath
13. Yuanhao Wang, Jian Li, “Improved algorithms for convex-concave minimax optimization”, NIPS 2020, Adv. Neural Inf. Process. Syst., 33, MIT Press, Cambridge, MA, 2020, 11 pp. http://proceedings.neurips.cc/paper/2020; arXiv: 2006.06359
14. A. Nemirovski, S. Onn, U. G. Rothblum, “Accuracy certificates for computational problems with convex structure”, Math. Oper. Res., 35:1 (2010), 52–78  crossref  mathscinet  zmath
15. A. Nemirovski, Information-based complexity of convex programming, Lecture notes, 1995, 268 pp. https://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf
16. Д. А. Пасечнюк, Ф. С. Стонякин, “Об одном методе минимизации выпуклой липшицевой функции двух переменных на квадрате”, Компьютерные исследования и моделирование, 11:3 (2019), 379–395  mathnet  crossref
17. Б. Т. Поляк, Введение в оптимизацию, Наука, М., 1983, 384 с.  mathscinet  zmath; англ. пер.: B. T. Polyak, Introduction to optimization, Transl. Ser. Math. Eng., Optimization Software, Inc., Publications Division, New York, 1987, xxvii+438 с.  mathscinet
18. O. Devolder, F. Glineur, Yu. Nesterov, “First-order methods of smooth convex optimization with inexact oracle”, Math. Program., 146:1-2, Ser. A (2014), 37–75  crossref  mathscinet  zmath
19. P. M. Vaidya, “A new algorithm for minimizing convex functions over convex sets”, Math. Program., 73:3, Ser. A (1996), 291–341  crossref  mathscinet  zmath
20. S. Bubeck, “Convex optimization: algorithms and complexity”, Found. Trends Mach. Learn., 8:3-4 (2015), 231–357  zmath
21. E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov, M. Alkousa, “Solving smooth min-min and min-max problems by mixed oracle algorithms”, MOTOR 2021: Mathematical optimization theory and operations research–recent trends, Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 19–40  crossref  mathscinet
22. А. В. Гасников, Ю. Е. Нестеров, “Универсальный метод для задач стохастической композитной оптимизации”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 52–69  mathnet  crossref  zmath; англ. пер.: A. V. Gasnikov, Yu. E. Nesterov, “Universal method for stochastic composite optimization problems”, Comput. Math. Math. Phys., 58:1 (2018), 48–64  crossref  mathscinet  adsnasa
23. J. M. Danskin, “The theory of Max-Min, with applications”, SIAM J. Appl. Math., 14:4 (1966), 641–664  crossref  mathscinet  zmath
24. O. Devolder, Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, PhD thesis, UCL, CORE, Louvain-la-Neuve, 2013, vii+309 pp. https://dial.uclouvain.be/pr/boreal/en/object/boreal
25. O. Devolder, F. Glineur, Yu. Nesterov, First-order methods with inexact oracle: the strongly convex case, CORE Discussion Papers, no. 2013/16, 2013, 35 pp. http://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2013_16web.pdf
26. Н. З. Шор, Методы минимизации недифференцируемых функций и их приложения, Наукова думка, Киев, 1979, 199 с.  mathscinet  zmath; англ. пер.: N. Z. Shor, Minimization methods for non-differentiable functions, Springer Ser. Comput. Math., 3, Springer-Verlag, Berlin, 1985, viii+162 с.  crossref  mathscinet  zmath
27. Исходный код экспериментов на GitHub https://github.com/ASEDOS999/SPP
28. P. Bernhard, A. Rapaport, “On a theorem of Danskin with an application to a theorem of von Neumann–Sion”, Nonlinear Anal., 24:8 (1995), 1163–1181  crossref  mathscinet  zmath

Образец цитирования: М. С. Алкуса, А. В. Гасников, Е. Л. Гладин, И. А. Курузов, Д. А. Пасечнюк, Ф. С. Стонякин, “Решение сильно выпукло-вогнутых композитных седловых задач с небольшой размерностью одной из групп переменных”, Матем. сб., 214:3 (2023), 3–53; M. S. Alkousa, A. V. Gasnikov, E. L. Gladin, I. A. Kuruzov, D. A. Pasechnyuk, F. S. Stonyakin, “Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable”, Sb. Math., 214:3 (2023), 285–333
Цитирование в формате AMSBIB
\RBibitem{AlkGasGla23}
\by М.~С.~Алкуса, А.~В.~Гасников, Е.~Л.~Гладин, И.~А.~Курузов, Д.~А.~Пасечнюк, Ф.~С.~Стонякин
\paper Решение сильно выпукло-вогнутых композитных седловых задач с небольшой размерностью одной из групп переменных
\jour Матем. сб.
\yr 2023
\vol 214
\issue 3
\pages 3--53
\mathnet{http://mi.mathnet.ru/sm9700}
\crossref{https://doi.org/10.4213/sm9700}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4643620}
\zmath{https://zbmath.org/?q=an:1522.90256}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2023SbMat.214..285A}
\transl
\by M.~S.~Alkousa, A.~V.~Gasnikov, E.~L.~Gladin, I.~A.~Kuruzov, D.~A.~Pasechnyuk, F.~S.~Stonyakin
\paper Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable
\jour Sb. Math.
\yr 2023
\vol 214
\issue 3
\pages 285--333
\crossref{https://doi.org/10.4213/sm9700e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001075677500001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85172707492}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm9700
  • https://doi.org/10.4213/sm9700
  • https://www.mathnet.ru/rus/sm/v214/i3/p3
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024