Условия Каруша – Куна – Таккера.

В математической оптимизации , в условиях Каруша-Куна-Таккер (KKT) , также известные как условия Куна-Таккер , являются первым производным испытанием (иногда называемым первым порядка необходимых условия ) для решения в нелинейном программировании , чтобы быть оптимальными , при условии , что некоторые условия регулярности выполнены.

Допуская ограничения неравенства, подход KKT к нелинейному программированию обобщает метод множителей Лагранжа , который допускает только ограничения типа равенства. Подобно подходу Лагранжа, задача ограниченной максимизации (минимизации) переписывается как функция Лагранжа, оптимальной точкой которой является седловая точка , то есть глобальный максимум (минимум) в области переменных выбора и глобальный минимум (максимум) в множители, поэтому теорему Каруша – Куна – Таккера иногда называют теоремой о перевалке. ^[1]

Условия KKT были первоначально названы в честь Гарольда В. Куна и Альберта В. Такера , которые впервые опубликовали условия в 1951 году. ^[2] Позже ученые обнаружили, что необходимые условия для этой проблемы были сформулированы Уильямом Карушем в его магистерской диссертации в 1939 году. . ^{[3] [4]}

Задача нелинейной оптимизации

Рассмотрим следующую задачу нелинейной минимизации или максимизации :

оптимизировать ${\ Displaystyle е (\ mathbf {х})}$

при условии

${\ displaystyle g_ {я} (\ mathbf {x}) \ leq 0,}$

${\ displaystyle h_ {j} (\ mathbf {x}) = 0.}$

где переменная оптимизации выбрана из выпуклого подмножества из , является объективной или полезностью функции, являются неравенство ограничений функции и является равенство ограничений функции. Номера неравенств и равенств обозначаются символами и соответственно. В соответствии с задачей оптимизации с ограничениями можно сформировать функцию Лагранжа${\ displaystyle \ mathbf {x} \ in \ mathbf {X}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle f}$${\displaystyle g_{i}\ (i=1,\ldots ,m)}$${\displaystyle h_{j}\ (j=1,\ldots ,\ell )}$${\displaystyle m}$${\displaystyle \ell }$

${\displaystyle L(\mathbf {x} ,\mathbf {\mu } ,\mathbf {\lambda } )=f(\mathbf {x} )+\mathbf {\mu } ^{\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )}$

где , . Теорема Каруша – Куна – Таккера утверждает следующее.${\displaystyle \mathbf {g} (\mathbf {x} )=\left(g_{1}(\mathbf {x} ),\ldots ,g_{m}(\mathbf {x} )\right)^{\top }}$${\displaystyle \mathbf {h} (\mathbf {x} )=\left(h_{1}(\mathbf {x} ),\ldots ,h_{\ell }(\mathbf {x} )\right)^{\top }}$

Теорема. Если это точка перевала о в , , то есть оптимальный вектор для вышеуказанной задачи оптимизации. Предположим , что и , являются выпуклыми в и что существует такое , что . Затем с оптимальным вектором для вышеупомянутой задачи оптимизации связан неотрицательный вектор , который является седловой точкой . ^[5]${\displaystyle (\mathbf {x} ^{\ast },\mathbf {\mu } ^{\ast })}$${\displaystyle L(\mathbf {x} ,\mathbf {\mu } )}$${\displaystyle \mathbf {x} \in \mathbf {X} }$${\displaystyle \mathbf {\mu } \geq \mathbf {0} }$${\displaystyle \mathbf {x} ^{\ast }}$${\displaystyle f(\mathbf {x} )}$${\displaystyle g_{i}(\mathbf {x} )}$${\displaystyle i=1,\ldots ,m}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} _{0}\in \mathbf {X} }$${\displaystyle \mathbf {g} (\mathbf {x} _{0})<0}$${\displaystyle \mathbf {x} ^{\ast }}$${\displaystyle \mathbf {\mu } ^{\ast }}$${\displaystyle L(\mathbf {x} ^{\ast },\mathbf {\mu } ^{\ast })}$${\displaystyle L(\mathbf {x} ,\mathbf {\mu } )}$

Поскольку идея этого подхода состоит в том, чтобы найти опорную гиперплоскость на допустимом множестве , доказательство теоремы Каруша – Куна – Такера использует теорему об отделении гиперплоскостей . ^[6]${\displaystyle \mathbf {\Gamma } =\left\{\mathbf {x} \in \mathbf {X} :g_{i}(\mathbf {x} )\leq 0,i=1,\ldots ,m\right\}}$

Система уравнений и неравенств, соответствующая условиям ККТ, обычно не решается напрямую, за исключением нескольких особых случаев, когда решение в замкнутой форме может быть получено аналитически. В общем, многие алгоритмы оптимизации можно интерпретировать как методы численного решения системы уравнений и неравенств ККТ. ^[7]

Необходимые условия

Предположу , что целевая функция и функция ограничений и может непрерывно дифференцируемы в точке . Если - локальный оптимум и задача оптимизации удовлетворяет некоторым условиям регулярности (см. Ниже), то существуют константы и , называемые множителями KKT, такие, что выполняются следующие четыре группы условий:${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle x^{*}\in \mathbb {R} ^{n}}$${\displaystyle x^{*}}$${\displaystyle \mu _{i}\ (i=1,\ldots ,m)}$${\displaystyle \lambda _{j}\ (j=1,\ldots ,\ell )}$

Стационарность

Для минимизации :${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\nabla h_{j}(x^{*})=\mathbf {0} }$

Для максимизации :${\displaystyle f(x)}$${\displaystyle -\nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\nabla h_{j}(x^{*})=\mathbf {0} }$

Первичная осуществимость

${\displaystyle g_{i}(x^{*})\leq 0,{\text{ for }}i=1,\ldots ,m}$

${\displaystyle h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell \,\!}$

Двойная осуществимость

${\displaystyle \mu _{i}\geq 0,{\text{ for }}i=1,\ldots ,m}$

Дополнительная расслабленность

${\displaystyle \sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0.}$

Последнее условие иногда записывают в эквивалентной форме: ${\displaystyle \mu _{i}g_{i}(x^{*})=0,{\text{ for }}i=1,\ldots ,m.}$

В частном случае , т.е. когда нет ограничений-неравенств, условия ККТ превращаются в условия Лагранжа, а множители ККТ называются множителями Лагранжа .${\displaystyle m=0}$

Если некоторые функции недифференцируемы, доступны субдифференциальные версии условий Каруша – Куна – Таккера (ККТ). ^[8]

Матричное представление

Необходимые условия можно записать с помощью якобиевых матриц функций ограничений. Позвольте быть определено как и пусть будет определено как . Пусть и . Тогда необходимые условия можно записать как:${\displaystyle \mathbf {g} (x):\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}}$${\displaystyle \mathbf {g} (x)=\left(g_{1}(x),\ldots ,g_{m}(x)\right)^{\top }}$${\displaystyle \mathbf {h} (x):\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{\ell }}$${\displaystyle \mathbf {h} (x)=\left(h_{1}(x),\ldots ,h_{\ell }(x)\right)^{\top }}$${\displaystyle {\boldsymbol {\mu }}=\left(\mu _{1},\ldots ,\mu _{m}\right)^{\top }}$${\displaystyle {\boldsymbol {\lambda }}=\left(\lambda _{1},\ldots ,\lambda _{\ell }\right)^{\top }}$

Стационарность

Для максимизации :${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})-D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}-D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0} }$

Для минимизации :${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})+D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}+D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0} }$

Первичная осуществимость

${\displaystyle \mathbf {g} (x^{*})\leq \mathbf {0} }$

${\displaystyle \mathbf {h} (x^{*})=\mathbf {0} }$

Двойная осуществимость

${\displaystyle {\boldsymbol {\mu }}\geq \mathbf {0} }$

Дополнительная расслабленность

${\displaystyle {\boldsymbol {\mu }}^{\top }\mathbf {g} (x^{*})=0.}$

Условия регулярности (или ограничения)

Можно спросить, должна ли точка минимизатора исходной задачи оптимизации с ограничениями (при условии, что таковая существует) удовлетворять вышеуказанным условиям KKT. Это похоже на вопрос, при каких условиях минимизатор функции в задаче без ограничений должен удовлетворять условию . Для случая с ограничениями ситуация более сложная, и можно сформулировать множество (все более усложняющихся) условий «регулярности», при которых минимизатор с ограничениями также удовлетворяет условиям KKT. Некоторые общие примеры условий, которые гарантируют это, приведены в следующей таблице, причем LICQ является наиболее часто используемым:${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})=0}$

Ограничение	Акроним	Заявление
Квалификация ограничения линейности	LCQ	Если и - аффинные функции , то других условий не требуется.${\displaystyle g_{i}}$${\displaystyle h_{j}}$
Квалификация ограничения линейной независимости	LICQ	Градиенты ограничений активного неравенства и градиенты ограничений равенства линейно независимы в точке .${\displaystyle x^{*}}$
Ограничительная квалификация Мангасарян-Фромовица	MFCQ	Градиенты ограничений-равенств линейно независимы в точке, и существует такой вектор , что для всех активных ограничений-неравенств и для всех ограничений-равенств. [9]${\displaystyle x^{*}}$${\displaystyle d\in \mathbb {R} ^{n}}$${\displaystyle \nabla g_{i}(x^{*})^{\top }d<0}$${\displaystyle \nabla h_{j}(x^{*})^{\top }d=0}$
Квалификация ограничения постоянного ранга	CRCQ	Для каждого подмножества градиентов ограничений активного неравенства и градиентов ограничений равенства ранг в окрестности является постоянным.${\displaystyle x^{*}}$
Квалификация ограничения постоянной положительной линейной зависимости	CPLD	Для каждого подмножества градиентов ограничений активного неравенства и градиентов ограничений равенства, если подмножество векторов линейно зависит от с неотрицательными скалярами, связанными с ограничениями неравенства, то оно остается линейно зависимым в окрестности .${\displaystyle x^{*}}$${\displaystyle x^{*}}$
Квазинормальность ограничения квалификации	QNCQ	Если градиенты ограничений активного неравенства и градиенты ограничений равенства линейно зависят в точке с соответствующими множителями для равенств и неравенств, то не существует такой последовательности , что и${\displaystyle x^{*}}$${\displaystyle \lambda _{j}}$${\displaystyle \mu _{i}\geq 0}$${\displaystyle x_{k}\to x^{*}}$${\displaystyle \lambda _{j}\neq 0\Rightarrow \lambda _{j}h_{j}(x_{k})>0}$${\displaystyle \mu _{i}\neq 0\Rightarrow \mu _{i}g_{i}(x_{k})>0.}$
Состояние Слейтера	SC	Для выпуклой задачи (т.е. в предположении минимизации, выпуклости и аффинности) существует точка такая, что и${\displaystyle f,g_{i}}$${\displaystyle h_{j}}$${\displaystyle x}$${\displaystyle h(x)=0}$${\displaystyle g_{i}(x)<0.}$

Строгие последствия могут быть показаны

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ.

и

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ.

На практике предпочтительны более слабые ограничивающие квалификации, поскольку они применяются к более широкому набору проблем.

Достаточные условия

В некоторых случаях необходимых условий также достаточно для оптимальности. В общем, необходимых условий недостаточно для оптимальности, и требуется дополнительная информация, такая как достаточные условия второго порядка (SOSC). Для гладких функций SOSC включает вторые производные, что объясняет его название.

Необходимые условия достаточны для оптимальности, если целевая функция задачи максимизации является вогнутой функцией , ограничения-неравенства являются непрерывно дифференцируемыми выпуклыми функциями, а ограничения-равенства являются аффинными функциями . Точно так же, если целевая функция задачи минимизации является выпуклой функцией , необходимые условия также достаточны для оптимальности.${\displaystyle f}$${\displaystyle g_{j}}$${\displaystyle h_{i}}$${\displaystyle f}$

В 1985 году Мартин показал, что более широкий класс функций, в которых условия KKT гарантируют глобальную оптимальность, - это так называемые invex-функции типа 1 . ^{[10] [11]}

Достаточные условия второго порядка

Для гладких нелинейных задач оптимизации достаточное условие второго порядка задается следующим образом.

Решение, найденное в предыдущем разделе, является ограниченным локальным минимумом, если для лагранжиана${\displaystyle x^{*},\lambda ^{*},\mu ^{*}}$

${\displaystyle L(x,\lambda ,\mu )=f(x)+\sum _{i=1}^{m}\mu _{i}g_{i}(x)+\sum _{j=1}^{\ell }\lambda _{j}h_{j}(x)}$

потом,

${\displaystyle s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s\geq 0}$

где - вектор, удовлетворяющий следующему,${\displaystyle s\neq 0}$

${\displaystyle \left[\nabla _{x}g_{i}(x^{*}),\nabla _{x}h_{j}(x^{*})\right]^{T}s=0}$

где применяются только те ограничения активного неравенства, которые соответствуют строгой дополнительности (т. е. где ). Решение представляет собой строгий ограниченный локальный минимум, если неравенство также строгое.${\displaystyle g_{i}(x)}$${\displaystyle \mu _{i}>0}$

Если , следует использовать разложение Тейлора третьего порядка лагранжиана, чтобы проверить, является ли он локальным минимумом. Минимизация - хороший контрпример, см. Также поверхность Пеано .${\displaystyle s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s=0}$${\displaystyle x^{*}}$${\displaystyle f(x_{1},x_{2})=(x_{2}-x_{1}^{2})(x_{2}-3x_{1}^{2})}$

Экономика

Часто в математической экономике подход ККТ используется в теоретических моделях для получения качественных результатов. Например, ^[12] рассмотрим фирму, которая максимизирует свой доход от продаж при условии минимального ограничения прибыли. Пусть - количество произведенного выпуска (которое необходимо выбрать), - выручка от продаж с положительной первой производной и с нулевым значением при нулевом выпуске, - производственные затраты с положительной первой производной и с неотрицательным значением при нулевом выпуске, и быть положительным минимально допустимым уровнем прибыли${\displaystyle Q}$${\displaystyle R(Q)}$${\displaystyle C(Q)}$${\displaystyle G_{\min }}$, то проблема становится значимой, если функция дохода выравнивается, так что в конечном итоге она становится менее крутой, чем функция затрат. Проблема, выраженная в ранее данной минимизационной форме, такова:

Минимизировать ${\displaystyle -R(Q)}$

при условии

${\displaystyle G_{\min }\leq R(Q)-C(Q)}$

${\displaystyle Q\geq 0,}$

и условия ККТ

${\displaystyle {\begin{aligned}&\left({\frac {{\text{d}}R}{{\text{d}}Q}}\right)(1+\mu )-\mu \left({\frac {{\text{d}}C}{{\text{d}}Q}}\right)\leq 0,\\[5pt]&Q\geq 0,\\[5pt]&Q\left[\left({\frac {{\text{d}}R}{{\text{d}}Q}}\right)(1+\mu )-\mu \left({\frac {{\text{d}}C}{{\text{d}}Q}}\right)\right]=0,\\[5pt]&R(Q)-C(Q)-G_{\min }\geq 0,\\[5pt]&\mu \geq 0,\\[5pt]&\mu [R(Q)-C(Q)-G_{\min }]=0.\end{aligned}}}$

Поскольку это нарушило бы ограничение минимальной прибыли, мы имеем и, следовательно, третье условие означает, что первое условие выполняется с равенством. Решение этого равенства дает${\displaystyle Q=0}$${\displaystyle Q>0}$

${\displaystyle {\frac {{\text{d}}R}{{\text{d}}Q}}={\frac {\mu }{1+\mu }}\left({\frac {{\text{d}}C}{{\text{d}}Q}}\right).}$

Поскольку было дано, что и являются строго положительными, это неравенство вместе с условием неотрицательности гарантий является положительным, и, таким образом, максимизирующая доход фирма работает на уровне выпуска, при котором предельный доход меньше предельных затрат - в результате представляет интерес, потому что это контрастирует с поведением максимизирующей прибыль фирмы, которая работает на уровне, на котором они равны.${\displaystyle {\text{d}}R/{\text{d}}Q}$${\displaystyle {\text{d}}C/{\text{d}}Q}$${\displaystyle \mu }$${\displaystyle \mu }$ ${\displaystyle {\text{d}}R/{\text{d}}Q}$ ${\displaystyle {\text{d}}C/{\text{d}}Q}$

Функция значения

Если мы пересмотрим задачу оптимизации как задачу максимизации с постоянными ограничениями-неравенствами:

${\displaystyle {\text{Maximize }}\;f(x)}$

${\displaystyle {\text{subject to }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0.}$

Функция ценности определяется как

${\displaystyle V(a_{1},\ldots ,a_{n})=\sup \limits _{x}f(x)}$

${\displaystyle {\text{subject to }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0}$

${\displaystyle j\in \{1,\ldots ,\ell \},i\in \{1,\ldots ,m\},}$

поэтому области ИБ${\displaystyle V}$${\displaystyle \{a\in \mathbb {R} ^{m}\mid {\text{for some }}x\in X,g_{i}(x)\leq a_{i},i\in \{1,\ldots ,m\}\}.}$

Учитывая это определение, каждый коэффициент - это скорость, с которой функция ценности увеличивается по мере увеличения. Таким образом, если каждый интерпретируется как ограничение ресурса, коэффициенты говорят вам, насколько увеличение ресурса увеличит оптимальное значение нашей функции . Эта интерпретация особенно важна в экономике и используется, например, в задачах максимизации полезности .${\displaystyle \mu _{i}}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle f}$

Обобщения

С дополнительным множителем , который может быть равен нулю (до тех пор, пока ), перед условиями стационарности KKT превращаются в${\displaystyle \mu _{0}\geq 0}$${\displaystyle (\mu _{0},\mu ,\lambda )\neq 0}$${\displaystyle \nabla f(x^{*})}$

${\displaystyle {\begin{aligned}&\mu _{0}\,\nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\,\nabla g_{i}(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\,\nabla h_{j}(x^{*})=0,\\[4pt]&\mu _{j}g_{i}(x^{*})=0,\quad i=1,\dots ,m,\end{aligned}}}$

которые называются условиями Фрица Джона . Эти условия оптимальности выполняются без оговорок ограничений и эквивалентны условию оптимальности KKT или (not-MFCQ) .

Условия KKT принадлежат к более широкому классу необходимых условий первого порядка (FONC), которые позволяют использовать негладкие функции с помощью подчиненных производных .

Смотрите также

• Лемма Фаркаша
• Множитель Лагранжа
• Метод Big M для линейных задач, который расширяет симплекс-алгоритм на задачи, содержащие ограничения «больше».
• Переменная Slack

использованная литература

дальнейшее чтение

• Andreani, R .; Мартинес, Дж. М.; Шувердт, ML (2005). «О связи между условием постоянной положительной линейной зависимости и квалификацией ограничения квазинормальности». Журнал теории оптимизации и приложений . 125 (2): 473–485. DOI : 10.1007 / s10957-004-1861-9 . S2CID  122212394 .
• Авриэль, Мардохей (2003). Нелинейное программирование: анализ и методы . Дувр. ISBN 0-486-43227-0.
• Болтянский, В .; Мартини, H .; Солтан, В. (1998). «Теорема Куна – Таккера» . Геометрические методы и проблемы оптимизации . Нью-Йорк: Спрингер. С. 78–92. ISBN 0-7923-5454-0.
• Boyd, S .; Ванденберге, Л. (2004). «Условия оптимальности» (PDF) . Выпуклая оптимизация . Издательство Кембриджского университета. С. 241–249. ISBN 0-521-83378-7.
• Кемп, Мюррей С .; Кимура, Йошио (1978). Введение в математическую экономику . Нью-Йорк: Спрингер. С.  38–73 . ISBN 0-387-90304-6.
• Рау, Николай (1981). «Множители Лагранжа». Матрицы и математическое программирование . Лондон: Макмиллан. С. 156–174. ISBN 0-333-27768-6.
• Nocedal, J .; Райт, SJ (2006). Численная оптимизация . Нью-Йорк: Спрингер. ISBN 978-0-387-30303-1.
• Сундарам, Рангараджан К. (1996). «Ограничения неравенства и теорема Куна и Таккера» . Первый курс теории оптимизации . Нью-Йорк: Издательство Кембриджского университета. С. 145–171. ISBN 0-521-49770-1.

внешние ссылки

• Условия Каруша – Куна – Таккера с выводом и примерами.
• Примеры и руководства по условиям KKT