Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
MS*L= 0; l<fc</C. (4.4.7)
да. k
Множество этих уравнений может не иметь решения, а если решения существуют, то они, возможно, не удовлетворяют ограничениям Покажем, однако, теперь, что если существует такое а, которое удовлетворяет как (4.4.7), так и этим ограничениям, то рассматриваемое а максимизирует функцию. Чтобы показать это, предположим, что результат не верен, т. е. что имеется некоторый вектор р, принадлежащий области, для которого / (Р) > / (а). Ордината хорды, соединяющей / (Р) и / (а), в этом случае увеличивается от / (а) к / (Р). Как показа-102
но на рис. 4.4.2, скорость увеличения функции в точке а в направлении Р не меньше, чем скорость возрастания ординаты хорды. Таким образом, а не может быть стационарной точкой / и мы пришли к противоречию.
Рассмотрим далее случай, когда максимум / (а) в R лежит на границе области, т. е. в точке, где одна или более компонент а равна нулю. В этом случае, как показано на рис. 4.4.3, не следует удивляться тому, что функция является строго убывающей при изменениях аргумента, направленных внутрь области, т. е. при изменениях нулевых компонент а. Вместе с тем, если / дифференцируема, то можно ожидать, что максимум будет в стационарной точке, соответствующей вариациям ненулевых компонент а. Это предполагает замену (4.4.7) на условия
— ^ =0 пои всех k, для которых ah>0, (4.4.8)
dah
— gC 0 при всех k, для которых aA = 0. (4.4.9)
дак
Сейчас мы не будем касаться того, как решить эти уравнения. Важным является то, что если а принадлежит области и удовлетворяет
(4.4.8) и (4.4.9), то оно максимизирует f и, наоборот, если f дифференцируема и имеет максимум в области в точке а, то (4.4.В) и (4.4.9) удовлетворяются. Ниже будет приведено доказательство этих утверждений.
В качестве второго примера рассмотрим максимизацию выпуклой функции / (а) в области, в которой а является вектором вероятностей, т. е. в области, где компоненты а неотрицательны и в сумме равны 1. Условие I,ah — 1 позволяет использовать метод множителей
Лагранжа, который означает максимизацию / (а) — по области, в которой компоненты неотрицательны, и выбор % таким образом, чтобы максимум имел место при = 1. Применяя (4.4.8) и (4.4.9) к функции f (а) — XZah, будем иметь:
Ж(°0. при всех k, для которых ah > 0, (4.4.10)
дак
<; % при всех k, для которых аь=0. (4.4.11)
Будет показано, что условия (4.4.10) и (4.4.11) являются в действительности необходимыми и достаточными условиями того, что вектор вероятностей а максимизирует выпуклую ^ дифференцируемую функцию /. Другими словами, если вектор вероятностей а удовлетворяет (4.4.10) и (4.4.11) при некотором значении X, то этот вектор а максимизирует / в области, и, наоборот, если а максимизирует / в области, то (4.4.10) и (4.4.11) удовлетворяются при некотором %. Приступим теперь к доказательству этого результата.
Теорема 4.4.1. Пусть / (а) является выпуклой функцией
а = (аъ ..., а%) в области R, где a — вектор вероятностей. Предполо-
жим, что частные производные df (a)/dah определены и непрерывны в области R с тем возможным исключением, что lim df (a)/dak может быть
ah~0
№
равен + 00 для некоторых k. Тогда (4.4.10) и (4.4.11) являются необходимыми и достаточными условиями того, что вектор вероятностей а максимизирует / в области R.
Доказательство. Достаточность. Предположим, что (4.4.10) и (4.4.11) удовлетворяются при некотором % и некотором векторе вероятностей а. Покажем теперь, что / (Р)—/ (а.) < 0 для любого вектора вероятностей р, что будет означать, что а максимизирует /. Из определения выпуклости следует
0/(P)+(i-e)/(o)</[ep+(i-0)o]; о<в<1. (4.4.12)
Преобразуя (4.4.12), будем иметь
/ (р)_/(а)<с +11Г~^*1-1W . (4.4.13)
0
В силу того, что (4.4.13) справедливо при всех 0, 0 <Г 0 <Г 1, можно перейти к пределу и получить
¦d/[ep + (i-0)«]
dQ
) = о
(4.4.14)
Выполняя дифференцирование, имеем
f№-f{»)< (4-4Л5>
дак
Существование производной в (4.4.14) и эквивалентность (4.4.14) и (4.4.15) следуют из непрерывности частных производных. Эта непрерывность является следствием предположения, так как (4.4.10) и
