ПРИЛОЖЕНИЕ 3Б. УСЛОВИЯ КУНА — ТАККЕРА И ДОКАЗАТЕЛЬСТВА ТЕОРЕМ 3.2.2 И 3.2.3

3Б.1. Условия Куна-Таккера

Теорема (Галлагер [1965] — частный случай результата Куна и Танжера [1951]). Пусть непрерывная, выпуклая функция аргумента определенная на множестве

Допустим, что частные производные существуют и непрерывны всюду, кроме, быть может, точек (на границе Тогда достигает максимума при некотором а необходимые и достаточные условия на - точку максимума функции состоят в том, что при некотором фиксированном

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

Если наложить линейное ограничение вида то стандартным методом множителей Лагранжа задача сводится к максимизации функции что приводит к условиям причем можно получить из задающего ограничение уравнения. С другой стороны, если область ограничена гиперплоскостями следует учесть возможность достижения максимума на границе. В этом случае условие для некоторой координаты не выполняется, но, по-видимому, должно выполняться [см. рис. 3Б.1,

Рис. 3Б.1. Примеры максимумов в областях, ограниченных гиперплоскостями: а — максимум во внутренней точке; б - максимум на границе.

где приведен одномерный случай]. Перейдем к доказательству необходимости и достаточности условий и

Доказательство. Необходимость: допустим, что имеет максимум в точке Пусть -вероятностный вектор и для всех к. Поскольку точка максимума для любого имеем

[Замечание: внутренняя точка поскольку внутренняя точка Рассмотрим теперь

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

так что по теореме о среднем значении из получаем

Воспользовавшись и положив получим неравенство

откуда ввиду предположения о непрерывности производных следует

Следовательно, для некоторого должно выполняться Пусть любое другое целое между Поскольку произвольная точка, выберем ее так, чтобы

Это всегда возможно, поскольку и гарантируют, что выбранное так будет вектором распределения. Подставив и в получим

Введем обозначение

Из того, что в следует, что

Но поскольку произвольно, то отсюда вытекает необходимость в Далее, когда мы можем выбрать в Неравенство перейдет в что доказывает необходимость

Достаточность. Пусть выполнены условия и покажем, что для всех

Из и имеем

которое переходит в равенство, если Суммируя по получаем

Из соотношения получим

«ли, что то же самое,

Но, поскольку выпукла левую часть в неравенстве можно заменить на

что доказывает достаточность условий и

3Б.2. Применение условия Куна — Таккера к ...

Доказательство теоремы 3.2.2. В лемме 3.2.2 мы показали, что выпукла Следовательно,

выпукла а максимизация эквивалентна максимизации Используя и получим

поскольку

Таким образом,

причем равенство достигается, если Просуммировав по после умножения на и поменяв порядок суммирования, для левой части неравенства получим

а для правой части

Следовательно, из вытекает

[поскольку обращается в равенство при а слагаемые, в которых не входят в суммы в обеих частях неравенства]. Таким образом, объединяя и получим

с равенством для всех х, таких, что

Доказательство теоремы 3.2.3. В лемме 3.2.3 мы доказали, что выпукла Следовательно, используя и получим

Суммируя по после умножения на для левой части получим

а для правой части

Поэтому следовательно, переходит в неравенство

[поскольку q обращает в максимум причем равенство достигается для всех х, таких, что