| Математический сборник |
|
|
|
|
|
Решение сильно выпукло-вогнутых композитных седловых задач с небольшой размерностью одной из групп переменных М. С. Алкусаa, А. В. Гасниковabcd, Е. Л. Гладинe, И. А. Курузовa, Д. А. Пасечнюкa, Ф. С. Стонякинaf a Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл. b Исследовательский центр доверенного искусственного интеллекта, Институт системного программирования им. В. П. Иванникова Российской академии наук, г. Москва c Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, г. Москва d Кавказский математический центр, Адыгейский государственный университет, г. Майкоп e Humboldt-Universität, Berlin, Germany f Крымский федеральный университет имени В. И. Вернадского, г. Симферополь
Англоязычная версия:
Sbornik: Mathematics, 2023, Volume 214, Issue 3, Pages DOI: https://doi.org/10.4213/sm9700e 
Реферативные базы данных:
    § 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)
Отметим, что седловую задачу можно сводить и к вариационному неравенству (далее – ВН) с монотонным оператором. Напомним, что оператор $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, 6–9 и леммы 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)), если Замечание 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) как композицию внутренней задачи максимизации и внешней задачи минимизации Итерационный метод для внешней задачи (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)$ верно неравенство На базе леммы 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$ условию Лемма 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$ и выполняется неравенство Таким образом, для отыскания $\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$ имеет вид где $\mu_y$-сильно выпуклая функция $h$ непрерывна, выпукло-вогнутая функция $F$ дифференцируема по $y$ и удовлетворяет для некоторого $L_{yy} \geqslant 0$ условию Пусть также выполнено одно из условий: Теорема 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$-субградиентовРассмотрим задачу вида где $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), удовлетворяет неравенству Следствие 1. Если дополнительно к условиям теоремы 3 допустить, что $g$ $\mu_x$-сильно выпукла, то точка выхода $x^N$ алгоритма 2 удовлетворяет неравенству где $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]). После Следствие 2. Если к условиям теоремы 4 добавить $\mu_x$-сильную выпуклость $g$, то точка выхода $x^N$ алгоритма 3 удовлетворяет неравенству где $x_*$ – точка минимума $g$. Замечание 4 (учет неточной информации о значении целевой функции). Как метод эллипсоидов, так и метод Вайды используют значения целевой функции при определении выходов алгоритмов ($x^N$). Однако по смыслу рассматриваемой в настоящей статье постановки седловой задачи естественна ситуация, когда значение целевой функции вспомогательной подзадачи доступно лишь с некоторой точностью $\widetilde{\delta}$. В таком случае выписанные оценки качества выдаваемых методами приближенных решений (2.9) и (2.16) необходимо уточнить, добавив в правые части неравенств слагаемые $\widetilde{\delta}$. Действительно, если функция $g_{\widetilde{\delta}}$ отличается от $g$ не больше, чем на $\widetilde{\delta}$, то для верно неравенство $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$ будет равно Замечание 7 (разделение оракульных сложностей). Если $v$ имеет $L_v$-липшицев градиент, то можно смотреть на вспомогательную задачу (2.18) как на гладкую сильно выпуклую задачу. Для ее решения можно также использовать рестартованный ускоренный метаалгоритм (УМ), положив 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}$ имеет вид где $\mu_y$-сильно выпуклая функция $h$ непрерывна, функционал $F$, заданный в некоторой окрестности множества $Q_x \times Q_y$, является выпуклым по $x$ и вогнутым по $y$. Допустим, что $F$ является достаточно гладким, а именно для произвольных $x, x' \in Q_x$ и $y, y' \in Q_y$ верны неравенства Введем для задачи (2.21) функцию Обозначим диаметр множества $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) на базе системы вспомогательных минимизационных задач. Однако для решения маломерных (внешних) подзадач на гиперкубе уже будем использовать некоторый аналог метода дихотомии. Поэтому сначала опишем этот подход к решению задач выпуклой минимизации на многомерном гиперкубе с использованием неточного градиента на итерациях. Рассмотрим задачу оптимизации вида где функция $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 достаточно Используя этот результат и методы вспомогательной минимизации, описанные в п. 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
$$
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}$. Если все вспомогательные подзадачи решаются со следующей точностью по функции: Данная оценка требует точности решения вспомогательной задачи по функции порядка $\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}$ удовлетворяет условию Тогда после каждого удаления части допустимого множества оставшаяся его часть содержит решение исходной задачи $\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$: где $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)$, удовлетворяющий условию Отметим, что критерий останова (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 количества обращений к соответствующим вспомогательным подзадачам:
Отметим, что условиями останова для решения вспомогательной задачи являются условия (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$ оценивается из условия Слейтера следующим образом: где $\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$
Из табл. 3 сравнения методов для $n=1000$ и $m=10$ видно, что предложенный метод на треугольнике эффективнее метода эллипсоидов. При этом время работы метода оптимизации на треугольнике несколько меньше, чем время работы метода оптимизации на квадрате, что достигается благодаря локализации двойственных множителей на прямоугольном треугольнике и вследствие этого меньшей длине отрезков, на которых необходимо решать дополнительные одномерные оптимизационные задачи на первых итерациях методов. Кроме того, значительно больших в сравнении с прочими методами числа итераций и времени работы требует метод эллипсоидов для задачи с $m$ ограничениями (не агрегированными в два ограничения вида $\max$) ввиду увеличения размерности задачи и больших временных затрат на выполнение матрично-векторных операций. При этом, как видно из табл. 3, замена субградиентного метода (СyбГМ) на быстрый градиентный метод (БГМ) для вспомогательной многомерной подзадачи не меняет ситуацию. Таблица 3.Сравнение работы методов при $n=1000$, $m=10$
Таблица 4.Работа быстрого градиентного метода при $n=1000$, $m=10$
Сравним работу метода на треугольнике для решения внешней задачи с быстрым градиентным методом (БГМ) при двух $\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)=\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$ они очевидны: Также очевидно, что для функции $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$ по двойственной переменной представлены в табл. 5–7. В этих таблицах указано время работы для случая, когда маломерная задача решается быстрым градиентным методом (БГМ) или маломерными методами (такими, как метод эллипсоидов с $\delta$-субградиентом или метод многомерной дихотомии, представленный в настоящей работе), а вспомогательная многомерная задача решается при помощи быстрого градиентного метода. Жирным шрифтом отмечено наилучшее (наименьшее) значение в строке (при заданных $\varepsilon$, $m$). Таблица 5.Сравнение работы методов при $n=2$
Таблица 6.Сравнение работы методов при $n=3$
Таблица 7.Сравнение работы методов при $n=4$
Случай, когда маломерная задача является вспомогательной, не представлен в таблицах, поскольку во всех экспериментах данные методы не успевали сойтись в рамках выделенного времени. Из этого можно сделать вывод, что при малых размерностях ограничений выгоднее решать маломерную задачу как основную. Обсудим полученные результаты. Во-первых, для всех $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$ такой, что В соответствии с замечанием 3 $\Delta$-аддитивную неточность градиента можно учитывать как дополнительную $\delta$-неточность оракула двумя способами: равномерно, используя $\mu$-сильную выпуклость (имеющую место для рассматриваемой задачи), или же динамически, изменяя $\delta$ в зависимости от диаметра текущего эллипсоида, равного (в обозначениях алгоритма 2) где $\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$ квадратичных ограничений
В табл. 8 указано время выполнения предлагаемого в настоящей статье подхода (алгоритм 2) и подхода работы [8] (алгоритм 4, Fast Projection Method – FPM) для случая $m=3$ ограничений вида где матрицы $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}$ дифференцируема и ее градиент равен Используя (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. Доказательство леммы 31. Для любых $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\}$. В случае дифференцируемой функции имеем Из того, что $\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Пусть мы решаем задачу вида Оценим сложность метода многомерной дихотомии (т.е. количество обращений к подпрограмме вычисления градиента $\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$, то для этого в методе достаточно решить вспомогательную задачу с точностью по аргументу где $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]). Рассмотрим задачу где $f$ и $g_i$ – выпуклые функции. Лагранжиан этой задачи имеет вид Пусть $x_0$ есть такая точка, что $g(x_0) < 0.$ Тогда для решения $y_*$ задачи $\max_y \phi(y)$ верно следующее неравенство: где $\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
Согласно табл. 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] для аналогичной постановки задачи. В рамках поставленных численных экспериментов рассматривались постановки задач, для которых задача малой размерности (в данном случае по двойственным переменным лагранжевой седловой задачи) не является сильно выпуклой (вогнутой). Несмотря на то, что теоретический анализ оценок скорости методов в настоящей статье приводится для случая сильно выпукло-вогнутых задач, правильная настройка методов на практике позволяет с тем же успехом применять предложенные схемы и для просто выпуклых (или вогнутых) маломерных подзадач с обеспечением достижения желаемого качества решения задачи. Это объясняется отсутствием необходимости требовать сильную выпуклость (вогнутость) целевой функции (она важна лишь для теоретических оценок) для реализации всех применяемых в работе к подзадачам небольшой размерности методов.
Цитирование в формате AMSBIB
\RBibitem{AlkGasGla23} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|