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

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

История

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

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

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

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

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

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

$g_i(x)⩽0,i=1\dots m$,

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга