Метод Каруша—Куна—Таккера

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

Содержание

Общая постановка задачи

Мы хотим найти экстремум функции f( bold x ) = f(x sub 1 , x sub 2 ,  ldots , x sub n ) . Функция f ( bold x ) — очень хорошая: она дифференцируема (имеет производную) в каждой точке (на всей) области своего определения (такие функции в курсе математического анализа обычно называют гладкими). Но помимо функции, экстремум(ы) которой мы хотим найти, в нашей задаче присутствуют ограничения. Ограничения выражают связь переменных функции между собой и могут быть представлены в виде функций (неравенств): left {
  matrix {
    ccol { 
      g sub 1 ( bold x ) = g sub 1 (x sub 1 , x sub 2 ,  ldots , x sub n ) <= 0, above
      g sub 2 ( bold x ) = g sub 2 (x sub 1 , x sub 2 ,  ldots , x sub n ) <= 0,  above
      vdots above
      g sub m ( bold x ) = g sub m (x sub 1 , x sub 2 ,  ldots , x sub n ) <= 0.
    }
  }
right nothing

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


КатегорияПрикладнаяМатематика | КатегорияМетодыОптимизации