2.1. Задача нелинейного программирования при ограничениях – неравенствах

Теорема Куна-Таккера. Рассмотрим случай задачи с ограничениями-неравенствами:

(2.1)

при ограничениях

, .

(2.2)

В точке минимума неравенства могут выполняться как равенства или строгие неравенства.

Ограничение называется активным в точке , если оно выполняется в ней как строгое равенство, то есть если .

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

, . (2.3)

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

Пусть точка является точкой минимума задачи (2.1) с ограничениями (2.3). Обозначим множество индексов активных ограничений через

.

(2.4)

Например, на рис. 2.1 приведен пример минимизации с линейными ограничениями. Выберем любую допустимую точку из . Вектор направлен из внутрь области . Такой вектор будем называть входящим. Для этого вектора с учетом того, что , можно записать следующее условие:

,

или

,

(2.5)

для всех и .

Рис. 2.1.

Таким образом, входящий вектор определяет допустимое направление перемещения из точки . Но так как минимальна в точке , то при любом , удовлетворяющем (2.5), будем иметь:

, .

(2.6)

Применим теперь теорему, которая есть следствием леммы Фаркаша. Из условий (2.5), (2.6) на основании леммы Фаркаша следует, что существует множество неотрицательных скаляров , для которых

.

(2.7)

Если принять, что при (то есть для неактивных ограничений), (2.7) можно переписать в виде

.

(2.8)

Кроме того, получим, что

.

(2.9)

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

(2.10)

Следовательно, удовлетворяет следующим условиям:

,		(2.11)
, , .	(2.12)

При рассмотрении задачи минимизации при условиях может случиться так, что не будет существовать таких , , для которых без дополнительных предположений о природе функций были бы справедливы уравнения (2.9), (2.10), где - оптимальное решение. Эти дополнительные предположения называют условиями регулярности ограничений. В частности, в рассмотренном случае, в качестве таких условий использовали линейную независимость векторов-градиентов ограничений , .

Теорема Куна-Таккера. Выше найдены условия оптимальности (2.9), (2.10) для задачи НП с линейными ограничениями. Обобщим эти условия на случай задачи (2.1), (2.2), когда все ограничения нелинейны.

Условия оптимальности решения задачи НП формулируются в следующей теореме, имеющей исключительно важное значение в теории нелинейного программирования.

Теорема 1.1. (Куна-Таккера). Пусть функции , , имеют непрерывные частные производные на некотором открытом множестве , содержащем точку . Если является точкой минимума функции при ограничениях , , удовлетворяющих условию регулярности в виде линейной независимости векторов , то существуют такие неотрицательные множители Лагранжа, что

,	(2.13)
, , .		(2.14)

Определим функцию Лагранжа следующим образом:

.

(2.15)

Тогда теорему Куна-Таккера можно записать в виде

,	(2.16)
,		(2.17)

.

(2.18)

Заметим, что множители Лагранжа в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.