Тема 6.6. Одномерная оптимизация

Известно, что необходимым условием существования экстремума дифференцируемой функции f(x) является выполнение равенства f¢(х) = 0. Точка х, удовлетворяющая данному условию, называется точкой стационарности. Достаточнымусловием существования минимума в точке стационарности является выполнение неравенства f¢¢(х)>0, а максимума - f¢¢(х)<0.

Задача одномерной оптимизации имеет единственное решение в том случае, если функция f(x)на отрезке [a;b] имеет только один экстремум. Тогда говорят, что функция унимодальная на отрезке [a;b].

Достаточнымиусловиями унимодальности функции на отрезке [a;b] являются:

1.Длядифференцируемой функции f(x) ее производная f¢(х) -неубывающая.

2.Для дважды дифференцируемой функции f(x) выполняется неравенство f¢¢(х)³0.

Все численные методы одномерной оптимизации применяются только для унимодальных на определенном интервале функций.

Пример 6.6.1-1. Провести исследование функции f(x) = x³ – x + e^-x на предмет существования экстремумов.

Вначале проведем графическое исследование. Построим график функции f(x) (рис. 6.6.1-2). Из графика видно, что f(x) имеет две точки минимума: х₁ и х₂, причем точка х₁ – точка глобального минимума. Исходя из графика, можно принять следующие отрезки неопределенности: для точких₁ - [-4;-3], а для точки х₂ - [0;1].

Рис. 6.6.1-2

Проверим достаточное условие существования минимума на выбранных отрезках:

f¢(x) = 3x² – 1 – e^-x; f¢¢ (x) = 6x + e^-x,

f¢(0) < 0, f¢(1) > 0, f¢¢ (x) > 0 для хÎ[0;1],

f¢(-4) < 0, f¢(-3) > 0, f¢¢ (x) > 0 для хÎ[-4;-3].

Условия существования минимума выполнены, поскольку f¢¢(x) > 0 для всех хÎ[0;1] и хÎ[-4;-3]. Следовательно, функция f(x) является унимодальной на выбранных отрезках.

На практике численные методы одномерной оптимизации применяют в следующих случаях:

· значения функции f(x) определены в ходе эксперимента;

· целевая функция очень сложна или не имеет непрерывных производных;

· классические методы поиска оптимального значения не применимы.

Суть методоводномерного поисказаключается в том, что на каждой итерации интервал неопределенности уменьшается и стягивается к точке минимума. Уменьшение отрезка происходит до тех пор, пока на некоторой n-й итерации отрезок неопределенности [b_n;a_n] не станет соизмеримым с заданной погрешностью e, то есть будет выполняться условие |b_n-a_n| < e. Тогда за точку минимума можно принять любую точку, принадлежащую этому отрезку, в частности, его середину.

Простейшим способом сужения интервала неопределенности является деление его на некоторое число равных частей с последующим вычислением значений целевой функции в точках разбиения. Очевидно, что за минимум принимают наименьшее из этих значений – это так называемый метод сканирования. На практике чаще применяют одну из основных модификаций метода – метод прямого перебора с переменным шагом. Суть его заключается в следующем. От начальной точки интервала неопределенности двигаются с начальным шагом до тех пор, пока функция в точках разбиения уменьшается (т.е. функция убывает). Если функция в очередной точке стала возрастать, то происходит сужение интервала неопределенности путем возврата от этой рассматриваемой (которая станет правой границей нового интервала) точки на два шага назад. Полученная таким образом точка будет левой границей нового отрезка. Новый отрезок вновь исследуют таким же образом, но уже с уменьшенным в два раза шагом. Процесс повторяется до момента достижения заданной точности минимума. Это весьма трудоемкий путь. Более эффективными являются методы одномерного поиска с другими способами выбора узлов и сужения интервалов неопределенности.

Рассмотрим, в частности, метод дихотомии и метод золотого сечения.