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

Соотношение 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*))

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), то:

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