<< Предыдущая

стр. 162
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

то для них можно не вводить множители Лагранжа, записав такие ограничения отдельно:
f (x) > max
x
gj (x) 0, j = 1, . . . , m, ()
x ? X,
0, i ? P ? {1, . . . , n}.
xi
17.9. Теоремы Куна—Таккера 691

Во внутренней точке (в том смысле, что1 x ? int X ) условия первого порядка для i ? P тогда
?
будут иметь следующий вид:
?L(? , ?)
x
0.
?xi
Для i ? P здесь, как и в случае представления задачи в виде ( ), производная функции Лагранжа
/
по той переменной будет иметь вид ?L(?i = 0 .
x,?)
?x
Кроме того, выполнены также условия дополняющей нежесткости
m
?L(? , ?)
x
?j = 0,
??j
j=1
?L(? , ?)
x
xi = 0.
?
?xi
i?P

Из второго из этих условий следует, что при xi > 0 (i ? P ) выполнено
?
?L(? , ?)
x
= 0.
?xi
С другой стороны, если ?L(? , ?)/?xi < 0, то xi должен быть равен нулю.
x ?
Другая модификация теоремы связана с наличием в задаче ограничений в виде равенств. Обозна-
чим множество соответствующих индексов через E . Задача принимает следующий вид:

f (x) > max
x
0, j ? {1, . . . , m}\E,
gj (x)
gj (x) = 0, j ? E, ( )
x ? X,
0, i ? P ? {1, . . . , n}.
xi

При этом в теореме Джона снимается условие, что все множители Лагранжа неотрицательны —
множители Лагранжа ?j при j ? E могут иметь произвольный знак.
Теорема Джона не гарантирует, что множитель Лагранжа целевой функции, ?0 , отличен от нуля.
Однако если ?0 = 0 , то условия Куна — Таккера характеризуют не решение рассматриваемой задачи, а
структуру множества ограничений в точке x и теорема не имеет непосредственной связи с интересую-
?
щей нас задачей максимизации функции f (·), поскольку градиент самой функции f (·) «пропадает» из
условий Куна — Таккера. Поэтому важно охарактеризовать условия, которые гарантируют, что ?0 > 0.
Такие условия называются условиями регулярности.
В случае, когда рассматриваемая задача является выпуклой, одно из условий регулярности, —
так называемое условие Слейтера — имеет вид:
В случае, когда целевая функция и ограничения задачи являются дифференцируемыми, простей-
шее условие регулярности формулируется в терминах градиентов функций-ограничений и имеет вид:
?
градиенты активных ограничений в точке x линейно независимы. (В число рассматриваемых ограни-
чений следует включать и ограничения на неотрицательность.)
?
Обозначим через A множество индексов тех ограничений, которые в точке оптимума x активны
(в том числе, индексы всех ограничений в виде равенств), т. е.

gj (? ) = 0 ? j ? A.
x

Тогда если градиенты ограничений — векторы

{ gj (? )}j?A
x

линейно независимы2 , то ?0 > 0 . Это условие называется условием регулярности Куна — Таккера.
Заметим, что если ?0 > 0, то без потери общности можно считать ?0 = 1, что обычно и делается.
Соответствующую теорему и называют собственно (прямой) теоремой Куна — Таккера.
1
Но не в том смысле, что xi > 0 для i ? P .
?
2
В конкретных приложениях может быть удобным проверять что градиенты всех ограничений линейно
независимы.
17.9. Теоремы Куна—Таккера 692
Теорема 198 (Прямая теорема Куна — Таккера, необходимое условие оптимальности):

?
Пусть функции f (·), g1 (·), . . . , gn (·) дифференцируемы, и x — решение задачи ( ), такое что
x ? int X и выполнено условие регулярности Куна — Таккера.
?
Тогда существуют множители Лагранжа ?j 0, j = 1, . . . , m , такие что при ?0 = 1 выполнены
следующие соотношения:
?L(? , ?)
x
= 0, i = 1, . . . , n
?xi
и
m
?L(? , ?)
x
?j = 0.
??j
j=1


Несложно переформулировать эту теорему для задач ( ) и ( ). Здесь требуются такие же мо-
дификации условий Куна — Таккера, как и в теореме Джона.
Условие
?L(? , ?)
x
= 0, i = 1, . . . , n
?xi
можно переписать в виде:
m
f (? ) = ?
x ?j gj (? ).
x
j=1

Это соотношение показывает, что в точке оптимума градиент целевой функции является линейной ком-
бинацией антиградиентов ограничений, причем все коэффициенты этой линейной комбинации неотри-
цательны. Рис. 17.1 иллюстрирует это свойство. Интуитивно, идея этого свойства состоит в том, что
если бы какой-нибудь коэффициент линейной комбинации был отрицательным, то можно было бы
увеличить значение целевой функции, двигаясь вдоль этого ограничения.




?
x




Рис. 17.1. Иллюстрация теоремы Куна—Таккера

Рис. 17.2 демонстрирует последствия нарушения условия регулярности. Градиенты ограничений в
?
точке максимума x на рисунке линейно зависимы, и, как следствие, градиент целевой функции нельзя
представить как линейную комбинацию градиентов ограничений.




?
x



Рис. 17.2. Нарушение условий регулярности
17.9. Теоремы Куна—Таккера 693

Один из вариантов обратной теорема Куна — Таккера утверждает, что при вогнутости функций
f (·), {gk (·)} выполнение этих условий в допустимом решении x (т. е. точке, удовлетворяющей огра-
?
ничениям) при некоторых множителях Лагранжа, удовлетворяющих требованиям прямой теоремы,
?
гарантирует, что x является решением задачи.
Теорема 199 (Обратная теорема Куна — Таккера /достаточное условие оптимальности/):

Пусть f (·) — дифференцируемая вогнутая функция, g1 (·), . . . , gn (·) — дифференцируемые
квазивогнутые функции, множество X выпукло и точка x допустима в задаче ( ), причем x ?
? ?
int X .
Пусть, кроме того, существуют множители Лагранжа ?j 0, j = 1, . . . , m , такие что при
?0 = 1 выполнены следующие соотношения:

?L(? , ?)
x
= 0, i = 1, . . . , n
?xi
и
m
?L(? , ?)
x
?j = 0.
??j
j=1

?
Тогда x — решение задачи ( ).

Теорему можно очевидным образом переформулировать для задач ( ) и ( ). Для задачи ( )
ограничения в виде равенств могут быть только линейными (это связано с тем, что ограничение в виде
равенства, gj (x) = 0, следует представить с помощью двух ограничений в виде неравенств, gj (x) 0
и ?gj (x) 0 , каждое из которых задается квазивогнутой функцией; такое может быть только если
ограничение линейное).
В еще одном варианте достаточного условия оптимальности предположение о вогнутости целевой
функции заменяется на предположение о квазивогнутости с добавлением условия f (? ) = 0.
x




Р. Рокафеллар: Выпуклый анализ, М.: Мир, 1973
Более подробно о дифференциальных свойствах квазивогнутой функции полезности см. A. P. Barten
and V. Bohm: Consumer Theory, in Handbook of Mathematical Economics, vol. II, K. J. Arrow and M. D. In-
trilligator (ed.), North Holland, 1982 (pp. 403–409), и содержащиеся там ссылки.
sssssssssssssssssssssssssssss




Именной указатель


Аллен, Рой, 34
Антонелли Дж.?? G. B. Antonelli, 67
Африат, Сидни, 43

Бентам, Иеремия, 19
Буридан, Иоанн, 6

Госсен, Герман Генрих, 20, 61

Дебре, Жерар, 7, 22, 24
Джевонс, Уильям Стенли, 20

Канеман, Дэниел, 50
Курно, Франсуа Огюстен, 61

Ланкастер, Кельвин Джон, 8

Мак-Кензи, Лайонель, 69

Парето, Вильфредо, 18, 20

Радер, Траут, 24

Самуэльсон, Пол, 69
Самуэльсон,??, 45

Тверски, Амош, 50

Хаутеккер,??, 108
Хикс, Джон, 34, 69

Эджворт, Фрэнсис Исидро, 20
Эрроу,??, 44




694
sssssssssssssssssssssssssssss




Предметный указатель


Й
CES . . . . . . . . . . . . . . см. функция с постоянной Йенсена неравенство . . . . . . . . . . . . . . . . . . . . . . 245
эластичностью замены
К
GARP . см. обобщенная аксиома выявленных
Кларка налог . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
предпочтений, см. обобщенная
Кондорсе парадокс . . . . . . . . . . . . . . . . . . . . . . . . 413
аксиома выявленных предпочтений

<< Предыдущая

стр. 162
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>