Журнал вычислительной математики и математической физики, 2020, T. 60, № 11, стр. 1843-1866

1. ВВЕДЕНИЕ

Одним из основных направлений в численных методах выпуклой оптимизации в последнее десятилетие стало повсеместное распространение конструкции ускорения обычного градиентного метода, предложенной в 1983 г. Ю.Е. Нестеровым [1], на различные другие численные методы оптимизации.

Напомним вкратце исходную конструкцию. Для решения задачи выпуклой оптимизации

было предложено использовать вместо стандартного метода градиентного спуска где $L$ – верхняя оценка константы Липшица градиента $f(x)$ в $2$-норме (далее, для краткости, будем говорить, что $f(x)$ имеет $L$-липшицев градиент), следующий ускоренный метод Сложность итерации этого метода сопоставима со сложностью итерации градиентного спуска. Однако если градиентный спуск сходится в общем случае (на плохо обусловленных задачах [2]) не лучше, чем [3] то ускоренный метод сходится как где ${{x}_{ * }}$ – решение задачи (1), а $R = {{\left\| {{{x}^{0}} - {{x}_{*}}} \right\|}_{2}}$. Если решение не единственное, то под ${{x}_{ * }}$ можно понимать то решение, которое наиболее близко (относительно 2-нормы) к точке старта метода ${{x}^{0}}$ [4]. Оценка (2) с точностью до числового множителя уже не может быть улучшена в общем случае ни на каком другом возможном методе при фиксированном классе задач выпуклой оптимизации (1) с $L$-липшицевым градиентом, см., например, [5], [6]. Аналогичные рассуждения можно провести и в невырожденном случае, когда $f(x)$ есть $\mu $-сильно выпуклая функция [7]. В следующих разделах мы рассмотрим именно такой случай.

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

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

где $y{\kern 1pt} *(x) = argma{{x}_{{y \in {{Q}_{y}}}}}\{ F(x,y) - h(y)\} $. Заметим, что задачи такого типа встречаются в самых разных приложениях, в том числе в поиске равновесий в двухстадийных моделях транспортных потоков [8].

Если задача не сильно выпукла, то ее можно свести к сильно выпуклой применением техники регурялизации и (или) двойственного сглаживания. Без ограничения общности можно считать ${{\mu }_{x}} \geqslant \tfrac{\varepsilon }{{2R_{x}^{2}}}$ (регуляризация [4]) и (или) ${{\mu }_{y}} \geqslant \tfrac{\varepsilon }{{2R_{y}^{2}}}$ (двойственное сглаживание [4], [6], [9], [10]), где ${{R}_{x}} = {{\left\| {{{x}^{0}} - {{x}_{*}}} \right\|}_{2}},$ ${{R}_{y}} = {{\left\| {{{y}^{0}} - y({{x}_{*}}){\text{|}}} \right\|}_{2}},$ $({{x}^{0}},{{y}^{0}})$ – стартовая точка для выбранного численного метода решения задачи (3). Здесь и всюду далее в работе под $\left\langle {x,\;y} \right\rangle $мы понимаем обычное скалярное произведение векторов в конечномерном пространстве и под ${{\left\| x \right\|}_{2}} = \left\langle {x,\;x} \right\rangle $ – евклидову норму.

С точки зрения ускоренных методов данный класс задач достаточно подробно исследован в основном в случае $F(x,y) = \left\langle {Ax,y} \right\rangle $ для некоторого линейного оператора $A$ (см., например, [9]).

В настоящей работе получены аналоги результатов [9] для более общего класса операторов $F$, которые не имеют билинейную структуру. Попутно найдены и некоторые уточнения оценок и для случая $F(x,y) = \left\langle {Ax,y} \right\rangle $. Предлагается сводить рассматриваемые седловые задачи к комбинации вспомогательных задач гладкой сильно выпуклой минимизации отдельно по каждой из групп переменных. Каждая из таких вспомогательных задач может решаться упомянутым выше быстрым градиентным методом Ю.Е. Нестерова. При этом неточность решения вспомогательной (внутренней) подзадачи для одной из групп переменных приводит к необходимости использовать для внешней задачи (которая определяется решением внутренней) концепцию неточного оракула [11], для которой известны оценки скорости сходимости быстрого градиентого метода. В этом случае получены оценки сложности (необходимого количества обращений к подпрограмме для вычисления градиента) предложенного метода, аналогичные известному результату об ускоренном градиентном слайдинге Дж. Лана (см. [9]). При этом с одной стороны предложена новая относительно простая схема пояснения ускоренного градиентного слайдинга с помощью техники Каталист [12], а с другой стороны – результат об ускоренном градиентном слайдинге обобщен на случай, когда вместо обычных градиентов целевых функционалов используются некоторые их неточные аналоги.

Работа состоит из введения, заключения и трех основных разделов. В разд. 2 приводится постановка рассматриваемой задачи и кратко описывается подход к ней на базе известного проксимального зеркального метода А.С. Немировского для вариационных неравенств и седловых задач. Разд. 3 посвящен обзору известных результатов о возможности ускорений оценки скорости сходимости для рассматриваемого класса достаточно гладких сильно выпукло-вогнутых седловых задач, а также формулировкам основных результатов настоящей статьи $({\text{i}})$–$({\text{iii}})$. В разд. 4 приводится схема обоснования основных утверждений работы, сформулированы необходимые вспомогательные утверждения (леммы 1, 2 и 3). Для леммы 3 об ускоренном градиентном слайдинге для минимизации суммы гладких выпуклых функционалов (один из которых сильно выпуклый) при использовании концепции неточного градиента в основной части статьи приведена схема рассуждений на базе недавно предложенной техники Каталист [12]. Полные доказательства лемм 1, 2 и 3 приводятся в приложении к работе.

2. ПОСТАНОВКА ЗАДАЧИ

Пусть ${{Q}_{x}} \subseteq {{\mathbb{R}}^{m}},$ ${{Q}_{y}} \subseteq {{\mathbb{R}}^{n}}$ – непустые, выпуклые и компактные множества, $r:{{Q}_{x}} \to \mathbb{R}$ и $h:{{Q}_{y}} \to \mathbb{R}$ есть ${{\mu }_{x}}$-сильно выпуклая и ${{\mu }_{y}}$-сильно выпуклая функции соответственно.

Всюду будем предполагать, что функционал $F:{{Q}_{x}} \times {{Q}_{y}} \to \mathbb{R}$ выпуклый по $x$ и вогнутый по $y$ и задан в некоторой окрестности множества ${{Q}_{x}} \times {{Q}_{y}}$. При этом $F$ будем считать достаточно гладким на ${{Q}_{x}} \times {{Q}_{y}}$. Точнее говоря, для произвольных $x,x{\kern 1pt} ' \in {{Q}_{x}}$ и $y,y' \in {{Q}_{y}}$, верны следующие неравенства:

где ${{L}_{{xx}}},{{L}_{{xy}}},{{L}_{{yy}}} \geqslant 0$.

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

Пусть

Тогда возможно переписать задачу (6) следующим образом: т.е. задача (6) имеет вид где

Поскольку функционал $\hat {S}(x, \cdot )$ есть ${{\mu }_{y}}$-сильно вогнутый на ${{Q}_{y}}$, то задача максимизации (8) имеет единственное решение

откуда

Всюду далее для произвольного $x \in {{Q}_{x}}$ и некоторого $\delta \geqslant 0$ будем называть ${{\tilde {y}}_{\delta }}(x) \in {{Q}_{y}}$  $\delta $-приближенным решением задачи (8), если

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

Напомним общую постановку задачи решения вариационного неравенства (ВН). Для некоторого оператора $G:Q \to {{\mathbb{R}}^{n}}$, заданного на выпуклом компакте $Q \subset {{\mathbb{R}}^{n}}$ будем рассматривать сильные вариационные неравенства (ВН) вида

где $G$ удовлетворяет условию Липшица. Отметим, что в (12) требуется найти ${{x}_{*}} \in Q$ (где ${{x}_{*}}$ – решение ВН), для которого

Для решения задачи вариационного неравенства в последние годы весьма популярен проксимальный зеркальный метод А.С. Немировского [13]. Недавно был предложен также его вариант с адаптивным выбором шага [14].

Гладкость рассматриваемой седловой задачи приводит к липшицевости оператора $G$, с некоторой константой $L > 0$. В таком случае, как известно, для проксимального зеркального метода справедлива следующая оценка [14]:

где

Заметим, что для всех ${{y}^{k}} \in Q$ имеем

Из (13) следует, что

Объединяя неравенства (14) и (15), получаем

Дополнительно предположим сильную монотонность оператора $G$, т.е. существование такого $\mu > 0$, что

С учетом выпуклости функции $\left\| x \right\|_{2}^{2}$ имеем где ${{\bar {y}}^{N}} = \tfrac{1}{N}\sum\nolimits_{k = 1}^N \,{{y}^{k}}$.

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

где $R = {{\left\| {{{x}^{0}} - {{x}_{*}}} \right\|}_{2}}$ и $\varepsilon $– точность решения ${{x}_{ * }}$. Хорошо известно, что данная оценка не может быть улучшена для рассматриваемого класса вариационных неравенств никакими другими методами.

Если применять рассмотренный подход к поставленной задаче (6), то оператор $G$ из (11) будет $\mu $-сильно монотонным $\mu = \min \{ {{\mu }_{x}},{{\mu }_{y}}\} $, что приведет к следующей оценке сложности:

достижения нужного качества решения. Если ${{\mu }_{x}}$ или ${{\mu }_{y}}$ близко к нулю, то величина в (16) может оказаться достаточно большой. В последующих разделах мы, в частности, рассмотрим альтернативные подходы, которые позволяют уточнить оценку (16) в случае, когда ${{\mu }_{x}} \ll {{\mu }_{y}}$ или ${{\mu }_{y}} \ll {{\mu }_{x}}$.

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

где ${{c}_{1}} \in {{Q}_{x}}$ и ${{c}_{2}} > 0$, может быть решена явно. Аналогично $h(y)$ – проксимально дружественная функция, если задача вида может быть решена явно.

Под $\varepsilon $-решением задачи (3) будем понимать такую пару $({{x}^{{{{N}_{x}}}}},{{y}^{{{{N}_{y}}}}}) \in {{Q}_{x}} \times {{Q}_{y}}$, что

где ${{B}_{n}}(R)$ – евклидов шар радиуса $R$ в ${{\mathbb{R}}^{n}}$.

Ниже приведены наилучшие известные нам результаты (см. [9], [10], [15], [16], [17] и цитированную в этих работах литературу) относительно сложности решения задачи (3), которые далее мы постараемся уточнить. Собственно, в пп. 2)–4) такое уточнение уже делается: ранее в приведенном виде данные результаты были известны только в предположении $F(x,y) = \left\langle {Ax,y} \right\rangle $ для некоторого линейного оператора $A$. В этом случае ${{L}_{{xx}}} = {{L}_{{yy}}} = 0$, ${{L}_{{xy}}} = {{L}_{{yx}}} = \sqrt {{{\lambda }_{{max}}}({{A}^{{\text{т}}}}A)} $, где ${{\lambda }_{{max}}}({{A}^{{\text{т}}}}A)$ – наибольшее собственное значение матрицы ${{A}^{{\text{т}}}}A$.

1) Если $r(x)$ и $h(y)$ проксимально дружественны, то $\varepsilon $-решение задачи (3) может быть достигнуто за $\tilde {O}\left( {\tfrac{{{{L}_{{xy}}}}}{{\sqrt {{{\mu }_{x}}{{\mu }_{y}}} }}} \right)$ вычислений (17), ${{\nabla }_{x}}F(x,y)$ и (18), ${{\nabla }_{y}}F(x,y)$ при $F(x,y) = \left\langle {Ax,y} \right\rangle $ и за $\tilde {O}\left( {\tfrac{{\max \{ {{L}_{{xx}}},{{L}_{{xy}}},{{L}_{{yy}}}\} }}{{\min \{ {{\mu }_{x}},{{\mu }_{y}}\} }}} \right)$ вычислений (17), ${{\nabla }_{x}}F(x,y)$ и (18), ${{\nabla }_{y}}F(x,y)$ в общем случае. Здесь и далее $\tilde {O}() = O()$ с точностью до небольшой степени логарифмического по $\varepsilon $, ${{\mu }_{x}}$ или ${{\mu }_{y}}$, а также по ${{R}_{x}}$ или ${{R}_{y}}$ множителя. Как правило, показатель этой степени 1 или 2.

2) Если $r(x)$ имеет ${{L}_{x}}$-липшицев градиент, но не проксимально дружественна, то $\varepsilon $-решение задачи (3) может быть достигнуто за $\tilde {O}\left( {\sqrt {\tfrac{{{{L}_{x}}}}{{{{\mu }_{x}}}}} } \right)$ вычислений $\nabla r(x)$,

вычислений ${{\nabla }_{x}}F(x,y)$ и вычислений (18), а также ${{\nabla }_{y}}F(x,y)$.

3) Если $h(y)$ имеет ${{L}_{y}}$-липшицев градиент, но не проксимально дружественна, то $\varepsilon $-решение задачи (3) может быть достигнуто за (19) вычислений (17), ${{\nabla }_{x}}F(x,y)$ и

вычислений $\nabla h(y)$, (20) вычислений ${{\nabla }_{y}}F(x,y)$.

4) Если $r(x)$ имеет ${{L}_{x}}$-липшицев градиент, $h(y)$ имеет ${{L}_{y}}$-липшицев градиент, но обе функции не проксимально дружественны, то $\varepsilon $-решение задачи (3) может быть достигнуто за $\tilde {O}\left( {\sqrt {\tfrac{{{{L}_{x}}}}{{{{\mu }_{x}}}}} } \right)$ вычислений $\nabla r(x)$, (19) вычислений ${{\nabla }_{x}}F(x,y)$ и (21) вычислений $\nabla h(y)$, (20) вычислений ${{\nabla }_{y}}F(x,y)$.

Отметим, что результаты всего п. 1) и пп. 2), 4) в части числа вычислений $\nabla r(x)$ (и, по-видимому, в части числа вычислений ${{\nabla }_{x}}F(x,y)$) в общем случае не могут быть улучшены [5], [18] (с точностью до логарифмического множителя), если

Заметим, что правую часть можно менять в зависимости от специфики постановки задачи. Если это условие не выполняется, то можно свести седловую задачу к негладкой задаче выпуклой оптимизации [19], [20] и решать ее методами типа центров тяжести, например, методом эллипсоидов или Вайды [20], [21]. Заметим, что методом эллипсоидов можно решать седловую задачу и напрямую [22].

Сформулируем результаты настоящей работы.

i) Основным результатом работы является обоснование возможности в пп. 2)–4) выше полностью убрать оговорку “при $F(x,y) = \left\langle {Ax,y} \right\rangle $”.

При ${{\mu }_{x}} = \tfrac{\varepsilon }{{R_{x}^{2}}}$ частично это уже было сделано в работе [16]. Однако полученные в этой работе оценки в части числа вычислений $\nabla r(x)$ проигрывают оценкам, приведенным выше, в $ \sim {\kern 1pt} \tfrac{1}{{{{\mu }_{y}}}}$ раз.

ii) Другим результатом работы является уточнение приведенных выше утверждений в случае, когда $F(x,y) = \left\langle {Ax,y} \right\rangle $ для некоторого линейного оператора $A$, ${{Q}_{y}} = {{\mathbb{R}}^{m}},$ $h(y)$ имеет ${{L}_{y}}$-липшицев градиент и $\tfrac{{{{\lambda }_{{min}}}({{A}^{{\text{т}}}}A)}}{{{{L}_{y}}}} \gg {{\mu }_{x}}$. В этом случае во всех приведенных выше формулах можно заменить ${{\mu }_{x}}$ на $\tfrac{{{{\lambda }_{{min}}}({{A}^{{\text{т}}}}A)}}{{{{L}_{y}}}}$.

iii) Более того, если $F(x,y) = \left\langle {Ax,y} \right\rangle $ для некоторого линейного оператора $A$, ${{Q}_{x}} = {{\mathbb{R}}^{n}}$, ${{Q}_{y}} = {{\mathbb{R}}^{m}}$, $r(x)$ имеет ${{L}_{x}}$-липшицев градиент, $h(y)$ имеет ${{L}_{y}}$-липшицев градиент, то оценки на количество вычислений ${{\nabla }_{x}}F(x,y) = {{A}^{{\text{т}}}}y$, ${{\nabla }_{y}}F(x,y) = Ax$ и (18) (здесь предполагается проксимальная дружественность $h(y)$) можно заменить (это имеет смысл, если новые оценки станут лучше имеющихся) на следующую оценку:

где $\lambda _{{min}}^{ + }({{A}^{{\text{т}}}}A)$ – минимальное положительное собственное значение матрицы ${{A}^{{\text{т}}}}A$.

Отметим, что аналогичное ii) утверждение можно сформулировать и в случае, когда $r(x)$ имеет ${{L}_{x}}$-липшицев градиент.

Стоит отметить, что результат ii) позволяет, среди прочего, элементарным образом объяснить, как решать матричную игру за $\tilde {O}\left( {\sqrt {\tfrac{{{{\lambda }_{{max}}}({{A}^{{\text{т}}}}A)}}{{{{\lambda }_{{min}}}({{A}^{{\text{т}}}}A)}}} } \right)$ матрично-векторных умножений. Сначала необходимо двойственно сгладить (должным образом) исходную постановку задачи [4], [6], [9], [10], т.е. ввести проксимально-дружественную функцию $h(y) = \tfrac{{\varepsilon \left\| y \right\|_{2}^{2}}}{{4R_{y}^{2}}}$. Отметим, что при этом ${{Q}_{x}} = {{Q}_{y}} = {{\mathbb{R}}^{n}}$. Далее, полученную в результате функцию $g(x)$ можно минимизировать обычным ускоренным (быстрым градиентным) методом [1], [4]–[7], [9], [10] (в сильно выпуклом случае). Полученная при этом сложность решения задачи существенно лучше популярных и активно исследуемых процедур типа экстраградиентного метода, для которого удалось лишь получить такую оценку трудоемкости $\tilde {O}\left( {\tfrac{{{{\lambda }_{{max}}}({{A}^{{\text{т}}}}A)}}{{{{\lambda }_{{min}}}({{A}^{{\text{т}}}}A)}}} \right)$ [23].

Отметим также, что результаты, приведенные в п. iii), нашли важное приложение в построении оптимальных ускоренных методов для гладких выпуклых задач децентрализованной распределенной оптимизации [24]. Собственно, наш изначальный интерес к этой проблематике и был связан с развитием идей работы [24].

4. НЕОБХОДИМЫЕ ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ И СХЕМА ОБОСНОВАНИЯ ОСНОВНЫХ РЕЗУЛЬТАТОВ РАБОТЫ

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

Лемма 1 (см. [4], [25], [26]). В обозначениях п. 2, если $F(x,y) = \left\langle {Ax,y} \right\rangle $, то $g(x)$ будет иметь $L$-липшицев градиент, где $L = \tfrac{{{{\lambda }_{{max}}}({{A}^{{\text{т}}}}A)}}{{{{\mu }_{y}}}}$. Если, дополнительно, $h(y)$ имеет ${{L}_{y}}$-липшицев градиент и ${{Q}_{y}} = {{\mathbb{R}}^{m}}$, то $g(x)$ есть $\mu $-сильно выпуклая функция на ${{(\operatorname{Ker} A)}^{ \bot }}$, где $\mu = \tfrac{{\lambda _{{min}}^{ + }({{A}^{{\text{т}}}}A)}}{{{{L}_{y}}}}$. При этом $\nabla g(x) \in {{(\operatorname{Ker} A)}^{ \bot }}$.

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

Лемма 2 (см. [11], [16], [17]). В обозначениях п. 2, $g(x)$ будет иметь $L$-липшицев градиент $\nabla g(x) = {{\nabla }_{x}}F(x,y{\kern 1pt} *{\kern 1pt} (x))$ (теорема Демьянова–Данскина), где $L = {{L}_{{xx}}} + \tfrac{{2L_{{xy}}^{2}}}{{{{\mu }_{y}}}}$. Более того, для всех $x,z \in {{Q}_{x}}$ выполняется следующее условие (словами: ${{\nabla }_{x}}F(x,\mathop {\tilde {y}}\nolimits_\delta (x))$ – $(2\delta ,2L)$ – градиент для $g(x)$):

где $\mathop {\tilde {y}}\nolimits_\delta (x)$ такой, чтокоторый определен в (10).

Рассмотрим наиболее тонкое из используемых нами вспомогательных утверждений [9]. Пусть нужно решить задачу сильно выпуклой композитной оптимизации

c точностью $\varepsilon $ по функции. Считаем, что функции $r(x)$ и $g(x)$ имеют константы Липшица градиента ${{L}_{r}}$ и ${{L}_{g}}$, и хотя бы одна из этих функций $\mu $-сильно выпуклая. К такой задаче (24) можно применить результат о так называемом ускоренном градиентном слайдинге из п. 8.2 [9].

Лемма 3. Необходимого качества решения задачи решения (24) можно достичь за ${{N}_{r}} = \tilde {O}\left( {\sqrt {\tfrac{{{{L}_{r}}}}{\mu }} } \right)$ вычислений градиента первого слагаемого $\nabla r(x)$ и ${{N}_{g}} = \tilde {O}\left( {\sqrt {\tfrac{{{{L}_{g}}}}{\mu }} } \right)$ вычислений градиента второго слагаемого $\nabla g(x)$. Результат останется верным, если вместо $\nabla g(x)$ использовать $\left( {O\left( {\tfrac{\varepsilon }{{{{N}_{g}}}}} \right),O({{L}_{g}})} \right)$-градиент.

Подробное доказательство леммы 3 приведено в приложении. Здесь мы лишь приведем некоторую схему рассуждений. Для наглядности полагаем $\mu $-сильно выпуклым именно функционал $g$. Если это не так и $r$ есть ${{\mu }_{r}}$-сильно выпуклый, а $g$ просто выпуклый, то можно заменить $r(x)$ на $r(x) - \tfrac{{{{\mu }_{g}}}}{2}\left\| x \right\|_{2}^{2}$ и $g(x)$ на $g(x) + \tfrac{{{{\mu }_{g}}}}{2}\left\| x \right\|_{2}^{2}$ для некоторого ${{\mu }_{g}} < {{\mu }_{r}}$. Тогда оба функционала будут как гладкими, так и сильно выпуклыми.

К рассмотренной задаче (24) можно применить технику Каталист (алгоритм 1) из [12] в предположении ${{L}_{r}} \ll {{L}_{g}}$ и $\mu $-сильной выпуклости $g$ в $2$-норме, причем $\mu \ll {{L}_{r}}$.

Алгоритм 1. Каталист.

1: Вход: ${{x}^{0}} \in {{\mathbb{R}}^{n}},$ параметр $L$.

2: ${{y}^{0}}: = {{x}^{0}}$.

3: while желаемая точность не достигнута do

4:  Найти ${{x}^{k}}$ с некоторой точностью применением алгоритма 2

5:  Вычисляем ${{y}^{k}}$, используя шаг экстраполяции, с ${{\beta }_{k}} \in (0,1)$

6: end while

7: Выход: ${{x}^{k}}$.

Алгоритм 2. Неускоренный градиентный метод для задач композитной оптимизации.

1: Вход: ${{x}^{0}} \in {{\mathbb{R}}^{n}},$ параметр ${{L}_{r}}$.

2: for $k = 0,1,2, \ldots $ do

3:

4: end for

5: Выход: ${{\bar {x}}_{N}} = \tfrac{1}{N}\sum\nolimits_{k = 0}^{N - 1} \,{{x}^{{k + 1}}}$.

Тогда (см. [12]) вместо исходной задачи потребуется $\tilde {O}\left( {\sqrt {\tfrac{L}{\mu }} } \right)$ раз решать задачу вида

где $L > 0$– некоторый параметр регуляризации, а последовательность ${{y}^{0}},{{y}^{1}}, \ldots $ образуется согласно схеме алгоритма 1. При этом задачу (25) можно решать неускоренным композитным градиентным методом (алгоритм 2), считая $g(x) + \tfrac{L}{2}\left\| {x - {{y}^{{k - 1}}}} \right\|_{2}^{2}$ композитом. Как известно, число итераций такого метода будет совпадать с количеством вычислений $\nabla r(x)$ и равно $\tilde {O}\left( {\tfrac{{{{L}_{r}}}}{{L + \mu }}} \right)$. Но при этом не предполагается проксимальная дружественность функции $g(x)$ и поэтому необходимо учитывать сложность решения возникающей на каждой итерации неускоренного композитного градиентного метода задачи вида Для решения уже этой вспомогательной задачи можно использовать ускоренный композитный градиентный метод для задач сильно выпуклой оптимизации [27] (см. также алгоритмы 3, 4 далее). При этом слагаемое $\tfrac{{{{L}_{r}}}}{2}\left\| {x - {{{\tilde {x}}}^{l}}} \right\|_{2}^{2} + \tfrac{L}{2}\left\| {x - {{y}^{{k - 1}}}} \right\|_{2}^{2}$ считается композитом. Число итераций такого метода будет $\tilde {O}\left( {\sqrt {\tfrac{{{{L}_{g}}}}{{{{L}_{r}} + L + \mu }}} } \right)$. Таким образом, общее количество вычислений $\nabla g(x)$ будет следующим Выберем параметр регуляризации $L$ так, чтобы последнее выражение было минимальным. Тогда с учетом сделанных предположений ${{L}_{r}} \ll {{L}_{g}}$ и $\mu \ll {{L}_{r}}$ получим, что $L \simeq {{L}_{r}}$. Следовательно, общее число вычислений $\nabla g(x)$ будет действительно равно $\tilde {O}\left( {\sqrt {\tfrac{{{{L}_{g}}}}{\mu }} } \right)$.

Заметим, что полностью новым является утверждение из последнего предложения формулировки леммы 3. Доказательство этого ключевого наблюдения проводится аналогично оригинальной статье [11], см. также [9], [16]. Действительно, если функционал $g:{{\mathbb{R}}^{n}} \to \mathbb{R}$ допускает ($\delta ,L$)-градиент ${{\nabla }_{\delta }}g(x)$ в любой запрошенной точке $x$, т.е. верно неравенство

Последнее неравенство отличается от стандартного условия $L$-липшицевости градиента выпуклого функционала $g$лишь постоянной величиной погрешности $\delta $. Поэтому применение указанного неравенства для модификации результата об ускоренном градиентном слайдинге [9] (который в стандартном случае основан на комбинации оценок, связанных с неравенством (26)) для решения ${{N}_{g}}$ вспомогательных подзадач приведет к накоплению в итоговой оценке погрешности, сопоставимой с величиной $O({{N}_{g}}\delta )$. Это обстоятельство и приводит к необходимости вместо $\nabla g(x)$ использовать именно $\left( {O\left( {\tfrac{\varepsilon }{{{{N}_{g}}}}} \right),O({{L}_{g}})} \right)$-градиент.

Утверждения i) и ii) получаются сочетанием лемм 1–3. Приведем схему доказательства первого из результатов. Напомним, что мы рассматриваем задачу вида

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

Замечание 1. Если некоторый функционал $S(x,y)$ является ${{\mu }_{x}}$-сильно выпуклым по $x$ и ${{\mu }_{y}}$-сильно вогнутым по $y$, то можно представить $S$ в виде

причем функционал $F$ сохранит свойство выпуклости по $x$ и вогнутости по $y$. Отметим, что ввиду достаточной гладкости функционалов $\left\| x \right\|_{2}^{2}$ и $\left\| y \right\|_{2}^{2}$ (липшицевость градиентов), если $S$ гладкий, то $F$ будет гладким. Таким образом, приводимая ниже схема рассуждений применима к седловым задачам для произвольного ${{\mu }_{x}}$-сильно выпуклого по $x$ и ${{\mu }_{y}}$-сильно вонутого по $y$, а также достаточно гладкого функционала $S(x,y)$.

Зафиксируем $x \in {{Q}_{x}}$ и введем вспомогательный функционал

что позволяет рассматривать седловую задачу (27) как задачу выпуклой минимизации

Ясно, что

По лемме 2 функционал $f$ (см. (28)) является ${{\mu }_{x}}$-сильно выпуклым и g имеет $L$-липщицев градиент

где Также согласно лемме 2 (см. также [16]) для функционала $f$ выполнено неравенство а $\gamma $ – точность решения вспомогательной задачи максимизации $S({{x}_{1}},y)$ по $y$: Задача ${{\mu }_{y}}$-сильно вогнутой композитной (в силу предположения для $h$ выше) максимизации (при фиксированном $x \in {{Q}_{x}}$) может быть решена с точностью $\gamma $ в (31) за итераций быстрого градиентного метода.

Алгоритм 3. Быстрый градиентный метод с $(\delta ,L)$-оракулом для задач композитной оптимизации (33).

1: Вход: ${{x}^{0}} \in Q$ – начальная точка, $N$ – количество шагов, $L > 0$ и $\delta > 0$.

2: ${{y}^{0}}: = {{x}^{0}},$ ${{u}^{0}}: = {{x}^{0}},$ ${{\alpha }_{0}}: = 0,$ ${{A}_{0}}: = 0$.

3: for $k = 1,2, \ldots ,N$ do

4:  Находим наибольший корень, ${{\alpha }_{{k + 1}}}$ так, что

5:

6:

7:

8:

9: end for

10: Выход: ${{x}^{N}}$.

Покажем, как с использованием рестартов быстрого градиентного метода в концепции $(\delta ,L)$-оракула можно достичь заданного качества решения по функции для задач композитной оптимизации с требуемой оценкой сложности. Для задачи композитной оптимизации

можно применить предложенный в [28] алгоритм 3.

Для алгоритма 3 в [28] доказана следующая оценка скорости сходимости (мы предполагаем, что вспомогательные задачи решаются точно):

где ${{R}^{2}} = \tfrac{1}{2}\left\| {{{x}_{*}} - {{x}^{0}}} \right\|_{2}^{2}$, а ${{x}_{*}}$ – ближайшая точка минимума к точке ${{x}^{0}}$. Введем вспомогательное обозначение

Тогда ввиду ${{\mu }_{x}}$-cильной выпуклости $g$ имеем

Алгоритм 4. Быстрый градиентный метод для задач сильно выпуклой композитной оптимизации с $(\delta ,L)$-оракулом, рестарты алгоритма 3.

1: Вход: ${{x}^{0}} \in Q$ – начальная точка, $L > 0,$ $\mu > 0,$ $\delta > 0,$ $\varepsilon $ – точность решения, $R$ и $p = \left\lceil {lo{{g}_{2}}\left( {\tfrac{{\mu {{R}^{2}}}}{\varepsilon }} \right)} \right\rceil $ – количество рестартов.

2: for $j = 1, \ldots ,p$ do

3:  Выполнить ${{N}_{j}} = \left\lceil {3e\sqrt {\tfrac{L}{\mu }} } \right\rceil $ итераций алгоритма 3.

4:  ${{x}^{0}}: = {{x}^{{{{N}_{j}}}}}$.

5: end for

6: Выход: $\hat {x}: = {{x}^{{{{N}_{p}}}}}$.

Если сделать естественное предположение $\psi (x,{{x}_{*}}) \geqslant \left\langle {\nabla (r + g)({{x}_{*}}),x - {{x}_{*}}} \right\rangle \geqslant 0$, то после ${{N}_{1}}$ итераций алгоритма 3 имеем

Если для числа итераций ${{N}_{1}}$ алгоритма 3 выбрать $\delta $ так, чтобы выполнялось неравенство то получим Поэтому, выбирая ${{N}_{1}} = \left\lceil {3e\sqrt {\tfrac{L}{{{{\mu }_{x}}}}} } \right\rceil $, получаем (Данный способ выбора количества итераций авторам подсказал Роланд Хильдебранд.)

После этого выберем для aлгоритма 3 в качестве точки старта ${{x}^{{{{N}_{1}}}}}$ и снова сделаем ${{N}_{1}}$ итераций и т.д. Ясно, что для достижения приемлемого качества решения можно выбрать количество рестартов $p$ алгоритма 3 для алгоритма 4 следующим образом:

где ${{R}^{2}} = \tfrac{1}{2}\left\| {{{x}^{0}} - {{x}_{*}}} \right\|_{2}^{2}$. В таком случае общее число итераций алгоритма 4 в предложенной схеме будет т.е.

Итак, ясно, что при $\delta = O\left( {{{\mu }_{x}}\varepsilon \sqrt {\frac{{{{\mu }_{x}}}}{L}} } \right)$ предложенной схемой возможно получить точность $f(\hat {x}) - f({{x}_{*}}) \leqslant \varepsilon $ для выхода $\hat {x}$ алгоритма 4.

Далее, неравенство (30) (см. также неравенство (2.20) из [16]) означает, что функционал $f$ в произвольной точке допускает $(2\gamma ,L,{{\mu }_{x}})$-оракул в смысле [29].

Таким образом, точность $\gamma $ для решения внутренней задачи (аналог точности $\delta $ в концепции ($\delta ,L$)-градиента) нужно выбирать как $O(\varepsilon )$ и тогда для внешней задачи будет гарантирована точность $\varepsilon $ по функции. Это означает, что общее количество вызовов оракула для ${{\nabla }_{x}}S( \cdot , \cdot )$ при решении внешней задачи (29) будет равно

Количество же вызовов оракула для ${{\nabla }_{y}}S( \cdot , \cdot )$ при решении внутренней задачи будет равно в силу (32)

Замечание 2. Согласно известной теореме о минимаксе сильная выпукло-вогнутость функционала $S( \cdot , \cdot )$ означает, что

и можно свести задачу (27) к задаче вогнутой максимизации В таком случае количество вызовов ${{\nabla }_{y}}S( \cdot , \cdot )$ будет а количество вызовов ${{\nabla }_{x}}S( \cdot , \cdot )$

Утверждение i) в случае, когда какая-то из функций $r(x)$ или $h(y)$ не проксимально дружественна, получается похожей схемой рассуждений. Но при этом мы получим вспомогательные подзадачи вида (24) с сильно выпуклой целевой функцией, которые можно решать с использованием результата об ускоренном градиентном слайдинге. Сформулированные оценки утверждения i), таким образом, вытекают из леммы 3.

Отметим, что для утверждения леммы 3 о сложности решения вспомогательной подзадачи (24) в случае сильной выпуклости $r$ и $g$ не имеет значения, параметр сильной выпуклости какого из этих функционалов использовать в оценках из леммы 3. Поэтому утверждение ii) теперь будет следовать из леммы 1 (где приводится оценка на параметр сильной выпуклости $g$).

Скажем несколько слов про обоснование утверждения iii). Мы отправляемся от [24].

Ясно, что решаемую задачу минимизаци функции $f(x) = r(x) + g(x)$ на множестве ${{Q}_{x}} = {{\mathbb{R}}^{n}}$ можно рассматривать как задачу композитной оптимизации с композитом $g$. Точнее говоря, ввиду ${{\mu }_{x}}$-сильной выпуклости и ${{L}_{x}}$-липшицевости градиента $r$ можно свести задачу минимизации $f$ к рассмотрению семейства $k = \tilde {O}\left( {\sqrt {\tfrac{{{{L}_{x}}}}{{{{\mu }_{x}}}}} } \right)$ вспомогательных задач вида

Поскольку $g$ уже, вообще говоря, не имеет простой структуры, то необходимо учитывать сложность каждой из $k$ задач (34). Поскольку вдоль ядра $\operatorname{Ker} A$ функция $g$ принимает постоянное значение, то без уменьшения общности рассуждений можно считать, что $x \in {{(\operatorname{Ker} A)}^{ \bot }}$. Дело в том, что вдоль всякого направления, ортогонального $\operatorname{Ker} A$, вспомогательная задача будет иметь обусловленность 1 и не представляет трудоемкости в предположении, что известно ${\text{Ker}}A$ (а стало быть, и ортогональные направления). Тогда согласно лемме 1 трудоемкость нахождения приемлемого качества решения каждой из задач (34) (линейные слагаемые не влияют на нее) будет определяться числом обусловленности поскольку для произвольных $a \geqslant b > 0$ и $c > 0$ верно неравенство $\tfrac{{a + c}}{{b + c}} \leqslant \tfrac{a}{b}$. Таким образом, верна оценка (22).

5. ЗАКЛЮЧЕНИЕ

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

Следует отметить, что в тексте статьи мы намерено избегали максимальной общности изложения для компактности и удобства восприятия. Тем не менее отметим, что приведенные в статье результаты можно обобщить на случай более общих оракулов [4]: стохастических, рандомизированных (в том числе инкрементальных, возникающих при работе с целевыми функционалами вида суммы функций), неполноградиентных, модельных (в том числе с дополнительными композитными членами); вместо евклидовой нормы, можно было рассматривать более общие нормы и прокс-структуры (впрочем, все же не в такой общности, как в не сильно выпуклом случае); наконец, можно попробовать рассмотреть более чем два слагаемых в структуре целевого функционала. Также весьма интересен вопрос о том, в какой степени можно перенести полученные результаты на классы негладких седловых задач. Многое упирается в возможность должным образом обобщить лемму 3. Нам представляется, что на этом пути может быть получено достаточно много новых интересных результатов.

Отметим также, что если в приведенных в статье постановках задач $dim(y)$ и(или) $dim(x)$ небольшие, то у использованных в статье ускоренных методов появляются конкуренты в виде методов типа центров тяжести [20], [21]. В качестве примера можно посмотреть случай $dim(y) = 2$, разобранный в [27].

Несмотря на полученное в работе улучшение известных верхних оценок, мы все же по-прежнему не знаем, оптимальны ли приведенные в этой статье оценки по совокупности критериев: число вычислений градиента по прямым переменным и по двойственным (не только по одному из них)? Недавно появился препринт [30], в котором получены нижние оценки для гладких сильно выпукло-вогнутых седловых задач. Однако при этом была показана достижимость этих оценок только на специальном подклассе задач. В общем случае предложенная в отмеченном препринте [30] методика (Section 4.2) приводит к оценкам, аналогичным полученным нами. Однако мы обосновываем указанные верхние оценки для более широкого класса задач, не предполагающих проксимальную дружественность $h$ и $r$.

Авторы выражают благодарность А.С. Немировскому, Ю.Е. Нестерову и Р. Хильдебранду за ценное обсуждение части материала статьи.