On Some Works of Boris Teodorovich Polyak on the Convergence of Gradient Methods and Their Development

Full Text

1. ВВЕДЕНИЕ

Данный обзор посвящен частичному разбору нескольких работ Б. Т. Поляка о сходимости методов градиентного типа, которые на многие десятилетия определили развитие численных методов оптимизации. В частности, продолжают активно цитироваться и развиваться в настоящее время. Прежде всего, речь пойдет о работах [1]–[15].

Подчеркнем, что в данной статье не планируется описывать научный путь Бориса Теодоровича. Мы коснемся лишь пары десятков статей из более чем 250-ти. Более подробно с научным путем Б. Т. Поляка можно познакомиться, например, по статьям [16], [17].

Структура обзора следующая. В разд. 2 описываются методы негладкой оптимизации и специальный способ адаптивного выбора шага (в литературе часто называется «шаг Поляка»). В частности, приводится субградиентный метод Поляка–Шора и вариант этого метода с переключением (для задач с функциональными ограничениями). Далее обсуждается вопрос о возможной линейной скорости сходимости таких методов, если минимум острый.

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

В разд. 4 приводятся результаты Поляка–Цыпкина и Поляка–Юдицкого–Рупперта, в которых возникают различные формы центральной предельной теоремы для выхода алгоритма типа стохастического градиентного спуска. Далее приводятся неасимптотические результаты, в том числе и для ускоренных вариантов стохастического градиентного спуска. В частности, рассматриваются так называемые мультипликативные помехи, которые в современных исследованиях чаще называют условием сильного роста, не ассоциируя это с пионерскими работами Б. Т. Поляка с соавторами. В заключении разд.4 рассматриваются рандомизированные безградиентные (также называемые поисковыми) методы. В условиях повышенной гладкости целевой функции обсуждается конструкция Поляка–Цыбакова, позволяющая строить хорошую модель производной по направлению целевой функции, исходя всего из двух проб.

2. НЕГЛАДКАЯ ВЫПУКЛАЯ ОПТИМИЗАЦИЯ

История развития методов негладкой оптимизации начинается в 60-е годы прошлого века и достаточно подробно описана в работе [18]. Наряду с работами Н. З. Шора [19] важный вклад в развитие этой области принадлежит Б. Т. Поляку (см. [11], [15]).

2.1. Субградиентный метод Поляка–Шора

Если не оговорено иное, то далее в тексте рассматриваются задачи вида

$f\left(x\right)\to \underset{x\in Q}{min}$, (1)

где f(x) — необязательно дифференцируемая выпуклая функция, Q — выпуклое замкнутое подмножество ${ℝ}^n$, $f^{*}=f\left(x_{*}\right)=mi{n}_{x\in Q}f\left(x\right)$.

В данном пункте мы поговорим про субградиентные методы для негладкой оптимизации и вклад Бориса Теодоровича Поляка. Хорошо известно, что при минимизации недифференцируемых функций возникает ряд проблем: неприменим метод покоординатного спуска, а субградиент целевой фyнкции не задает направление наискорейшего возрастания. В связи с этим Н. З. Шором был предложен субградиентный метод [20], являющийся прямым аналогом градиентного метода. Особенность идеи такого метода в том, что вместо градиента целевой функции в методе используется произвольный сyбградиент негладкой выпyклой фyнкции. Рассмотрим случай, когда Q — замкнyтое выпyклое подмножество ${ℝ}^n$ с евклидовой нормой ||·||₂. Пусть $B_2^n(x_{*},R)=\left\{x\in {ℝ}^n:{||x-x_{*}||}_2⩽R\right\}$. Будем всюду далее обозначать субградиент f (некоторый элемент субдифференциала $\partial f\left(x\right)$) в точке x как ∇f(x). Если функция f дифференцируема в точке x, то ∇f(x) — ее градиент. Итерация сyбградиентного метода при h_k > 0 имеет следyющий вид:

$x^{k+1}={\mathrm{Pr}}_Q\{x^k-h_k\nabla f(x^k\left)\right\}, \nabla f\left(x^k\right)\in \partial f\left(x^k\right)$, (2)

где ${\mathrm{Pr}}_Q\left(y\right):={\mathrm{argmin}}_{x\in Q}\{\parallel y-x{\parallel }_2\}$ — оператор евклидова проектирования на множество Q. Одна из главных особенностей субградиентных методов состоит в том, что значения функции в этом методе могут не убывать монотонно с ростом количества итераций. Вообще, f не обязательно убывает вдоль направления −∇f(x^k), обратного направлению сyбградиента в текyщей точке. Однако оказывается, что при этом возможно гарантировать монотонное убывание расстояния от текущей точки до точки минимума. Вторая особенность — это выбор шага сyбградиентного метода. Если выбирать постоянный шаг, то метод может не сходиться. Действительно, пycть для фyнкции одной переменной f(x) = |x|, x₀ = −0.01 и выбран постоянный шаг h_k = 0.02. Тогда итеративная последовательность метода (2) будет состоять всего из двyх точек −0.01 и 0.01 и не бyдет сходимости к точке минимума 0.

Интересный подход к выбору шага в сyбградиентном методе предложен Б. Т. Поляком. Он предложил при выборе шага использовать степень близости значения функции в текущей точке к минимальному. Это вполне возможно, если известно искомое минимальное значение функции f^*. Например, если систему совместных линейных уравнений

$⟨a_i,x⟩=b_i, i=\mathrm{1,2,}\dots ,n, x\in {ℝ}^n$,

свести к минимизации функции

$f\left(x\right)=\sum _{i=1}^n\left|<a_i,x>-b_i\right|$,

то f^* = 0. Также f^* бывает известно в геометрических задачах — проекция точки на множество, нахождение общей точки системы множеств. Используя f^*, можно построить адаптивный вариант шага (впервые он предложен в [11]), не содержащий таких параметров задачи, как константа Липшица целевой функции или расстояние от точки старта до множества решений:

$h_k=\frac{f\left(x^k\right)-f^{*}}{{||\nabla f\left(x^k\right)||}_2^2}$. (3)

Такой шаг принято называть шагом Б. Т. Поляка. Для субградиентного метода с таким шагом известен следующий результат о сходимости (см. [2]).

Теорема 1. Пусть f(x) — выпуклая на ${ℝ}^n$ функция, множество точек минимума X* которой не пусто. Тогда в методе (2) с шагом (3) $x^k\to x_{*}\in X_{*}$. При этом $\underset{k\to \infty }{lim}\sqrt{k}\left(f\right(x^k)-f^{*})=0$.

Доказательство. Как известно, для всякой точки минимума x* ∈ X* верны неравенства

$\begin{array}{c}2h_k\left(f\right(x^k)-f(x_{*}\left)\right)\le 2h_k<\nabla f\left(x^k\right),x^k-x_{*}>\le \\ \le h_k^2{||\nabla f\left(x^k\right)||}_2^2+{||x^k-x_{*}||}_2^2-{||x^{k+1}-x_{*}||}_2^2.\end{array}$

Поэтому

$\begin{array}{c}{||x^{k+1}-x_{*}||}_2^2\le h_k^2{||\nabla f\left(x^k\right)||}_2^2-\\ -2h_k\left(f\right(x^k)-f(x_{*}\left)\right)+{||x^k-x_{*}||}_2^2=\\ =\frac{{\left(f\right(x^k)-f(x_{*}\left)\right)}^2}{{||\nabla f\left(x^k\right)||}_2^2}-\frac{2{\left(f\right(x^k)-f(x_{*}\left)\right)}^2}{{||\nabla f\left(x^k\right)||}_2^2}+{||x^k-x_{*}||}_2^2=\end{array}$ (4)

$=-\frac{{\left(f\right(x^k)-f(x_{*}\left)\right)}^2}{{||\nabla f\left(x^k\right)||}_2^2}+{||x^k-x_{*}||}_2^2$. (5)

Таким образом, имеем

$\frac{f\left(x^k\right)-f^{*}}{{||\nabla f\left(x^k\right)||}_2}\to 0$.

Более того, неравенство $\parallel x^k-x_{*}{\parallel }_2\le \parallel x^0-x_{*}{\parallel }_2$ означает, что последовательность x^k ограничена, и тогда $\parallel \nabla f\left(x^k\right){\parallel }_2\le M$. Поэтому $f\left(x^k\right)\to f^{*}$. Следовательно, найдется подпоследовательность $x^{k_l}\to x_{*}$. Итак, получаем, что $\parallel x^k-x_{*}{\parallel }_2$ монотонно убывает, а $\parallel x^{k_l}-x_{*}{\parallel }_2\to 0$. Отсюда $x^k\to x_{*}$. Ввиду (5) получаем

$\sum _{k=0}^{\infty }\frac{{\left(f\right(x^k)-f^{*})}^2}{{||\nabla f\left(x^k\right)||}_2^2}<\infty$,

а из ограниченности $\parallel \nabla f\left(x^k\right){\parallel }_2$ следует $\sum _{k=0}^{\infty }{\left(f\right(x^k)-f^{*})}^2<\infty$. Если предположить, что $\underset{k\to \infty }{lim}\sqrt{k}\left(f\right(x^k)-f^{*})>0$, то $f\left(x^k\right)-f^{*}>a/\sqrt{k}$ для достаточно больших k, что противоречит условию $\sum _{k=0}^{\infty }{\left(f\right(x^k)-f^{*})}^2<\infty$. Итак, $\underset{k\to \infty }{lim}\sqrt{k}\left(f\right(x^k)-f^{*})=0$. Теорема 1 доказана.

Предыдущий результат означает, что для достижения точности ε > 0 решения задачи по функции гарантированно достаточно O(1 / ε²) итераций. Данная оценка скорости сходимости неулучшаема на классе минимизационных задач с выпуклыми липшицевыми (как гладкими, так и негладкими) целевыми функциями. Хотя известны и другие подходы к выбору шага для субградиентного метода. Например, если при $Q={ℝ}^n$ предположить (здесь и всюду далее $R⩾{||x^0-x_{*}||}_2$), что

${||\nabla f\left(x\right)||}_2\le M для всякого x\in B_2^n(x_{*},R\sqrt{2})$, (6)

и выбрать шаг субградиентного метода, а также точку выхода следующим образом:

$h=\frac{R}{M\sqrt{N}}, {\overline{x}}^N=\frac{1}{N}\sum _{k=0}^{N-1}{x}^k$, (7)

то будет выполняться неравенство

$f\left({\overline{x}}^N\right)-f\left(x_{*}\right)\le \frac{MR}{\sqrt{N}}$. (8)

Неравенство (8) означает, что при выборе

$N=\frac{M^2{R}^2}{{\epsilon }^2}, h=\frac{\epsilon }{M^2}$ (9)

будет достигаться оценка $f\left({\overline{x}}^N\right)-f\left(x_{*}\right)⩽\epsilon$, которая оптимальна с точностью до умножения на константу. Действительно, известно, что точная нижняя оценка на классе задач выпуклой оптимизации с условием (6) для методов первого порядка вида

$x^{k+1}\in x^0+span\left\{\nabla f\left(x^0\right),\dots ,\nabla f\left(x^k\right)\right\}$, (10)

где для всех j = 0, 1, ..., k верно $\nabla f\left(x^j\right)\in \partial f\left(x^j\right)$, имеет вид (см. [21])

$f\left(x^N\right)-f\left(x_{*}\right)\ge \frac{MR}{\sqrt{N+1}}$. (11)

Представляется, что интерес выбора шага Б. Т. Поляка для сyбградиентного метода в том, что он в каждой точке позволяет учесть динамику значений целевой функции и не содержит параметров типа константы Липшица целевой фyнкции или оценки расстояния от начальной точки до множества точных решений задачи. Такого типа процедуры выбора шагов в оптимизационных методах часто называют адаптивными. Разным подходам к адаптивным процедурам при выборе шагов оптимизационных методов посвящаются все новые работы (см. [22]–[24]). В этом плане можно отметить многочисленные исследования в области универсальных градиентных методов (см. [25], [26]), адаптивных методов типа AdaGrad, да и разные модификации шага Б. Т. Поляка в детерминированном и стохастическом случаях (см. [22], [27]). Важно, что, помимо процедyры выбора шага, Б. Т. Поляк еще выделил и класс задач с острым минимyмом (см. [11]), для которого этот шаг позволил доказать резyльтат о сходимости сyбградиентного метода со скоростью геометрической прогрессии. Далее поговорим об этом результате и его развитии в современных работах.

2.2. Острый минимум и линейная скорость сходимости субградиентного метода с шагом Б. Т. Поляка

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

$f\left(x\right)-f^{*}⩾\alpha \underset{x_{*}\in X_{*}}{min}{||x-x_{*}||}_2$, (12)

где X* — множество точек минимума функции f на множестве Q, α > 0 — некоторое фиксированное положительное число. В частности, условие (12) верно для задачи евклидова проектирования точки x на выпуклый компакт X* ⊂ Q, причем f* = 0. Условие острого минимума было введено Б. Т. Поляком в [11]. Рассмотрим субградиентный метод (2) с шагом Б. Т. Поляка (3) для задачи минимизации f.

Теорема 2. Пусть f — выпуклая функция и для задачи минимизации f с острым минимумом используется алгоритм (2) c шагом Б. Т. Поляка (3). Тогда после k итераций алгоритма (2) верно неравенство

$\underset{x_{*}\in X_{*}}{min}{||x^{k+1}-x_{*}||}_2^2\le \prod _{i=0}^k\left(1-\frac{{\alpha }^2}{{||\nabla f\left(x^i\right)||}_2^2}\right)\underset{x_{*}\in X_{*}}{min}{||x^0-x_{*}||}_2^2$.

Доказательство. Согласно (5) и условию острого минимума имеем

$\begin{array}{c}\underset{x_{*}\in X_{*}}{min}{||x^{k+1}-x_{*}||}_2^2\le -\frac{{\alpha }^2}{\parallel \nabla f\left(x^k\right){\parallel }_2^2}\underset{x_{*}\in X_{*}}{min}{||x^k-x_{*}||}_2^2+\underset{x_{*}\in X_{*}}{min}{||x^k-x_{*}||}_2^2=\\ =\left(1-\frac{{\alpha }^2}{{||\nabla f\left(x^k\right)||}_2^2}\right)\underset{x_{*}\in X_{*}}{min}{||x^k-x_{*}||}_2^2.\end{array}$. (13)

Далее, получаем цепочку неравенств

$\begin{array}{c}\underset{x_{*}\in X_{*}}{min}{||x^{k+1}-x_{*}||}_2^2\le \left(1-\frac{{\alpha }^2}{{||\nabla f{x}^k||}_2^2}\right)\underset{x_{*}\in X_{*}}{min}{||x^k-x_{*}||}_2^2\le \\ \le \left(1-\frac{{\alpha }^2}{{||\nabla f{x}^k||}_2^2}\right)\left(1-\frac{{\alpha }^2}{{||\nabla f{x}^{k-1}||}_2^2}\right)\underset{x_{*}\in X_{*}}{min}{||x^{k-1}-x_{*}||}_2^2\le \cdots \le \end{array}$ (14)

$\le \prod _i^k\left(1-\frac{{\alpha }^2}{{||\nabla f{x}^i||}_2^2}\right)\underset{x_{*}\in X_{*}}{min}{||x^0-x_{*}||}_2^2$. (15)

Теорема 2 доказана.

Следствие 1. Если в условиях предыдущей теоремы допустить, что f удовлетворяет условию Липшица с константой m > 0 (т. е. все нормы сyбградиентов f равномерно сверхy ограничены этой константой), то можно утверждать сходимость алгоритма (2) со скоростью геометрической прогрессии:

$\underset{x_{*}\in X_{*}}{min}{||x^{k+1}-x_{*}||}_2^2\le {\left(1-\frac{{\alpha }^2}{M^2}\right)}^{k+1}\underset{x_{*}\in X_{*}}{min}{||x^0-x_{*}||}_2^2$.

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

Б. Т. Поляк внес существенный вклад и в изучение задач математического программирования. Ему принадлежит идея так называемых схем с переключениями по продуктивным и непродуктивным шагам (см. [28]). Общая идея подхода заключается в следующем: если в текущей точке значение ограничения достаточно хорошее, то спуск выполняем по целевой функции, а в противном случае — по функции ограничения. Такого типа подходам, которые интересны ввиду малых затрат памяти на итерациях, посвящаются все новые работы как для выпуклых задач большой и сверхбольшой размерностей (см. [29]–[32]), так и для некоторых классов невыпуклых задач (см. [29]). В последние годы некоторыми из авторов статьи были исследованы адаптивные субградиентные методы с переключениями для липшицевых задач выпуклого программирования, в том числе и для некоторых нелипшицевых и/или квазивыпyклых целевых функций (см. [30], [33]–[35]). Достаточно полное исследование стохастического варианта сyбградиентного метода с переключениями по продуктивным и непродуктивным шагам имеется в работе [36].

В этом пункте приводится результат о сходимости субградиентных методов со скоростью геометрической прогрессии для субградиентных схем с переключениями по продуктивным и непродуктивным шагам в случае выпуклых задач с ограничениями в виде неравенств. Случай квазивыпуклых задач с квазивыпуклыми ограничениями исследован в [35]. Будем рассматривать задачу с функциональными ограничениями вида

$\left(\begin{array}{c}\min f\left(x\right),\\ x\in Q, g\left(x\right)\le \mathrm{0,}\end{array}\right.$ (16)

где f(x) и g(x) — липшицевы функции. Всюдy далее будем считать, что задача (16) разрешима.

Algorithm 1. Адаптивный субградиентный метод для выпуклой целевой функции

Require: $\delta >\mathrm{0,}{M}_g>\mathrm{0,}{x}^0,{\theta }_0:{\theta }_0^2\ge \frac{1}{2}\parallel x_{*}-x^0{\parallel }_2^2$, множество Q.

1: $I=:\varnothing$

2: $N\leftarrow 0$

3: repeat

4: if $g\left(x^N\right)\le \delta M_g$ then

5:$h_N^f=\frac{\delta }{\parallel \nabla f\left(x^N\right){\parallel }_2^2}$ ,

6: $x^{N+1}={\mathrm{Pr}}_Q\left(x^N-h_N^f\nabla f\left(x^N\right)\right)$, // “продуктивные шаги”

7: $N\to I$

8: else

9: $h_N^g=\frac{\delta }{\parallel \nabla g\left(x^N\right){\parallel }_2}$,

10: $x^{N+1}={\mathrm{Pr}}_Q\left(x^N-h_N^g\nabla g\left(x^N\right)\right)$, // “непродуктивные шаги”

11: end if

12: $N\leftarrow N+1$

13: until $\frac{2{\theta }_0^2}{{\delta }^2}\le \sum _{k\in I}\frac{1}{\parallel \nabla f\left(x^k\right){\parallel }_2^2}+N-\left|I\right|$.

Ensure:

Рассмотрим теперь алгоритм 1, где I и J — множества индексов продуктивных и непродуктивных шагов соответственно, а | I | и | J | — мощности этих множеств.

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

Пример 1. Рассмотрим случай задачи с несколькими ограничениями

$g\left(x\right)=\max \left\{g_1\right(x),\dots ,g_m(x\left)\right\}$. (17)

Можно сэкономить время работы алгоритма за счет рассмотрения не всех функциональных ограничений на непродуктивных шагах. То есть на непродyктивных шагах вместо субградиента ограничения g(x) можно рассматривать субградиент любого из функционалов g_m(x), для которого верно g_m(x^k) > ε. Другие ограничения при этом можно игнорировать. Легко проверить, что результат о сходимости алгоритма 1 при этом сохранится. Аналогичное замечание можно сделать и про иные подходы указанного типа (см. [33]).

Пример 2. Интересным примером приложений может быть использование схем с переключениями к задачам проектирования механических констрyкций, сводящихся к минимизации функций max-типа с разреженной матрицей A (см. [32], [37]):

$\underset{y}{max}<f,y>:g\left(y\right):=\underset{1⩽i⩽d}{max}\left(\pm ⟨a_i,y⟩-1\right)=\underset{1\le i\le 2d}{max}{g}_i\left(y\right)\le 0$. (18)

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

$y^{k+1}=y^k-h_g\cdot \nabla g\left(y^k\right) или y^{k+1}=y^k+h_f\cdot f$

в векторе y обновляется не больше чем r = O(1) элементов. Из того, что в каждом узле встречаются не более чем s стержней, следует, что обновление y влечет за собой обновление максимум sr скалярных произведений ⟨a_i, y⟩.

Теорема 3. После остановки алгоритма 1 для всякого M_g-липшицева квазивыпуклого ограничения g верно $f\left(\widehat{x}\right)-f\left(x_{*}\right)\le \delta$ и $g\left(\widehat{x}\right)\le \delta M_g$. При этом в случае M_f -липшицевой функции f достаточное количество итераций для выполнения критерия остановки алгоритма 1 оценивается следующим образом:

$N\ge \frac{2{\theta }_0^2\max \left\{\mathrm{1,}{M}_f^2\right\}}{{\delta }^2}$.

Заметим, что на практике для реализации алгоритма 1 знание константы Липшица M_f функции f(x) необязательно, достаточно остановить алгоритм после выполнения критерия остановки.

2.4. Аналог условия острого минимума для задач с ограничениями

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

$\begin{array}{ll}\min ⟨c,x⟩,& x\in {ℝ}^n,\\ Ax\le b,& b\in {ℝ}^m,\end{array}\begin{array}{}\\ \end{array}$ (19)

где c есть n-мерный вектор, A — матрица порядка m × n.

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

Для такой постановки (16) будем использовать следующую вариацию понятия острого минимума (см. [35], [38]).

Определение 1. Будем говорить, что для задачи вида (16) выполняется условие острого минимума (“условный” острый минимум), если при некотором α > 0 для всех x справедливо неравенство

$\max \left\{f\right(x)-f^{*},g(x\left)\right\}\ge \alpha \underset{x_{*}\in X_{*}}{min}{||x-x_{*}||}_2$. (20)

Смысл такого подхода следующий. Поскольку задача (16) с ограничениями в виде неравенств, то в тех точках x, где эти неравенства нарушены, возможно f(x) ≤ f*, и тогда выполнение неравенства (20) возможно за счет положительного g (очевидный пример — когда в качестве ограничения выбирается функция расстояния от точки до допустимого множества). В случае же g(x) ≤ 0 потенциально возможна ситуация, когда неравенство $f\left(x\right)-f^{*}\ge \alpha \underset{x_{*}\in X_{*}}{min}\parallel x-x_{*}{\parallel }_2$ справедливо, а на всем допустимом множестве было бы неверным. Рассмотрим некоторые примеры таких задач с “условным” острым минимумом.

Пример 3 (cпециальный вариант линейной задачи, см. [38]):

$\min -x_1$, (21)

$\rho \cos \left(\frac{j\pi }{10}\right)x_1+\rho \sin \left(\frac{j\pi }{10}\right)x_2\le \rho , j=\mathrm{0,1,}\dots \mathrm{,19}$. (22)

Как известно (см. [38]), в этой задаче точка минимума x_* = (1,0), а оптимальное значение f^* = −1. Отдельно целевая функция −x₁, вообще говоря, не удовлетворяет условию острого минимума (12), поскольку зависит только от одной переменной из двух. Но при наличии ограничений (22) для этой задачи выполнен “условный” вариант острого минимума (20) при α = ρ / 2 (см. [38]). Выбор масштабирующего коэффициента ρ может влиять на значение параметра такого острого минимума.

Пример 4. Рассмотрим задачу

$\begin{array}{l}\min \left\{f(x_1,x_2)=\left|x_1\right|+\left|x_2\right|\right\},\\ g(x_1,x_2)=\max \{\epsilon -x_1,\epsilon -x_2\}\le \mathrm{0,}\end{array}$

где ε > 0. В этом примере целевая функция удовлетворяет условию острого минимума (12). Действительно, $f\left(x\right)=\left|x_1\right|+\left|x_2\right|$, f^* = 0, а x_* = (0,0), и неравенство $\left|x_1\right|+\left|x_2\right|\ge \alpha \parallel x{\parallel }_2$ выполняется, например, при α = 1. Однако функциональные ограничения смещают точку минимума x_* = (ε, ε), и условие острого минимума нарушается. А условному острому минимуму эта задача удовлетворяет, учитывая, что x_* = (ε, ε), а минимальное значение функции f^* = 2ε.

Пример 5 (задача классификации с ограничениями, см. [38]). Рассмотрим множество, состоящее из n пар: $\mathcal{D}={\left\{\right(a_i,b_i\left)\right\}}_{i=1}^n$, где $a\in {ℝ}^p$ — вектор признаков, а b_i ∈ {1, −1} — множество меток при i = 1, 2,...,n. Пусть ${\mathcal{D}}_M\in {ℝ}^p$, ${\mathcal{D}}_F\in {ℝ}^p$ — два типа признаков. Мы хотим найти линейный классификатор $x\in {ℝ}^p$, который не только минимизирует функцию потерь, но и правильным образом обрабатывает каждый элемент из множеств ${\mathcal{D}}_F$ и ${\mathcal{D}}_M$. Указанная задача сводится к следующей постановке:

$$\begin{gathered} \underset{x}{min}\frac{1}{n}\sum _{i=1}^n\underset{x}{max}\{\mathrm{0,1}-b_i{a}_i^{т}x\}, \\ \frac{1}{n_F}\sum _{a\in {\mathcal{D}}_F}\sigma \left(a^{т}x\right)\ge \frac{\kappa }{n_M}\sum _{a\in {\mathcal{D}}_M}\sigma \left(a^{т}x\right), \\ \frac{1}{n_M}\sum _{a\in {\mathcal{D}}_M}\sigma \left(a^{т}x\right)\ge \frac{\kappa }{n_F}\sum _{a\in {\mathcal{D}}_F}\sigma \left(a^{т}x\right), \end{gathered}$$

где κ ∈ (0, 1] — константа, n_M и n_F — количество экземпляров из ${\mathcal{D}}_M$ и ${\mathcal{D}}_F$ соответственно и $\sigma \left(a^{T}x\right):=\max \left\{\mathrm{0,}\min \right\{\mathrm{1,}\{0.5+a^{T}x\}\}\in [\mathrm{0,1}]$ — вероятность присваивания метки +1 предсказанию a.

Построим схему рестартов алгоритма 1 и 2 в предположении, что верно условие (20).

Algorithm 2. Рестарты алгоритма 1

Require: $\epsilon >\mathrm{0,}\alpha >\mathrm{0,}{M}_g>\mathrm{0,}{x}^0,{\theta }_0:{\theta }_0^2\ge \frac{1}{2}\parallel x_{*}-x^0{\parallel }_2^2$, множество Q.

1: Set $p=1$.

2: repeat

3: ${\widehat{х}}^p$ — результат работы алгоритма 1 с параметрами δ_p, θ_p, x⁰, где

4: ${х}^0={\widehat{х}}^p$,

5: ${\theta }_p=\frac{1}{\sqrt{2^p}}{\theta }_0$,

6: ${\delta }_p=\frac{\alpha {\theta }_p}{\sqrt{2}\max \{\mathrm{1,} M_g\}}$.

7: Set $p=p+1$.

8: until $p>⌈2{\log }_2\frac{{\theta }_0}{\epsilon }⌉$

Ensure: x^p.

Для алгоритмов 1 и 2 верна следующая

Теорема 4. Пусть f(x) и g(x) — липшицевы функции с константами M_f и M_g соответственно, удовлетворяющие условию (20), и известна константа θ₀ > 0 такая, что $2{\theta }_0^2\ge \parallel x_{*}-x^0{\parallel }_2^2$. Тогда для алгоритма 1 можно подобрать параметр δ > 0 так, чтобы после

$⌈\frac{4}{{\alpha }^2}\max \left\{\mathrm{1,}{M}_f^2\right\}\max \left\{\mathrm{1,}{M}_g^2\right\}⌉$

итераций было выполнено неравенство $\underset{x_{*}\in X_{*}}{min}\parallel \widehat{x}-x_{*}{\parallel }_2\le \frac{1}{\sqrt{2}}{\theta }_0$. После p − 1 запусков алгоритма 2.4 (рестартов алгоритма 2.3) имеем

$\underset{x_{*}\in X_{*}}{min}{||{\widehat{x}}^{p-1}-x_{*}||}_2\le \frac{1}{\sqrt{2^p}}{\theta }_0$.

Тогда для достижения ε-точного решения вида

$\underset{x_{*}\in X_{*}}{min}{||{\widehat{x}}^{p-1}-x_{*}||}_2\le \epsilon$

достаточное количество обращений к субградиенту f или g можно оценить как

$⌈\frac{4}{{\alpha }^2}\max \left\{\mathrm{1,}{M}_f^2\right\}\max \left\{\mathrm{1,}{M}_g^2\right\}⌉⌈2{\log }_2\frac{{\theta }_0}{\epsilon }⌉$.

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

Введенный Б. Т. Поляком класс выпyклых негладких оптимизационных задач с острым минимумом интересен тем, что на нем сyбградиентный метод имеет неплохие вычислительные гарантии (сходится со скоростью геометрической прогрессии). Однако представляется, что условие острого минимума достаточно существенно сужает рассматриваемый класс выпуклых задач. В этой связи интересно отметить наблюдение многих статей последних лет (см. [39]–[42]) о том, что многие возникающие в приложениях слабо выпуклые задачи имеют острый минимум. Это касается разных типов задач нелинейной регрессии, восстановления фазы, восстановления матрицы (matrix recovery) и др. Класс слабо выпуклых оптимизационных задач интересен, ему посвящаются все новые работы (см. [29], [39], [43]–[47]), но без дополнительных предположений скоростные гарантии достаточно пессимистичны. Однако в случае острого минимума недавно доказаны результаты о сходимости субградиентного метода со скоростью геометрической прогрессии при условии достаточной близости начальной точки к точному решению (см. [39]). При этом заметим, что в одном из этих результатов используется способ выбора шага, предложенный Б. Т. Поляком. Немного расскажем об этом направлении.

Как и ранее, рассматриваем задачи минимизации вида (1). Напомним, что функция $f:{ℝ}^n\to ℝ$ (аналогично и для функций $f:Q\to ℝ$) называется µ-слабо выпуклой (µ ≥ 0), если функция $x\to f\left(x\right)+\frac{\mu }{2}\parallel x{\parallel }_2^2$ выпукла. Для недифференцируемых µ-слабо выпуклых функций f под субдифференциалом $\partial f\left(x\right)$ в точке x можно понимать (см. [39] и цитируемую там литературу) множество всех векторов $\nabla f\left(x\right)\in {ℝ}^n$, удовлетворяющих неравенству

$f\left(y\right)\ge f\left(x\right)+〈\nabla f\left(x\right),y-x〉+o\left({||y-x||}_2\right) при y\to x$. (23)

Известно (см. [39]), что все векторы-субградиенты $\nabla f\left(x\right)\in {ℝ}^n$ из (23) автоматически удовлетворяют неравенству

$f\left(y\right)\ge f\left(x\right)+〈\nabla f\left(x\right),y-x〉-\frac{\mu }{2}{||y-x||}_2^2\forall x,y\in {ℝ}^n, \nabla f\left(x\right)\in \partial f\left(x\right)$. (24)

Можно проверить, что слабо выпуклые функции локально липшицевы, и поэтому в качестве субградиентов можно использовать произвольный вектор из субдифференциала Кларка (см., например, [43]).

Известно немало примеров прикладных слабо выпуклых задач, которые не являются выпуклыми. Так, слабо выпуклыми будут задачи вида (см., например, [39])

$\underset{x}{min}f\left(x\right):=h\left(c\right(x\left)\right)$,

где $h:{ℝ}^m\to ℝ$ выпукло и M-липшицево, а $c:{ℝ}^n\to {ℝ}^m$ является C¹-гладким отображением с β-липшицевой матрицей Якоби. Нетрудно проверить, что при указанных допущениях f — Mβ-слабо выпукла. В частности, в указанный класс задач входят задачи нелинейной регрессии с h(x) = ||x||₁, где ||·||₁ — 1-норма.

Интересно, что слабая выпyклость позволяет сyщественно расширить класс задач с yсловием острого минимyма, предложенного Б. Т. Поляком в [11]. Приведем еще пару достаточно популярных в современных приложениях примеров слабо выпуклых задач с острым минимумом.

Пример 6 (задача восстановления фазы). Восстановление фазы — распространенная вычислительная задача, имеющая приложения в различных областях, таких как визуализация, рентгеновская кристаллография и обработка речи (см. [40], [41], [45]).

Она сводится к задаче минимизации следующей функции:

$f\left(x\right)=\frac{1}{m}\sum _{i=1}^m\left|<a_i,x{>}^2-b_i\right|$, (25)

где $a_i\in {ℝ}^n$ и $b_i\in ℝ$ заданы для каждого i = 1, 2,..., m. Данная целевая фyнкция имеет вид $f\left(x\right):=h\left(c\right(x\left)\right)\to mi{n}_x$, где $h:{ℝ}^m\to ℝ$ — выпуклая и M-липшицева функция, а $c:{ℝ}^n\to {ℝ}^m$ — это C¹-гладкое отображение с β -липшицевым отображением Якоби. Как отмечено выше, такие фyнкции слабо выпуклы. В данном случае функция (25) µ -слабо выпукла (см. [44]) при

$\mu =2\underset{1\le i\le m}{max}{||a_i||}_2^2$. (26)

Более того, при соответствующей модели шума в измерениях фyнкция имеет острый минимyм (см. [40], утверждение 3).

Пример 7 (см. [42]):

$minimiz{e}_{U\in {ℝ}^{n\times r}}\left\{\xi \left(U\right):=\frac{1}{m}{||y-A\left(U{U}^T\right)||}_2^2\right\}$. (27)

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

$y=A\left(X^{\ast }\right)+s^{\ast }$, (28)

где $s^{\ast }\in {ℝ}^m$ — вектор всплесков-возмущений, у которого небольшая часть элементов имеет произвольную величину, а остальные элементы равны нулю. Кроме того, множество ненулевых элементов предполагается неизвестным.

Хорошо известно, что ${\mathcal{l}}_2$-функция потерь чувствительна к возмущениям, что приводит к недостаточной эффективности постановки (27) для восстановления базовой матрицы низкого ранга. Глобальные минимумы ξ в (27) отклоняются от базовой матрицы низкого ранга из-за всплесков, и большая доля всплесков приводит к большему возмущению. Напротив, функция потерь ${\mathcal{l}}_1$ более устойчива к выбросам и широко используется для обнаружения выбросов (см. [48]–[50]). Это привело к идее использовать функцию потерь ${\mathcal{l}}_1$ и факторизованное представление матричной переменной для решения надежной задачи восстановления малоранговой матрицы:

$minimiz{e}_{U\in {ℝ}^{n\times r}}\left\{f\left(U\right):=\frac{1}{m}{||y-A\left(U{U}^T\right)||}_1\right\}$. (29)

Известно (см. [42]), что эта целевая функция слабо выпуклая и обладает острым минимумом.

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

Пример 8. Действительно (см. [51]), пусть

$f\left(x\right)\equiv f(x^{\left(1\right)},x^{\left(2\right)})=\frac{1}{2}{\left(x^{\left(1\right)}\right)}^2+\frac{1}{4}{\left(x^{\left(2\right)}\right)}^4-\frac{1}{2}{\left(x^{\left(2\right)}\right)}^2$.

Это слабо выпуклая задача, поскольку добавление к f половины квадрата нормы x приводит к выпуклой функции. Градиент целевой функции имеет вид

$\nabla f\left(x\right)={\left(x^{\left(1\right)},{\left(x^{\left(2\right)}\right)}^3-x^{\left(2\right)}\right)}^T$,

откуда следует, что существуют только три точки, которые могут претендовать на локальный минимум: $x_1^{*}=\left(\mathrm{0,0}\right), x_2^{*}=(\mathrm{0,}-1), x_3^{*}=\left(\mathrm{0,1}\right)$. Вычисляя матрицу Гессе

${\nabla }^{2}f\left(x\right)=\left(\begin{array}{cc}1& 0\\ 0& 3{\left(x^{\left(2\right)}\right)}^2-1\end{array}\right)$,

заключаем, что $x_2^{*}$ и $x_3^{*}$ являются точками изолированного локального минимума, в то время как $x_1^{*}$ есть только стационарная точка нашей функции. Действительно, $f\left(x_1^{*}\right)=0$ и $f(x_1^{*}+\epsilon e_2)=\left({\epsilon }^4/4\right)-\left({\epsilon }^2/2\right)<0$ при достаточно малых ε. Рассмотрим траекторию градиентного метода, начинающуюся в точке x₀ = (1,0). Обратим внимание на то, что вторая координата этой точки 0, поэтому вторая координата для ∇f(x₀) также 0. Следовательно, вторая координата точки x₁ равна нулю и т. д. Таким образом, вся последовательность точек, образованная градиентным методом, будет иметь нулевую вторую координату, что означает сходимость этой последовательности к $x_1^{*}$.

Теорема 5 (см. [39]). Пусть f µ-слабо выпукла и имеет α-острый минимум (α,µ > 0), а точка x₀: $\underset{x_{*}\in X_{*}}{min}\parallel x^0-x_{*}{\parallel }_2\le \alpha \gamma /\mu$ для некоторого фиксированного γ ∈ (0;1). Тогда для метода (2) с шагом (3) верно неравенство

$\underset{x_{*}\in X_{*}}{min}{||x^{k+1}-x_{*}||}_2^2\le \prod _{i=0}^k\left(1-\frac{{\alpha }^2(1-\gamma )}{{||\nabla f\left(x^i\right)||}_2^2}\right)\underset{x_{*}\in X_{*}}{min}{||x^0-x_{*}||}_2^2$. (30)

Следствие 2. Если в условиях предыдущей теоремы допустить, что f удовлетворяет условию Липшица с константой M > 0, то можно утверждать сходимость алгоритма (2) со скоростью геометрической прогрессии:

$\underset{x_{*}\in X_{*}}{min}{||x^{k+1}-x_{*}||}_2^2\le {\left(1-\frac{{\alpha }^2(1-\gamma )}{M^2}\right)}^{k+1}\underset{x_{*}\in X_{*}}{min}{||x^0-x_{*}||}_2^2$.

Отметим, что в условиях теоремы 5 нулевой (суб)градиент возможен только в точке x^k ∈ X_*, поскольку справедливо следующее

Предложение 1 (окрестность множества X_* не имеет стационарных точек). Задача минимизации µ-слабо выпуклой функции f c α-острым минимумом не имеет стационарных точек x, удовлетворяющих условию

$0<\underset{x_{*}\in X_{*}}{min}{||x-x_{*}||}_2<\frac{2\alpha }{\mu }$. (31)

3. ГЛАДКАЯ ОПТИМИЗАЦИЯ

Пожалуй, основным атрибутом гладкой оптимизации является наличие моментного ускорения, роль которого, по-видимому, впервые была отмечена в 1964 г. в работе Б. Т. Поляка (см. [9]). Отметим, что в этой работе (как и в работе по негладким методам 1969 г., см. [11]) были заложены основы разработки численных методов оптимизации на базе непрерывных аналогов (дифференциальных уравнений, порождающих при дискретизации итерационный процесс). Впоследствии аналогичным образом неоднократно разрабатывались новые численные методы оптимизации (см. [52]–[55]). Однако наличие гладкости дает возможность не только ускорения скорости сходимости. В данном разделе, следуя работам Б. Т. Поляка в основном 60-х годов прошлого века, продемонстрировано, какие дополнительные возможности приобретаются при наличии гладкости (липшицевости градиента целевой функции).

3.1. Условие градиентного доминирования (Поляка–Лоясиевича)

В 1963 г. Б. Т. Поляк (см. [1]) предложил простое условие, достаточное для того, чтобы показать глобальную линейную скорость сходимости градиентного спуска для достаточно гладких задач. Это условие является частным случаем неравенства Лоясиевича, предложенного в том же году (см. [56]), и не требует сильной выпуклости (или даже выпуклости). Условие вида (32) называется условием градиентного доминирования или же условием Поляка–Лоясиевича (PL-условием) (см. [1], [56]–[58]):

$f\left(x\right)-f\left(x_{*}\right)\le \frac{1}{2\mu }{||\nabla f\left(x\right)||}_2^2 \forall x\in {ℝ}^n$. (32)

Как правило, в литературе это условие называют условием Поляка–Лоясиевича, но стоит отметить еще работу Лежанского (см. [57]), в которой оно появилось независимо. По-видимому, правильнее называть (32) условием Лежанского–Поляка–Лоясиевича. Зачастую в теоретических приложениях данное условие используется как ослабление сильной выпуклости, так как любая µ-сильно выпуклая функция удовлетворяет PL-условию с константой µ.

В последние годы условие градиентного доминирования обширно исследуется в различных областях оптимизации и смежных науках. Толчком к возрождению интереса к этому условию послужила работа [58], в которой авторы показали, что PL-условие слабее тех условий, которые ранее использовались для получения линейной скорости сходимости без сильной выпуклости. Также в этой работе PL-условие использовалось для проведения нового анализа рандомизированных и жадных методов покоординатного спуска, а также стохастических градиентных методов в различных постановках. Было предложено и обобщение результатов на проксимальные градиентные методы, позволяющее несложно доказать их линейную скорость сходимости. Попутно были получены результаты сходимости для широкого круга задач машинного обучения: метода наименьших квадратов, логистической регрессии, бустинга, устойчивого метода обратного распространения ошибки, L1-регуляризации, метода опорных векторов.

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

Пример 9 (PL-условие для нелинейных задач). Пусть $f\left(x\right)=\frac{1}{2}\parallel \Phi \left(x\right)-y{\parallel }_2^2$, где $\Phi :{ℝ}^d\to {ℝ}^n$ дифференцируемо. Тогда f удовлетворяет PL-условию, если существует такое µ > 0, что для всех $x\in {ℝ}^d$ имеет место равномерная невырожденность матрицы Якоби:

${\lambda }^{\min }\left(\frac{\partial \Phi \left(x\right)}{\partial x}\cdot {\left[\frac{\partial \Phi \left(x\right)}{\partial x}\right]}^T\right)\ge \mu$, (33)

где

$\frac{\partial \Phi \left(x\right)}{\partial x}={\left(\frac{\partial {\Phi }_i\left(x\right)}{\partial x_j}\right)}_{i,j=1}^{n,d}=D\Phi \left(x\right)$.

Действительно, достаточно написать

${||\nabla f\left(x\right)||}_2^2={||D\Phi {\left(x\right)}^T\left(\Phi \right(x)-y)||}_2^2\ge \mu {||\Phi \left(x\right)-y||}_2^2=2\mu f\left(x\right)\ge 2\mu \left(f\right(x)-f(x_{*}\left)\right)$.

В качестве Φ(x) может выступать, например, система нелинейных уравнений. В частности, из этого можно получить, что функции Розенброка и Нестерова–Скокова локально удовлетворяют условию Поляка–Лоясиевича.

Обратим внимание, что допущение (33) предполагает d ≥ n. Это верно, если, например, Φ задает перепараметризованную нейронную сеть (более точные рассуждения с опорой на использование структуры нейронной сети см. в [59]).

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

Пример 10 (композиция сильно (строго) выпуклой и линейной функций). В [58] показано, что если функция f имеет вид f(x) = g(Ax), где g — сильно выпукла, то f удовлетворяет PL-условию. Функции данного вида часто возникают в машинном обучении (например, метод наименьших квадратов). Если ослабить условие сильной выпуклости функции g до строгой выпуклости, то функция f также будет удовлетворять PL-условию, однако уже не на всем пространстве, а только на произвольном компакте. Например, из данного факта следует, что целевая функция задачи логистической регрессии

$f\left(x\right)=\sum _{i=1}^n\log \left(1+\exp \left(b_i{a}_i^{T}x\right)\right)$

локально (т. е. на всяком компакте) обладает PL-условием.

Приведем также пример функции с условием градиентного доминирования, связанной с теорией оптимального управления. Этот достаточно интересный класс функций с условием градиентного доминирования был получен совсем недавно И.Ф. Фатхуллиным и Б. Т. Поляком в [60].

Пример 11 (см. [60]). Пусть задана линейная система управления

$\dot{x}\left(t\right)=Ax\left(t\right)+Bu\left(t\right), y = Cx$,

где $x\left(t\right)\in {ℝ}^n$ — состояние системы, а $y\left(t\right)\in {ℝ}^l$ — управление; с начальными условиями x(0), распределенными случайно с нулевым средним и ковариационной матрицей Σ ($\mathbb{E}x\left(0\right)x{\left(0\right)}^T=\Sigma$); с критерием качества вида

$f\left(K\right)=\mathbb{E}\underset{0}{\overset{\infty }{\int }}\left(x{\left(t\right)}^{T}Qx\left(t\right)+u{\left(t\right)}^{T}Ru\left(t\right)\right)dt, Q,R\succ 0$,

заданным на множестве S с целью найти матрицу обратной связи по состоянию u(t) = −Kx(t), минимизирующую f(K). Тогда, если известен K₀ — стабилизирующий регулятор, то градиент ∇f(K) липшицев на множестве уровня $S_0=\left\{K:f\left(K\right)\le f\left(K_0\right)\right\}$, а для f выполнено условие градиентного доминирования со следующей константой µ:

$\mu =\frac{{\lambda }_1\left(R\right){\lambda }_1^2\left(\Sigma \right){\lambda }_1\left(Q\right)}{8f\left(K_{*}\right){\left({||A||}_2+\frac{{||B||}_2^{2}f\left(K_0\right)}{{\lambda }_1\left(\Sigma \right){\lambda }_1\left(R\right)}\right)}^2}$,

где K_* — точка минимума f на множестве S. Здесь λ_i(X) — собственные числа матрицы $X\in {ℝ}^{m\times m}$, занумерованные в порядке возрастания их действительных частей, т. е. Re λ₁(X) ≤ Re λ₂(X) ≤ Re λ_m(X).

Отметим, что функция f(K) достаточно гладкая (имеет липшицев градиент), но невыпуклая.

Таким образом, условие Поляка–Лоясиевича верно для достаточно большого класса невыпyклых задач. Тем не менее, оно позволяет обосновать сходимость градиентного метода со скоростью геометрической прогрессии. Приведем оценку скорости сходимости градиентного метода для L -гладких функций с условием Поляка–Лоясиевича. Будем рассматривать задачи минимизации функции f, удовлетворяющей PL-условию (32), а также условию Липшица градиента

${||\nabla f\left(x\right)-\nabla f\left(y\right)||}_2\le L{||x-y||}_2 \forall x,y\in {ℝ}^n$. (34)

Справедлива следующая

Теорема 6. Пусть дана задача безусловной оптимизации arg min f(x), где функция f является L-гладкой и удовлетворяет PL-условию с константой µ. Тогда градиентный метод с постоянным шагом 1 / L вида

$x^{k+1}=x^k-\frac{1}{L}\nabla f\left(x^k\right)$ (35)

имеет линейную скорость сходимости, т. е.

$f\left(x^k\right)-f\left(x_{*}\right)\le {\left(1-\frac{\mu }{L}\right)}^k\left(f\right(x^0)-f(x_{*}\left)\right)\le \exp \left(-\frac{\mu }{L}k\right)\left(f\right(x^0)-f(x_{*}\left)\right)$. (36)

Доказательство. В силу L -гладкости функции f

$f\left(x^{k+1}\right)\le f\left(x^k\right)+⟨\nabla f\left(x^k\right),x^{k+1}-x^k⟩+\frac{L}{2}{||x^{k+1}-x^k||}_2^2$.

Пользуясь правилом обновления (35), получаем

$f\left(x^{k+1}\right)\le f\left(x^k\right)-\frac{1}{2L}{||\nabla f\left(x^k\right)||}_2^2$. (37)

Из PL-условия имеем

$f\left(x^k\right)-f\left(x_{*}\right)\le \frac{1}{2\mu }{||\nabla f\left(x^k\right)||}_2^2$. (38)

Из (37) и (38) путем преобразований следует

$f\left(x^{k+1}\right)-f\left(x_{*}\right)\le \left(1-\frac{\mu }{L}\right)\left(f\right(x^k)-f(x_{*}\left)\right)$.

Рекурсивное применение последнего неравенства и дает требуемый результат (36). Теорема 6 доказана.

Доказанная верхняя оценка скорости сходимости из теоремы 6 известна уже около 60 лет. До недавнего времени вопрос о ее оптимальности оставался открытым. В последние дни 2022 г. был выложен препринт [61], в котором обоснована оптимальность этой оценки на классе гладких задач с условием Поляка–Лоясиевича.

Отметим, что существует аналог условия Поляка–Лоясиевича для седловых задач, так называемое двухстороннее условие Поляка–Лоясиевича, которое позволяет получить ряд схожих результатов (см. [62]–[64]). Будем рассматривать седловую задачу $\underset{x}{min}\underset{y}{max}f\left(x,y\right)$. Говорят, что функция f(x,y) удовлетворяет двустороннему PL-условию, если существуют такие константы µ₁ и µ₂, что ∀x,y

$\begin{array}{c}{||{\nabla }_{x}f(x,y)||}_2^2\ge 2{\mu }_1\left(f(x,y)-\underset{x}{min}f(x,y)\right),\\ {||{\nabla }_{y}f(x,y)||}_2^2\ge 2{\mu }_2\left(\underset{y}{max}f(x,y)-f(x,y)\right).\end{array}$

Примеры функций, удовлетворяющих двустороннему PL-условию:

• f(x,y) = F(Ax,By), где F(·, ·) — сильно-выпукло-сильно-вогнутая и A, B — произвольные матрицы.
• Невыпукло-невогнутая $f(x,y)=x^2+3{\sin }^{2}x{\sin }^{2}y-4y^2-10{\sin }^{2}y$ (µ₁ = 1 /16, µ₂ = 1 /14) (см. [62]).
• Релаксация задачи Robust Least Squares (RLS):

$$\begin{gathered} \underset{x\in {ℝ}^n}{min}\underset{y\in {ℝ}^m}{max}F(x,y); \\ F(x,y):={||Ax-y||}_M^2-\lambda {||y-y_0||}_M^2, \end{gathered}$$

где M — положительно полуопределена и $\parallel x{\parallel }_M^2=x^{T}Mx$. RLS минимизирует невязку наихудшего случая при заданном ограниченном детерминированном возмущении δ на зашумленном векторе измерений $y_0\in {ℝ}^m$ и матрице коэффициентов $A\in {ℝ}^{m\times n}$. Саму задачу RLS можно сформулировать так (ρ > 0) (см. [65]):

$\underset{x\in {ℝ}^n}{min}\underset{\delta :\parallel \delta {\parallel }_2\le \rho }{max}\parallel Ax-y{\parallel }_2^2, или \delta =y_0-y\in {ℝ}^m$.

Известно, что при λ > 1 F(x, y) удовлетворяет двустороннему PL-условию, поскольку F(x, y) можно представить как комбинацию аффинной функции и сильно-выпукло-сильно-вогнутой функции.

Для седловых задач с двусторонним условием градиентного доминирования может использоваться вариация градиентного метода — метод градиентного спуска-подъема. Этот подход сейчас довольно популярен (см. [62], [63], [66]), но был подробно проанализирован еще в малоизвестной статье Бакушинского–Поляка [67].

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

Сфокусируемся на двух основных известных типах неточной информации о градиенте: абсолютной и относительной погрешностях. Типичными примерами областей, в которых возникает данная проблема неточного градиента, являются безградиентная оптимизация, в которой используется приближенно вычисляемый градиент (см. [69]–[71]), а также оптимизация в бесконечномерных пространствах, связанная с обратными задачами (см. [72], [73]).

Начнем с вопроса влияния на качество выдаваемого решения абсолютной погрешности в градиенте. Будем рассматривать задачу минимизации функции f, удовлетворяющей PL-условию (32), а также условию Липшица градиента (34). Считаем, что методу доступно не точное, а приближенное значение градиента $\tilde{\nabla }f\left(x\right)$ в любой запрашиваемой точке x:

$\nabla f\left(x\right)=\tilde{\nabla }f\left(x\right)+v\left(x\right), причём {||v\left(x\right)||}_2\le \Delta$

при некотором фиксированном ∆ > 0. Тогда (32) означает, что

$f\left(x\right)-f\left(x_{*}\right)\le \frac{1}{\mu }\left({||\tilde{\nabla }f\left(x\right)||}_2^2+{\Delta }^2\right)\forall x\in {ℝ}^n$, (39)

откуда

${||\tilde{\nabla }f\left(x\right)||}_2^2\ge \mu \left(f\right(x)-f(x_{*}\left)\right)-{\Delta }^2\forall x\in {ℝ}^n$.

Заметим, что вопросы исследования влияния погрешностей градиента на оценки скорости сходимости методов первого порядка уже достаточно давно привлекают многих исследователей (см., например, [2], [74]–[77]). Однако мы сфокусируемся именно на выделенном классе, вообще говоря, невыпуклых задач. Невыпуклость целевой функции задачи, а также использование на итерациях неточно заданного градиента могут приводить к разным проблемам. В частности, при отсутствии каких-либо правил ранней остановки возможно достаточно большое удаление траектории градиентного метода от начальной точки. Это может быть проблемным, если начальное положение метода уже обладает определенными хорошими свойствами. С другой стороны, неограниченное удаление траектории градиентного метода в случае градиентного метода с помехами может привести к удалению от искомого точного решения. Опишем некоторые ситуации такого типа.

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

$f\left(x\right)=<Ax,x>$, (40)

где A = diag(L, µ, 0) — диагональная матрица 3-го порядка с ровно двумя положительными элементами L > µ > 0. Если для задачи минимизации функции (40) допустить наличие погрешности градиента v(x) = (0,0,∆) при ∆ > 0, то при x⁰ = (0,0,0) и h_k > 0 последовательность $x^{k+1}=x^k-h_k\tilde{\nabla }f\left(x^k\right)$ стремится к бесконечности при неограниченном увеличении k. Далее, можно рассмотреть функцию Розенброка двух переменных x = (x₍₁₎, x₍₂₎)

$f\left(x\right)=100{\left(x_{\left(2\right)}-{\left(x_{\left(1\right)}\right)}^2\right)}^2+{\left(1-x_{\left(1\right)}\right)}^2$.

При x⁰ = (1,1) = x_* на каждом шаге градиентного метода возможна такая погрешность градиента v(x^k), что $x_{\left(2\right)}^k={\left(x_{\left(1\right)}^k\right)}^2$ и без остановки траектория может уходить весьма далеко от точного решения x_*. Аналогично траектория градиентного метода может уходить к бесконечности для целевой функции двух переменных f(x) = (x₍₂₎ − (x₍₁₎)²)².

Немного расскажем об одной из последних работ, подготовленных Б. Т. Поляком с соавторами (см. [68]). В этой статье поставлена цель исследовать оценку расстояния ||x^N − x⁰||₂ для выдаваемых градиентным методом точек x^N и предложить правило ранней остановки, которое гарантирует некоторый компромисс между стремлением достичь приемлемого качества выдаваемого методом решения задачи по функции и не столь существенным удалением траектории от выбранной начальной точки метода. Отметим, что правила ранней остановки в итеративных процедурах активно исследуются для самых разных типов задач. По-видимому, впервые идеология раннего прерывания итераций была предложена в статье [78], посвященной методике приближенного решения возникающих при регуляризации некорректных или плохо обусловленных задач (в упомянутой работе рассматривалась задача решения линейного уравнения). Ранняя остановка в этом случае нацелена на преодоление проблемы потенциального накопления погрешностей регуляризации исходной задачи. К данной тематике примыкают известные подходы, связанные с ранней остановкой методов первого порядка в случае использования на итерациях неточной информации о градиенте (см. [2], гл. 6, параграф 1, а также, к примеру, недавний препринт [77]). Однако известные прежде результаты для выпуклых (не сильно выпуклых) задач отличаются по сравнению с полученным в рассматриваемой работе тем, что обычно гарантируется достижение худшего уровня по функции (если сравнить с комментарием после теоремы 2 параграфа 1 гл. 6 из [2]) или оценки вида $\parallel x^N-x_{*}{\parallel }_2\le \parallel x^0-x_{*}{\parallel }_2$ без исследования ||x^N − x⁰||₂, где ${\left\{x^k\right\}}_{k\in \mathbb{N}}$ — образуемая методом последовательность, x_* — ближайшее к точке старта метода x⁰ точное решение задачи минимизации f.

В предположении доступности значений параметров L > 0 и ∆ > 0 применим к задаче минимизации f градиентный метод вида

$x^{k+1}=x^k-\frac{1}{L}\tilde{\nabla }f\left(x^k\right)$. (41)

Тогда ввиду (34) для метода (41) имеем следующие соотношения:

$\begin{array}{c}f\left(x^{k+1}\right)\le f\left(x^k\right)+〈\nabla f\left(x^k\right),x^{k+1}-x^k〉+\frac{L}{2}{||x^{k+1}-x^k||}_2^2=\\ =f\left(x^k\right)+\frac{1}{2L}{||\nabla f\left(x^k\right)-\tilde{\nabla }f\left(x^k\right)||}_2^2-\frac{{||\nabla f\left(x^k\right)||}_2^2}{2L}\le \\ \le f\left(x^k\right)+\frac{{\Delta }^2}{2L}-\frac{1}{2L}{||\nabla f\left(x^k\right)||}_2^2,\end{array}$

т.е.

$f\left(x^{k+1}\right)-f\left(x^k\right)\le \frac{{\Delta }^2}{2L}-\frac{1}{2L}{||\nabla f\left(x^k\right)||}_2^2$. (42)

Суммирование неравенств (42) приводит нас к оценке

$\underset{k=\mathrm{0,}N-1}{min}{||\nabla f\left(x^k\right)||}_2\le \sqrt{{\Delta }^2+\frac{2L\left(f\right(x^0)-f(x_{*}\left)\right)}{N}}\le \Delta +\sqrt{\frac{2L\left(f\right(x^0)-f(x_{*}\left)\right)}{N}}$, (43)

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

С учетом (32) тогда получаем, что

$f\left(x^{k+1}\right)-f\left(x^k\right)\le \frac{{\Delta }^2}{2L}-\frac{2\mu \left(f\right(x^k)-f(x_{*}\left)\right)}{2L}=-\frac{\mu }{L}\left(f\right(x^k)-f(x_{*}\left)\right)+\frac{{\Delta }^2}{2L}$,

откуда

$\begin{array}{c}f\left(x^{k+1}\right)-f\left(x_{*}\right)\le \left(1-\frac{\mu }{L}\right)\left(f\right(x^k)-f(x_{*}\left)\right)+\frac{{\Delta }^2}{2L}\le {\left(1-\frac{\mu }{L}\right)}^{k+1}\left(f\right(x^0)-f(x_{*}\left)\right)+\\ +\frac{{\Delta }^2}{2L}\left(1+1-\frac{\mu }{L}+\cdots +{\left(1-\frac{\mu }{L}\right)}^k\right)<{\left(1-\frac{\mu }{L}\right)}^{k+1}\left(f\right(x^0)-f(x_{*}\left)\right)+\frac{{\Delta }^2}{2\mu },\end{array}$

т. е.

$f\left(x^{k+1}\right)-f\left(x_{*}\right)\le {\left(1-\frac{\mu }{L}\right)}^{k+1}\left(f\right(x^0)-f(x_{*}\left)\right)+\frac{{\Delta }^2}{2\mu }$. (44)

Оценки (43) и (44), вообще говоря, неулучшаемы. К примеру, известны нижние оценки уровня точности по функции O(∆² / (2µ)) для градиентного метода с абсолютной погрешностью задания градиента (см., например, разд. 2.11.1 пособия [37], а также имеющиеся там ссылки) даже на классе сильно выпуклых функций.

В [68] для градиентного метода с постоянным шагом при достаточно малом значении возмущенного градиента получена теорема, в которой указан уровень точности по функции, который возможно гарантировать после выполнения предложенного правила ранней остановки. Данный результат можно применять ко всяким L -гладким невыпуклым задачам. Далее, с использованием PL-условия получено уточнение этого результата — достаточное количество итераций градиентного метода для достижения желаемого качества точки выхода $\widehat{x}$ по функции $f\left(\widehat{x}\right)-f\left(x_{*}\right)=O({\Delta }^2/\mu )$.

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

${||\tilde{\nabla }f\left(x\right)-\nabla f\left(x\right)||}_2\le \alpha {||\nabla f\left(x\right)||}_2$, (45)

где под $\tilde{\nabla }f\left(x\right)$, как и ранее, мы понимаем неточный градиент, а α ∈ [0, 1) — некоторая константа, указывающая на величину относительной погрешности градиента. Данное условие на неточный градиент было введено и изучено в [2], [79].

Из (45) можно получить вариант условия градиентного доминирования (32) для относительно неточного градиента

$f\left(x\right)-f\left(x_{*}\right)\le \frac{1}{2\mu {(1-\alpha )}^2}{||\tilde{\nabla }f\left(x\right)||}_2^2$.

Описанную задачу предлагается также решать методом градиентного типа вида

$x^{k+1}=x^k-h_k\tilde{\nabla }f\left(x^k\right)$. (46)

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

Если при реализации метода (46) градиент доступен с известной относительной погрешностью α ∈ [0, 1) и известен параметр L > 0, то выбор шага $h_k=\frac{1}{L}\frac{(1-\alpha )}{{(1+\alpha )}^2}$ приводит к следующим результатам (см. параграф 1 из пособия [80] и имеющиеся там ссылки):

$\begin{array}{c}f\left(x^{k+1}\right)-f\left(x^k\right)\le ⟨\nabla f\left(x^k\right),x^{k+1}-x^k⟩+\frac{L}{2}{||x^{k+1}-x^k||}_2^2=-h_k〈\nabla f\left(x^k\right),\tilde{\nabla }f\left(x^k\right)〉+\frac{L{h}_k^2}{2}{||\tilde{\nabla }f\left(x^k\right)||}_2^2=\\ =-h_k{||\nabla f\left(x^k\right)||}_2^2-h_k〈\nabla f\left(x^k\right),\tilde{\nabla }f\left(x^k\right)-\nabla f\left(x^k\right)〉+\frac{L{h}_k^2}{2}{||\tilde{\nabla }f\left(x^k\right)||}_2^2\le \\ \le -h_k{||\nabla f\left(x^k\right)||}_2^2+h_k{||\nabla f\left(x^k\right)||}_2{||\tilde{\nabla }f\left(x^k\right)-\nabla f\left(x^k\right)||}_2+\frac{L{h}_k^2}{2}{||\tilde{\nabla }f\left(x^k\right)||}_2^2\le \end{array}$

$\le -h_k{||\nabla f\left(x^k\right)||}_2^2+\alpha h_k{||\nabla f\left(x^k\right)||}_2^2+{\left(1+\alpha \right)}^2\frac{L{h}_k^2}{2}{||\nabla f\left(x^k\right)||}_2^2=\left(-(1-\alpha )h_k+{(1+\alpha )}^2\frac{L{h}_k^2}{2}\right){||\nabla f\left(x^k\right)||}_2^2.$

После подстановки h_k (которое, заметим, минимизирует выражение в скобках в последнем выражении) получаем

$f\left(x^{k+1}\right)-f\left(x^k\right)\le -\frac{1}{2L}\frac{{(1-\alpha )}^2}{{(1+\alpha )}^2}{||\nabla f\left(x^k\right)||}_2^2$. (47)

Пользуясь условием Поляка–Лоясиевича (32), имеем следующую оценку на скорость сходимости по функции:

$f{x}^{k+1}-f{x}_{*}\le \left(1-\frac{\mu }{L}\frac{{-\alpha }^2}{{+\alpha }^2}\right)\left(f{x}^k-f{x}_{*}\right)$,

т.е.

$f\left(x^N\right)-f\left(x_{*}\right)\le {\left(1-\frac{\mu }{L}\frac{{(1-\alpha )}^2}{{(1+\alpha )}^2}\right)}^N\left(f\left(x^0\right)-f\left(x_{*}\right)\right)$.

Если вместо PL-условия (32) предполагать выполнение условия сильной выпуклости, то приведенную оценку можно уточнить (см. [80]):

$\frac{{(1-\alpha )}^2}{{(1+\alpha )}^2}\to O\left(\frac{1-\alpha }{1+\alpha }\right)$.

В работе [82] предлагается адаптивный алгоритм для случая относительной погрешности градиента. По сути, предлагается критерий выхода из итерации, содержащий норму неточного градиента $\parallel \tilde{\nabla }f\left(x^k\right){\parallel }_2$. Это обстоятельство затрудняет использование подхода с оценками типа (47) для нормы точного градиента. Поэтому рассматривается альтернативный вариант выбора шага для метода (46) с относительной погрешностью задания градиента, который позволит получить приемлемый аналог оценки (47) для квадрата нормы неточного градиента. Аналогично ранее рассмотренным случаям, пользуясь L -липшицевостью градиента и условием (45), можно вывести следующее неравенство (см. [82]):

$\begin{array}{c}f\left(x^{k+1}\right)\le f\left(x^k\right)+<\tilde{\nabla }f\left(x^k\right),x^{k+1}-x^k>+\frac{L}{2}{||x^{k+1}-x^k||}_2^2+\\ +\frac{\alpha }{1-\alpha }{||\tilde{\nabla }f\left(x^k\right)||}_2{||x^{k+1}-x^k||}_2.\end{array}$ (48)

Таким образом, при α ∈ [0; 0,5) для адаптивного варианта градиентного метода (46) c

$h_k=\frac{1}{L_{k+1}}\frac{1-2\alpha }{1-\alpha }$ (49)

и критерием выхода из итерации (до его выполнения L_k+1 увеличивается в 2 раза)

$\begin{array}{c}f\left(x^{k+1}\right)\le f\left(x^k\right)+〈\tilde{\nabla }f\left(x^k\right),x^{k+1}-x^k〉+\frac{L_{k+1}}{2}{||x^{k+1}-x^k||}_2^2+\\ +\frac{\alpha }{1-\alpha }{||\tilde{\nabla }f\left(x^k\right)||}_2{||x^{k+1}-x^k||}_2\end{array}$ (50)

неравенство (48) гарантирует выход из итерации при L_k+1 ≥ L. Тогда оценка скорости сходимости метода (46) c шагом (49) имеет вид

$f\left(x^N\right)-f\left(x_{*}\right)\le \prod _{k=0}^{N-1}\left(1-\frac{\mu }{L_{k+1}}{(1-2\alpha )}^2\right)\left(f\left(x^0\right)-f\left(x_{*}\right)\right)$. (51)

Если L₀ ≥ 2L, то последнее неравенство означает сходимость рассматриваемого метода со скоростью геометрической прогрессии

Отметим, что оценка (51) может быть применима в случае неизвестного значения L. Кроме того, даже в случае известной оценки на L потенциально возможно улучшение качества точки выхода метода при условии L_k+1 < L.

3.2. Метод условного градиента (Франк–Вульфа–Левитина–Поляка)

В этом пункте мы вспомним о направлении научных исследований Б. Т. Поляка, связанном с методами условного градиента. К примеру, таким методам посвящена достаточно известная работа [10]. Несмотря на то что методы условного градиента по числу итераций проигрывают оптимальным на классе выпуклых гладких задач ускоренным методам (см. п. 3.3) для решения задач со структурой (например, на единичном симплексе или прямом произведении таких симплексов), по времени работы эти методы могут быть существенно эффективнее ускоренных из-за возможной дешевизны итерации (см. [83]–[86]). На данный момент методы условного градиента достаточно хорошо разработаны (см., например, обзорную статью [87] и монографию [88]). В частности, среди последних достижений можно отметить безградиентные варианты метода условного градиента для задач стохастической оптимизации (см. [89]), а также вариант метода условного градиента для децентрализованных оптимизационных задач на меняющихся графах (см. [90]).

Рассмотрим задачу выпуклой оптимизации (f(x) — выпуклая функция, Q — ограниченное выпуклое множество):

$\underset{x\in Q}{min}f\left(x\right)$. (52)

Обозначим решение задачи (52) через x_* (если решение не единственно, то x_* — какое-то из решений).

Algorithm 3. Метод условного градиента (см. [10], [88])

Require: f — выпуклая, непрерывно дифференцируемая функция; Q — допустимое множество, выпуклое и компактное; x¹ — начальная точка; N — количество итераций.

Ensure: точка x^N

1: for $k=\mathrm{1,} \dots , N-1$ do

2: ${\gamma }_k=\frac{2}{k+1}, 0\le {\gamma }_k\le 1$

3: $y^k={\mathrm{argmin}}_{y\in Q}<\nabla f\left(x^k\right),y>$

4: $x^{k+1}=(1-{\gamma }_k)x^k+{\gamma }_k{y}^k$

5: end for

6: return x^N

Теорема 7 (см. [10], [88]). Пусть ∇f(x) удовлетворяет на Q условию Липшица с константой L по отношению к некоторой норме ||·||: для всех x, y ∈ Q выполняется

${||\nabla f\left(y\right)-\nabla f\left(x\right)||}_{*}\le L||y-x||$, $R=su{p}_{x,y\in Q}\parallel x-y\parallel$, ${\gamma }_k=2/(k+1)$ для k ≥ 1. Тогда для любого N ≥ 2 выполняется

$f\left(x^N\right)-f\left(x_{*}\right)\le \frac{2L{R}^2}{N+2}$. (53)

Доказательство. Из условия Липшица на градиент f(x) и выпуклости f(x) имеем оценку

$0\le f\left(x\right)-f\left(y\right)-<\nabla f\left(y\right),x-y>\le \frac{L}{2}{||x-y||}^2$

для всех x, y ∈ Q. Получаем цепочку неравенств

$\begin{array}{c}f\left(x^{k+1}\right)-f\left(x^k\right)\le 〈\nabla f\left(x^k\right),x^{k+1}-x^k〉+\frac{L}{2}{||x^{k+1}-x^k||}^2={\gamma }_k〈\nabla f\left(x^k\right),y^k-x^k〉+\frac{L{\gamma }_k^2}{2}{||y^k-x^k||}^2\le \\ \le {\gamma }_k<\nabla f\left(x^k\right),x_{*}-x^k>+\frac{L{\gamma }_k^2}{2}{R}^2\le {\gamma }_k\left(f\right(x_{*})-f(x^k\left)\right)+{\gamma }_k^2\frac{L{R}^2}{2}.\end{array}$

Введем обозначение ${\delta }_k=\left(f\right(x^k)-f(x_{*}\left)\right)/\left(L{R}^2\right)$. Тогда неравенство можно переписать в виде

${\delta }_{k+1}\le (1-{\gamma }_k){\delta }_k+\frac{{\gamma }_k^2}{2}=\left(1-\frac{2}{k+1}\right){\delta }_k+\frac{2}{{(k+1)}^2}$.