Условия Каруша-Куна-Таккера
- Условия Каруша-Куна-Таккера
-
В теории оптимизации условия Каруша — Куна — Таккера (англ. Karush — Kuhn — Tucker conditions, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.
Постановка задачи
Рассмотрим задачу нелинейной оптимизации. Пусть есть функции
- при условиях .
Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.
Необходимые условия минимума функции
Если при наложенных ограничениях — решение задачи, то найдётся ненулевой вектор множителей Лагранжа такой, что для функции Лагранжа выполняются условия:
- стационарности — ;
- дополняющей нежёсткости — ;
- неотрицательности — .
Достаточные условия минимума функции
Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. Существует несколько вариантов дополнительных условий, которые делают их достаточными.
Простая формулировка
Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также λ1 > 0, то .
Более слабые условия
Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также (условие Слейтера), то .
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 Описание метода … Википедия