Лекция 5

Вспомогательное утверждение

Пусть $U$ - замкнутое множество, функция $f(x)$ непрерывна на $U$, $\exists x^0\in U$ такое, что множество $V=\{x\in U:f(x)\le f(x^0)\}$ ограничено. Тогда существует точка $\min x^{\ast }$ функции $f(x)$ на множестве $U$.

Обоснование $⟹$ $V$ замкнуто $⟹$ ограничено и замкнуто $⟹$ существует точка $\min x^{\ast }$ функции $f(x)$ на множестве $V$. Она же является точкой минимума функции $f(x)$ на множестве $U$.

Из условия

Теорема (об ограниченности множеств Лебега сильно выпуклой функции)

Пусть $U$ - замкнутое выпуклое множество, $f(x)$ сильно выпукла на $U$ с константой $\gamma >0$. Тогда $\forall \beta \in \mathbb{R}$ множество $U_{\beta }=\{x\in U:f(x)\le \beta \}$ ограничено.

Доказательство $U_{\beta }=\varnothing$, то условие очевидно. Пусть $U_{\beta }\ne \varnothing$. Выберем $x^0\in U_{\beta }$. Пусть $V=\{x:||x-x_0||\le 1\}$. Покажем, что $\exists R>0$ такое, что $\forall x\in U_{\beta }||x-x_0||\le R$.

Если

1. Если $x\in U_{\beta }\cap V$, то $\Vert x-x_0\Vert \le 1$
2. Пусть $x\in U_{\beta }\setminus V$. Соединим $x^0$ и $x$ отрезком и выберем на нём точку $\overline{x}=\lambda x+(1-\lambda )x^0$, где $\lambda =\frac{1}{||x-x_0||}$, $0<\lambda <1$ Так как $\Vert \overline{x}-x^0\Vert =\Vert \lambda x+(1-\lambda )x^0-x^0\Vert =\Vert \lambda x-\lambda x^0\Vert =\Vert \lambda (x-x^0)=\lambda \Vert x-x^0\Vert =1$, то $\overline{x}\in V$

Таким образом, $\overline{x}\in U$ и $\overline{x}\in V$ $⟹$ $\overline{x}\in U\cap V$. Так как $U\cap V$ ограниченно и замкнуто, то $\exists \alpha :f(\overline{x})\ge \alpha$. Таким образом, $\alpha \le f(\overline{x})=f(\lambda x+(1-\lambda )x^0)$. Применим определение сильно выпуклой функции. f(\lambda x - (1-\lambda)x^0) \leq \lambda f(x) + (1-\lambda)f(x^0) - \gamma \lambda (1-\lambda) \lVert x-x^0 \rVert \leq$$\leq \lambda \beta + (1-\lambda)\beta - \gamma(1-\lambda)\lVert x-x^0 \rVert = \beta - \gamma(1-\lambda) \lVert x-x^0 \rVert = \beta - \gamma\left( 1-\frac{1}{|x-x^0|} \right) \lVert x-x^0 \rVert =$$\beta - \gamma \lVert x-x^0 \rVert + \gamma

Получили неравенство $\alpha \le \beta -\gamma \Vert x-x^0\Vert +\gamma$ $\gamma \Vert x-x^0\Vert \le \beta +\gamma -\alpha$ $\Vert x-x^0\Vert \le 1+\frac{\beta -\alpha }{\gamma }$

Следствие

Пусть $f(x)$ сильно выпукла с константой $\gamma >0$ на замкнутом, выпуклом множестве $U$, Тогда точка $\min x^{\ast }$ функции $f(x)$ существует и единственна

Обоснование

Существование следует из утверждения и теоремы. Единственность следует из строгой выпуклости (строгая выпуклость вытекает из сильной выпуклости)

Дифференциальные критерии сильной выпуклости

Первый дифференциальный критерий сильной выпуклости

Пусть $U$ выпукло, $f(x)\in C^1(U)$. $f(x)$ сильно выпукла на $U$ с константой $\gamma >0$ $<=>$ $\forall x,x^0\in Uf(x)\ge f(x^0)+(gradf(x^0),x-x^0)+\gamma \Vert x-x^0{\Vert }^2$

$(⟹)$. Пусть $f(x)$ сильно выпукла на $U$ с константой $\gamma >0$. Тогда $\forall x,x^0\in U\alpha \in [0,1]$ $f(\alpha x+(1-\alpha )x^0)\le \alpha f(x)+(1-\alpha )f(x^0)-\gamma (1-\alpha )\Vert x-x^0{\Vert }^2$ $\frac{1}{\alpha }f(\alpha x+(1-\alpha )x^0)\le f(x)+\frac{1}{\alpha }f(x^0)-f(x^0)-\gamma (1-\alpha )\Vert x-x^0{\Vert }^2$ $f(x)-f(x^0)\ge \frac{f(\alpha x+(1-\alpha )x^0)-f(x^0)}{\alpha }+\gamma (1-\alpha )\Vert x-x^0{\Vert }^2$. Перейдем к пределу при $\alpha \to 0$

${\lim }_{\alpha \to 0}(f(x)-f(x^0))\ge {\lim }_{\alpha \to 0}(f(x^0)+\alpha (x-x^0))$ ??? ??? ??? :LiFileQuestion:

Геометрическая интерпретация сильной выпуклости. Пусть $f(x)$ сильно выпукла в ${\mathbb{R}}^n$ с константой $\gamma >0$ $⟹$ у $f(x)$ в ${\mathbb{R}}^n$ существует единственная точка глобального $\min x^{\ast }$. Согласно теореме. $\forall x\in {\mathbb{R}}^{n}f(x)\ge f(x^{\ast })+(gradf(x^{\ast }),x-x^{\ast })+\gamma \Vert x-x^{\ast }{\Vert }^2$. $gradf(x^{\ast })=0$ согласно необходимому условию экстремума. $⟹$ $\forall x\in {\mathbb{R}}^{n}f(x)>=f(x^{\ast })+\gamma \Vert x-x^{\ast }{\Vert }^2$, Таким образом, график $f(x)$ в ${\mathbb{R}}^n$ расположен не ниже, чем параболоид вращения, задаваемый уравнением $z=f(x^{\ast })+\gamma \Vert x-x^{\ast }{\Vert }^2$

Пусть $f(x)\in C^2(U)$, $U\subset {\mathbb{R}}^n$. Тогда $\forall x\in U$ определена матрица Гессе $H(x)=(\frac{{\partial }^{2}f}{\partial x_i\partial x_j}{)}_{i,j=\overline{1,n}}$, причем $\left(\frac{{\partial }^{2}f}{\partial x_i\partial x_j}\right)\in C(U)$, $i,j=\overline{1,n}$. Так как $\forall i,j=\overline{1,n}\frac{{\partial }^{2}f}{\partial x_i\partial x_j}=\frac{{\partial }^{2}f}{\partial x_j\partial x_i}$, то $H(x)$ симметрично на множестве $U$.

Теорема (второй дифференциальный критерий сильной выпуклости)

1. Пусть $f(x)$ сильно выпукла с константой $\gamma >0$ на выпуклом множестве $U\subset {\mathbb{R}}^n$ и $f(x)\in C^2(U)$. Тогда $\forall x^0\in U\forall p\in {\mathbb{R}}^n(H(x^0)p,p)\ge 2\gamma ||p|{|}^2$
2. Пусть $U\subset {\mathbb{R}}^n$ выпукло и $f(x)\in C^2(U)$. Если для некоторого $\gamma >0$ $\forall x^0\in U\forall p\in {\mathbb{R}}^n(H(x^0)p,p)\ge 2\gamma \Vert p{\Vert }^2$, то $f(x)$ сильно выпукло на $U$ с константой $\gamma >0$

Доказательство $x^0$ множества $U$ и выберем $\forall p\in {\mathbb{R}}^n$. Тогда из первого дифференциального критерия сильной выпуклости $f(x^0+\alpha p)\ge f(x^0)+(gradf(x^0),dp)+\gamma \Vert \alpha p{\Vert }^2$, где $\alpha >0$ мало и таково, что $x^0+\alpha p\in U$

Выберем любую внутреннюю точку

Согласно формуле Тейлора,
$f(x^0+\alpha p)=f(x^0)+(\text{grad}f(x^0),\alpha p)+\frac{1}{2}(H(x^0)\alpha p,\alpha p)+o({\alpha }^2)$

$\ge f(x^0)+(\text{grad}f(x^0),\alpha dp)+\frac{{\alpha }^2}{2}(H(x^0)p,p)+o({\alpha }^2)\ge \gamma {\alpha }^2\Vert p{\Vert }^2$

Делим на ${\alpha }^2$:
$\frac{1}{2}(H(x^0)p,p)+\frac{o({\alpha }^2)}{{\alpha }^2}\ge \gamma \Vert p{\Vert }^2$

При $\alpha \to 0$ получим $\frac{1}{2}(H(x^0)p,p)\ge \gamma \Vert p{\Vert }^2$

Если $x^0\in U$ — предельная точка множества $U$, не являющаяся внутренней, то рассмотрим последовательность $\{x^k\}$, внутренних точек множества и такую, что $x^k\to x^0$, $k\to \infty$. Тогда $\forall k(H(x^k)p,p)\ge 2\gamma \Vert p{\Vert }^2$.

Переходя к пределу при $k\to \infty$, получим $(H(x^0)p,p)\ge 2\gamma \Vert p{\Vert }^2$.

2. Выберем $\forall x,x^0\in U$ и запишем ряд Тейлора для $f(x)$ в окрестности $x^0$:

$f(x)=f(x^0)+(\text{grad}f(x^0),x-x^0)+\frac{1}{2}(H(x^0+\Theta (x-x^0))(x-x^0),x-x^0)$, $\Theta \in (0,1)$. $\Rightarrow f(x)\ge f(x^0)+(\text{grad}f(x^0),x-x^0)+\gamma \Vert x-x^0{\Vert }^2\ge f(x^0)+(\text{grad}f(x^0),x-x^0)+\frac{\gamma }{2}\Vert x-x^0{\Vert }^2$

Согласно 1-му дифференциальному критерию сильной выпуклости, $f(x)$ сильно выпукла на $U$ с константой $\gamma >0$.

Рассмотрим квадратичную функцию $f(x)=\frac{1}{2}(Qx,x)+(b,x)+c$, где $x\in {\mathbb{R}}^n$ - переменные, $Q$ - положительно определенная $n\times n$ матрица (то есть $\forall x\ne 0(Qx,x)>0$ ) с элементами $q_{ij}$, $i,j=\overline{1,n}$; $b\in {\mathbb{R}}^n,c\in \mathbb{R}$.

В координатах $f(x)$ примет вид
$f(x)=\frac{1}{2}{\sum }_{i=1}^n{q}_{ii}{x}_i^2+{\sum }_{\begin{array}{c}i,j=1\\ i\ne j\end{array}}^n{q}_{ij}{x}_i{x}_j+{\sum }_{j=1}^n{b}_j{x}_j+c$

Известно, что $\text{grad}f(x)=Qx+B,H(x)=Q$

Пусть ${\lambda }_{\min }$ — наименьшее собственное число матрицы $Q$.

Тогда $\forall p\in {\mathbb{R}}^n(Qp,p)\ge {\lambda }_{\min }\Vert p{\Vert }^2,{\lambda }_{\min }>0.$

Таким образом, $\forall x\in {\mathbb{R}}^n\forall p\in {\mathbb{R}}^n(H(x)p,p)\ge {\lambda }_{\min }\Vert p{\Vert }^2$
$\Rightarrow$ согласно 2-му дифф. критерию сильной выпуклости $f(x)$ сильно выпукла в ${\mathbb{R}}^n$ с константой $\gamma =\frac{{\lambda }_{\min }}{2}$

Методы безусловной многомерной оптимизации

Задача безусловной минимизации - это задача $f(x)\to \min$, $x\in {\mathbb{R}}^n$. Полагаем, что $f(x)$ сильно выпукла в ${\mathbb{R}}^n$ $f(x){\to }_{x\in {\mathbb{R}}^n}\min ,x=(x_1,\dots ,x_n)$

Метод циклического покоординатного спуска

Пусть $x^0\in {\mathbb{R}}^n$ - начальное приближение. Построим последовательность приближений по следующему правилу. Чтобы перейти от приближения $x^k$ к приближению $x^{k+1}$ выполним $n$ этапов.

Этап 1. Зафиксируем у $f(x)$ все переменные, кроме $x_1$. Тогда получим функцию одной переменной ${\phi }_{k_1}(x_1)=f(x_1,x_2^k,x_3^k,\dots ,x_n^k)$. Найдем точку $\min x_1^{k+1}$ функции ${\phi }_{k_1}(x_1)$ в $\mathbb{R}$. Результат этапа 1 - переход из точки $x^k$ в точку $(x_1^{k+1},x_2^k,x_3^k,\dots ,x_n^k{)}^T$. Этап 2. Зафиксируем у $f(x)$ все перемнные, кроме $x_2$ $⟹$ получим функцию ${\phi }_{k_2}(x_2)=f(x_1^{k+1},x_2,x_3^k,\dots ,x_n^k)$. Найдем точку $\min x_2^{k+1}$ функции ${\phi }_{k_2}(x_2)$ в $\mathbb{R}$. Результат этапа 2 - переход из точки $(x_1^{k+1},x_2^k,x_3^k,\dots ,x_n^k{)}^T$ в точку $(x_1^{k+1},x_2^{k+1},x_3^k,\dots ,x_n^k{)}^T$. … Этап n. Зафиксируем у $f(x)$ все переменные, кроме $x_n$ $⟹$ получим функцию ${\phi }_{k_n}(x_n)=f(x_1^{k+1},\dots ,x_{n-1}^{k+1},x_n)$. Найдем точку $\min x_n^{k+1}$ функции ${\phi }_{k_n}(x_n)$ в $\mathbb{R}$. Результат этапа $n$ - переход из точки $(x_1^{k+1},\dots ,x_{n-1}^{k+1},x_{n^k})$ в точку $(x_1^{k+1},\dots ,x_{n-1}^{k+1},x_n^{k+1})$. Это и есть следующиее приближение $x^{k+1}$.

Условие окончания поиска - выполнение неравенства $\Vert x^{k+1}-x^k\Vert <\epsilon$, где $\epsilon >0$ - заданная точность. При этом полагаем, что $x^{\ast }\simeq x^{k+1}$

Замечание. Задачи одномерной минимизации ${\phi }_{k_i}(x_i){\to }_{x_i\in \mathbb{R}}\min$ решаются методами одномерной оптимизации