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

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

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

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

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

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

минимизировать

f(\mathbf {x} )

при условии

g_{i}(\mathbf {x} )\leq 0,

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

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

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

где

$\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}}.$ Теорема Каруша – Куна – Такера утверждает следующее.

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

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

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

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

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

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

Стационарность: Для минимизации $f(x)$ : $\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}$; Для максимизации $f(x)$ : $-\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}$
Первичная осуществимость: $h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell \,\!$; $g_{i}(x^{*})\leq 0,{\text{ for }}i=1,\ldots ,m$

Двойная осуществимость: $\mu _{i}\geq 0,{\text{ for }}i=1,\ldots ,m$

Дополнительная расслабленность: $\sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стационарность: Для максимизации $f(x)$ : $\partial f(x^{*})-D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}-D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0}$; Для минимизации $f(x)$ : $\partial f(x^{*})+D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}+D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0}$

Первичная осуществимость: $\mathbf {g} (x^{*})\leq \mathbf {0}$; $\mathbf {h} (x^{*})=\mathbf {0}$

Двойная осуществимость: ${\boldsymbol {\mu }}\geq \mathbf {0}$

Дополнительная расслабленность: ${\boldsymbol {\mu }}^{\top }\mathbf {g} (x^{*})=0.$

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

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

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

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

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

и

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

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

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

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

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

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

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

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

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

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

затем,

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

где $s\neq 0$ является вектором, удовлетворяющим следующему:

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

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

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

Экономика

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

Свернуть

-R(Q)

при условии

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

Q\geq 0,

и условия ККТ

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

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

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

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

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

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

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

{\text{subject to }}\

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

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

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

{\text{subject to }}\

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

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

так что область $V$ является $\{a\in \mathbb {R} ^{m}\mid {\text{for some }}x\in X,g_{i}(x)\leq a_{i},i\in \{1,\ldots ,m\}\}.$

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

Обобщения

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

{\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) .

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

См. также

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

Ссылки

^ Табак, Дэниел; Куо, Бенджамин К. (1971). Оптимальное управление посредством математического программирования . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 19–20. ISBN 0-13-638106-5 .
^ Кун, Х.В. ; Такер, AW (1951). «Нелинейное программирование» . Материалы 2-го симпозиума в Беркли . Беркли: Издательство Калифорнийского университета. стр. 481–492. МР 0047303 .
^ В. Каруш (1939). Минимумы функций нескольких переменных с неравенствами в качестве боковых ограничений (магистерская диссертация). Кафедра математики, Univ. Чикаго, Чикаго, Иллинойс.
^ Кьельдсен, Тинне Хофф (2000). «Контекстуальный исторический анализ теоремы Куна-Таккера в нелинейном программировании: влияние Второй мировой войны» . История математики . 27 (4): 331–361. дои : 10.1006/hmat.2000.2289 . МР 1800317 .
^ Уолш, Г. Р. (1975). «Свойство перевала функции Лагранжа» . Методы оптимизации . Нью-Йорк: Джон Уайли и сыновья. стр. 39–44. ISBN 0-471-91922-5 .
^ Кемп, Мюррей К.; Кимура, Ёсио (1978). Введение в математическую экономику . Нью-Йорк: Спрингер. стр. 38–44 . ISBN 0-387-90304-6 .
^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . п. 244. ИСБН 0-521-83378-7 . МР 2061575 .
^ Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . ISBN 978-0691119151 . МР 2199043 .
^ Джефф Гордон и Райан Тибширани. «Условия Каруша-Куна-Такера, оптимизация 10-725 / 36-725» (PDF) . Архивировано из оригинала (PDF) 17 июня 2022 г.
^ Дмитрий Берцекас (1999). Нелинейное программирование (2-е изд.). Афина Сайентифик. стр. 329–330. ISBN 9781886529007 .
^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . п. 244. ИСБН 0-521-83378-7 . МР 2061575 .
^ Мартин, Д.Х. (1985). «Сущность Invexity». Дж. Оптим. Теория Прикл . 47 (1): 65–76. дои : 10.1007/BF00941316 . S2CID 122906371 .
^ Хэнсон, Массачусетс (1999). «Инвексность и теорема Куна-Такера» . Дж. Математика. Анальный. Приложение . 236 (2): 594–604. дои : 10.1006/jmaa.1999.6484 .
^ Чан, Альфа К. Фундаментальные методы математической экономики , 3-е издание, 1984, стр. 750–752.

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

Андреани, Р.; Мартинес, Х.М.; Шувердт, М.Л. (2005). «О связи между условием постоянной положительной линейной зависимости и условием ограничения квазинормальности». Журнал теории оптимизации и приложений . 125 (2): 473–485. дои : 10.1007/s10957-004-1861-9 . S2CID 122212394 .
Авриэль, Мордехай (2003). Нелинейное программирование: анализ и методы . Дувр. ISBN 0-486-43227-0 .
Болтянский, В.; Мартини, Х.; Солтан, В. (1998). «Теорема Куна-Такера» . Геометрические методы и задачи оптимизации . Нью-Йорк: Спрингер. стр. 78–92. ISBN 0-7923-5454-0 .
Бойд, С.; Ванденберге, Л. (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 .
Носедаль, Дж.; Райт, С.Дж. (2006). Численная оптимизация . Нью-Йорк: Спрингер. ISBN 978-0-387-30303-1 .
Сундарам, Рангараджан К. (1996). «Ограничения-неравенства и теорема Куна и Такера» . Первый курс теории оптимизации . Нью-Йорк: Издательство Кембриджского университета. стр. 145–171. ISBN 0-521-49770-1 .

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

[1] Табак, Дэниел; Куо, Бенджамин К. (1971). Оптимальное управление посредством математического программирования . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 19–20. ISBN 0-13-638106-5 .

[2] Кун, Х.В. ; Такер, AW (1951). «Нелинейное программирование» . Материалы 2-го симпозиума в Беркли . Беркли: Издательство Калифорнийского университета. стр. 481–492. МР 0047303 .

[3] В. Каруш (1939). Минимумы функций нескольких переменных с неравенствами в качестве боковых ограничений (магистерская диссертация). Кафедра математики, Univ. Чикаго, Чикаго, Иллинойс.

[4] Кьельдсен, Тинне Хофф (2000). «Контекстуальный исторический анализ теоремы Куна-Таккера в нелинейном программировании: влияние Второй мировой войны» . История математики . 27 (4): 331–361. дои : 10.1006/hmat.2000.2289 . МР 1800317 .

[Walsh1975-5] Уолш, Г. Р. (1975). «Свойство перевала функции Лагранжа» . Методы оптимизации . Нью-Йорк: Джон Уайли и сыновья. стр. 39–44. ISBN 0-471-91922-5 .

[6] Кемп, Мюррей К.; Кимура, Ёсио (1978). Введение в математическую экономику . Нью-Йорк: Спрингер. стр. 38–44 . ISBN 0-387-90304-6 .

[7] Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . п. 244. ИСБН 0-521-83378-7 . МР 2061575 .

[8] Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . ISBN 978-0691119151 . МР 2199043 .

[9] Джефф Гордон и Райан Тибширани. «Условия Каруша-Куна-Такера, оптимизация 10-725 / 36-725» (PDF) . Архивировано из оригинала (PDF) 17 июня 2022 г.

[10] Дмитрий Берцекас (1999). Нелинейное программирование (2-е изд.). Афина Сайентифик. стр. 329–330. ISBN 9781886529007 .

[11] Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . п. 244. ИСБН 0-521-83378-7 . МР 2061575 .

[12] Мартин, Д.Х. (1985). «Сущность Invexity». Дж. Оптим. Теория Прикл . 47 (1): 65–76. дои : 10.1007/BF00941316 . S2CID 122906371 .

[13] Хэнсон, Массачусетс (1999). «Инвексность и теорема Куна-Такера» . Дж. Математика. Анальный. Приложение . 236 (2): 594–604. дои : 10.1006/jmaa.1999.6484 .

[14] Чан, Альфа К. Фундаментальные методы математической экономики , 3-е издание, 1984, стр. 750–752.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]