Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
не Выпуклая
Не выпуклая
Не Выпуклая
Выпуклая
Рис. 4.4.1. Примеры выпуклых областей для двумерных векторов.
Весьма полезным для наших целей примером выпуклого множества является область векторов вероятностей. Назовем вектор вектором вероятностей, если все его компоненты неотрицательны и в сумме равны 1. Чтобы показать, что эта область выпукла, предположим, что аир являются векторами вероятностей, и положим \ = 0а + -t- (1 — 0) р при 0 < 0 < 1. Тогда
Vft = 0«ft + (1 — 9) Pft- (4.4.1)
Следовательно, yh ^ 0, а также
| Тй = 0 | «* + (* —0) S Ь (4-4.2)
k=\ k=\ А=1
Таким образом, \ является вектором вероятностей и область векторов вероятностей выпукла.
Назовем действительную функцию f векторного аргумента выпуклой г\ (следует читать выпуклой вверх) в выпуклой области R вектор-
*> Более полное описание свойства выпуклости можно найти, например, в книге Блекуэлла и Гирцшка, Теория игр и статистические решения, гл. 2 (1954).
100
noio пространства, если для всех а из R, $ из R и 6, 0 < в < 1, функция удовлетворяет условию
6/ („) + (j _0) f (р) < / [0о + (1 - 0) р]. (4.4.3)
Если имеет место неравенство, обратное (4.4.3) для всех таких а, р и 0, то f (а) называется выпуклой ^ (следует читать выпуклой вниз). Если неравенство может быть заменено на строгое неравенство, то f(a) называется строго выпуклой ^ или строго выпуклой
На рис. 4.4.2 изображены выражения, стоящие в двух частях
(4.4.3), как функции 0. Можно заметить, что геометрическая интерпретация (4.4.3) состоит в том, что любая хорда, соединяющая две точки на кривой, представляющей функцию, лежит ниже (или на) этой кривой. Причина, по которой область в определении взята выпуклой, состоит в том, чтобы обеспечить то, чтобы вектор, стоящий в правой части
(4.4.3), принадлежал R.
Из (4.4.3) непосредственно следует, что если / (а) выпукла то
— /(а) выпукла и наоборот. Поэтому мы будем иметь дело только с выпуклыми функциями, так как результаты могут быть легко применены к выпуклым ^ функциям.
Для удобства приведем здесь ряд свойств выпуклых функций, которые часто оказываются полезными.
1) Если f1(a), ..., /l(o) являются выпуклыми /-ч функциями и если Сх, ..., Cl положительные числа, то функция
i
является выпуклой и выпуклость строгая, если какая-либо ио ft (а) строго выпукла.
2) Пусть для одномерного вектора а
d2f(a)/da2^ 0 (4.4.4)
на всем интервале, тогда f(а) выпукла на этом интервале со строгой выпуклостью, если (4.4.4) справедливо со строгим неравенством.
3) Если (alt ..., aL) — множество векторов из области, в которой f (а) выпукла /~\, и если (Qlt ..., 0L) — множество вероятностей (т. е. 0,>О; 2 0, = 1), то
L
2 0//(«/)</ 1
L
i= 1
(4.4.5)
Считая а дискретным случайным вектором и используя черту сверху для обозначения математического ожидания, получаем, что это неравенство эквивалентно
/1^</(а). (4.4.6)
*) В математической литературе выпуклая о функция обычно называется вогнутой, а выпуклая w функция ¦— выпуклой. Эта терминология не используется здесь потому, что для большинства людей такое различие очень трудно для запоминания. В недавно устроенном испытании для десяти человек, которые думали, что они помнят это различие, восемь человек спутали выпуклость с вогнутостью.
101
Подставляя 2с;/, (а) в неравенство, определяющее выпуклость
(4.4.3), устанавливаем справедливость свойства 1. Свойство 2 почти очевидно геометрически (см. рис. 4.4.2) и оно доказано в задаче 4.9. Свойство 3 на геометрическом языке означает, что часть «плоскости», в которой лежат точки / (о^, ..., / (ol), находится ниже (или на) поверхности, порождаемой f (а) между этими точками (см. для доказательства задачу 4.9).
С помощью этих свойств легко показать, что энтропия ансамбля
— 2 Р (ah) log Р (ah) является строго выпуклой ^ функцией входя-k
щих в нее вероятностей. Свойство 2 показывает, что — Р (ah) х X log Р (ah) строго выпукла ^ по Р (ак), а свойство 1 показывает, что
Рис. 4.4.2. Выпуклая функция. Рис. 4.4.3. Вид выпуклой функции
с максимумом в области cii^sO, a2^0, который достигается при а2 = 0.
сумма строго выпукла /-^. Неравенство (4.3.16), которое мы оставили недоказанным в предыдущем параграфе, следует из (4.4.6) и выпуклости энтропии.
Основной причиной рассмотрения здесь свойства выпуклости является то, что выпуклые ^ функции относительно легко максимизировать в выпуклой области. Для того чтобы показать это, рассмотрим вначале не строго некоторые примеры. Предположим, что / (а) — выпуклая ^ функция в области R, где ай^0, 1 -< k < К. Разумно было бы попытаться найти максимум / (а) в R с помощью отыскания стационарной точки / (а), т. е. отыскания такого а, для которого
