Русская Википедия:Условия Каруша — Куна — Таккера
В теории оптимизации условия Каруша — Куна — Таккера (Шаблон:Lang-en, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.
История
Кун и Таккер обобщили метод множителей Лагранжа (для использования при построении критериев оптимальности для задач с ограничениями в виде равенств) на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств[1].
Необходимые условия локального минимума для задач с ограничениями исследуются давно. Одним из основных остаётся предложенный Лагранжем перенос ограничений в целевую функцию. Условия Куна-Таккера тоже выведены из этого принципа[2].
Постановка задачи
В задаче нелинейной оптимизации требуется найти значение многомерной переменной <math>x=(x^{(1)}, ..., x^{(n)})</math>, минимизирующее целевую функцию:
- <math>\min\limits_{x \in X} f(x)</math>
при условиях, когда на переменную <math>x</math> наложены ограничения типа неравенств:
- <math>g_i(x)\leqslant 0,\;i=1\ldots m</math>,
а компоненты вектора <math>x</math> неотрицательныШаблон:Sfn.
Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.
Необходимые условия минимума функции
Если <math>\hat{x}\in\arg\min f</math> при наложенных ограничениях — решение задачи, то найдётся вектор множителей Лагранжа <math>\lambda\in\R^m</math> такой, что для функции Лагранжа <math>L(x)=f(x)+\sum^m_{i=1}\lambda_i g_i(x)</math> выполняются условия:
- стационарности: <math>\min_x L(x)=L(\hat{x})</math>;
- дополняющей нежёсткости: <math>\lambda_i g_i(\hat{x})=0,\;i=1\ldots m</math>;
- неотрицательности: <math>\lambda_i \geqslant 0,\;i=1\ldots m</math>.
Достаточные условия минимума функции
Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. При условии, что функции <math>f</math> и <math>g_1,\dots,g_m</math> выпуклы существует несколько вариантов дополнительных условий, которые делают условия из теоремы Каруша — Куна — Таккера достаточными:
Простая формулировка
Если для допустимой точки <math>\hat{x}</math> выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также <math>\lambda_1>0</math>, то <math>\hat{x}\in\arg\min f</math>.
Более слабые условия
Если для допустимой точки <math>\hat{x}</math> выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также <math>\exists\tilde{x}: g_i(\tilde{x})<0,\;i=1\ldots m</math> (условие Слейтера), то <math>\hat{x}\in\arg\min f</math>.
Примечания
См. также
Литература
- ↑ Шаблон:Cite web
- ↑ Жилинискас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 76, ISBN 5-02-006737-7
