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

Концепция математической оптимизации

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

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

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

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

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

минимизировать ${\displaystyle f(\mathbf {x} )}$

при условии

${\displaystyle g_{i}(\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 {\mathcal {L}}(\mathbf {x} ,\mathbf {\mu } ,\mathbf {\lambda } )=f(\mathbf {x} )+\mathbf {\mu } ^{\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )=L(\mathbf {x} ,\mathbf {\alpha } )=f(\mathbf {x} )+\mathbf {\alpha } ^{\top }{\begin{pmatrix}\mathbf {g} (\mathbf {x} )\\\mathbf {h} (\mathbf {x} )\end{pmatrix}}}$$

где

$${\displaystyle \mathbf {g} \left(\mathbf {x} \right)={\begin{bmatrix}g_{1}\left(\mathbf {x} \right)\\\vdots \\g_{i}\left(\mathbf {x} \right)\\\vdots \\g_{m}\left(\mathbf {x} \right)\end{bmatrix}},\quad \mathbf {h} \left(\mathbf {x} \right)={\begin{bmatrix}h_{1}\left(\mathbf {x} \right)\\\vdots \\h_{j}\left(\mathbf {x} \right)\\\vdots \\h_{\ell }\left(\mathbf {x} \right)\end{bmatrix}},\quad \mathbf {\mu } ={\begin{bmatrix}\mu _{1}\\\vdots \\\mu _{i}\\\vdots \\\mu _{m}\\\end{bmatrix}},\quad \mathbf {\lambda } ={\begin{bmatrix}\lambda _{1}\\\vdots \\\lambda _{j}\\\vdots \\\lambda _{\ell }\end{bmatrix}}\quad {\text{and}}\quad \mathbf {\alpha } ={\begin{bmatrix}\mu \\\lambda \end{bmatrix}}.}$$Теорема Каруша –Куна–Таккера утверждает следующее.

Теорема  —  (достаточность) Если — седловая точка в , то — оптимальный вектор для указанной выше задачи оптимизации . ${\displaystyle (\mathbf {x} ^{\ast },\mathbf {\alpha } ^{\ast })}$ ${\displaystyle L(\mathbf {x} ,\mathbf {\alpha } )}$ ${\displaystyle \mathbf {x} \in \mathbf {X} }$ ${\displaystyle \mathbf {\mu } \geq \mathbf {0} }$ ${\displaystyle \mathbf {x} ^{\ast }}$

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

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

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

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

Предположим, что целевая функция и функции ограничений и имеют производные в точке . Если — локальный оптимум и задача оптимизации удовлетворяет некоторым условиям регулярности (см. ниже), то существуют константы и , называемые множителями ККТ, такие, что выполняются следующие четыре группы условий: ^[8] ${\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle g_{i}\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle h_{j}\colon \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 \partial f(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\partial h_{j}(x^{*})+\sum _{i=1}^{m}\mu _{i}\partial g_{i}(x^{*})\ni \mathbf {0} }$

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

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

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

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

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

${\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}$

Доказательство

Теорема  —  (достаточность) Если существует решение основной задачи, решение двойственной задачи, такие, что вместе они удовлетворяют условиям ККТ, то пара задач имеет сильную двойственность и является парой решений основной и двойственной задач. ${\displaystyle x^{*}}$ ${\displaystyle (\mu ^{*},\lambda ^{*})}$ ${\displaystyle x^{*},(\mu ^{*},\lambda ^{*})}$

(необходимость) Если пара задач имеет сильную двойственность, то для любого решения основной задачи и любого решения двойственной задачи пара должна удовлетворять условиям ККТ. ^[9] ${\displaystyle x^{*}}$ ${\displaystyle (\mu ^{*},\lambda ^{*})}$ ${\displaystyle x^{*},(\mu ^{*},\lambda ^{*})}$

Доказательство

Во-первых, для того чтобы удовлетворялись условия ККТ, необходимо, чтобы они были равновесием Нэша . ${\displaystyle x^{*},(\mu ^{*},\lambda ^{*})}$

Фиксируйте и изменяйте : равновесие эквивалентно первичной стационарности. ${\displaystyle (\mu ^{*},\lambda ^{*})}$ ${\displaystyle x}$

Фиксируйте и варьируйте : равновесие эквивалентно изначальной осуществимости и дополнительной нежесткости. ${\displaystyle x^{*}}$ ${\displaystyle (\mu ,\lambda )}$

Достаточность: пара решений удовлетворяет условиям ККТ, следовательно, является равновесием Нэша и, следовательно, закрывает разрыв двойственности. ${\displaystyle x^{*},(\mu ^{*},\lambda ^{*})}$

Необходимость: любая пара решений должна закрывать разрыв двойственности, таким образом, они должны составлять равновесие Нэша (поскольку ни одна из сторон не может добиться лучшего), таким образом, они удовлетворяют условиям ККТ. ${\displaystyle x^{*},(\mu ^{*},\lambda ^{*})}$

Интерпретация: условия ККТ как уравновешивающие силы ограничений в пространстве состояний

Первичную задачу можно интерпретировать как перемещение частицы в пространстве и воздействие на нее трех видов силовых полей: ${\displaystyle x}$

• ${\displaystyle f}$потенциальное поле, которое минимизирует частица. Сила, генерируемая . ${\displaystyle f}$ ${\displaystyle -\partial f}$
• ${\displaystyle g_{i}}$являются односторонними поверхностями ограничения. Частице разрешено двигаться внутри , но всякий раз, когда она касается , она вталкивается внутрь. ${\displaystyle g_{i}\leq 0}$ ${\displaystyle g_{i}=0}$
• ${\displaystyle h_{j}}$являются двусторонними поверхностями ограничения. Частице разрешено двигаться только по поверхности . ${\displaystyle h_{j}}$

Первичная стационарность утверждает, что «сила» точно уравновешивается линейной суммой сил и . ${\displaystyle \partial f(x^{*})}$ ${\displaystyle \partial h_{j}(x^{*})}$ ${\displaystyle \partial g_{i}(x^{*})}$

Двойственная осуществимость дополнительно утверждает, что все силы должны быть односторонними, направленными внутрь допустимого множества для . ${\displaystyle \partial g_{i}(x^{*})}$ ${\displaystyle x}$

Дополнительная нежесткость утверждает, что если , то сила, исходящая от , должна быть равна нулю, т.е. , поскольку частица не находится на границе, односторонняя сила ограничения не может активироваться. ${\displaystyle g_{i}(x^{*})<0}$ ${\displaystyle \partial g_{i}(x^{*})}$ ${\displaystyle \mu _{i}(x^{*})=0}$

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

Необходимые условия можно записать с помощью матриц Якоби функций ограничений. Пусть будет определено как и пусть будет определено как . Пусть и . Тогда необходимые условия можно записать как: ${\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 \partial f(x^{*})-D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}-D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0} }$

Для минимизации : ${\displaystyle f(x)}$ ${\displaystyle \partial 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}$

Строгие импликации могут быть показаны

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

и

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

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

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

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

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

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

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

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

Решение, найденное в предыдущем разделе, представляет собой ограниченный локальный минимум, если для лагранжиана ${\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_{\mathbb {R} ^{2}}}$

где применяются только те активные ограничения неравенства, которые соответствуют строгой дополнительности (т.е. где ). Решение представляет собой строгий ограниченный локальный минимум в случае, если неравенство также является строгим. ${\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})}$

Экономика

Часто в математической экономике подход KKT используется в теоретических моделях для получения качественных результатов. Например, ^[14] рассмотрим фирму, которая максимизирует свой доход от продаж при условии ограничения минимальной прибыли. Пусть будет количеством произведенного продукта (которое должно быть выбрано), будет доходом от продаж с положительной первой производной и с нулевым значением при нулевом выходе, будут издержками производства с положительной первой производной и с неотрицательным значением при нулевом выходе, и будет положительным минимально приемлемым уровнем прибыли , тогда задача имеет смысл, если функция дохода выравнивается, так что в конечном итоге она становится менее крутой, чем функция затрат. Задача, выраженная в ранее заданной форме минимизации, имеет вид ${\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}$

Обобщения

При наличии дополнительного множителя , который может быть равен нулю (при условии ), перед ККТ условия стационарности превращаются в ${\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 или (не-MFCQ) .

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

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

• Лемма Фаркаса
• Множитель Лагранжа
• Метод Big M для линейных задач, который расширяет симплексный алгоритм на задачи, содержащие ограничения «больше, чем».
• Метод внутренней точки — метод решения условий ККТ.
• Слабый переменный
• Состояние Слейтера

Ссылки

1. Табак, Дэниел; Куо, Бенджамин С. (1971). Оптимальное управление с помощью математического программирования . Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. С. 19–20. ISBN 0-13-638106-5.
2. Kuhn, HW ; Tucker, AW (1951). «Нелинейное программирование». Труды 2-го симпозиума в Беркли . Беркли: Издательство Калифорнийского университета. С. 481–492. MR  0047303.
3. В. Каруш (1939). Минимумы функций многих переменных с неравенствами в качестве побочных ограничений (диссертация на степень магистра наук). Кафедра математики, Чикагский университет, Чикаго, Иллинойс.
4. Кьельдсен, Тинне Хофф (2000). «Контекстуализированный исторический анализ теоремы Куна-Таккера в нелинейном программировании: влияние Второй мировой войны». Historia Math . 27 (4): 331–361. doi : 10.1006/hmat.2000.2289 . MR  1800317.
5. Уолш, GR (1975). "Свойство седловой точки функции Лагранжа". Методы оптимизации . Нью-Йорк: John Wiley & Sons. стр. 39–44. ISBN 0-471-91922-5.
6. Кемп, Мюррей С.; Кимура, Ёсио (1978). Введение в математическую экономику. Нью-Йорк: Springer. С. 38–44. ISBN 0-387-90304-6.
7. Бойд, Стивен; Ванденберг, Ливен (2004). Выпуклая оптимизация . Кембридж: Cambridge University Press . стр. 244. ISBN 0-521-83378-7. МР  2061575.
8. Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Princeton University Press . ISBN 978-0691119151. МР  2199043.
9. Джефф Гордон и Райан Тибширани. "Условия Каруша-Куна-Таккера, Оптимизация 10-725 / 36-725" (PDF) . Архивировано из оригинала (PDF) 2022-06-17.
10. Димитрий Берцекас (1999). Нелинейное программирование (2-е изд.). Athena Scientific. стр. 329–330. ISBN 9781886529007.
11. Бойд, Стивен; Ванденберг, Ливен (2004). Выпуклая оптимизация . Кембридж: Cambridge University Press . стр. 244. ISBN 0-521-83378-7. МР  2061575.
12. Мартин, Д. Х. (1985). «Сущность извращения». J. Optim. Theory Appl . 47 (1): 65–76. doi :10.1007/BF00941316. S2CID  122906371.
13. Хансон, MA (1999). «Invexity и теорема Куна-Таккера». J. Math. Anal. Appl . 236 (2): 594–604. doi : 10.1006/jmaa.1999.6484 .
14. Чан, Альфа С. Фундаментальные методы математической экономики , 3-е издание, 1984, стр. 750–752.

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

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

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

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