Лекция 8

Определим, при каких $\alpha$ выполняется $\Vert E-\alpha Q\Vert =\max \{|1-\alpha {\lambda }_{min}|,|1-\alpha {\lambda }_{max}|\}<1$

Обозначим $q_1(\alpha )=|1-\alpha {\lambda }_{min}|$, $q_2=|1-\alpha {\lambda }_{max}|$ и построим графики функций $q_1(\alpha )$, $q_2(\alpha )$.

Из условия $\Vert E-\alpha Q\Vert <1$ получаем неравенство $\alpha {\lambda }_{max}-1<1$. Отсюда $\alpha <\frac{2}{{\lambda }_{max}}$. Таким образом, если $\alpha \in [0,\frac{2}{{\lambda }_{max}}]$, то метод сходится к точке минимума $x^{\ast }=0$ функции $f(x)$.

Теорема

Пусть $f(x)=\frac{1}{2}(Qx,x)$, где $Q$ положительно определена. Пусть также ${\lambda }_{min}$ и ${\lambda }_{max}$ - наименьшие и наибольшие собственные числа матрицы $Q$. Тогда если шаг спуска $\alpha \in (0,\frac{2}{{\lambda }_{max}})$, то $\forall x\in {\mathbb{R}}^n$ градиентный спуск с постоянным шагом сходится к точке глобального $\min x^{\ast }=0$ функции $f(x)$, причем норма $\Vert x^k\Vert \le q^k\ast \Vert x^0\Vert$, где $q=\max \{|1-\alpha {\lambda }_{min}|,|1-\alpha {\lambda }_{max}|\}$

Сходимость должна быть самой быстрой, если $\alpha ={\alpha }_{опт}$, где ${\alpha }_{опт}$ - точка минимума функции $\Vert E-\alpha Q\Vert$. Очевидно, $1-{\alpha }_{опт}{\lambda }_{min}={\alpha }_{опт}{\lambda }_{max}-1$ тогда и только тогда, когда ${\alpha }_{опт}=\frac{2}{{\lambda }_{min}+{\lambda }_{max}}$. ${\alpha }_{опт}$ - оптимальный шаг градиентного спуска с постоянным шагом.

Так как $\Vert E-{\alpha }_{опт}Q\Vert =\frac{2{\lambda }_{max}}{{\lambda }_{min}+{\lambda }_{max}}-1=\frac{{\lambda }_{max}-{\lambda }_{min}}{{\lambda }_{max}+{\lambda }_{min}}$, то при оптимальном шаге пуска $\Vert x^k\Vert \le (\frac{{\lambda }_{max}-{\lambda }_{min}}{{\lambda }_{max}+{\lambda }_{min}}{)}^k\Vert x^0\Vert$. Заметим, что $\frac{\frac{{\lambda }_{max}}{{\lambda }_{min}}-1}{\frac{{\lambda }_{max}}{{\lambda }_{min}}+1}=\frac{C(Q)-1}{C(Q)+1}$, где $C(Q)=\frac{{\lambda }_{max}}{{\lambda }_{min}}$. $C(Q)$ - число обусловленности матрицы $Q$. Очевидно, $C(Q)\ge 1$. Окончательно получаем такую оценку скорости сходимости градиентного спуска с постоянным оптимальным шагом. $\Vert x^k\Vert \le (\frac{C(Q)-1}{C(Q)+1}{)}^k\Vert x^0\Vert$.

2 критических случая:

1. $C(Q)\simeq 1$ $⟹$ ${\lambda }_{max}\simeq {\lambda }_{min}$ (если $n=2$, то это означает, что линии уровня $f(x)$ близки к окружностям). Если ${\lambda }_{max}={\lambda }_{min}$, то $C(Q)=1$ $⟹$ $\forall k\Vert x^k\Vert \le 0$ \implies$$\forall k \lVert x^k \rVert \leq 0 $⟹$ $\forall k\Vert x^k\Vert =0$, то есть за 1 итерацию будет достигнута точка $x^{\ast }=0$ из любого начального приближения. Если $C(Q)\simeq 1$, то говорят, что задача хорошо обусловлена.
2. $C(Q)\gg 1$ $⟹$ ${\lambda }_{max}\gg {\lambda }_{min}$ (если $n=2$, то это означает, что линии уровня $f(x)$ - это сильно вытянутые в одном из направлений эллипсы). В этом случае $\left(\frac{C(Q)-1}{C(Q)+1}\right)\simeq 1$ $⟹$ $(\frac{C(Q)-1}{C(Q)+1}{)}^k{\to }_{k\to \infty }0$ медленно. Если $C(Q)\gg 1$, то говорят, что задача $f(x)=\frac{1}{2}(Qx,x){\to }_{x\in {\mathbb{R}}^n}\min$ плохо обусловлена.

Метод наискорейшего спуска

Рассмотрим задачу $f(x){\to }_{x\in {\mathbb{R}}^n}\min$, где $f\in C^1({\mathbb{R}}^n)$ и $f$ сильно выпукла в ${\mathbb{R}}^n$ (с константой $\gamma >0$).

Построим последовательность приближений $\{x^k\}$ по правилу $x^{k+1}=x^k+{\alpha }_k{p}^k$, $k=0,1,2,\dots ,$ где $p^k=-\text{grad}f(x^k)$ - антиградиент функции $f$ в точке $x^k$, ${\alpha }_k$ - точка $\min$ функции $\Phi (k)(\alpha )=f(x^k+\alpha p^k)$ на промежутке $[0,+\infty )$.

Условие окончания поиска - выполнение хотя бы одного из неравенств $\Vert x^{k+1}-x^k\Vert <{\epsilon }_1$, $|f(x^{k+1})-f(x^k)|<{\epsilon }_2$, $\Vert \text{grad}f(x^{k+1})\Vert <{\epsilon }_3$, где ${\epsilon }_1,{\epsilon }_2,{\epsilon }_3$ - параметры точности. При этом полагаем, что $x^{\ast }\simeq x^{k+1}$.

Свойство метода

$\forall k=0,1,2,\dots (p^k,p^{k+1})=0$

$(p^k,p^{k+1})=-(p^k,\text{grad}f(x^{k+1}))=0$ (свойство исчерпывающего спуска).

Геометрическая интерпретация. $\forall k=0,1,2,\dots ,p^k\perp p^{k+1}$.