Методы одномерного поиска

МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Методы нелинейного программирования классифицируются по разным признакам. На рис. 3.10 приведена упрощенная схема классификации, в которой каждая группа представлена тремя наиболее распространенными методами.

Рис. 3.10. Классификация методов нелинейного программирования

Методы одномерного поиска

Функция одной переменной, имеющая в интервале исследования [ a, b ] один оптимум, называется унимодальной. Или более строгое определение унимодальности функции. Функция унимодальна, если выполняются следующие условия при поиске максимума:

1) если , и , то Y ;

2) если , и , то Y .

Унимодальная функция не обязательно должна быть гладкой и даже непрерывной она может быть в некоторых точках интервала неопределенной. Предположение унимодальности не связано с жесткими ограничениями и выполняется во многих практических задачах поиска оптимума. Если целевая функция унимодальна, то можно сузить интервал исследования функции на оптимум путем определения значений целевой функции в двух точках интервала задания функций Y () и Y () и последующего сравнения. При этом возможны три случая при поиске максимума (рис. 3.11):

1) если значение целевой функции в точке больше значения целевой функции в точке (), то , т.е. оптимум не может лежать правее точки , иначе нарушается предположение об унимодальности функции (следовательно, интервал [ , b ] из дальнейшего рассмотрения исключается);

2) если значение целевой функции в точке больше значения целевой функции в точке (), то , т. е. оптимум не может лежать левее точки , иначе нарушается предположение об унимодальности функции (следовательно, интервал [ a, ] из дальнейшего рассмотрения исключается);

3) если значения целевой функции в точках и равны (), то , т.е. оптимум не может лежать правее точки и левее точки , иначе нарушается предположение об унимодальности функции (следовательно, интервалы [ a, ] и [ , b ] из дальнейшего рассмотрения исключается).

Как правило, задачи одномерной оптимизации имеют унимодальную целевую функцию.

Последовательно сужая интервал исследования, в котором находится оптимальное значение искомой переменной, можно с достаточной степенью точности найти это оптимальное значение. Для этого необходимо выработать такую стратегию поиска, чтобы за меньшее число шагов (этапов) определить минимальный интервал, в котором лежит искомый оптимум, или свести исходный интервал до области заданной длины за минимальное число шагов.

К последовательным детерминированным методам поиска экстремума унимодальных функций относятся методы сканирования, дихотомии, золотого сечения и Фибоначчи.