В теории оптимизации условия Каруша — Куна — Таккера (англ. Karush — Kuhn — Tucker conditions, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.
История
Кун и Таккер обобщили метод множителей Лагранжа (для использования при построении критериев оптимальности для задач с ограничениями в виде равенств) на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств.
Необходимые условия локального минимума для задач с ограничениями исследуются давно. Одним из основных остаётся предложенный Лагранжем перенос ограничений в целевую функцию. Условия Куна-Таккера тоже выведены из этого принципа.
Постановка задачи
В задаче нелинейной оптимизации требуется найти значение многомерной переменной x = ( x ( 1 ) , . . . , x ( n ) ) {displaystyle x=(x^{(1)},...,x^{(n)})} , минимизирующее целевую функцию:
min x ∈ X f ( x ) {displaystyle min limits _{xin X}f(x)}при условиях, когда на переменную x {displaystyle x} наложены ограничения типа неравенств:
g i ( x ) ⩽ 0 , i = 1 … m {displaystyle g_{i}(x)leqslant 0,;i=1ldots m} ,а компоненты вектора x {displaystyle x} неотрицательны.
Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.
Необходимые условия минимума функции
Если x ^ ∈ arg min f {displaystyle {hat {x}}in arg min f} при наложенных ограничениях — решение задачи, то найдётся вектор множителей Лагранжа λ ∈ R m {displaystyle lambda in mathbb {R} ^{m}} такой, что для функции Лагранжа L ( x ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) {displaystyle L(x)=f(x)+sum _{i=1}^{m}lambda _{i}g_{i}(x)} выполняются условия:
- стационарности: min x L ( x ) = L ( x ^ ) {displaystyle min _{x}L(x)=L({hat {x}})} ;
- дополняющей нежёсткости: λ i g i ( x ^ ) = 0 , i = 1 … m {displaystyle lambda _{i}g_{i}({hat {x}})=0,;i=1ldots m} ;
- неотрицательности: λ i ⩾ 0 , i = 1 … m {displaystyle lambda _{i}geqslant 0,;i=1ldots m} .
Достаточные условия минимума функции
Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. При условии, что функции f {displaystyle f} и g 1 , … , g m {displaystyle g_{1},dots ,g_{m}} выпуклы существует несколько вариантов дополнительных условий, которые делают условия из теоремы Каруша — Куна — Таккера достаточными:
Простая формулировка
Если для допустимой точки x ^ {displaystyle {hat {x}}} выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также λ 1 > 0 {displaystyle lambda _{1}>0} , то x ^ ∈ arg min f {displaystyle {hat {x}}in arg min f} .
Более слабые условия
Если для допустимой точки x ^ {displaystyle {hat {x}}} выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также ∃ x ~ : g i ( x ~ ) < 0 , i = 1 … m {displaystyle exists { ilde {x}}:g_{i}({ ilde {x}})<0,;i=1ldots m} (условие Слейтера), то x ^ ∈ arg min f {displaystyle {hat {x}}in arg min f} .