Открыть главное меню

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

Содержание

ИсторияПравить

Кун и Таккер обобщили метод множителей Лагранжа (для использования при построении критериев оптимальности для задач с ограничениями в виде равенств) на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств[1].

Необходимые условия локального минимума для задач с ограничениями исследуются давно. Одним из основных остаётся предложенный Лагранжем перенос ограничений в целевую функцию. Условия Куна-Таккера тоже выведены из этого принципа[2].

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

В задаче нелинейной оптимизации требуется найти значение многомерной переменной  , минимизирующее целевую функцию:

 

при условиях, когда на переменную   наложены ограничения типа неравенств:

 ,

а компоненты вектора   неотрицательны[3].

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

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

Если   при наложенных ограничениях — решение задачи, то найдётся вектор множителей Лагранжа   такой, что для функции Лагранжа   выполняются условия:

  • стационарности:  ;
  • дополняющей нежёсткости:  ;
  • неотрицательности:  .

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

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

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

Если для допустимой точки   выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также  , то  .

Более слабые условияПравить

Если для допустимой точки   выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также   (условие Слейтера), то  .

ПримечанияПравить

  1. Условия Куна-Таккера
  2. Жилинискас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 76, ISBN 5-02-006737-7
  3. Математические основы кибернетики, 1980, с. 253.

См. такжеПравить

ЛитератураПравить

  • Дж. Хедли. Нелинейное и динамическое программирование. — М.: Мир, 1967. — 506 с.
  • Коршунов Ю. М. Математические основы кибернетики. — М.: Энергия, 1980. — 424 с.