Оптимизация нелинейных целевых функций при наличии ограничений

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

Прежде всего остановимся на исследовании необходимых и достаточных условий оптимума целевой функции при наличии ограничений. Предположим вначале, что ограничения заданы функциями вида равенств фу (Л')=0, j = 1,2,..т. Для простоты рассуждений рассмотрим

случай, когда целевая функция равна / = f(x{2) и задано одно ограничение ф(.т,, д:2) = 0. Пусть / = f(x]9x2) = у4 определяет уравнение линии равного уровня.

В точке оптимума линия, задаваемая ограничением ф(*,, *2) = 0, и одна из линий равного уровня /=f(x],x2) = А должны касаться друг друга (рис. 1.17). Здесь А - точка оптимума X* =(*,*, *2)• Определим направление вектор-градиентов целевой функции / = /(лг,,л:2) и функции ограничений ф(.т,,х2). По определению, градиенты являются нормалями к касательным, проведенным к линиям равного уровня. Так как в точке оптимума касательные к целевой функции и функции ограничений совпадают, то градиенты целевой функции и функции, задаваемой ограничениями, коллинеарны, а их величины пропорциональны с точностью до множителя X.

Отсюда в точке X должны выполняться: во-первых, условие, связывающее вектор-градиенты целевой функции и функции ограничений:

во-вторых, требование, задаваемое ограничением

Полученные равенства являются необходимыми условиями оптимума, а для выпуклых функций - не только необходимыми, но и достаточными. Их можно получать аналитически, если образовать вспомогательную функцию ЬуХ9к)9 объединив целевую функцию с ограничениями с помощью неопределенных множителей Хг В общем случае

Геометрическая интерпретация условий оптимума при ограничениях в форме равенств

Рис. 1.17. Геометрическая интерпретация условий оптимума при ограничениях в форме равенств

Функция L, называемая функцией Лагранжа, уже не содержит ограничений. Множители X новой функции называются множителями Лагранжа. Необходимым условием экстремума является обращение в ноль частных производных по переменным X и Х9 а именно:

Итак, имеем систему из (/и + л) уравнений с п величинами х(, и т величинами Xj. В стационарной точке множители Лагранжа могут быть отрицательными, положительными или нулевыми.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >