МетОп 3 ЛЕКЦИЯ

Пусть $f(x)$ непрерывно дифференцируема на $[a,b]$. Тогда $f(x)$ выпукла на $[a,b]$ $<=>$ $\forall x,x_0\in [a,b]f(x)\ge f(x_0)+f^{\prime }(x_0)(x-x_0)$. Аналогично $f(x)$ строго выпукла на $[a,b]$ $<=>$ $\forall x,x_0\in [a,b]x\ne x_{0}f(x)>f(x_0)+f^{\prime }(x_0)(x-x_0)$.

Утверждение

Пусть $f(x)\in C_1[a,b]$, $f(x)$ выпукла на $[a,b]$ и $f^{\prime }(x_0)=0$ для некоторого $x_0\in [a,b]$. Тогда $x_0$ - точка глобального минимума функции $f(x)$ на $[a,b]$.

Обоснование $\forall x\in [a,b]f(x)\ge f(x_0)+f^{\prime }(x_0)(x-x_0)\ge f(x_0)$.

Из дифференциального критерия выпуклости

Метод Ньютона

Рассмотрим задачу $f(x){\to }_{x\in [a,b]}min,$где $f(x)\in C^2[a,b]$ и $f^{\prime \prime }(x)>0$ на $[a,b]$.

В $f^{\prime \prime }(x)$ заложено требование унимодальности. Так как $f^{\prime \prime }(x)>0$ на $[a,b]$, то $f(x)$ строго выпукла на $[a,b]$ $⟹$ $f(x)$ унимодальна на $[a,b]$.

Пусть $x_0\in [a,b]$ - некоторое начальное приближение к искомой точке минимума $x^{\ast }\in [a,b]$. Построим последовательность приближений $\{x_k\}$ по следующему правилу. Чтобы перейти от приближения к $x_k$ к следующему приближению $x_{k+1}$, запишем формулу Тейлора для $f(x)$ второго порядка в окрестности точки $x_k$: $f(x)=f(x_k)+f^{\prime }(x_k)(x-x_k)+\frac{1}{2}{f}^{\prime \prime }(x_k)(x-x_k{)}^2+o((x-x_k{)}^2),x\to x_k$ Заменим в окрестности точки $x_k$ функцию $f(x)$ её многочленом Тейлора 2-го порядка: $P_k=f(x_k)+f^{\prime }(x_k)(x-x_k)+\frac{1}{2}{f}^{\prime \prime }(x_k)(x-x_k{)}^2$ и найдем точку $\min$ функции $P_k(x)$ из условия $P_k^{\prime }$ в этой точке $=0$. Так как $P_k^{\prime }(x)=f^{\prime }(x_k)+f^{\prime \prime }(x_k)(x-x_0)$, то получаем уравнение $f^{\prime }(x_k)+f^{\prime \prime }(x_k)(x-x_k)=0$ $f^{\prime \prime }(x_k)(x-x_k)=-f^{\prime }(x_k)$ $x-x_k=-\frac{f^{\prime }(x_k)}{f^{\prime \prime }(x_k)}$

Эту точку $x_{k+1}=x_k-\frac{f^{\prime }(x_k)}{f^{\prime \prime }(x_k)}$ считаем следующим приближением к искомой точке минимума.

Таким образом, метод Ньютона состоит в построении из начальной точки $x_0\in [a,b]$ последовательности приближений $\{x_k\}$ по правилу $x_{k+1}=x_k-\frac{f^{\prime }(x_k)}{f^{\prime \prime }(x_k)},k=0,1,2,\dots$, до выполнения условия окончания поиска $|f^{\prime }(x_{k+1})|<\epsilon$, где $\epsilon >0$ - заданная точность. При этом полагаем, что $x^{\ast }\simeq x_{k+1}$.

Плюсы

1. Высокая скорость сходимости при удачно выбранном начальном приближении, то есть если $x_0$ находится близко к $x^{\ast }$, то $\exists c>0\exists q\in (0,1):|x_k-x^{\ast }|\le C{q}^{2^k}\forall k$.

Минусы

1. При неудачном выборе начального приближения (то есть $x_0$ находится далеко от $x^{\ast }$) сходимость может замедляться. Более того, может оказаться, что метод вообще расходится. Требование $f^{\prime \prime }>0$ предъявляется к отрезку $[a,b]$. Вместе с тем может оказаться,что $x_{k+1}\notin [a,b]$ для некоторого $k$. Тогда возможна, например, ситуация, в которой $f^{\prime \prime }(x_{k+1})\simeq 0$. В этом случае приближение $x_{k+2}=x_{k+1}-\frac{f^{\prime }(x_{k+1})}{f^{\prime \prime }(x_{k+1})}$ уйдет на бесконечность.
2. Необходимость вычисления на каждой итерации первой и второй производных функции $f$.

Оптимизация мультимодальных функций

Рассмотрим функцию $f(x)$, определенную на $[a,b]$.

Условие Липшица

Функция удовлетворяет условию Липшица на с константой $L>0$, если $\forall x,y\in [a,b]|f(x)-f(y)|\le L|x-y|$.

Пусть $\alpha$ - угол наклона отрезка, соединяющего точки $(y,f(y))$ и $(x,f(x))$. Тогда $tg(\alpha )=\frac{f(x)-f(y)}{x-y}$ $⟹$ $|\tan \alpha |=\frac{|f(x)-f(y)|}{|x-y|}\le \frac{L|x-y|}{|x-y|}=L$. Таким образом, $f$ удовлетворяет на $[a,b]$ условию Липшица с константой $L$, если $\forall x,y\in [a,b]$ $|\tan \alpha |\le L$.

Теорема 1

Пусть $f(x)\in C^1[a,b]$. Тогда $f(x)$ удовлетворяет на $[a,b]$ условию Липшица с константой $L={\max }_{x\in [a,b]}|f^{\prime }(x)|$.

Доказательство $\forall x,y\in [a,b]$. Тогда $f(x)-f(y)=f^{\prime }(c)(x-y)$, где $c\in (a,b)$ $⟹$ $|f(x)-f(y)|=|f^{\prime }(c)||x-y|$, так как $f^{\prime }\in C[a,b]$, то $\exists {\max }_{x\in [a,b]}|f^{\prime }(x)|=L$ $⟹$ $|f^{\prime }(c)|\le L$. Следовательно, $|f(x)-f(y)|\le L|x-y|$

Выберем

Метод перебора

Решаем задачу $f(x){\to }_{x\in [a,b]}\min ,$где $f$ многомодальна на $[a,b]$ и удовлетворяет условию Липшица с константой $L$ на $[a,b]$.

Разобьём $[a,b]$ на $n$ равных частей точками $x_i=a+\frac{b-a}{n}i,i=\overline{0,n}$. Найдём узел $x_m$ такой, что $f(x_m)={\min }_{i=\overline{0,n}}f(x_i)$, и положим $x^{\ast }\simeq x_m$.

Теорема 2

Пусть $x_m$ - узел разбиения, такой, что $f(x_m)={\min }_{i=\overline{0,n}}f(x_i)$. Тогда $f(x_m)-f(x^{\ast })\le L\cdot \frac{b-a}{2n}$.

Доказательство $x_c$ узел, самый близкий к точке $x^{\ast }$. Тогда $|x_c-x^{\ast }|\le \frac{b-a}{2n}⟹(f(x^m)-f(x^{\ast }))=|f(x_c)-f(x^{\ast })|\le L|x_c-x^{\ast }|\le L\frac{b-a}{2n}$.

Обозначим через

Следствие

Чтобы найти минимум функции $f(x^{\ast })$ с точностью $\epsilon >0$, надо разбить $[a,b]$ на $n\ge \frac{b-a}{2\epsilon }$ частей.

Обоснование $f(x_m)-f(x^{\ast })\le \epsilon$, составим неравенство $L\cdot \frac{b-a}{2n}<\epsilon$ и решим его относительно $n$: $n\ge L\cdot \frac{b-a}{2\epsilon }$

Требуя, чтобы

Замечание. Даже если выполнено неравенство $f(x_m)-f(x^{\ast })\le \epsilon$, гарантировать хорошую точность для точки $\min x^{\ast }$ нельзя, то есть $|x_m-x^{\ast }|$ может оказаться большим $f(x_m)-f(x^{\ast })$ мало $|x_m-x^{\ast }|$ велико

Метод ломаных

$f(x){\to }_{x\in [a,b]}\min$, где $f(x)$ многомодальна и удовлетворяет условию Липшица с постоянной $L$ на $[a,b]$

Введём вспомогательную функцию $g(x,y)=f(y)-L|x-y|$, $x,y\in [a,b]$.

Построим 2 прямые с уравнениями $y=f(a)-L|x-a|$, и $y=f(b)+L(x-b)$. Найдём точку $(x_0,y_0)$ их пересечения $f(a)-L(x-a)=f(b)+L(x_0-b)$ $2L{x}_0=f(a)-f(b)+L(a+b)$ $x_0=\frac{f(a)-f(b)}{2L}+\frac{a+b}{2}$ $y_0=f(a)-L(x_0-a)=f(a)+La-\frac{f(a)-f(b)}{2}-\frac{L(a+b)}{2}=\frac{f(a)+f(b)}{2}+\frac{L(a-b)}{2}$

Таким образом, $x_0=\frac{f(a)-f(b)}{2L}+\frac{a+b}{2}$; $y_0=\frac{f(a)+f(b)}{2}+\frac{L(a-b)}{2}$

$P_0(x)$ - кусочно-линейная функция, её точка $\min$ $x_0^{\ast }-x_0$, её $\min p_0^{\ast }=y_0$. Положим $p_1(x)$ = $\max \{p_0(x),g(x,x_0^{\ast })\}$. У $p_1(x)$ по сравнению с $p_0(x)$ исчезла точка $\min x_0^{\ast }$, но появились две новые точки локального $\min :x_1^{\prime }$ и $x_1^{\prime \prime }$ $L=\frac{f(x_0^{\ast })-p_0^{\ast }}{2(x_0^{\ast }-x_1^{\prime })}$ $x_0^{\ast }-x_1^{\prime }=\frac{1}{2L}(f(x_0^{\ast }-p_0^{\ast }))$ $x_1^{\prime }=x_0^{\ast }-{\Delta }_1$, где ${\Delta }_1=\frac{1}{2L}(f(x_0^{\ast })-p_0^{\ast })$

В силу симметрии $x_1^{\prime \prime }-x_0^{\ast }+{\Delta }_1$ Очевидно, $p_1(x_1^{\prime })=p_1(x_1^{\prime \prime })=\frac{1}{2}(f(x_0^{\ast })+p_0)$. Обозначим $p_1^{\ast }=p_1(x_1^{\prime })=p_1(x_1^{\prime \prime })$. Выберем любую из точек $\min$ фукнции $p_1(x)$ и обозначим её через $x_1^{\ast }$. Пусть, например, $x_1^{\ast }=x_1^{\prime }$. Положим $p_2(x)=\max \{p_1(x),g(x,x_1^{\ast })\}$. У $p_2(x)$ по сравнению с $p_1(x)$ исчезла точка $\min x_1^{\ast }$ и появились две новые точки локального $\min$: $x_2^{\prime }$ и $x_2^{\prime \prime }$. $x_2^{\prime }=x_1^{\ast }-{\Delta }_2,x_2^{\prime \prime }=x_1^{\ast }+{\Delta }_2$, где ${\Delta }_2=\frac{1}{2L}(f(x_1^{\ast })-p_1^{\ast })$, при этом $p_2(x_2^{\prime })=p_2(x_2^{\prime \prime })=\frac{1}{2(f(x_1^{\ast })+p_1^{\ast })}$ и т. д.

Пусть $p_{k-1}(x)$ построена. Обозначим $x_{k-1}^{\ast }$ любую её точку минимума, $p_{k-1}^{\ast }=p_{k-1}(x_{k-1}^{\ast })$. Положим $p_k(x)=\max \{p_{k-1}(x),g(x,x_{k-1}^{\ast })\}$. У $p_k$ по сравнению с $p_{k-1}(x)$ исчезла точка $\min$ $x_{k-1}^{\ast }$ и появились 2 новые точки локального $\min$: $x_k^{\prime }=x_{k-1}^{\ast }-{\Delta }_k$, $x_k^{\prime \prime }=x_{k-1}^{\ast }+{\Delta }_k$, где ${\Delta }_k=\frac{1}{2L}(f(x_{k-1}^{\ast })-p_{k-1}^{\ast })$, причем $p_k(x_k^{\prime })=p_k(x_k^{\prime \prime })=\frac{1}{2}(f(x_{k-1})+p_{k-1}^{\ast })$.

У $p_k(x)$ есть $k+1$ точек локального $\min$. При этом $\forall k$ на $[a,b]$ выполняются неравенства $p_{k-1}(x)\le p_k(x)\le f(x)$.

При большом $k$ (то есть таком, что $f(x_k^{\ast })-p_k^{\ast }\le \epsilon$), положим, что задача решена и $x^{\ast }\simeq x_k^{\ast }$, $f(x^{\ast })\simeq f(x_k^{\ast })$.