В математической оптимизации , в условиях Каруша-Куна-Таккер (KKT) , также известные как условия Куна-Таккер , являются первым производным испытанием (иногда называемым первым порядка необходимых условия ) для решения в нелинейном программировании , чтобы быть оптимальными , при условии , что некоторые условия регулярности выполнены.
Допуская ограничения неравенства, подход KKT к нелинейному программированию обобщает метод множителей Лагранжа , который допускает только ограничения типа равенства. Подобно подходу Лагранжа, задача ограниченной максимизации (минимизации) переписывается как функция Лагранжа, оптимальной точкой которой является седловая точка , то есть глобальный максимум (минимум) в области переменных выбора и глобальный минимум (максимум) в множители, поэтому теорему Каруша – Куна – Таккера иногда называют теоремой о перевалке. [1]
Условия KKT были первоначально названы в честь Гарольда В. Куна и Альберта В. Такера , которые впервые опубликовали условия в 1951 году. [2] Позже ученые обнаружили, что необходимые условия для этой проблемы были сформулированы Уильямом Карушем в его магистерской диссертации в 1939 году. . [3] [4]
Задача нелинейной оптимизации
Рассмотрим следующую задачу нелинейной минимизации или максимизации :
- минимизировать
- при условии
где является переменной оптимизации выбирается из выпуклого подмножества из, это цель или полезности функции,- функции ограничения неравенства и- функции ограничения равенства . Номера неравенств и равенств обозначаются через а также соответственно. В соответствии с задачей оптимизации с ограничениями можно сформировать функцию Лагранжа
где , . Теорема Каруша – Куна – Таккера утверждает следующее.
Теорема. Еслиявляется седловой точкой из в , , тогда является оптимальным вектором для указанной выше задачи оптимизации. Предположим, что а также , , выпуклы в и что существует такой, что . Тогда с оптимальным вектором для указанной выше задачи оптимизации связан неотрицательный вектор такой, что это седловая точка . [5]
Поскольку идея этого подхода состоит в том, чтобы найти опорную гиперплоскость на допустимом множестве, доказательство теоремы Каруша – Куна – Таккера использует теорему об отделении гиперплоскостей . [6]
Система уравнений и неравенств, соответствующая условиям ККТ, обычно не решается напрямую, за исключением нескольких особых случаев, когда решение в замкнутой форме может быть получено аналитически. В общем, многие алгоритмы оптимизации можно интерпретировать как методы численного решения системы уравнений и неравенств ККТ. [7]
Необходимые условия
Предположим, что целевая функция и функции ограничения а также являются непрерывно дифференцируема в точке. Еслиявляется локальным оптимумом и задача оптимизации удовлетворяет некоторым условиям регулярности (см. ниже), то существуют постоянные а также , называемые мультипликаторами ККТ, такие, что выполняются следующие четыре группы условий:
- Стационарность
- Для минимизации :
- Для максимизации :
- Первичная осуществимость
- Двойная осуществимость
- Дополнительная расслабленность
Последнее условие иногда записывают в эквивалентной форме:
В частном случае , т.е. при отсутствии ограничений-неравенств, условия ККТ превращаются в условия Лагранжа, а множители ККТ называются множителями Лагранжа .
Если некоторые функции недифференцируемы, доступны субдифференциальные версии условий Каруша – Куна – Таккера (ККТ). [8]
Матричное представление
Необходимые условия можно записать с помощью якобиевых матриц функций ограничений. Позволять быть определенным как и разреши быть определенным как . Позволять а также . Тогда необходимые условия можно записать как:
- Стационарность
- Для максимизации :
- Для минимизации :
- Первичная осуществимость
- Двойная осуществимость
- Дополнительная расслабленность
Условия регулярности (или ограничения)
Можно спросить, есть ли точка минимизатора исходной задачи оптимизации с ограничениями (при условии, что она существует) должна удовлетворять указанным выше условиям KKT. Это похоже на вопрос, при каких условиях минимизатор функции в задаче без ограничений должен удовлетворять условию . Для случая с ограничениями ситуация более сложная, и можно сформулировать множество (все более усложняющихся) условий «регулярности», при которых минимизатор с ограничениями также удовлетворяет условиям KKT. Некоторые общие примеры условий, которые гарантируют это, приведены в следующей таблице, причем LICQ является наиболее часто используемым:
Ограничение | Акроним | Заявление |
---|---|---|
Квалификация ограничения линейности | LCQ | Если а также являются аффинными функциями , то других условий не требуется. |
Квалификация ограничения линейной независимости | LICQ | Градиенты ограничений активного неравенства и градиенты ограничений равенства линейно независимы при. |
Ограничительная квалификация Мангасарян-Фромовица | MFCQ | Градиенты ограничений равенства линейно независимы при и существует вектор такой, что для всех ограничений активного неравенства и для всех ограничений равенства. [9] |
Квалификация ограничения постоянного ранга | CRCQ | Для каждого подмножества градиентов ограничений активного неравенства и градиентов ограничений равенства ранг в окрестности постоянно. |
Квалификация ограничения постоянной положительной линейной зависимости | CPLD | Для каждого подмножества градиентов ограничений активного неравенства и градиентов ограничений равенства, если подмножество векторов линейно зависит в с неотрицательными скалярами, связанными с ограничениями неравенства, то он остается линейно зависимым в окрестности . |
Квазинормальность ограничения квалификации | QNCQ | Если градиенты ограничений активного неравенства и градиенты ограничений равенства линейно зависимы при со связанными множителями за равенство и для неравенств не существует последовательности такой, что а также |
Состояние Слейтера | SC | Для выпуклой задачи (т. Е. Предполагая минимизацию, выпуклые и аффинно) существует точка такой, что а также |
Строгие последствия могут быть показаны
- LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ.
а также
- LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ.
На практике предпочтительны более слабые ограничивающие квалификации, поскольку они применяются к более широкому набору проблем.
Достаточные условия
В некоторых случаях необходимых условий также достаточно для оптимальности. В общем, необходимых условий недостаточно для оптимальности, и требуется дополнительная информация, такая как достаточные условия второго порядка (SOSC). Для гладких функций SOSC включает вторые производные, что объясняет его название.
Необходимые условия достаточны для оптимальности, если целевая функция задачи максимизации является вогнутой функцией , ограничения неравенства- непрерывно дифференцируемые выпуклые функции и ограничения типа равенстваявляются аффинными функциями . Аналогично, если целевая функциязадачи минимизации является выпуклой функцией , необходимые условия также достаточны для оптимальности.
В 1985 году Мартин показал, что более широкий класс функций, в которых условия KKT гарантируют глобальную оптимальность, - это так называемые invex-функции типа 1 . [10] [11]
Достаточные условия второго порядка
Для гладких нелинейных задач оптимизации достаточное условие второго порядка задается следующим образом.
Решение найденный в предыдущем разделе, является ограниченным локальным минимумом, если для лагранжиана
тогда,
где вектор, удовлетворяющий следующему,
где только те активные ограничения неравенства соответствующая строгой дополнительности (т. е. где ) применяются. Решение представляет собой строгий ограниченный локальный минимум, если неравенство также строгое.
Если , следует использовать разложение Тейлора третьего порядка лагранжиана, чтобы проверить, это местный минимум. Минимизацияявляется хорошим контрпримером, см. также поверхность Пеано .
Экономика
Часто в математической экономике подход ККТ используется в теоретических моделях для получения качественных результатов. Например, [12] рассмотрим фирму, которая максимизирует свой доход от продаж при условии минимального ограничения прибыли. Сдача быть количеством произведенной продукции (будет выбрано), быть выручкой от продаж с положительной первой производной и с нулевым значением при нулевом выпуске, быть производственными затратами с положительной первой производной и с неотрицательным значением при нулевом выпуске, и - положительный минимально допустимый уровень прибыли , то проблема становится значимой, если функция дохода выравнивается, так что в конечном итоге она становится менее крутой, чем функция затрат. Проблема, выраженная в ранее данной минимизационной форме, такова:
- Минимизировать
- при условии
и условия ККТ
С нарушит ограничение минимальной прибыли, мы имеем а значит, из третьего условия следует, что первое условие выполняется с равенством. Решение этого равенства дает
Потому что было дано, что а также строго положительны, это неравенство вместе с условием неотрицательности гарантирует, что положительна, и поэтому фирма, максимизирующая доход, работает на уровне выпуска, при котором предельный доход меньше предельной стоимости - результат, представляющий интерес, поскольку он контрастирует с поведением максимизирующей прибыль фирмы, которая работает на уровне, на котором они равны.
Функция значения
Если мы пересмотрим задачу оптимизации как задачу максимизации с постоянными ограничениями-неравенствами:
Функция ценности определяется как
так что область является
Учитывая это определение, каждый коэффициент - скорость, с которой функция цены растет как увеличивается. Таким образом, если каждый интерпретируется как ограничение ресурса, коэффициенты говорят вам, насколько увеличение ресурса увеличит оптимальное значение нашей функции . Эта интерпретация особенно важна в экономике и используется, например, в задачах максимизации полезности .
Обобщения
С дополнительным множителем , который может быть равен нулю (до тех пор, пока ), перед условия стационарности ККТ превращаются в
которые называются условиями Фрица Джона . Эти условия оптимальности выполняются без оговорок ограничений и эквивалентны условию оптимальности KKT или (not-MFCQ) .
Условия KKT принадлежат к более широкому классу необходимых условий первого порядка (FONC), которые позволяют использовать негладкие функции с помощью подчиненных производных .
Смотрите также
- Лемма Фаркаша
- Множитель Лагранжа
- Метод Big M для линейных задач, который расширяет симплекс-алгоритм на задачи, содержащие ограничения «больше».
- Переменная Slack
Рекомендации
- ^ Табак, Даниил; Куо, Бенджамин С. (1971). Оптимальное управление математическим программированием . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. С. 19–20. ISBN 0-13-638106-5.
- ^ Kuhn, HW ; Такер, А. В. (1951). «Нелинейное программирование» . Труды 2-го симпозиума в Беркли . Беркли: Калифорнийский университет Press. С. 481–492. Руководство по ремонту 0047303 .
- ^ В. Каруш (1939). Минимумы функций нескольких переменных с неравенствами как боковыми ограничениями (диплом магистра). Кафедра математики Univ. Чикаго, Чикаго, Иллинойс.
- ^ Кьельдсен, Тинне Хофф (2000). «Контекстуализированный исторический анализ теоремы Куна-Такера в нелинейном программировании: влияние Второй мировой войны». Historia Math . 27 (4): 331–361. DOI : 10.1006 / hmat.2000.2289 . Руководство по ремонту 1800317 .
- ^ Уолш, Г. Р. (1975). «Свойство перевала функции Лагранжа» . Методы оптимизации . Нью-Йорк: Джон Вили и сыновья. С. 39–44. ISBN 0-471-91922-5.
- ^ Кемп, Мюррей С .; Кимура, Йошио (1978). Введение в математическую экономику . Нью-Йорк: Спрингер. С. 38–44 . ISBN 0-387-90304-6.
- ^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета . п. 244. ISBN 0-521-83378-7. Руководство по ремонту 2061575 .
- ^ Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . ISBN 978-0691119151. Руководство по ремонту 2199043 .
- ^ Дмитрий Берцекас (1999). Нелинейное программирование (2-е изд.). Афина Сайентифик. С. 329–330. ISBN 9781886529007.
- ^ Мартин, Д.Х. (1985). «Сущность косности». J. Optim. Теория Appl . 47 (1): 65–76. DOI : 10.1007 / BF00941316 . S2CID 122906371 .
- ^ Хэнсон, Массачусетс (1999). «Невыпуклость и теорема Куна-Такера». J. Math. Анальный. Прил . 236 (2): 594–604. DOI : 10,1006 / jmaa.1999.6484 .
- ^ Чан, Альфа С. Фундаментальные методы математической экономики , 3-е издание, 1984, стр. 750–752.
дальнейшее чтение
- 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