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

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

Прежде всего остановимся на исследовании необходимых и достаточных условий оптимума целевой функции при наличии ограничений. Предположим вначале, что ограничения заданы функциями вида равенств ф_у (Л')=0, j = 1,2,.т. Для простоты рассуждений рассмотрим случай, когда целевая функция равна / = f (x_{, х₂) и задано одно ограничение ф (.т, д:₂) = 0. Пусть / = f (x_]9x₂) ^{= у}4 определяет уравнение линии равного уровня.

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

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

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

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

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

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

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