Лекция: Методы одномерного поиска

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

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

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

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

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

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

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

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

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

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

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

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

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

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