WikiSort.ru - Не сортированное

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

История

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

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

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

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

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

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

${\displaystyle g_{i}(x)\leqslant 0,\;i=1\ldots m}$ ,

а компоненты вектора ${\displaystyle x}$ неотрицательны^[3].

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

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

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

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

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

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

Примечания

См. также

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

Литература

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

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.