Унимодальные функции
[latexpage]
Пусть дана функция $y=f(x)$, непрерывная на некотором множестве $X$, являющемся подмножеством множества действительных чисел $R (X \subset R)$.
Задачей безусловной оптимизации для функции $y=f(x)$ называется задача отыскания всех её локальных минимумов (максимумов) в случае, если множество $X$ совпадает с множеством $R (X = R)$ .
Функция $y=f(x)$ называется при этом целевой функцией.
Задачу отыскания локального минимума целевой функции $y=f(x)$ символически записывают так:
\[
f(x) \to min, x \in R
\]
Определение. Непрерывная функция $y=f(x)$ называется унимодальной на отрезке $[a,b]$, если:
1. точка $x_0$ локального минимума функции принадлежит отрезку $[a,b]$;
2. для любых двух точек отрезка $x_1,x_2$, взятых по одну сторону от точки минимума, точке, более близкой к точке минимума соответствует меньшее значение функции; то есть из условий $x_2<x_1<x_0$ или $x_0<x_1<x_2$ следует условие $f(x_1)<f(x_2)$.
Достаточное условие унимодальности функции $y=f(x)$ на отрезке $[a,b]$ содержится в следующей теореме.
Теорема. Если функция $y=f(x)$ дважды дифференцируема на отрезке $[a,b]$ и $f»(x)>0$ в любой точке этого отрезка, то данная функция является унимодальной на отрезке $[a,b]$.
Заметим, что условие определяет выпуклость вниз (вогнутость) функции на указанном отрезке.
Схема сужения промежутка унимодальности функции.
Пусть требуется решить задачу
\[
f(x) \to min, x \in X, X \subset R.
\]
Применение численных методов для отыскания точек $x_0$ локального минимума предполагает:
1. определение промежутков унимодальности функции, то есть нахождение отрезков, каждому из которых принадлежит одна точка локального минимума;
2. вычисление значения $x_0$, принадлежащего выбранному промежутку, с заданной точностью.
Для непрерывной функции $f(x)$ строят её график на некотором отрезке $[a,b]$ и, если окажется, что на этом отрезке функция выпукла вниз, то $[a,b]$ — отрезок унимодальности функции. Отрезок $[a,b]$ берётся, по возможности, малым.
При вычислении точки минимума точность достигается последовательным уменьшением отрезка $[a,b]$, содержащего точку $x_0$, до размеров, не превышающих заданную точность $\epsilon$ .
Рассмотрим один из приёмов, позволяющих сузить отрезок унимодальности функции. Пусть функция $f(x)$ унимодальна на отрезке $[a,b]$. Возьмём две произвольные точки $x_1$ и $x_2$ , принадлежащие этому отрезку и такие, что $x_1<x_2$ .
Возможны, очевидно, следующие три случая, в каждом из которых можно указать отрезок меньших размеров $[a_1,b_1]$, содержащий точку минимума $x_0$ и принадлежащий первоначальному отрезку:
1. Если $y_1=f(x_1)<y_2=f(x_2)$, то положим $a_1=a$, $b_1=x_2$ и получим меньший отрезок унимодальности $[a_1,b_1]$.
2. Если $y_1=f(x_1)>y_2=f(x_2)$, то положим $a_1=x_1$, $b_1=b$.
3. Если $y_1=f(x_1)=y_2=f(x_2)$, то, очевидно, $a_1=x_1$, $b_1=x_2$ .
Методы, с помощью которых вычисляют значения точки минимума функции одной переменной, отличаются алгоритмами выбора точек $x_1$ и $x_2$ для локализации точки $x_0$ с заданной точностью.
Наиболее известными являются :
- метод золотого сечения
- метод деления отрезка пополам
- метод сканирования.