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

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

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

В теории оптимизации условия Каруша — Куна — Таккера (англ. Karush — Kuhn — Tucker conditions, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.

Содержание

Постановка задачи

Рассмотрим задачу нелинейной оптимизации. Пусть есть функции

\min\limits_x f(x) при условиях g_i(x)\leqslant 0,\;i=1\ldots m.

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

Необходимые условия минимума функции

Если \hat{x}\in\arg\min f при наложенных ограничениях — решение задачи, то найдётся ненулевой вектор множителей Лагранжа \lambda\in\R^m такой, что для функции Лагранжа L(x)=f(x)+\sum^m_{i=1}\lambda_i g_i(x) выполняются условия:

  • стационарности — \min_x L(x)=L(\hat{x});
  • дополняющей нежёсткости — \lambda_i g_i(\hat{x})=0,\;i=1\ldots m;
  • неотрицательности — \lambda_i \geqslant 0,\;i=1\ldots m.

Достаточные условия минимума функции

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

Простая формулировка

Если для допустимой точки \hat{x} выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также λ1 > 0, то \hat{x}\in\arg\min f.

Более слабые условия

Если для допустимой точки \hat{x} выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также \exists\tilde{x}: g_i(\tilde{x})<0,\;i=1\ldots m (условие Слейтера), то \hat{x}\in\arg\min f.



Wikimedia Foundation. 2010.

Нужна курсовая?

Полезное


Смотреть что такое "Условия Каруша — Куна — Таккера" в других словарях:

  • Условия Каруша — В теории оптимизации условия Каруша  Куна  Таккера (англ. Karush Kuhn Tucker conditions, KKT)  необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые… …   Википедия

  • Условия Каруша-Куна-Таккера — В теории оптимизации условия Каруша  Куна  Таккера (англ. Karush Kuhn Tucker conditions, KKT)  необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности.… …   Википедия

  • Каруш, Вильям — Вильям Каруш William Karush Дата рождения: 1 марта 1917(1917 03 01) Место рождения: Чикаго, США Дата смерти …   Википедия

  • Оптимизация (математика) — У этого термина существуют и другие значения, см. Оптимизация. Оптимизация  в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного …   Википедия

  • Метод множителей Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции , где , относительно ограничений , где меняется от единицы до . Содержание …   Википедия

  • Лагранжа множители — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Лагранжа функция — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Множители Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Множитель Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Функция Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»