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

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

ОГЛАВЛЕНИЕ

Следующая >>

 714. При каких значениях дисконтирующих множителей пара стратегий следующего вида41 будет
совершенным в подыграх равновесием в повторяющейся игре Ауманна: «В первом раунде сотрудни-
чать. В остальных раундах поступать так же, как другой игрок в предыдущем раунде»?
 715. Найдите совершенное в подыграх равновесие в бесконечно продолжающемся торге. Решение
может опираться на тот факт, что через каждые два раунда подыгра, начинающаяся с текущей вер-
шины, повторяет исходную игру с точностью до дисконтирования. Таким образом, естественно искать
стационарное равновесие. Найдите такое равновесие и покажите, что оно является совершенным в
подыграх равновесием. Будет ли это равновесие оптимальным по Парето?




41
По-английски эту стратегию называют tit-for-tat, что может означать как «око за око», так и «услуга за
услугу», а если обобщенно, то «платить той же монетой».
sssssssssssssssssssssssssssss
Глава

Математическое
17
приложение

»»»»>


17.1 Вогнутые и квазивогнутые функции
Будем предполагать, что X — подмножество Rn .
Определение 97:
Функция f (·): X > R называется вогнутой, если X выпукло и для всех x, y ? X и ? ? [0, 1]
выполнено
f (?x + (1 ? ?)y) ?f (x) + (1 ? ?)f (y).
Функция f (·) называется выпуклой, если ?f (·) вогнута.

Определение 98:
Функция f (·): X > R называется строго вогнутой, если X выпукло и для всех x, y ? X , таких
что x = y и ? ? (0, 1) выполнено

f (?x + (1 ? ?)y) > ?f (x) + (1 ? ?)f (y).

Функция f (·) называется строго выпуклой, если ?f (·) строго вогнута.

Заметим, что строго вогнутая функция является вогнутой. Линейная функция p x является приме-
ром вогнутой, но не строго вогнутой функции.
Теорема 161:
Функция f (·): X > R является вогнутой тогда и только тогда, когда X выпукло и для всех
k
x1 , . . . , xk ? X и ?1 , . . . , ?k 0, таких что j=1 ?j = 1 , выполнено
k k
f ?j xj ?j f (xj ).
j=1 j=1


Данное свойство (как и определение вогнутой функции) является частным случаем неравенства Йен-
? ?
сена: f (E x) E f (? ) (для таких случайных величин, x , у которых соответствующие математические
x
ожидания существуют, в частности, для дискретных случайных величин).
Определение 99:
Верхним лебеговским множеством (superlevel set) функции f (·): X > R , соответствующим уровню
t ? R называется множество x ? X f (x) t .

Теорема 162:
Всякое верхнее лебеговское множество вогнутой функции выпукло.

Заметим, что это необходимое, но не достаточное условие вогнутости функции. Например, всякое верх-
нее лебеговское множество функции x3 выпукло, но сама она не вогнута (при x 0 она строго выпук-
ла, что несовместимо с вогнутостью). Указанное свойство является необходимым и достаточным для
квазивогнутых функций, о которых речь ниже.
Определение 100:
Подграфиком функции f (·): X > R называется множество (x, t) x ? X, t f (x) .

683
17.1. Вогнутые и квазивогнутые функции 684
Теорема 163:
Подграфик функции является выпуклым множеством тогда и только тогда, когда функция
вогнута.

Теорема 164:
m
Пусть fj (·): X > R (j = 1, . . . , m ) — вогнутые функции. Тогда j=1 ?j fj (x), где ?1 , . . . , ?k
0 , — вогнутая функция. В частности, сумма вогнутых функций вогнута.
m
Пусть fj (·): X > R (j = 1, . . . , m ) — строго вогнутые функции. Тогда j=1 ?j fj (x), где
?1 , . . . , ?k 0 и ?j > 0 хотя бы для одного j , — строго вогнутая функция. В частности, сумма
строго вогнутых функций строго вогнута.

Теорема 165:
Пусть fj (·): X > R (j = 1, . . . , m ) — вогнутые функции. Тогда их поточечный минимум
minj=1,...,m fj (x) — вогнутая функция.

Аналогичное свойство верно и в общем случае (не обязательно конечного) семейства вогнутых функ-
ций.
Теорема 166:
Пусть f (x, y): X > R (j = 1, . . . , m ) — семейство вогнутых по x функций, зависящих от
параметра y ? Y (где Y ? Rm ). Тогда их поточечный инфимум g(x) = inf y?Y f (x, y) — вогнутая
функция с областью определения x ? X inf y?Y f (x, y) > ?? .

Теорема 167:
Пусть g(·): X > R — вогнутая функция и ее область значений Y является выпуклым множе-
ством, и пусть h(·): Y > R — вогнутая неубывающая функция. Тогда суперпозиция этих функций
f (x) = h(g(x)) — вогнутая функция.

Теорема 168:
Пусть множество X является открытым, а функция f (·): X > R дифференцируема (т. е. во
всех точках X существует ее градиент f (·)). Эта функция является вогнутой тогда и только
тогда, когда ее множество определения X выпукло и для всех x, y ? X выполнено неравенство

f (x) (y ? x).
f (y) f (x) +

Т. е. вогнутая функция лежит (не строго) ниже любой своей касательной.

Теорема 169:
Точка x ? int(X) является минимумом дифференцируемой вогнутой функции f (·): X > R
тогда и только тогда, когда f (x) = 0.

Теорема 170:
Пусть множество X является открытым, функция f (·): X > R дважды дифференцируема
(т. е. во всех точках X существует ее матрица Гессе 2 f (·)). Эта функция является вогнутой
тогда и только тогда, когда ее множество определения X выпукло и для всех x ? X ее матрица
Гессе 2 f (x) отрицательно полуопределена.

Теорема 171:
Пусть множество X является открытым. Если функция f (·): X > R дважды дифференциру-
ема и ее матрица Гессе 2 f (x) отрицательно определена для всех x ? X , то f (·) строго вогнута.

Заметим, что обратное, вообще говоря, неверно. Так, функция f (x) = ?x4 является строго вогнутой,
но f (0) = 0.

Теорема 172:
Выпуклая (вогнутая) функция f (·): X > R непрерывна на внутренности ее множества опре-
деления int(X).
17.1. Вогнутые и квазивогнутые функции 685
Определение 101:
Функция f (·): X > R называется квазивогнутой, если X выпукло и для всех x, y ? X и ? ? [0, 1]
выполнено
f (?x + (1 ? ?)y) min(f (x), f (y)).
Определение 102:
Функция f (·): X > R называется строго квазивогнутой, если для всех x, y ? X , таких что x = y ,
и ? ? (0, 1) выполнено
f (?x + (1 ? ?)y) > min(f (x), f (y)).
Определение 103:
Функция f (·) называется квазивыпуклой, если ?f (·) квазивогнута.

Определение 104:
Функция f (·) называется строго квазивыпуклой, если ?f (·) строго квазивогнута.

Теорема 173:
Всякое верхнее лебеговское множество квазивогнутой функции выпукло.
???
Теорема 174:
Непрерывная функция f (·): X > R , где X ? R , является квазивогнутой тогда и только тогда,
когда ее множество определения X выпукло, и выполнено по крайней мере одно из трех условий:
• функция f (·) является неубывающей;
• функция f (·) является невозрастающей;
• существует точка x? ? X , такая что на множестве X ? (??, x? ] функция f (·) является
неубывающей, а на на множестве X ? [x? , +?) — невозрастающей.

Теорема 175:
Пусть g(·): X > R — квазивогнутая функция с областью значений Y , и пусть h(·) : Y >
R — неубывающая функция. Тогда суперпозиция этих функций f (x) = h(g(x)) — квазивогнутая
функция.
Теорема 176:
Пусть множество X является открытым, и функция f (·): X > R дифференцируема. Эта функ-
ция является квазивогнутой тогда и только тогда, когда ее множество определения X выпукло, и
для всех x, y ? X , таких что f (y) f (x), выполнено неравенство
f (x) (y ? x) 0.

Заметим, что для квазивогнутой функции (в отличие от вогнутой) из f (x) = 0 не следует, что точка
x является максимумом этой функции.
Теорема 177:
Пусть множество X является открытым. Если функция f (·): X > R дважды дифферен-
цируема и квазивогнута, то для всех x ? X и p ? Rn , таких что p f (x) = 0 , выполнено
2
p f (x)p 0 .
Как следствие, для всех x ? X , таких что f (x) = 0, матрица Гессе 2 f (x) дважды дифферен-
цируемой и квазивогнутой функции является отрицательно полуопределенной на гиперплоскости
p f (x) = 0 .
Обратное, вообще говоря, неверно, но имеется близкий аналог.
Теорема 178:
Пусть множество X является открытым. Если функция f (·): X > R дважды дифференциру-
ема и для всех x ? X и p ? Rn , таких что p = 0 и p 2
f (x) = 0 , выполнено p f (x)p < 0, то
функция f (·) является квазивогнутой.
Другими словами, достаточным условием квазивогнутости дважды дифференцируемой функ-
ции является то, что ее матрица Гессе 2 f (x) является отрицательно определенной на гиперплос-
f (x) = 0 при всех x ? X , таких что f (x) = 0, и отрицательно определенной при
кости p
x ? X , таких что f (x) = 0.
17.2. Однородные функции 686


17.2 Однородные функции
Напомним, что функция ?(x): Rn > R называется положительно однородной степени ? , если для
любого положительного числа t выполнено
?(tx) = t? ?(x).
Теорема 179:
Дифференцируемая функция ?(·) является положительно однородной степени ? тогда и толь-
ко тогда, когда выполняется тождество (формула Эйлера)
n
??(x)
xi = ??(x).
?xi
i=1


Теорема 180:
Если дифференцируемая функция ?(x) положительно однородна степени ? , то ее производная
??(x)
?i положительно однородна степени ? ? 1 .
?xi




17.3 Теорема Юнга
Теорема 181 ((теорема Юнга)):
Пусть функция f : Rn > R дважды непрерывно дифференцируема в точке x ? Rn . Тогда
? 2 f (x) ? 2 f (x)
= , i, j = 1, . . . , n.
?xi ?xj ?xj ?xi



17.4 Теоремы о неподвижной точке
Теорема 182 ((теорема Брауэра)):
Пусть A ? Rn — непустое, компактное и выпуклое множество и функция f : A > A непре-
рывна на A. Тогда существует точка x ? A:
?
?
x = f (? ).
x

Теорема 183 ((теорема Какутани)):
Пусть A ? Rn — непустое, компактное и выпуклое множество и f : A > A — полунепрерывное
сверху отображение, такое что f (x) — непустое выпуклое множество для любой точки x ? A. Тогда
существует точка x ? A :
?
x ? f (? ).
? x



17.5 Теоремы отделимости
Теорема 184 ((теорема Минковского)):
Пусть имеются непустое замкнутое выпуклое множество C ? Rn и точка x ? Rn , не принад-
лежащая C . Тогда найдется вектор a ? Rn , a = 0, и два числа b1 , b2 ? R , b1 > b2 , такие что
выполнены неравенства:
n
ai xi b1
i=1
и
n
b2 ?y ? C.
ai yi
i=1
17.6. Теорема об огибающей 687
Теорема 185:
Пусть имеются два непустых выпуклых множества C1 , C2 ? Rn не имеющие общих точек.
Тогда найдется вектор a ? Rn , a = 0, и число b ? R , такие что выполнены неравенства:
n
b ?x ? C1 .
ai xi
i=1

и
n
b ?y ? C2 .
ai yi
i=1

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

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

ОГЛАВЛЕНИЕ

Следующая >>