17.9 Теоремы Куна-Таккера

Теоремы Куна- Таккера - родовое название для утверждений, представляющих собой обобщение теоремы Лагранжа на случай задач оптимизации с ограничениями в виде неравенств, т. е.

f (х) ^ max

x

gj (х) > 0, j = 1,..., m, (*) х = (xi,..., xn) е X.

Здесь f: X ^ R - (в соответствие с установившейся терминологией) целевая функция, gr: X ^ R, r = 1,..., m, - функции ограничений, X С Rn - открытое множество.

Теорема 196 (Теорема Джона в терминах сеаловоп точки):

Пусть функции f (?),gi(?),...,gn(-) вогнуты и х - решение задачи (*), такое что х е intX. Тогда существуют множители Лагранжа Aj ^ 0, j = 0,..., m, не все равные нулю, такие что х является решением задачи

?(х, Л) -> max . ,

xex J

Мы приведем эти утверждения для случая, когда функции f, gr дифференцируемы (теоремы Куна- Таккера в дифференциальной форме). Напомним, что функция

m

Дх, Л) = Aof (х) + ? Aj gj (х) j=i

называется функцией Лагранжа (лагранжианом) этой задачи, а коэффициенты Aj - множителями Лагранжа.

Имеет место следующее утверждение.

Теорема 197 (Теорема Джона для дифференцируемых функций):

Пусть х - решение задачи (*), такое что х е intX и функции f (-),gi(-),..., gn(-) дифференцируемы в точке х.

Тогда существуют множители Лагранжа Aj ^ 0, j = 0,..., m, не все равные нулю, такие что выполнены следующие соотношения (условия Куна- Таккера):

д?(х, Л) 0 . 1 =0, i = 1, . . . , n

dxi

и

EdL^ Л) a =0 (условия дополняющей j

dA,- j нежесткости).

j=i j

Отметим, что условия дополняющей нежесткости можно записать в виде

gj(Х)А, =0, j = 1,..., m.

Из этих условий следует, что если множитель Лагранжа положителен (Aj > 0), то соответствующее ограничение в решении задачи (при х = х) выполняется как равенство (т. е. gj (х) = 0). Другими словами, это ограничение активно. С другой стороны, в случае, когда gj (х) > 0, то соответствующий множитель Лагранжа Aj равен нулю.

Если в задаче (*) часть ограничений имеет вид ограничений на неотрицательность некоторых xj, то для них можно не вводить множители Лагранжа, записав такие ограничения отдельно:

f (х) ^ max

x

gj (х) > 0, j = 1,..., m, (**)

х е X,

xi > 0, i е P С {1,..

Во внутренней точке (в том смысле, что x € int X) условия первого порядка для i € P тогда будут иметь следующий вид:

dL(x, A)

я , ^ < 0.

dxj

Для i € P здесь, как и в случае представления задачи в виде (*), производная функции Лагранжа по той переменной будет иметь вид ^JX^ = 0.

Кроме того, выполнены также условия дополняющей нежесткости

m dL(xA) А =0

Aj = 0, Е

dL(x,A) xi = 0.

dx,

ieP 1 Из второго из этих условий следует, что при x, > 0 (i € P) выполнено

dL(x, A)

0.

dx,

С другой стороны, если dL(x, A)/dx, < 0, то x, должен быть равен нулю.

Другая модификация теоремы связана с наличием в задаче ограничений в виде равенств. Обозначим множество соответствующих индексов через E. Задача принимает следующий вид:

f (x) ^ max

x

gj (x) > 0,j € {1,..., m}\E,

gj (x) = 0, j € E, (***)

x € X,

x, > 0, i € P С {1,.. ., n}.

При этом в теореме Джона снимается условие, что все множители Лагранжа неотрицательны - множители Лагранжа Aj при j € E могут иметь произвольный знак.

Теорема Джона не гарантирует, что множитель Лагранжа целевой функции, Ao, отличен от нуля. Однако если Ao =0, то условия Куна - Таккера характеризуют не решение рассматриваемой задачи, а структуру множества ограничений в точке x и теорема не имеет непосредственной связи с интересующей нас задачей максимизации функции f (o), поскольку градиент самой функции f (o) "пропадает" из условий Куна- Таккера. Поэтому важно охарактеризовать условия, которые гарантируют, что Ao > 0. Такие условия называются условиями регулярности.

В случае, когда рассматриваемая задача является выпуклой, одно из условий регулярности, - так называемое условие Слейтера - имеет вид:

В случае, когда целевая функция и ограничения задачи являются дифференцируемыми, простейшее условие регулярности формулируется в терминах градиентов функций-ограничений и имеет вид: градиенты активных ограничений в точке x линейно независимы. (В число рассматриваемых ограничений следует включать и ограничения на неотрицательность.)

Обозначим через A множество индексов тех ограничений, которые в точке оптимума x активны (в том числе, индексы всех ограничений в виде равенств), т. е.

gj (x) = 0 ^ j € A.

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

{vgj (x)}jeA

линейно независимы , то Ao > 0.

Заметим, что если Ao > 0, то без потери общности можно считать Ao = 1, что обычно и делается. Соответствующую теорему и называют собственно (прямой) теоремой Куна- Таккера.

Теорема 198 (Прямая теорема Куна-Таккера, необходимое условие оптимальности):

Пусть функции f (?), gi(?),..., g"(-) дифференцируемы, и х - решение задачи (*), такое что х € int X и выполнено условие регулярности Куна- Таккера.

Тогда существуют множители Лагранжа Aj ^ 0, j = 1,..., m, такие что при Ао = 1 выполнены следующие соотношения:

дЬ(х, Л)

0, i = 1,..., n

и

? dLg^ Aj = o.

o , dAj

j=i J
Несложно переформулировать эту теорему для задач (**) и (***). Здесь требуются такие же модификации условий Куна- Таккера, как и в теореме Джона. Условие

дЬ(х, Л)

0, i = 1 , . . . , n

можно переписать в виде:

Vf (х) = - ? Aj Vgj(х).

j=i

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

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

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

Рис. 17.2. Нарушение условий регулярности

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

Теорема 199 (Обратная теорема Куна-Таккера /достаточное условие оптимальности/):

Пусть f(?) - дифференцируемая вогнутая функция, gi(-),...,gn(0 - дифференцируемые квазивогнутые функции, множество X выпукло и точка х допустима в задаче (*), причем х € int X.

Пусть, кроме того, существуют множители Лагранжа Aj ^ 0, j = 1,...,m, такие что при Ао = 1 выполнены следующие соотношения:

и

J

Тогда х - решение задачи (*).

В еще одном варианте достаточного условия оптимальности предположение о вогнутости целевой функции заменяется на предположение о квазивогнутости с добавлением условия Vf (х) = 0.

Р. РокАФЕЛЛАР: Выпуклый анализ, М.: Мир, 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), и содержащиеся там ссылки. Аллен, Рой, 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