Унимодальные функции
Пусть дана функция , непрерывная на некотором множестве , являющемся подмножеством множества действительных чисел .
Задачей безусловной оптимизации для функции называется задача отыскания всех её локальных минимумов (максимумов) в случае, если множество совпадает с множеством .
Функция называется при этом целевой функцией.
Задачу отыскания локального минимума целевой функции символически записывают так:
Определение. Непрерывная функция называется унимодальной на отрезке , если:
1. точка локального минимума функции принадлежит отрезку ;
2. для любых двух точек отрезка , взятых по одну сторону от точки минимума, точке, более близкой к точке минимума соответствует меньшее значение функции; то есть из условий или следует условие .
Достаточное условие унимодальности функции на отрезке содержится в следующей теореме.
Теорема. Если функция дважды дифференцируема на отрезке и в любой точке этого отрезка, то данная функция является унимодальной на отрезке .
Заметим, что условие определяет выпуклость вниз (вогнутость) функции на указанном отрезке.
Схема сужения промежутка унимодальности функции.
Пусть требуется решить задачу
Применение численных методов для отыскания точек локального минимума предполагает:
1. определение промежутков унимодальности функции, то есть нахождение отрезков, каждому из которых принадлежит одна точка локального минимума;
2. вычисление значения , принадлежащего выбранному промежутку, с заданной точностью.
Для непрерывной функции строят её график на некотором отрезке и, если окажется, что на этом отрезке функция выпукла вниз, то — отрезок унимодальности функции. Отрезок берётся, по возможности, малым.
При вычислении точки минимума точность достигается последовательным уменьшением отрезка , содержащего точку , до размеров, не превышающих заданную точность .
Рассмотрим один из приёмов, позволяющих сузить отрезок унимодальности функции. Пусть функция унимодальна на отрезке . Возьмём две произвольные точки и , принадлежащие этому отрезку и такие, что .
Возможны, очевидно, следующие три случая, в каждом из которых можно указать отрезок меньших размеров , содержащий точку минимума и принадлежащий первоначальному отрезку:
1. Если , то положим , и получим меньший отрезок унимодальности .
2. Если , то положим , .
3. Если , то, очевидно, , .
Методы, с помощью которых вычисляют значения точки минимума функции одной переменной, отличаются алгоритмами выбора точек и для локализации точки с заданной точностью.
Наиболее известными являются :
- метод золотого сечения
- метод деления отрезка пополам
- метод сканирования.