ВИ Одномерная оптимизация. Унимодальные функции

Унимодальные функции

Пусть дана функция 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 с заданной точностью.

Наиболее известными являются :

  • метод золотого сечения
  • метод деления отрезка пополам
  • метод сканирования.
Updated: 20.09.2015 at 06:37
Метки: