Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Микроэкономика
| Бусыгин В.П, Желободько Е.В, Цыплаков А.А.. Микроэкономика. Третий уровень, 2005 | |
17.8. Теоремы КунаЧТаккера |
|
|
Теоремы КунаЧТаккера - родовое название для утверждений, представляющих собой обобще- ние теоремы Лагранжа на случай задач оптимизации с ограничениями в виде неравенств, т. е. задач следующего типа: f(x) ! max x gj(x) > 0, j = 1, . . . , m, (?) x = (x1, . . . , xn) 2 X. Здесь f : X 7! R - (в соответствие с установившейся терминологией) целевая функция, gr : X 7! R, r = 1, . . . ,m, - функции ограничений, X _ Rn - открытое множество. Теорема 196 (Теорема Джона в терминах седловой точки): Пусть функции f(Х), g1(Х), . . . , gn(Х) вогнуты и ?x - решение задачи (?), такое что ?x 2 intX. Тогда существуют множители Лагранжа _j > 0, j = 0, . . . ,m, не все равные нулю, такие что ?x является решением задачи L(?x,_) ! max x2X . Мы приведем эти утверждения для случая, когда функции f, gr дифференцируемы (теоремы Ку- наЧТаккера в дифференциальной форме). Напомним, что функция L(x,_) = _0f(x) + Xm j=1 _jgj(x) называется функцией Лагранжа (лагранжианом) этой задачи, а коэффициенты _j - множителями Лагранжа. Имеет место следующее утверждение. Теорема 197 (Теорема Джона для дифференцируемых функций): Пусть ?x - решение задачи (?), такое что ?x 2 intX и функции f(Х), g1(Х), . . . , gn(Х) дифферен- цируемы в точке ?x. Тогда существуют множители Лагранжа _j > 0, j = 0, . . . ,m, не все равные нулю, такие что выполнены следующие соотношения (условия КунаЧТаккера): @L(?x,_) @xi = 0, i = 1, . . . , n и Xm j=1 @L(?x,_) @_j _j = 0 (условия дополняющей нежесткости). Отметим, что условия дополняющей нежесткости можно записать в виде gj(?x)_j = 0, j = 1, . . . , m. Из этих условий следует, что если множитель Лагранжа положителен (_j > 0), то соответствующее ограничение в решении задачи (при x = ?x) выполняется как равенство (т. е. gj(?x) = 0). Другими словами, это ограничение активно. С другой стороны, в случае, когда gj(?x) > 0, то соответствующий множитель Лагранжа _j равен нулю. Если в задаче (?) часть ограничений имеет вид ограничений на неотрицательность некоторых xi , то для них можно не вводить множители Лагранжа, записав такие ограничения отдельно: f(x) ! max x gj(x) > 0, j = 1, . . . , m, (??) x 2 X, xi > 0, i 2 P _ {1, . . . , n}. Во внутренней точке (в том смысле, что1 ?x 2 intX) условия первого порядка для i 2 P тогда будут иметь следующий вид: @L(?x,_) @xi 6 0. Для i /2 P здесь, как и в случае представления задачи в виде (?), производная функции Лагранжа по той переменной будет иметь вид @L(?x,_) @xi = 0. Кроме того, выполнены также условия дополняющей нежесткости Xm j=1 @L(?x,_) @_j _j = 0, X i2P @L(?x,_) @xi ?xi = 0. Из второго из этих условий следует, что при ?xi > 0 (i 2 P ) выполнено @L(?x,_) @xi = 0. С другой стороны, если @L(?x,_)/@xi < 0, то ?xi должен быть равен нулю. Другая модификация теоремы связана с наличием в задаче ограничений в виде равенств. Обозна- чим множество соответствующих индексов через E. Задача принимает следующий вид: f(x) ! max x gj(x) > 0, j 2 {1, . . . ,m}\E, gj(x) = 0, j 2 E, (???) x 2 X, xi > 0, i 2 P _ {1, . . . , n}. При этом в теореме Джона снимается условие, что все множители Лагранжа неотрицательны Ч множители Лагранжа _j при j 2 E могут иметь произвольный знак. Теорема Джона не гарантирует, что множитель Лагранжа целевой функции, _0 , отличен от нуля. Однако если _0 = 0, то условия КунаЧТаккера характеризуют не решение рассматриваемой задачи, а структуру множества ограничений в точке ?x и теорема не имеет непосредственной связи с интересую- щей нас задачей максимизации функции f(Х), поскольку градиент самой функции f(Х) .пропадает. из условий КунаЧТаккера. Поэтому важно охарактеризовать условия, которые гарантируют, что _0 > 0. Такие условия называются условиями регулярности. В случае, когда рассматриваемая задача является выпуклой, одно из условий регулярности, Ч так называемое условие Слейтера - имеет вид: В случае, когда целевая функция и ограничения задачи являются дифференцируемыми, простей- шее условие регулярности формулируется в терминах градиентов функций-ограничений и имеет вид: градиенты активных ограничений в точке ?x линейно независимы. (В число рассматриваемых ограни- чений следует включать и ограничения на неотрицательность.) Обозначим через A множество индексов тех ограничений, которые в точке оптимума ?x активны (в том числе, индексы всех ограничений в виде равенств), т. е. gj(?x) = 0 , j 2 A. Тогда если градиенты ограничений - векторы {rgj(?x)}j2A линейно независимы2, то _0 > 0. Это условие называется условием регулярности КунаЧТаккера. Заметим, что если _0 > 0, то без потери общности можно считать _0 = 1, что обычно и делается. Соответствующую теорему и называют собственно (прямой) теоремой КунаЧТаккера. Теорема 198 (Прямая теорема КунаЧТаккера, необходимое условие оптимальности): Пусть функции f(Х), g1(Х), . . . , gn(Х) дифференцируемы, и ?x - решение задачи (?), такое что ?x 2 intX и выполнено условие регулярности КунаЧТаккера. Тогда существуют множители Лагранжа _j > 0, j = 1, . . . ,m, такие что при _0 = 1 выполнены следующие соотношения: @L(?x,_) @xi = 0, i = 1, . . . , n и Xm j=1 @L(?x,_) @_j _j = 0. Несложно переформулировать эту теорему для задач (??) и (???). Здесь требуются такие же мо- дификации условий КунаЧТаккера, как и в теореме Джона. Условие @L(?x,_) @xi = 0, i = 1, . . . , n можно переписать в виде: rf(?x) = ? Xm j=1 _jrgj(?x). Это соотношение показывает, что в точке оптимума градиент целевой функции является линейной ком- бинацией антиградиентов ограничений, причем все коэффициенты этой линейной комбинации неотри- цательны. Рис. 17.1 иллюстрирует это свойство. Интуитивно, идея этого свойства состоит в том, что если бы какой-нибудь коэффициент линейной комбинации был отрицательным, то можно было бы увеличить значение целевой функции, двигаясь вдоль этого ограничения. Один из вариантов обратной теорема КунаЧТаккера утверждает, что при вогнутости функций f(Х), {gk(Х)} выполнение этих условий в допустимом решении ?x (т. е. точке, удовлетворяющей огра- ничениям) при некоторых множителях Лагранжа, удовлетворяющих требованиям прямой теоремы, гарантирует, что ?x является решением задачи. Теорема 199 (Обратная теорема КунаЧТаккера /достаточное условие оптимальности/): Пусть f(Х) - дифференцируемая вогнутая функция, g1(Х), . . . , gn(Х) - дифференцируемые квазивогнутые функции, множество X выпукло и точка ?x допустима в задаче (?), причем ?x 2 intX. Пусть, кроме того, существуют множители Лагранжа _j > 0, j = 1, . . . ,m, такие что при _0 = 1 выполнены следующие соотношения: @L(?x,_) @xi = 0, i = 1, . . . , n и Xm j=1 @L(?x,_) @_j _j = 0. Тогда ?x - решение задачи (?). Теорему можно очевидным образом переформулировать для задач (??) и (???). Для задачи (???) ограничения в виде равенств могут быть только линейными (это связано с тем, что ограничение в виде равенства, gj(x) = 0, следует представить с помощью двух ограничений в виде неравенств, gj(x) > 0 и ?gj(x) > 0, каждое из которых задается квазивогнутой функцией; такое может быть только если ограничение линейное). В еще одном варианте достаточного условия оптимальности предположение о вогнутости целевой функции заменяется на предположение о квазивогнутости с добавлением условия rf(?x) 6= 0. |
|
| << Предыдушая | |
| = К содержанию = | |
Похожие документы: "17.8. Теоремы КунаЧТаккера" |
|
|