В теории оптимизации условия Каруша — Куна — Таккера (, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.
История Кун и Таккер обобщили метод множителей Лагранжа (для использования при построении критериев оптимальности для задач с ограничениями в виде равенств) на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств.
Необходимые условия локального минимума для задач с ограничениями исследуются давно. Одним из основных остаётся предложенный Лагранжем перенос ограничений в целевую функцию. Условия Куна-Таккера тоже выведены из этого принципаЖилинискас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 76, ISBN 5-02-006737-7.
Постановка задачи В задаче нелинейной оптимизации требуется найти значение многомерной переменной , минимизирующее целевую функцию:
при условиях, когда на переменную наложены ограничения типа неравенств:
,
а компоненты вектора неотрицательны.
Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.
Необходимые условия минимума функции Если при наложенных ограничениях — решение задачи, то найдётся вектор множителей Лагранжа такой, что для функции Лагранжа выполняются условия: стационарности: ; дополняющей нежёсткости: ; неотрицательности: .
Достаточные условия минимума функции Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. При условии, что функции и выпуклы существует несколько вариантов дополнительных условий, которые делают условия из теоремы Каруша — Куна — Таккера достаточными:
Простая формулировка Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также , то .
Более слабые условия Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также (условие Слейтера), то .
Примечания
См. также Исследование операций
Литература
Категория:Теория оптимизации Категория:Микроэкономика Категория:Математические методы в экономике