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

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

ИсторияПравить

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

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

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

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

$\underset{x\in <!--\; \in \; -->X}{min}f(x)$$\min \limits _{{x\in X}}f(x)$ 

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

$g_i(x)⩽<!--\; ⩽\; -->0,i=1\dots <!--\; \dots \; -->m$$g_{i}(x)\leqslant 0,\;i=1\ldots m$ ,

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

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

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

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

• стационарности: $\underset{x}{min}L(x)=L(\stackrel{^<!--\; ^\; -->}{x})$$\min _{x}L(x)=L({\hat {x}})$ ;
• дополняющей нежёсткости: ${\mathrm{\lambda <!--\; \lambda \; -->}}_i{g}_i(\stackrel{^<!--\; ^\; -->}{x})=0,i=1\dots <!--\; \dots \; -->m$$\lambda _{i}g_{i}({\hat {x}})=0,\;i=1\ldots m$ ;
• неотрицательности: ${\mathrm{\lambda <!--\; \lambda \; -->}}_i⩾<!--\; ⩾\; -->0,i=1\dots <!--\; \dots \; -->m$$\lambda _{i}\geqslant 0,\;i=1\ldots m$ .

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

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

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

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

Более слабые условияПравить

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

См. такжеПравить

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

ЛитератураПравить

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