Условия Каруша

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

История

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

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

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

Рассмотрим задачу нелинейной оптимизации.

$\min\limits_{x \in X} f(x)$

при условиях $g_i(x)\leqslant 0,\;i=1\ldots m$. Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.

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

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

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

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

Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. Существует несколько вариантов дополнительных условий, которые делают их достаточными.

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

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

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

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

Примечания

1. ↑ Условия Куна–Таккера
2. ↑ Жилинискас А., Шатлянис В. Поиск оптимума: компьютер расширяет возможности. - М.: Наука, 1989, с. 76, ISBN 5-02-006737-7

См. также

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

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 15 мая 2011.