Метод модифицированной функции Лагранжа.

Соотношение y(x* , l)£ y(x* ,l*)£ y(x ,l*) "xÎRⁿ, l ³ 0

записывается так в случае функции Лагранжа.

 

(*) y(x* ,l*) = y(x ,l) = y(x ,l) = f(x*)

Если назвать x прямыми переменными, а l двойственными, то видно, что прямые и двойственные переменные равноправны.

Доказательство (*):

1. y(x ,l) ³ y(x ,l*) = y(x* ,l*) = f(x*) + (l*, g(x*))

y(x ,l)£ y(x* ,l) = y(x* ,l*) = f(x*)

То есть y(x ,l) = f(x*)

2. y(x ,l) ³ y(x ,l) = y(x* ,l*) = f(x*)

y(x ,l)£ y(x* ,l) = y(x* ,l*) = f(x*) отсюда следует

y(x ,l) = f(x*).

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

Можно показать, что седловая точка определяется соотношениями:

,где

Если на x наложены ограничения (x ³ 0), то :

Существуют различные методы поиска седловой точки, например: