Interested Article - Условия Каруша — Куна — Таккера

В теории оптимизации условия Каруша — Куна — Таккера ( англ. Karush — Kuhn — Tucker conditions , KKT) — необходимые условия решения задачи нелинейного программирования . Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа . В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения , а неравенства .

История

Кун и Таккер обобщили метод множителей Лагранжа (для использования при построении критериев оптимальности для задач с ограничениями в виде равенств) на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств .

Необходимые условия локального минимума для задач с ограничениями исследуются давно. Одним из основных остаётся предложенный Лагранжем перенос ограничений в целевую функцию. Условия Куна-Таккера тоже выведены из этого принципа .

Постановка задачи

В задаче нелинейной оптимизации требуется найти значение многомерной переменной $x=(x^{(1)},...,x^{(n)})$ $x=(x^{{(1)}},...,x^{{(n)}})$ , минимизирующее целевую функцию:

\min \limits _{x\in X}f(x)

\min \limits _{{x\in X}}f(x)

при условиях, когда на переменную $x$ $x$ наложены ограничения типа неравенств:

g_{i}(x)\leqslant 0,\;i=1\ldots m

g_{i}(x)\leqslant 0,\;i=1\ldots m

,

а компоненты вектора $x$ $x$ неотрицательны .

Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер .

Необходимые условия минимума функции

Если ${\hat {x}}\in \arg \min f$ ${\hat {x}}\in \arg \min f$ при наложенных ограничениях — решение задачи, то найдётся вектор множителей Лагранжа $\lambda \in \mathbb {R} ^{m}$ $\lambda \in \mathbb{R} ^{m}$ такой, что для функции Лагранжа $L(x)=f(x)+\sum _{i=1}^{m}\lambda _{i}g_{i}(x)$ $L(x)=f(x)+\sum _{{i=1}}^{m}\lambda _{i}g_{i}(x)$ выполняются условия:

стационарности : $\min _{x}L(x)=L({\hat {x}})$ $\min _{x}L(x)=L({\hat {x}})$ ;
дополняющей нежёсткости : $\lambda _{i}g_{i}({\hat {x}})=0,\;i=1\ldots m$ $\lambda _{i}g_{i}({\hat {x}})=0,\;i=1\ldots m$ ;
неотрицательности : $\lambda _{i}\geqslant 0,\;i=1\ldots m$ $\lambda _{i}\geqslant 0,\;i=1\ldots m$ .

Достаточные условия минимума функции

Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. При условии, что функции $f$ $f$ и $g_{1},\dots ,g_{m}$ $g_{1},\dots ,g_{m}$ выпуклы существует несколько вариантов дополнительных условий, которые делают условия из теоремы Каруша — Куна — Таккера достаточными:

Простая формулировка

Если для допустимой точки ${\hat {x}}$ ${\hat {x}}$ выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также $\lambda _{1}>0$ $\lambda _{1}>0$ , то ${\hat {x}}\in \arg \min f$ ${\hat {x}}\in \arg \min f$ .

Более слабые условия

Если для допустимой точки ${\hat {x}}$ ${\hat {x}}$ выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также $\exists {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ $\exists {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ ( условие Слейтера ), то ${\hat {x}}\in \arg \min f$ ${\hat {x}}\in \arg \min f$ .

Примечания

(неопр.) . Дата обращения: 7 февраля 2011. 24 января 2011 года.
Жилинискас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 76, ISBN 5-02-006737-7
, с. 253.

См. также

Исследование операций

Литература

Дж. Хедли. Нелинейное и динамическое программирование. — М. : Мир, 1967. — 506 с.
Коршунов Ю. М. Математические основы кибернетики. — М. : Энергия, 1980. — 424 с.