Условия Каруша – Куна – Таккера - Karush–Kuhn–Tucker conditions

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

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

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

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

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

оптимизировать
при условии

где переменная оптимизации выбрана из выпуклого подмножества из , является объективной или полезностью функции, являются неравенство ограничений функции и является равенство ограничений функции. Номера неравенств и равенств обозначаются символами и соответственно. В соответствии с задачей оптимизации с ограничениями можно сформировать функцию Лагранжа

где , . Теорема Каруша – Куна – Таккера утверждает следующее.

Теорема. Если это точка перевала о в , , то есть оптимальный вектор для вышеуказанной задачи оптимизации. Предположим , что и , являются выпуклыми в и что существует такое , что . Затем с оптимальным вектором для указанной выше задачи оптимизации связан неотрицательный вектор , который является седловой точкой .

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

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

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

Предположу , что целевая функция и функция ограничений и может непрерывно дифференцируемы в точке . Если - локальный оптимум и задача оптимизации удовлетворяет некоторым условиям регулярности (см. Ниже), то существуют константы и , называемые множителями KKT, такие, что выполняются следующие четыре группы условий:

Диаграмма ограничений неравенства для задач оптимизации
Стационарность
Для минимизации :
Для максимизации :
Первичная осуществимость
Двойная осуществимость
Дополнительная расслабленность

Последнее условие иногда записывают в эквивалентной форме:

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

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

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

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

Стационарность
Для максимизации :
Для минимизации :
Первичная осуществимость
Двойная осуществимость
Дополнительная расслабленность

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

Можно спросить, должна ли точка минимизатора исходной задачи оптимизации с ограничениями (при условии, что таковая существует) удовлетворять вышеуказанным условиям KKT. Это похоже на вопрос, при каких условиях минимизатор функции в задаче без ограничений должен удовлетворять условию . Для случая с ограничениями ситуация более сложная, и можно сформулировать множество (все более усложняющихся) условий «регулярности», при которых минимизатор с ограничениями также удовлетворяет условиям KKT. Некоторые общие примеры условий, которые гарантируют это, приведены в следующей таблице, причем LICQ является наиболее часто используемым:

Ограничение Акроним Заявление
Квалификация ограничения линейности LCQ Если и - аффинные функции , то других условий не требуется.
Квалификация ограничения линейной независимости LICQ Градиенты ограничений активного неравенства и градиенты ограничений равенства линейно независимы в точке .
Ограничительная квалификация Мангасарян-Фромовица MFCQ Градиенты ограничений-равенств линейно независимы в точке, и существует такой вектор , что для всех активных ограничений-неравенств и для всех ограничений-равенств.
Квалификация ограничения постоянного ранга CRCQ Для каждого подмножества градиентов ограничений активного неравенства и градиентов ограничений равенства ранг в окрестности является постоянным.
Квалификация ограничения постоянной положительной линейной зависимости CPLD Для каждого подмножества градиентов ограничений активного неравенства и градиентов ограничений равенства, если подмножество векторов линейно зависит от с неотрицательными скалярами, связанными с ограничениями неравенства, то оно остается линейно зависимым в окрестности .
Квазинормальность ограничения квалификации QNCQ Если градиенты ограничений активного неравенства и градиенты ограничений равенства линейно зависят в точке с соответствующими множителями для равенств и неравенств, то не существует такой последовательности , что и
Состояние Слейтера SC Для выпуклой задачи (т.е. в предположении минимизации, выпуклости и аффинности) существует точка такая, что и

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

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ.

а также

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ.

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

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

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

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

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

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

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

Решение, найденное в предыдущем разделе, является ограниченным локальным минимумом, если для лагранжиана

тогда,

где - вектор, удовлетворяющий следующему:

где применяются только те ограничения активного неравенства, которые соответствуют строгой комплементарности (т. е. где ). Решение представляет собой строгий ограниченный локальный минимум, если неравенство также строгое.

Если , следует использовать разложение Тейлора третьего порядка лагранжиана, чтобы проверить, является ли он локальным минимумом. Минимизация - хороший контрпример, см. Также поверхность Пеано .

Экономика

Часто в математической экономике подход ККТ используется в теоретических моделях для получения качественных результатов. Например, рассмотрим фирму, которая максимизирует свой доход от продаж при условии минимального ограничения прибыли. Пусть - количество произведенного выпуска (которое необходимо выбрать), - выручка от продаж с положительной первой производной и с нулевым значением при нулевом выпуске, - производственные затраты с положительной первой производной и с неотрицательным значением при нулевом выпуске, и - положительный минимально допустимый уровень прибыли , то проблема становится значимой, если функция дохода выравнивается, так что в конечном итоге она становится менее крутой, чем функция затрат. Проблема, выраженная в ранее приведенной форме минимизации, такова:

Минимизировать
при условии

и условия ККТ

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

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

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

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

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

поэтому области ИБ

Учитывая это определение, каждый коэффициент - это скорость, с которой функция ценности увеличивается по мере увеличения. Таким образом, если каждый интерпретируется как ограничение ресурса, коэффициенты говорят вам, насколько увеличение ресурса увеличит оптимальное значение нашей функции . Эта интерпретация особенно важна в экономике и используется, например, в задачах максимизации полезности .

Обобщения

С дополнительным множителем , который может быть равен нулю (до тех пор, пока ), перед условиями стационарности KKT превращаются в

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

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

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

Рекомендации

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

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