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

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

$p(x)=p_0+p_1(x-a)+p_2(x-a)(x-\overline{x})$ $\overline{x}=\frac{a+\overline{x}}{2}-\frac{p_1}{2p_2}$

Что выбирать в качестве пробных точек на $[a,b]$? Далее применяем идею методов исключения отрезков, рассматривая в качестве пробных точек $\tilde{x}$ и $\overline{x}$. Возможны 4 варианта (ту из пробных точек исходного отрезка, которая окажется внутри нового отрезка поиска, принимаем за новую точку $\tilde{x}$).

1. $\tilde{x}<\overline{x}$
   1. Если $f(\tilde{x})\le f(\overline{x})$, то полагаем, что $b=\overline{x}$
   2. Если $f(\tilde{x})>f(\overline{x})$, то полагаем $a=\tilde{x}$, $\tilde{x}=\overline{x}$
2. $\overline{x}<\tilde{x}$
   1. Если $f(\overline{x})\le f(\tilde{x})$, то полагаем $b=\tilde{x}$, $\tilde{x}=\overline{x}$
   2. Если $f(\overline{x})>f(\tilde{x})$, то положим $a=\overline{x}$

Если оказалось, что на исходном отрезке $[a,b]$ $\tilde{x}=\overline{x}$, то в качестве второй пробной точки на исходном отрезке $[a,b]$ берем любую другую внутреннюю точку отрезка. Итог выполненных переобозначений - 3 новые точки $a,b,\tilde{x}$. Для нового отрезка $[a,b]$ повторяем описанные действия, начиная с построения параболы $p(x)$ через новые точки $(0,f(a))$, $(\tilde{x},f(\tilde{x}))$, $(b,f(b))$.

Схема алгоритма: 0) Задать точность $\epsilon >0$.

1. Выбрать $\tilde{x}\in (a,b):f(\tilde{x})<f(a),f(\tilde{x})<f(b)$
2. Найти $\overline{x}$ по формуле 1. На 1 итерации перейти к шагу 4
3. Проверка на окончание поиска. Если модуль разности значений $\overline{x}$, найденных на этой и на предыдущей итерации $<\epsilon$, то полагаем что $x^{\ast }=\overline{x}$ и поиск завершён.
4. Уменьшение отрезка поиска. Найти новые точки $a,b,\tilde{x}$, используя пункты 1.1, 1.2, 2.1, 2.2. Перейти к шагу 2.

Минимизация дифференцируемых функций одной переменной

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

Выпуклая функция

Функцию $f(x)$ называют выпуклой на $[a,b]$, если $\forall x,y\in [a,b]\forall \alpha \in [0,1]$ выполнено $f(\alpha x+(1-\alpha )y)\le \alpha f(x)+(1-\alpha )f(y)$.

Функцию $f(x)$ называют строго выпуклой на bye hello

Утверждение

Пусть $f(x)$ выпукла на $[a,b]$, $\tilde{x}\in [a,b]$, $\tilde{x}\in (a,b)$ - точка локального минимума функции $f(x)$. Тогда $\tilde{x}$ - точка глобального минимума $f(x)$ на $[a,b]$.

Обоснование $\exists x^{\ast }\in [a,b]:f(x^{\ast })<f(\tilde{x})$. Рассмотрим $f(\alpha x^{\ast }+(1-\alpha )\tilde{x})$ при $\alpha \in (0,1]$. Так как $f$ выпукла, то $f(\alpha x^{\ast }+(1-\alpha )\tilde{x})\le \alpha f(x^{\ast })+(1-\alpha )f(\tilde{x})<\alpha f(\tilde{x})+(1-\alpha )f(\tilde{x})=f(\tilde{x})$ $⟹$ $\tilde{x}$ - не точка локального минимума - противоречие $⟹$ $\tilde{x}$ - точка глобального минимума.

От противного: предположим, что

Утверждение

Пусть $f(x)$ строго выпукла на $[a,b]$ и $x^{\ast }$ - точка глобального минимума $f(x)$ на $[a,b]$. Тогда других точек глобального минимума у $f(x)$ на $[a,b]$ нет.

Обоснование $\overline{x}$ - ещё одна точка глобального минимума $f(x)$ на $[a,b]$. Рассмотрим $f(\alpha x^{\ast }+(1-\alpha )\overline{x})$ при $\alpha \in (0,1)$: $f(\alpha x^{\ast }+(1-\alpha )\overline{x})<\alpha f(x^{\ast })+(1-\alpha )f(\overline{x})=\alpha f(x^{\ast })+(1-\alpha )f(x^{\ast })=f(x^{\ast })$ $⟹$ в промежуточных точках между $x^{\ast }$ и $\overline{x}$ значения функции $f$ меньше, чем в точке $x^{\ast }$ - противоречие $⟹$ точка глобального минимума у строго выпуклой функции единственна.

От противного: предположим, что

Утверждение

Если $f(x)$ строго выпукла на $[a,b]$, то $f(x)$ унимодальна на $[a,b]$. Так как $f$ строго выпукла на $[a,b]$, то $f$ непрерывна на $[a,b]$

Обоснование $⟹$ $\exists$ точка глобального минимума функции $f$ на $[a,b]$. Предположим, что у $f$ есть другая точка локального минимума. Но так как $f$ выпукла, эта точка является точкой локального минимума функции $f$ на $[a,b]$. Но $f$ строго выпукла, поэтому точка локального минимума единственна. Таким образом, у $f$ на $[a,b]$ нет других точек локального минимума кроме точки глобального минимума. $⟹$ $f$ унимодальна на $[a,b]$.

Следствие. Пусть $f(x)$ дважды дифференцируема на $[a,b]$. Если $f^{\prime \prime }(x)>0\forall x\in [a,b]$, то $f(x)$ унимодальна на $[a,b]$.