9.4. Теорема Куна-Таккера

Описанный подход обобщения метода множителей Лагранжа связан с необходимостью решения большого числа промежуточных задач при определении экстремального значения целевой функции. Однако если функция Лагранжа в точке глобального экстремума исходной функции f(Х) имеет особенность, так называемую седловую точку, то схема обобщения метода множителей Лагранжа принимает более простую форму.

Седловой точкой для функции Лагранжа (локальной седловой точкой) называется точка =(x₁^(o), x₂^(o),..., x_n^(o), ₁^(o), ₂^(o),..., _m^(o)), для которой для всех Х из -окрестности точки и всех из -окрестности точки будут выполняться неравенства L(X, ^(o))  L(X^(o), ^(o))  L(X^(o), ).

Точка определена как точка максимума функции Лагранжа по Х и минимума L по .

Если неравенство L(X, ^(o))  L(X^(o), ^(o))  L(X^(o), ) выполняется для любых Х и , то точка является глобальной седловой точкой.

Центральное место в теории нелинейного программирования занимает теорема Куна-Таккера, которая устанавливает связь между условиями существования в точке глобальной седловой точки функции Лагранжа и необходимыми и достаточными условиями, которым должна удовлетворять точка X⁰=( ), в которой целевая функция f(Х) достигает абсолютного условного экстремума.

Пусть дана ЗНП: найти максимальное значение функции Z=f(x₁,x₂,...,x_n) при ограничениях

_i (x₁,x₂,...,x_n)=0, i=1,2,...,m,

x₁, x₂, ... ,x_n  0 (9)

Составим функцию Лагранжа для данной задачи:

L(X,)=f(X) + (10)

Если выполняется условие регулярности ( существует по крайней мере одна точка X, для которой _i (X)>0 для всех i), то имеет место следующая теорема.

Теорема Куна-Таккера. Вектор X^(o) тогда и только тогда является оптимальным решением задачи (9), когда существует такой вектор ^(o), что при X^(o)  0 и ^(o)  0 для всех X  0 и   0

L(X, ^(o))  L(X^(o), ^(o))  L(X^(o), ). (11)

Теорема также называется теоремой о седловой точке.

Доказательство достаточности условий (11). Пусть X^(o) > 0 и ^(o) > 0 - седловая точка функции L(X, ). Если в (11) вместо L(X, ) подставить ее значение (10), то получим

f(X)+ f(X^(o))+ f(X^(o))+

при X  0,   0.

Правое неравенство справедливо при любом   0, поэтому

_i (X)  0, =0.

Тогда из левого неравенства получим

f(X^(o))  f(X)+ при X  0.

Так как при этом  0, то f(X^(o))  f(X).

Таким образом, точка X^(o) удовлетворяет ограничениям (11) и во всех других точках функция принимает значение меньшее, чем в X^(o). Это утверждение приводит решение задачи к отысканию седловых точек функции Лагранжа L(X,).

Доказательство необходимости условий (11) ввиду его сложности не рассматривается.

Если f(X) и _i(X) - дифференцируемые функции, то (11) эквивалентны следующим локальным условиям Куна-Таккера:

(12)

(13)

Выражение означает, что значение частной производной функции Лагранжа берется в точке (X^(o), ^(o)), где X^(o)=(x₁^(o), x₂^(o),..., x_n^(o)), ^(o)=( ₁^(o), ₂^(o),..., _m^(o)).

Пример. Найти max Z = -x₁² -x₂² при ограничениях

x₁0, x₂0.

Решение. С помощью графического метода легко решить данную задачу: x₁=0,8, x₂=0,4, Z= -0,8.

Покажем, что существует ^(o)  0, при котором в точке оптимума выполняются условия Куна-Таккера (12), (13) для функции F(X, ):

F(X, )=-x₁²-x₂²+₁(2x₁+x₂-2)+₂(8-2x₁-x₂)+₃(6-x₁-x₂).

Находим:

= -2x₁+2₁-₃; = -2x₂+₁-₂-₃;

=2x₁+x₂-2; =8-2x₁-x₂; =6-x₁-x₂.

Согласно условиям (13) ₂ и ₃ должны принимать нулевые значения, так, как, подставляя x₁=0,8 и x₂=0,4 в выражения и , имеем значения, большие нуля, а по условию, . Согласно условию ₁ может принимать ненулевое значение, так как . В соответствии с (12) производная (j=1,2) должна принимать ненулевые значения, так как координаты вектора X^(o) отличны от нуля. Находим ₁=0,8. Следовательно, в точке (X^(o), ^(o)) выполняются условия Куна-Таккера и она действительно является точкой экстремума.