1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 59, № 7, 2019

Журнал вычислительной математики и математической физики, 2019, T. 59, № 7, стр. 1137-1150

Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим (δ, L)-модель функции в запрошенной точке

А. В. Гасников 1, 2, 3, А. И. Тюрин 1, *

1 НИУ ВШЭ
101000 Москва, ул. Мясницкая, 20, Россия

2 НИУ МФТИ
141700 М.о., Долгопрудный, Институтский пер., 9, Россия

3 Ин-т пробл. передачи информац. РАН
127051 Москва, Бол. Каретный пер., 19, стр. 1, Россия

* E-mail: atyurin@hse.ru

Поступила в редакцию 08.11.2017
После доработки 08.11.2017
Принята к публикации 11.03.2019

Полный текст (PDF)

Аннотация

Предлагается новая концепция $(\delta ,L)$-модели функции, которая обобщает концепцию $(\delta ,L)$-оракула Деволдера–Глинера–Нестерова. В рамках этой концепции строятся градиентный спуск, быстрый градиентный спуск и показывается, что многие известные ранее конструкции методов (композитные методы, методы уровней, метод условных градиентов, проксимальные методы) являются частными случаями предложенных в данной работе методов. Библ. 34.

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

1. ВВЕДЕНИЕ

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

Общая задача оптимизации, когда имеется только информация о липшицевости градиента или о липшицевости функции, хорошо изучена и для нее имеются нижние и верхние оценки [1], [2]. В последнее время стала популярна структурная оптимизация, когда мы имеем априорную информацию о структуре задачи. Дополнительная информация о задаче позволяет находить новые методы и улучшать верхние оценки. В частности, композитная постановка задачи, когда заданная функция имеет вид суммы гладкой и негладкой функции [3], может быть решена со скоростью быстрого градиентного метода, используя дополнительную информацию о негладком слагаемом в сумме. Помимо этого, часто можно находить минимум негладкой функции со скоростью быстрого градиентного метода, несмотря на то, что в общем случае это невозможно для негладких задач. Как пример, можем рассмотреть минимаксную задачу, которая является негладкой, но для нее предложен быстрый градиентный метод [1]. Основной целью данной работы является попытка объединить различные подходы в один, таким образом, предложить метод, который бы смог в себя включать ранее предложенные концепции. В разд. 4 мы привели большое количество примеров задач оптимизации, которые могут быть решены нашим методом. Для этого вводится понятие $(\delta ,L)$-модели, которое по своей сути является обобщением определения липшицевости градиента или концепции $(\delta ,L)$-оракула Деволдера–Глинера–Нестерова.

Статья построена следующим образом. В разд. 2 на базе концепции $(\delta ,L)$-оракула [4] приводится оригинальная концепция $(\delta ,L)$-модели функции, при этом дополнительно допускается возможность неточного решения вспомогательной задачи [5]. Также в этом разделе приводится обобщение метода градиентного спуска на случай работы с введенной моделью. В разд. 3 результаты разд. 2 с градиентного спуска переносятся на быстрый градиентный спуск. В разд. 4 содержатся приложения предложенных в разд. 2, 3 методов в концепции $(\delta ,L)$-модели к различным постановкам задач. Именно в этом разделе показывается, что предложенная концепция и методы, действительно, позволяют собрать имеющиеся в данном направлении результаты. В Приложении приводится обоснование того, что выбранная, следуя А.С. Немировскому, концепция точности, с которой решается вспомогательная задача, вполне практична и для ограниченных гладких постановок задач сводится к обычной концепции сходимости по функции (стоит отметить, что есть и другие концепции [6]–[8]).

2. ГРАДИЕНТНЫЙ МЕТОД С ОРАКУЛОМ, ИСПОЛЬЗУЮЩИМ (δ, L)-МОДЕЛЬ

Опишем сначала общую постановку задачи выпуклой оптимизации [1]. Пусть определена функция $F(x):Q \to \mathbb{R}$ и дана произвольная норма $\left\| \; \right\|$ в ${{\mathbb{R}}^{n}}$. Сопряженная норма определяется следующим образом:

(1)
${{\left\| \lambda \right\|}_{ * }} = \mathop {max}\limits_{\left\| \nu \right\| \leqslant 1;\nu \in {{\mathbb{R}}^{n}}} \langle \lambda ,\nu \rangle \quad \forall \lambda \in {{\mathbb{R}}^{n}}.$

Будем полагать следующее.

1. $Q \subseteq {{\mathbb{R}}^{n}}$, выпуклое, замкнутое.

2. $F(x)$ – непрерывная и выпуклая функция на $Q$.

3. $F(x)$ ограничена снизу на $Q$ и достигает своего минимума в некоторой точке (необязательно единственной) ${{x}_{ * }} \in Q$.

Рассмотрим следующую задачу оптимизации:

(2)
$F(x) \to \mathop {min}\limits_{x \in Q} .$

Введем два понятия: прокс-функция и дивергенция Брэгмана [9].

Определение 1. $d(x):Q \to \mathbb{R}$ называется прокс-функцией, если $d(x)$, непрерывно дифференцируемая на $\operatorname{int} Q$ и $d(x)$, является 1-сильно выпуклой относительно нормы $\left\| \; \right\|$ на $\operatorname{int} Q$.

Определение 2. Дивергенцией Брэгмана называется

(3)
$V(x,y)\;\mathop = \limits^{{\text{def}}} \;d(x) - d(y) - \langle \nabla d(y),x - y\rangle ,$
где $d(x)$ – произвольная прокс-функция.

Легко показать [5], что

$V(x,y) \geqslant \frac{1}{2}\mathop {\left\| {x - y} \right\|}\nolimits^2 .$

Далее мы введем определение $(\delta ,L)$-модели функции [10], которая является прямым обобщением $(\delta ,L)$-оракула [4], [11], [12].

Определение 3. Будем говорить, что имеем $(\delta ,L)$-модель функции $F(x)$ в точке $y$, и обозначать эту модель через $({{F}_{\delta }}(y),{{\psi }_{\delta }}(x,y))$, если для любого $x \in Q$ справедливо неравенство

(4)
$0 \leqslant F(x) - {{F}_{\delta }}(y) - {{\psi }_{\delta }}(x,y) \leqslant \frac{L}{2}{{\left\| {x - y} \right\|}^{2}} + \delta ,$
причем
(5)
${{\psi }_{\delta }}(x,x) = 0\quad \forall x \in Q$
и ${{\psi }_{\delta }}(x,y)$ – выпуклая функция по $x$ для $\forall y \in Q$.

Будем считать, что для $F(x)$ имеются такие $\delta $ и $L$, что существует $(\delta ,L)$-модель в любой точке $x \in Q$. Соответствующие примеры представлены в разд. 4.

Следствие 1. Возьмем $x = y$ в (4) и воспользуемся (5), тогда

(6)
${{F}_{\delta }}(y) \leqslant F(y) \leqslant {{F}_{\delta }}(y) + \delta \quad \forall y \in Q.$

Рассмотрим концепцию неточного решения задачи, представленную в [5].

Определение 4. Пусть имеется задача

$\psi (x) \to \mathop {min}\limits_{x \in Q} ,$
где $\psi (x)$ – выпуклая, тогда ${\text{Arg}}\min _{{x \in Q}}^{{\widetilde \delta }}\psi (x)$ – множество таких $\tilde {x}$, что
$\exists h \in \partial \psi (\tilde {x}),\quad \langle h,x - \tilde {x}\rangle \geqslant - \widetilde \delta \quad \forall x \in Q.$
Произвольный элемент из ${\text{Arg}}\min _{{x \in Q}}^{{\widetilde \delta }}\psi (x)$ будем обозначать через ${\text{arg}}\min _{{x \in Q}}^{{\widetilde \delta }}\psi (x)$.

Рассмотрим простое следствие. Пусть $\tilde {x} \in {\text{Arg}}\min _{{x \in Q}}^{{\widetilde \delta }}\psi (x)$, тогда из выпуклости верно: $\psi (x) \geqslant \psi (\tilde {x}) + \langle h,x - \tilde {x}\rangle \geqslant \psi (\tilde {x}) - \widetilde \delta $, где $h \in \partial \psi (\tilde {x})$. Возьмем $x = {{x}_{ * }}$, тогда $\psi (\tilde {x}) - \psi ({{x}_{ * }}) \leqslant \widetilde \delta $. Таким образом, из $\tilde {x} \in {\text{Arg}}\min _{{x \in Q}}^{{\widetilde \delta }}\psi (x)$ следует, что $\tilde {x}$ является $\widetilde \delta $-решением по функции. Обратное, вообще говоря, неверно, в доказательстве далее ключевым образом будет использоваться именно условие на $\widetilde \delta $-решение из определения 4, которое является более строгим.

Рассмотрим обобщение алгоритма градиентного спуска для задачи (2) (см. [10]). В данном алгоритме будем предполагать, что дана начальная точка ${{x}_{0}}$, $N$ – количество шагов метода, ${{L}_{0}}$ – константа, которая имеет смысл предположительной “локальной” константы Липшица градиента в точке ${{x}_{0}}$. Также на вход алгоритму подаются последовательности $\{ {{\delta }_{k}}\} _{{k = 0}}^{{N - 1}}$, $\{ {{\tilde {\delta }}_{k}}\} _{{k = 0}}^{{N - 1}}$. Должно быть выполнено, что для любого $k$ существует $({{\delta }_{k}},L)$-модель для $F(x)$ в любой точке $x \in Q$. Последовательность $\{ {{\tilde {\delta }}_{k}}\} _{{k = 0}}^{{N - 1}}$ – точности решения из определения 4, причем в зависимости от задачи они могут быть равными нулю, иметь постоянное значение или меняться от итерации к итерации.

Стоит отметить, что далее нигде явно в методе не будет использоваться константа $L$. Будем считать, что ${{L}_{0}} \leqslant L$, иначе во всех оценках далее следует полагать $L: = max\left( {{{L}_{0}},L} \right)$.

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

Алгоритм

Дано: ${{x}_{0}}$ – начальная точка, $N$ – количество шагов, $\{ {{\delta }_{k}}\} _{{k = 0}}^{{N - 1}}$, $\{ {{\tilde {\delta }}_{k}}\} _{{k = 0}}^{{N - 1}}$ – последовательности и ${{L}_{0}} > 0$.

0 – шаг:

${{L}_{1}}: = \frac{{{{L}_{0}}}}{2}.$

${\mathbf{k}} + 1$ – шаг:

(7)
$\begin{gathered} {{\alpha }_{{k + 1}}}: = \frac{1}{{{{L}_{{k + 1}}}}}, \\ {{\phi }_{{k + 1}}}(x) = V(x,{{x}_{k}}) + {{\alpha }_{{k + 1}}}{{\psi }_{{{{\delta }_{k}}}}}(x,{{x}_{k}}), \\ {{x}_{{k + 1}}}: = \mathop {\arg {{{\min }}^{{\mathop {\widetilde \delta }\nolimits_k }}}}\limits_{x \in Q} {{\phi }_{{k + 1}}}(x). \\ \end{gathered} $
Если выполнено условие
(8)
${{F}_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}}) \leqslant {{F}_{{{{\delta }_{k}}}}}({{x}_{k}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}},{{x}_{k}}) + \frac{{{{L}_{{k + 1}}}}}{2}\mathop {\left\| {{{x}_{{k + 1}}} - {{x}_{k}}} \right\|}\nolimits^2 + {{\delta }_{k}},$
то
${{L}_{{k + 2}}}: = \frac{{{{L}_{{k + 1}}}}}{2}$
и перейти к следующему шагу, иначе
${{L}_{{k + 1}}}: = 2{{L}_{{k + 1}}}$
и повторить текущий шаг.

Замечание 1. Для всех $k \geqslant 0$ выполнено

${{L}_{k}} \leqslant 2L.$
Для $k = 0$ верно из того, что ${{L}_{0}} \leqslant L$. Для $k \geqslant 1$ это следует из того, что мы выйдем из внутреннего цикла, где подбирается ${{L}_{k}}$, ранее, чем ${{L}_{k}}$ станет больше $2L$. Выход из цикла гарантируется тем, что по условию существует $({{\delta }_{k}},L)$-модель для $F(x)$ в любой точке $x \in Q$.

Докажем важную лемму, которая нам пригодится далее.

Лемма 1. Пусть $\psi (x)$ выпуклая функция и

$y = {{\mathop {{\text{argmin}}}\limits_{x \in Q} }^{{\tilde {\delta }}}}\{ \psi (x) + V(x,z)\} .$
Тогда выполнено неравенство

$\psi (x) + V(x,z) \geqslant \psi (y) + V(y,z) + V(x,y) - \widetilde \delta \quad \forall x \in Q.$

Доказательство. По определению 4 имеем

$\exists g \in \partial \psi (y),\quad \langle g + {{\nabla }_{y}}V(y,z),x - y\rangle \geqslant - \widetilde \delta \quad \forall x \in Q.$
Тогда неравенство
$\psi (x) - \psi (y) \geqslant \langle g,x - y\rangle \geqslant \left\langle {{{\nabla }_{y}}V(y,z),\;y - x} \right\rangle - \widetilde \delta $
и равенство
$\begin{gathered} \langle {{\nabla }_{y}}V(y,z),y - x\rangle = \langle \nabla d(y) - \nabla d(z),y - x\rangle = d(y) - d(z) - \langle \nabla d(z),y - z\rangle + d(x) - \\ - \;d(y) - \langle \nabla d(y),x - y\rangle - d(x) + d(z) + \langle \nabla d(z),x - z\rangle = V(y,z) + V(x,y) - V(x,z) \\ \end{gathered} $
завершают доказательство.

Лемма 2. Для любого $x \in Q$ выполнено неравенство

${{\alpha }_{{k + 1}}}F({{x}_{{k + 1}}}) - {{\alpha }_{{k + 1}}}F(x) \leqslant V(x,{{x}_{k}}) - V(x,{{x}_{{k + 1}}}) + {{\tilde {\delta }}_{k}} + 2{{\delta }_{k}}{{\alpha }_{{k + 1}}}.$

Доказательство. Рассмотрим цепочку неравенств:

$\begin{gathered} F({{x}_{{k + 1}}})\mathop \leqslant \limits^{(8),\;(6)} {{F}_{{{{\delta }_{k}}}}}({{x}_{k}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}},{{x}_{k}}) + \tfrac{{{{L}_{{k + 1}}}}}{2}{{\left\| {{{x}_{{k + 1}}} - {{x}_{k}}} \right\|}^{2}} + 2{{\delta }_{k}} \leqslant \\ \leqslant {{F}_{{{{\delta }_{k}}}}}({{x}_{k}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}},{{x}_{k}}) + \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V({{x}_{{k + 1}}},{{x}_{k}}) + 2{{\delta }_{k}}{{ \leqslant }_{}} \\ \end{gathered} $
$\begin{gathered} \leqslant \;{{F}_{{{{\delta }_{k}}}}}({{x}_{k}}) + {{\psi }_{{{{\delta }_{k}}}}}(x,{{x}_{k}}) + \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V(x,{{x}_{k}}) - \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V(x,{{x}_{{k + 1}}}) + \tfrac{{\mathop {\widetilde \delta }\nolimits_k }}{{{{\alpha }_{{k + 1}}}}} + 2{{\delta }_{k}}\mathop \leqslant \limits^{(4)} \\ \leqslant F(x) + \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V(x,{{x}_{k}}) - \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V(x,{{x}_{{k + 1}}}) + \tfrac{{\mathop {\widetilde \delta }\nolimits_k }}{{{{\alpha }_{{k + 1}}}}} + 2{{\delta }_{k}}. \\ \end{gathered} $

Неравенство следует из леммы 1 с $\psi (x) = {{\alpha }_{{k + 1}}}{{\psi }_{{{{\delta }_{k}}}}}(x,{{x}_{k}})$ и левой части (4).

Теорема 1. Пусть $V({{x}_{ * }},{{x}_{0}}) \leqslant {{R}^{2}}$, где ${{x}_{0}}$ – начальная точка, а ${{x}_{ * }}$ – ближайшая точка минимума к точке ${{x}_{0}}$ в смысле дивергенции Брэгмана, и

${{\bar {x}}_{N}} = \frac{1}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{x}_{{k + 1}}}.$
Для предложенного алгоритма выполнено следующее неравенство:

$F({{\bar {x}}_{N}}) - F({{x}_{ * }}) \leqslant \frac{{2L{{R}^{2}}}}{N} + \frac{{2L}}{N}\sum\limits_{k = 0}^{N - 1} \,{{\tilde {\delta }}_{k}} + \frac{2}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}}.$

Доказательство. Суммируя неравенство из леммы 2 по $k = 0,...,N - 1$, получаем

$\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}F({{x}_{{k + 1}}}) - {{A}_{N}}F(x) \leqslant V(x,{{x}_{0}}) - V(x,{{x}_{N}}) + \sum\limits_{k = 0}^{N - 1} \,{{\tilde {\delta }}_{k}} + 2\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}}.$
Если взять $x = {{x}_{ * }}$, то получим
$\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}F({{x}_{{k + 1}}}) - {{A}_{N}}F({{x}_{ * }}) \leqslant {{R}^{2}} - V({{x}_{ * }},{{x}_{N}}) + \sum\limits_{k = 0}^{N - 1} \,{{\tilde {\delta }}_{k}} + 2\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}}.$
Используя условие $V({{x}_{ * }},{{x}_{N}}) \geqslant 0$, получаем
$\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}F({{x}_{{k + 1}}}) - {{A}_{N}}F({{x}_{ * }}) \leqslant {{R}^{2}} + \sum\limits_{k = 0}^{N - 1} \,{{\tilde {\delta }}_{k}} + 2\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}}.$
Разделим обе части неравенства на ${{A}_{N}}$ и получим
$\frac{1}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}F({{x}_{{k + 1}}}) - F({{x}_{ * }}) \leqslant \frac{{{{R}^{2}}}}{{{{A}_{N}}}} + \frac{1}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\tilde {\delta }}_{k}} + \frac{2}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}}.$
Если воспользоваться выпуклостью $F(x)$, то будет верно

$\begin{gathered} F(\mathop {\bar {x}}\nolimits_N ) - F({{x}_{ * }}) \leqslant \frac{{{{R}^{2}}}}{{{{A}_{N}}}} + \frac{1}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{{\tilde {\delta }}}_{k}} + \frac{2}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}} \leqslant \\ {{ \leqslant }_{}}\;\frac{{2L{{R}^{2}}}}{N} + \frac{{2L}}{N}\sum\limits_{k = 0}^{N - 1} \,{{{\tilde {\delta }}}_{k}} + \frac{2}{{{{A}_{N}}}}\sum\limits_{k = 0}^{N - 1} \,{{\alpha }_{{k + 1}}}{{\delta }_{k}}. \\ \end{gathered} $

Неравенство следует из замечания 1 и ${{\alpha }_{{k + 1}}} = 1{\text{/}}{{L}_{{k + 1}}}$.

3. БЫСТРЫЙ ГРАДИЕНТНЫЙ МЕТОД С ОРАКУЛОМ, ИСПОЛЬЗУЮЩИМ $(\delta ,L)$-МОДЕЛЬ

Рассмотрим быстрый вариант алгоритма из разд. 2.

Алгоритм

Дано: ${{x}_{0}}$ – начальная точка, $N$ – количество шагов, $\{ {{\delta }_{k}}\} _{{k = 0}}^{{N - 1}}$, $\{ {{\tilde {\delta }}_{k}}\} _{{k = 0}}^{{N - 1}}$ – последовательности и ${{L}_{0}} > 0$.

0 – шаг:

${{y}_{0}}: = {{x}_{0}},\;{{u}_{0}}: = {{x}_{0}},\;{{L}_{1}}: = \tfrac{{{{L}_{0}}}}{2},\;{{\alpha }_{0}}: = 0,\;{{A}_{0}}: = {{\alpha }_{0}}.$

${\mathbf{k}} + 1$ – шаг:

Найти наибольший корень

(9)
$\begin{gathered} {{\alpha }_{{k + 1}}}:{{A}_{k}} + {{\alpha }_{{k + 1}}} = {{L}_{{k + 1}}}\alpha _{{k + 1}}^{2}, \\ {{A}_{{k + 1}}}: = {{A}_{k}} + {{\alpha }_{{k + 1}}}, \\ {{y}_{{k + 1}}}: = \frac{{{{\alpha }_{{k + 1}}}{{u}_{k}} + {{A}_{k}}{{x}_{k}}}}{{{{A}_{{k + 1}}}}}, \\ \end{gathered} $
(10)
$\begin{gathered} {{\phi }_{{k + 1}}}(x) = V(x,{{u}_{k}}) + {{\alpha }_{{k + 1}}}{{\psi }_{{{{\delta }_{k}}}}}(x,{{y}_{{k + 1}}}), \\ {{u}_{{k + 1}}}: = {{\mathop {\arg \min }\limits_{x \in Q} }^{{{{{\tilde {\delta }}}_{k}}}}}{{\phi }_{{k + 1}}}(x), \\ \end{gathered} $
(11)
${{x}_{{k + 1}}}: = \frac{{{{\alpha }_{{k + 1}}}{{u}_{{k + 1}}} + {{A}_{k}}{{x}_{k}}}}{{{{A}_{{k + 1}}}}}.$
Если выполнено условие
(12)
${{F}_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}}) \leqslant {{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}},{{y}_{{k + 1}}}) + \frac{{{{L}_{{k + 1}}}}}{2}{{\left\| {{{x}_{{k + 1}}} - {{y}_{{k + 1}}}} \right\|}^{2}} + {{\delta }_{k}},$
то
${{L}_{{k + 2}}}: = \frac{{{{L}_{{k + 1}}}}}{2}$
и перейти к следующему шагу, иначе
${{L}_{{k + 1}}}: = 2{{L}_{{k + 1}}}$
и повторить текущий шаг.

Лемма 3. Пусть для последовательности ${{\alpha }_{k}}$ выполнено

${{\alpha }_{0}} = 0,\quad {{A}_{k}} = \sum\limits_{i = 0}^k \,{{\alpha }_{i}},\quad {{A}_{k}} = {{L}_{k}}\alpha _{k}^{2},$
где ${{L}_{k}} \leqslant 2L$ для любого $k \geqslant 0$ (замечание 1). Тогда для любого $k \geqslant 1$ верно следующее неравенство:

(13)
${{A}_{k}} \geqslant \frac{{{{{(k + 1)}}^{2}}}}{{8L}}.$

Доказательство. Пусть $k = 1$. Таким образом,

${{\alpha }_{1}} = {{L}_{1}}\alpha _{1}^{2}$
и
${{A}_{1}} = {{\alpha }_{1}} = \frac{1}{{{{L}_{1}}}} \geqslant \frac{1}{{2L}}.$
Пусть $k \geqslant 2$, тогда верны следующие эквивалентные равенства:
${{L}_{{k + 1}}}\alpha _{{k + 1}}^{2} = {{A}_{{k + 1}}} \Leftrightarrow {{L}_{{k + 1}}}\alpha _{{k + 1}}^{2} = {{A}_{k}} + {{\alpha }_{{k + 1}}} \Leftrightarrow {{L}_{{k + 1}}}\alpha _{{k + 1}}^{2} - {{\alpha }_{{k + 1}}} - {{A}_{k}} = 0.$
Решая данное квадратное уравнение, будем брать наибольший корень:
${{\alpha }_{{k + 1}}} = \frac{{1 + \sqrt {1 + 4{{L}_{{k + 1}}}{{A}_{k}}} }}{{2{{L}_{{k + 1}}}}}.$
По индукции, пусть неравенство (13) верно для $k$, тогда имеем
${{\alpha }_{{k + 1}}} = \frac{1}{{2{{L}_{{k + 1}}}}} + \sqrt {\frac{1}{{4L_{{k + 1}}^{2}}} + \frac{{{{A}_{k}}}}{{{{L}_{{k + 1}}}}}} \geqslant \frac{1}{{2{{L}_{{k + 1}}}}} + \sqrt {\frac{{{{A}_{k}}}}{{{{L}_{{k + 1}}}}}} \geqslant \frac{1}{{4L}} + \frac{1}{{\sqrt {2L} }}\frac{{k + 1}}{{2\sqrt {2L} }} = \frac{{k + 2}}{{4L}}.$
Последнее неравенство следует из индукционного предположения. В конечном счете получаем, что
${{\alpha }_{{k + 1}}} \geqslant \frac{{k + 2}}{{4L}}$
и

${{A}_{{k + 1}}} = {{A}_{k}} + {{\alpha }_{{k + 1}}} = \frac{{{{{(k + 1)}}^{2}}}}{{8L}} + \frac{{k + 2}}{{4L}} \geqslant \frac{{{{{(k + 2)}}^{2}}}}{{8L}}.$

Докажем основную лемму.

Лемма 4. Для любого $x \in Q$ выполнено неравенство

${{A}_{{k + 1}}}F({{x}_{{k + 1}}}) - {{A}_{k}}F({{x}_{k}}) + V(x,{{u}_{{k + 1}}}) - V(x,{{u}_{k}}) \leqslant {{\alpha }_{{k + 1}}}F(x) + 2{{\delta }_{k}}{{A}_{{k + 1}}} + {{\tilde {\delta }}_{k}}.$

Доказательство. Рассмотрим цепочку неравенств

$F({{x}_{{k + 1}}})\, \leqslant \,{{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}})\, + \,{{\psi }_{{{{\delta }_{k}}}}}({{x}_{{k + 1}}},{{y}_{{k + 1}}})\, + \,\tfrac{{{{L}_{{k + 1}}}}}{2}\mathop {\left\| {{{x}_{{k + 1}}} - {{y}_{{k + 1}}}} \right\|}\nolimits^2 \, + \,2{{\delta }_{k}}\mathop = \limits^{(11)} {{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}})\, + \,{{\psi }_{{{{\delta }_{k}}}}}(\tfrac{{{{\alpha }_{{k + 1}}}{{u}_{{k + 1}}} + {{A}_{k}}{{x}_{k}}}}{{{{A}_{{k + 1}}}}},{{y}_{{k + 1}}})\, + $
$ + \;\tfrac{{{{L}_{{k + 1}}}}}{2}\mathop {\left\| {\tfrac{{{{\alpha }_{{k + 1}}}{{u}_{{k + 1}}} + {{A}_{k}}{{x}_{k}}}}{{{{A}_{{k + 1}}}}} - {{y}_{{k + 1}}}} \right\|}\nolimits^2 + 2{{\delta }_{k}}\mathop \leqslant \limits^{{\text{О п р }}.\;3,\;(9)} {{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + \tfrac{{{{\alpha }_{{k + 1}}}}}{{{{A}_{{k + 1}}}}}{{\psi }_{{{{\delta }_{k}}}}}({{u}_{{k + 1}}},{{y}_{{k + 1}}}) + $
$ + \;\tfrac{{{{A}_{k}}}}{{{{A}_{{k + 1}}}}}{{\psi }_{{{{\delta }_{k}}}}}({{x}_{k}},{{y}_{{k + 1}}}) + \tfrac{{{{L}_{{k + 1}}}\alpha _{{k + 1}}^{2}}}{{2A_{{k + 1}}^{2}}}{{\left\| {{{u}_{{k + 1}}} - {{u}_{k}}} \right\|}^{2}} + 2{{\delta }_{k}} = \tfrac{{{{A}_{k}}}}{{{{A}_{{k + 1}}}}}({{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{k}},{{y}_{{k + 1}}})) + $
$ + \;\tfrac{{{{\alpha }_{{k + 1}}}}}{{{{A}_{{k + 1}}}}}({{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{u}_{{k + 1}}},{{y}_{{k + 1}}})) + \tfrac{{{{L}_{{k + 1}}}\alpha _{{k + 1}}^{2}}}{{2A_{{k + 1}}^{2}}}\mathop {\left\| {{{u}_{{k + 1}}} - {{u}_{k}}} \right\|}\nolimits^2 + 2{{\delta }_{k}}{{ = }_{}}$
$ = \;\tfrac{{{{A}_{k}}}}{{{{A}_{{k + 1}}}}}({{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{k}},{{y}_{{k + 1}}})) + \tfrac{{{{\alpha }_{{k + 1}}}}}{{{{A}_{{k + 1}}}}}({{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{u}_{{k + 1}}},{{y}_{{k + 1}}}) + \tfrac{1}{{2{{\alpha }_{{k + 1}}}}}{{\left\| {{{u}_{{k + 1}}} - {{u}_{k}}} \right\|}^{2}}) + 2{{\delta }_{k}} \leqslant $
$ \leqslant \;\tfrac{{{{A}_{k}}}}{{{{A}_{{k + 1}}}}}({{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{x}_{k}},{{y}_{{k + 1}}})) + \tfrac{{{{\alpha }_{{k + 1}}}}}{{{{A}_{{k + 1}}}}}({{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}({{u}_{{k + 1}}},{{y}_{{k + 1}}}) + \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V({{u}_{{k + 1}}},{{u}_{k}})) + 2{{\delta }_{k}}{{ \leqslant }_{}}$
$ \leqslant \;\tfrac{{{{A}_{k}}}}{{{{A}_{{k + 1}}}}}F({{x}_{k}}) + \tfrac{{{{\alpha }_{{k + 1}}}}}{{{{A}_{{k + 1}}}}}\left( {{{F}_{{{{\delta }_{k}}}}}({{y}_{{k + 1}}}) + {{\psi }_{{{{\delta }_{k}}}}}(x,{{y}_{{k + 1}}}) + \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V(x,{{u}_{k}}) - \tfrac{1}{{{{\alpha }_{{k + 1}}}}}V(x,{{u}_{{k + 1}}}) + \tfrac{{\mathop {\widetilde \delta }\nolimits_k }}{{{{\alpha }_{{k + 1}}}}}} \right) + 2{{\delta }_{k}}\mathop \leqslant \limits^{(4)} $
$ \leqslant \tfrac{{{{A}_{k}}}}{{{{A}_{{k + 1}}}}}F({{x}_{k}}) + \tfrac{{{{\alpha }_{{k + 1}}}}}{{{{A}_{{k + 1}}}}}F(x) + \tfrac{1}{{{{A}_{{k + 1}}}}}V(x,{{u}_{k}}) - \tfrac{1}{{{{A}_{{k + 1}}}}}V(x,{{u}_{{k + 1}}}) + 2{{\delta }_{k}} + \tfrac{{\mathop {\widetilde \delta }\nolimits_k }}{{{{\alpha }_{{k + 1}}}}}.$

Неравенство следует из равенства ${{A}_{k}} = {{L}_{k}}\alpha _{k}^{2}$. Неравенство следует из леммы 1 с $\psi (x) = {{\alpha }_{{k + 1}}}{{\psi }_{{{{\delta }_{k}}}}}(x,{{y}_{{k + 1}}})$ и левой части (4).

Теорема 2. Пусть $V({{x}_{ * }},{{x}_{0}}) \leqslant {{R}^{2}}$, где ${{x}_{0}}$ – начальная точка, а ${{x}_{ * }}$ – ближайшая точка минимума к точке ${{x}_{0}}$ в смысле дивергенции Брэгмана. Для предложенного алгоритма выполнено следующее неравенство:

$F({{x}_{N}}) - F({{x}_{ * }}) \leqslant \frac{{8L{{R}^{2}}}}{{{{{(N + 1)}}^{2}}}} + \frac{{2\sum\limits_{k = 0}^{N - 1} {{{\delta }_{k}}{{A}_{{k + 1}}}} }}{{{{A}_{N}}}} + \frac{{8L\sum\limits_{k = 0}^{N - 1} {{{{\tilde {\delta }}}_{k}}} }}{{{{{(N + 1)}}^{2}}}}.$

Доказательство. Суммируя неравенство из леммы 18 по $k = 0,\;...,\;N - 1$, получаем

$\begin{gathered} {{A}_{N}}F({{x}_{N}}) - {{A}_{0}}F({{x}_{0}}) + V(x,{{u}_{N}}) - V(x,{{u}_{0}}) \leqslant ({{A}_{N}} - {{A}_{0}})F(x) + 2\sum\limits_{k = 0}^{N - 1} \,{{\delta }_{k}}{{A}_{{k + 1}}} + \sum\limits_{k = 0}^{N - 1} \,{{{\tilde {\delta }}}_{k}} \Leftrightarrow \\ \Leftrightarrow {{A}_{N}}F({{x}_{N}}) + V(x,{{u}_{N}}) - V(x,{{u}_{0}}) \leqslant {{A}_{N}}F(x) + 2\sum\limits_{k = 0}^{N - 1} \,{{\delta }_{k}}{{A}_{{k + 1}}} + \sum\limits_{k = 0}^{N - 1} \,{{{\tilde {\delta }}}_{k}}. \\ \end{gathered} $
Если взять $x = {{x}_{ * }}$, то будет верно неравенство
${{A}_{N}}(F({{x}_{N}}) - {{F}_{ * }}) \leqslant {{R}^{2}} + 2\sum\limits_{k = 0}^{N - 1} \,{{\delta }_{k}}{{A}_{{k + 1}}} + \sum\limits_{k = 0}^{N - 1} \,{{\tilde {\delta }}_{k}}.$
Разделим обе части неравенства на ${{A}_{N}}$ и в конечном счете получим, что

$F({{x}_{N}}) - {{F}_{ * }} \leqslant \frac{{{{R}^{2}}}}{{{{A}_{N}}}} + \frac{{2\sum\limits_{k = 0}^{N - 1} {{{\delta }_{k}}{{A}_{{k + 1}}}} }}{{{{A}_{N}}}} + \frac{{\sum\limits_{k = 0}^{N - 1} {{{{\tilde {\delta }}}_{k}}} }}{{{{A}_{N}}}}{{ \leqslant }_{}}\frac{{8L{{R}^{2}}}}{{{{{(N + 1)}}^{2}}}} + \frac{{2\sum\limits_{k = 0}^{N - 1} {{{\delta }_{k}}{{A}_{{k + 1}}}} }}{{{{A}_{N}}}} + \frac{{8L\sum\limits_{k = 0}^{N - 1} {{{{\tilde {\delta }}}_{k}}} }}{{{{{(N + 1)}}^{2}}}}.$

Неравенство следует из леммы 3.

4. СЛЕДСТВИЯ

4.1. Быстрый градиентный метод

Предположим, что $F(x)$ – гладкая выпуклая функция с $L$-липшицевым градиентом в норме $\left\| \; \right\|$, тогда (см. [11])

(14)
$0 \leqslant F(x) - F(y) - \langle \nabla F(y),x - y\rangle \leqslant \frac{L}{2}{{\left\| {x - y} \right\|}^{2}}\quad \forall x,y \in Q.$
Таким образом, получаем, что ${{\psi }_{{{{\delta }_{k}}}}}(x,y) = \langle \nabla F(y),x - y\rangle $, ${{F}_{{{{\delta }_{k}}}}}(y) = F(y)$ и ${{\delta }_{k}} = 0$ $\forall k$. Помимо этого, будем предполагать, что промежуточную задачу мы можем решать точно, поэтому ${{\tilde {\delta }}_{k}} = 0$ для любого $k$. Получаем следующую скорость сходимости для быстрого варианта метода (разд. 3 и теорема 2):

$F({{x}_{N}}) - F({{x}_{ * }}) \leqslant \frac{{8L{{R}^{2}}}}{{{{{(N + 1)}}^{2}}}}.$

Данная скорость сходимости является оптимальной с точностью до числового множителя (лучше константы 2 получить нельзя [6], в то время, как у нас константа 8).

4.2. Сравнение градиентного и быстрого градиентного метода

Предположим, что у нас для задачи (2) имеется $(\delta ,L)$-оракул из [11] и будем считать, что промежуточную задачу в смысле определения 4 мы можем решать на каждом шаге с точностью $\widetilde \delta $, тогда (теоремы 1 и 2) верны следующие неравенства:

$F(\mathop {\bar {x}}\nolimits_N ) - F({{x}_{ * }}) \leqslant \frac{{2L{{R}^{2}}}}{N} + 2L\widetilde \delta + 2\delta ,$
$F({{x}_{N}}) - F({{x}_{ * }}) \leqslant \frac{{8L{{R}^{2}}}}{{{{{(N + 1)}}^{2}}}} + \frac{{8L\widetilde \delta }}{{N + 1}} + 2N\delta ,$
где $\mathop {\bar {x}}\nolimits_N $ – точка из теоремы 1, а ${{x}_{N}}$ – точка из теоремы 2. Мы получаем, что быстрый вариант более устойчив к ошибкам $\widetilde \delta $, возникающим при решении промежуточных задач, но при этом он накапливает ошибки $\delta $, которые возникают при вызове $(\delta ,L)$-оракула. Стоит отметить, что существует промежуточный градиентный метод [13] (для стохастического случая [14]), для которого можно получить оценку вида
$\mathcal{O}(1)\frac{{L{{R}^{2}}}}{{{{N}^{p}}}} + \mathcal{O}(1){{N}^{{1 - p}}}\widetilde \delta + \mathcal{O}(1){{N}^{{p - 1}}}\delta ,$
где $p \in [1,2]$ можно выбирать произвольным образом и за счет этого уменьшать непрерывно влияние шума, но при этом ухудшать оценку скорости сходимости.

4.3. Универсальный метод

Рассмотрим быструю версию градиентного метода (разд. 3 и теорема 2).

Универсальный метод [15] позволяет применять концепцию $(\delta ,L)$-оракула [11], [15] для решения негладких задач. Будем предполагать, что выполняется условие Гёльдера: существует $\nu \in [0,1]$ такое, что

$\mathop {\left\| {\nabla F(x) - \nabla F(y)} \right\|}\nolimits_ * \leqslant {{L}_{\nu }}{{\left\| {x - y} \right\|}^{\nu }}\quad \forall x,y \in Q.$
Тогда (см. [15]) имеем
(15)
$0 \leqslant F(x) - F(y) - \langle \nabla F(y),x - y\rangle \leqslant \frac{{L(\delta )}}{2}\mathop {\left\| {x - y} \right\|}\nolimits^2 + \delta \quad \forall x,y \in Q,$
где
$L(\delta ) = {{L}_{\nu }}{{\left[ {\frac{{{{L}_{\nu }}}}{{2\delta }}\frac{{1 - \nu }}{{1 + \nu }}} \right]}^{{\tfrac{{1 - \nu }}{{1 + \nu }}}}}$
и $\delta > 0$ – свободный параметр. Получаем, что ${{\psi }_{{{{\delta }_{k}}}}}(x,y) = \langle \nabla F(y),x - y\rangle $, ${{F}_{{{{\delta }_{k}}}}}(y) = F(y)$. Будем предполагать, что промежуточную задачу мы можем решать точно, таким образом, ${{\tilde {\delta }}_{k}} = 0$ для любого $k$. Возьмем
(16)
${{\delta }_{k}} = \epsilon \frac{{{{\alpha }_{{k + 1}}}}}{{4{{A}_{{k + 1}}}}}\quad \forall k,$
где $\epsilon $ – необходимая точность решения по функции.

Из теоремы 2 с нашими предположениями мы имеем следующую скорость сходимости:

(17)
$f({{x}_{N}}) - f({{x}_{ * }}) \leqslant \frac{{{{R}^{2}}}}{{{{A}_{N}}}} + \frac{\epsilon }{2}.$
Как и в статье [15] мы можем показать, что верно следущее неравенство:
${{A}_{N}} \geqslant \frac{{{{N}^{{\tfrac{{1 + 3\nu }}{{1 + \nu }}}}}{{\epsilon }^{{\tfrac{{1 - \nu }}{{1 + \nu }}}}}}}{{{{2}^{{\tfrac{{2 + 4\nu }}{{1 + \nu }}}}}L_{\nu }^{{\tfrac{2}{{1 + \nu }}}}}}.$
Отсюда получаем, что

$N \leqslant \mathop {inf}\limits_{\nu \in [0,1]} \left[ {{{2}^{{\tfrac{{3 + 5\nu }}{{1 + 3\nu }}}}}\mathop {\left( {\frac{{{{L}_{\nu }}{{R}^{{1 + \nu }}}}}{\epsilon }} \right)}\nolimits^{\tfrac{2}{{1 + 3\nu }}} } \right].$

Данная оценка является оптимальной с точностью до числового множителя [16].

4.4. Метод условного градиента

На практике часто вспомогательная задача (10) не может быть решена за разумное время [5], [17]. В работе [18] показывается, что метод условного градиента (Франк–Вульфа) [5], [18], [19] может быть очень эффективен для определенного класса задач. Поэтому вместо ${{\phi }_{{k + 1}}}(x) = V(x,{{u}_{k}}) + {{\alpha }_{{k + 1}}}{{\psi }_{{{{\delta }_{k}}}}}(x,{{y}_{{k + 1}}})$ в (10) используют ${{\tilde {\phi }}_{{k + 1}}}(x) = {{\alpha }_{{k + 1}}}{{\psi }_{{{{\delta }_{k}}}}}(x,{{y}_{{k + 1}}})$. Рассмотрим данную замену с точки зрения ошибки ${{\tilde {\delta }}_{k}}$. Далее будем предполагать, что $F(x)$ – гладкая выпуклая функция с $L$-липшицевым градиентом в норме $\left\| \; \right\|$ и $V(x,y) \leqslant R_{Q}^{2}$ для любого $x,y \in Q$. И пусть

${{u}_{{k + 1}}} = \left( {\arg \min _{{x \in Q}}^{{\mathop {\widetilde \delta }\nolimits_k }}{{\phi }_{{k + 1}}}(x)\;\mathop = \limits^{{\text{def}}} \;\arg {{{\min }}_{{x \in Q}}}{{{\tilde {\phi }}}_{{k + 1}}}(x)} \right),$

тогда

$\begin{gathered} \exists h \in \partial {{\phi }_{{k + 1}}}({{u}_{{k + 1}}}),\quad \exists g \in \partial {{{\tilde {\phi }}}_{{k + 1}}}({{u}_{{k + 1}}}),\langle h,x - {{u}_{{k + 1}}}\rangle = \langle g,x - {{u}_{{k + 1}}}\rangle + \langle {{\nabla }_{{{{u}_{{k + 1}}}}}}V({{u}_{{k + 1}}},{{u}_{k}}),x - {{u}_{{k + 1}}}\rangle \geqslant \\ \geqslant \;\langle {{\nabla }_{{{{u}_{{k + 1}}}}}}V({{u}_{{k + 1}}},{{u}_{k}}),x - {{u}_{{k + 1}}}\rangle = - V({{u}_{{k + 1}}},{{u}_{k}}) - V(x,{{u}_{{k + 1}}}) + V(x,{{u}_{k}}) \geqslant - 2R_{Q}^{2}. \\ \end{gathered} $

В алгоритме будем предполагать, что ${{\tilde {\delta }}_{k}} = 2R_{Q}^{2}$ для любого $k$. Остальное аналогично гладкому случаю с $L$-липшицевым градиентом в норме $\left\| {} \right\|$. Тогда получаем следующую скорость сходимости для быстрого варианта метода (разд. 3 и теорема 2):

$F({{x}_{N}}) - F({{x}_{ * }}) \leqslant \frac{{8L{{R}^{2}}}}{{{{{(N + 1)}}^{2}}}} + \frac{{16LR_{Q}^{2}}}{{N + 1}}.$

Данная оценка с точностью до числового множителя не может быть улучшена для приведенного метода [20].

4.5. Композитная оптимизация

Рассмотрим задачу композитной оптимизации [3]]:

(18)
$F(x)\;\mathop = \limits^{{\text{def}}} \;f(x) + h(x) \to \mathop {min}\limits_{x \in Q} ,$
где $f(x)$ – гладкая выпуклая функция с $L$-липшицевым градиентом в норме $\left\| {} \right\|$ и $h(x)$ – выпуклая функция (в общем случае негладкая). Для данной задачи верно неравенство
(19)
$0 \leqslant F(x) - F(y) - \langle \nabla f(y),x - y\rangle - h(x) + h(y) \leqslant \frac{L}{2}{{\left\| {x - y} \right\|}^{2}}\quad \forall x,y \in Q.$
Таким образом, мы можем взять ${{\psi }_{{{{\delta }_{k}}}}}(x,y) = \langle \nabla f(y),x - y\rangle + h(x) - h(y)$, ${{F}_{{{{\delta }_{k}}}}}(y) = F(y)$ и ${{\delta }_{k}} = 0$ для любого $k$. Получается, что для данной задачи обычный и ускоренный варианты метода будут работать без изменений. Стоит отметить, что часть сложности задачи мы таким образом переносим в (7) или (10). Если в гладком случае во вспомогательной задаче стоит функция вида $V(x,{{u}_{k}}) + {{\alpha }_{{k + 1}}}\langle \nabla f({{y}_{{k + 1}}}),x - {{y}_{{k + 1}}}\rangle $, то в данной задаче (18) добавляется слагаемое $h(x)$, и в конечном счете нужно решать более сложную задачу на каждом шаге вида $V(x,{{u}_{k}}) + $ $ + \;{{\alpha }_{{k + 1}}}\left( {\langle \nabla f({{y}_{{k + 1}}}),x - {{y}_{{k + 1}}}\rangle + h(x) - h({{y}_{{k + 1}}})} \right)$.

4.6. Прокс-метод

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

(20)
$F(x) \to \mathop {min}\limits_{x \in Q} ,$
где $F(x)$ – в общем случае негладкая выпуклая функция. Можем в описанном выше подходе выбрать ${{\psi }_{{{{\delta }_{k}}}}}(x,y) = F(x) - F(y)$, ${{F}_{{{{\delta }_{k}}}}}(y) = F(y)$ и ${{\delta }_{k}} = 0$ для любого $k$. Условие (4) будет выполняться при любом выборе $L \geqslant 0$. Методы из разд. 2 и разд. 3 являются, вообще говоря, адаптивными в том смысле, что “локальная” константа Липшица градиента ${{L}_{k}}$ подбирается во время работы метода. Зафиксируем произвольную константу $L \geqslant 0$, возьмем все ${{L}_{k}}$ равными $L$, не подбирая их во внутреннем цикле. При этом довольно легко показать, что метод и все оценки останутся без изменений. Тогда промежуточный шаг для метода из разд. 2 будет выглядеть следующим образом:
(21)
${{x}_{{k + 1}}}: = {{\mathop {\arg \min }\limits_{x \in Q} }^{{{{{\tilde {\delta }}}_{k}}}}}\left[ {LV(x,{{x}_{k}}) + F(x)} \right].$
Данный метод называется проксимальным методом [20], [21], он может быть эффективным в ряде задач [22]. Для негладкой функции алгоритм из разд. 3 сходится по оценкам теоремы 2, что противоречит нижним оценкам для негладких функций [1], [2]. Однако задача (21), вообще говоря, может быть решена только приближенно [23], [24]. Более детальный анализ показывает [10], что общее число обращений к оракулу за субградиентом функции $f(x)$ не противоречит нижним оценкам [1], [2] для негладких задач, и более того, соответствует, им.

4.7. Суперпозиция функций

Рассмотрим следующую задачу (см. [25]–[27]):

(22)
$F(x)\;\mathop = \limits^{{\text{def}}} \;f({{f}_{1}}(x), \ldots ,{{f}_{m}}(x)) \to \mathop {min}\limits_{x \in Q} ,$
где ${{f}_{k}}(x)$ – гладкая выпуклая функция с ${{L}_{k}}$-липшицевым градиентом в норме $\left\| {} \right\|$ для любого $k$. Функция $f(x)$ является $M$-липшицевой выпуклой функцией относительно ${{L}_{1}}$-нормы, неубывающей по каждому из своих аргументов. Как следствие (см. [28], [26]), функция $F(x)$ так же является выпуклой функцией и выполняется следующее неравенство [26]:
$0 \leqslant F(x) - f({{f}_{1}}(y) + \langle \nabla {{f}_{1}}(y),x - y\rangle , \ldots ,{{f}_{m}}(y) + \langle \nabla {{f}_{m}}(y),x - y\rangle ) \leqslant M\frac{{\sum\limits_{i = 1}^m {{{L}_{i}}} }}{2}{{\left\| {x - y} \right\|}^{2}}\quad \forall x,y \in Q.$
И верно
$\begin{gathered} 0 \leqslant F(x) - F(y) - f({{f}_{1}}(y) + \langle \nabla {{f}_{1}}(y),x - y\rangle , \ldots ,{{f}_{m}}(y) + \langle \nabla {{f}_{m}}(y),x - y\rangle ) + F(y) \leqslant \\ \leqslant M\frac{{\sum\limits_{i = 1}^m {{{L}_{i}}} }}{2}\mathop {\left\| {x - y} \right\|}\nolimits^2 \quad \forall x,y \in Q. \\ \end{gathered} $
Мы можем взять ${{\psi }_{{{{\delta }_{k}}}}}(x,y) = f({{f}_{1}}(y) + \langle \nabla {{f}_{1}}(y),x - y\rangle , \ldots ,{{f}_{m}}(y) + \langle \nabla {{f}_{m}}(y),x - y\rangle ) - F(y)$, ${{F}_{{{{\delta }_{k}}}}}(y) = F(y)$ и ${{\delta }_{k}} = 0$ для любого $k$. Как и в задаче (18), оценки на скорость сходимости сохраняются, но при этом вспомогательные задачи (7) и (10) могут сильно усложниться. Данная задача может включать обширное количество частных случаев [26], [25]: гладкая оптимизация, негладкая оптимизация, минимаксная задача [1], композитная оптимизация, задача с регуляризацией.

4.8. Дополнительные примеры

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

1. Рассматривается следующая минмин задача [29]:

(23)
$f(x)\;\mathop = \limits^{{\text{def}}} \;\mathop {min}\limits_{y \in Q} F(y,x) \to \mathop {min}\limits_{x \in {{\mathbb{R}}^{n}}} .$
Пусть $F(y,x)$ – гладкая и выполнено условие:
$\mathop {\left\| {\nabla F(y{\kern 1pt} ',x{\kern 1pt} ') - \nabla F(y,x)} \right\|}\nolimits_2 \leqslant L{{\left\| {(y{\kern 1pt} ',x{\kern 1pt} ') - (y,x)} \right\|}_{2}}\quad \forall y,y{\kern 1pt} ' \in Q,\quad \forall x,x{\kern 1pt} ' \in {{\mathbb{R}}^{n}}.$
Тогда (из [30]), если можно найти такую ${{\tilde {y}}_{\delta }}(x) \in Q$, что верно неравенство
$\langle {{\nabla }_{y}}F({{\tilde {y}}_{\delta }}(x),x),y - {{\tilde {y}}_{\delta }}(x)\rangle \geqslant - \delta \quad \forall y \in Q,$
то
$F({{\tilde {y}}_{\delta }}(x),x) - f(x) \leqslant \delta ,\quad {{\left\| {\nabla f(x{\kern 1pt} ') - \nabla f(x)} \right\|}_{2}} \leqslant L\mathop {\left\| {x{\kern 1pt} {\text{'}} - x} \right\|}\nolimits_2 ,$
и
$\left( {{{F}_{\delta }}(x) = F({{{\tilde {y}}}_{\delta }}(x),x) - 2\delta ,{{\psi }_{\delta }}(z,x) = \langle {{\nabla }_{y}}F({{{\tilde {y}}}_{\delta }}(x),x),z - x\rangle } \right)$
будет $(6\delta ,2L)$-моделью для функции $f(x)$ в точке $x$.

Таким образом, мы получаем $(6\delta ,2L)$-модель, которая может быть использована для решения (23).

2. Рассматривается следующая задача поиска седловой точки [29]:

(24)
$f(x)\;\mathop = \limits^{{\text{def}}} \;\mathop {\max }\limits_{y \in Q} {\kern 1pt} [\langle x,b - Ay\rangle - \phi (y)] \to \mathop {min}\limits_{x \in {{\mathbb{R}}^{n}}} ,$
где $\phi (y)$ является $\mu $-сильно выпуклой относительно $p$-нормы, $1 \leqslant p \leqslant 2$. Тогда из [11] функция $f(x)$ – гладкая функция с константой Липшица градиента в 2-норме
$L = \frac{1}{\mu }\mathop {max}\limits_{{{{\left\| y \right\|}}_{p}} \leqslant 1} \mathop {\left\| {Ay} \right\|}\nolimits_2^2 .$
Если ${{y}_{\delta }}(x)$ – решение вспомогательной задачи максимизации с точностью по функции $\delta $, то пара
$\left( {{{F}_{\delta }}(x) = \langle x,b - A{{y}_{\delta }}(x)\rangle - \phi ({{y}_{\delta }}(x)),{{\psi }_{\delta }}(z,x) = \langle b - A{{y}_{\delta }}(x),z - x\rangle } \right)$
будет $(\delta ,2L)$-моделью для функции $f(x)$ в точке $x$.

3. Рассматривается следующая функция (следует сравнить c (21)):

(25)
$f(x)\;\mathop = \limits^{{\text{def}}} \;\mathop {min}\limits_{y \in Q} \underbrace {\left\{ {\phi (y) + \frac{L}{2}\mathop {\left\| {y - x} \right\|}\nolimits_2^2 } \right\}}_{\Lambda (x,y)}.$
Пусть $\phi (y)$ – выпуклая функция и
$\mathop {max}\limits_{y \in Q} \left\{ {\Lambda (x,y(x)) - \Lambda (x,y) + \frac{L}{2}\mathop {\left\| {y - y(x)} \right\|}\nolimits_2^2 } \right\} \leqslant \delta .$
Тогда из [11] верно, что
$\left( {{{F}_{\delta }}(x) = \phi (y(x)) + \frac{L}{2}\left\| {y(x) - x} \right\|_{2}^{2} - \delta ,{{\psi }_{\delta }}(z,x) = \langle L(x - y(x)),z - x\rangle } \right)$
будет $(\delta ,L)$-моделью для функции $f(x)$ в точке $x$.

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

В работе представлен градиентный и быстрый градиентный метод для $(\delta ,L)$-модели. Приведены алгоритмы методов и оценки скоростей сходимости. В разд. 4 показано, что данные методы могут быть довольно сильным инструментом для решения большого класса задач. Стоит отметить, что список задач из разд. 4, который покрывает данная работа, не исчерпывает полный потенциал концепции. Мы верим, что данный подход может быть применим во многих других проблемах, включая стохастическую, покомпонентную, безградиентную оптимизацию [31]. Также можно показать, что предложенные в статье алгоритмы являются прямо-двойственными [32]. Детали планируется изложить в будущих исследованиях.

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

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

  1. Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010. 262 с.

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

  3. Nesterov Yu. Gradient methods for minimizing composite functions // Math. Program. 2013. V. 140. № 1. P. 125–161.

  4. Devolder O., Glineur F., Mesterov Yu. First-order methods with inexact oracle: the strongly convex case // CORE Discussion Paper 2013/16. 2013. URL https://www.uclouvain.be/cps/ucl/doc/core/documents/ coredp2013_16web.pdf.

  5. Ben-Tal A., Nemirovski A. Lectures on Modern Convex Optimization. Philadelphia: SIAM, 2015. URL: http//www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf.

  6. Taylor A., Hendrickx J., Glineur F. Exact worst-case performance of first-order methods for composite convex optimization // SIAM. J. Optimizat. 2017. V. 27. № 3. P. 1283–1313.

  7. Ochs P., Fadili J., Brox T. Non-smooth non-convex Bregman minimization: Unification and new algorithms // e-print. arXiv:1707.02278. 2017.

  8. Mairal J. Optimization with first-order surrogate functions // ICML, 2013. P. 783–791.

  9. Gupta M.D., Huang T. Bregman distance to l1 regularized logistic regression // ICPR, 2008.

  10. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска // e-print. arXiv: 1711.00394. 2018.

  11. Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle // Math. Program. 2014. V. 146. № 1–2. P. 37–75.

  12. Devolder O. Exactness, inexaсtness and stochasticity in first-order methods for large-scale convex optimization. PhD thesis. CORE UCL, 2013.

  13. Devolder O., Glineur F., Mesterov Yu. Intermediate gradient methods for smooth convex problems with inexact oracle // CORE Discussion Paper. 2013/17. 2013.

  14. Dvurechensky P., Gasnikov A. Stochastic intermediate gradient method for convex Problems with inexact stochastic oracle // J. of Optimizat. Theory and App. 2016. V. 171. № 1. P. 121–145.

  15. Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Programm. 2015. V. 152. № 1–2. P. 381–404.

  16. Guzmán C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization // J. of Complexity. 2015. V. 31. № 1. P. 1–14.

  17. Nesterov Yu. Complexity bounds for primal-dual methods minimizing the model of objective function // Math. Program. 2018. V. 171. № 1–2. P. 311–330.

  18. Jaggi M. Revisiting frank-wolfe: projection-free sparse convex optimization // ICML, 2013.

  19. Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization // Math. Program. 2015. V. 152. № 1–2. P. 75–112.

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

  21. Boyd S., Parikh N. Proximal algorithms // Fondations and Trends in Optimization. 2014. V. 1. № 3. P. 123–231.

  22. Lin H., Mairal J., Harchaoui Z. A universal catalyst for first-order optimization // Proc. of 29th International conference Neural Information Processing Systems (NIPS). 2015. P. 3384–3392.

  23. Rakhlin A., Shamir O., Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization // Proc. of the 29th International Conference on Machine Learning (ICML). 2012. P. 449–456.

  24. Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale optimization, i.: general purpose methods // Optimization for Machine Learning. 2011. P. 121–148.

  25. Nemirovski A. Information-based complexity of convex programming. Technion. 1995.

  26. Lan G. Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization // Math. Program. 2015. V. 149. № 1–2. P. 1–45.

  27. Немировский А.С., Нестеров Ю.Е. Оптимальные методы гладкой выпуклой оптимизации // Ж. вычисл. матем. и матем. физ. 1985. Т. 25. № 3. С. 356–369.

  28. Boyd S., Vandenberghe L. Convex otpimization. Cambridge University Press. 2004.

  29. Гасников А.В. Эффективные численные методы поиска равновесий в больших транспортных сетях: дис. … д.ф.-м.н.: 05.13.18. М.: МФТИ, 2016. 487 с.

  30. Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. 2016. Т. 8. № 1. С. 41–91.

  31. Tyurin A. Mirror version of similar triangles method for constrained optimization problems // e-print. arXiv: 1705.09809. 2017.

  32. Аникин А.С., Гасников А.В., Двуреченский П.Е., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях // Ж. вычисл. матем. и матем. физ. 2017. Т. 57. № 8. С. 1270–1284.

  33. Васильев Ф.П. Методы оптимизации. Т. 1. М.: МЦНМО, 2011. 620 с.

  34. Juditsky A., Nesterov Yu. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization // Stoch. System. 2014. V. 4. № 1. P. 44–80.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал