§ 2.8. Поиск экстремумов

В заключение этой главы мы рассмотрим задачу поиска экстремумов функций нескольких переменных при наличии ограничений. Эта задача непосредственно не относится к исследованию свойств количества информации, но весьма часто встречается в теории информации в приложении к максимизации или минимизации средней взаимной информации, а также других теоретико-информационных функций. Ниже будут сформулированы необходимые условия экстремума, так называемые условия Куна-Таккера, и показано, что эти условия являются достаточными для максимизации или минимизации выпуклых функций, заданных на выпуклых множествах.

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

2.8.1. Метод неопределенных множителей Лагранжа.

Предположим, что требуется найти экстремум функции при условии, что где все функции определены на множестве -мерных действительных векторов Стандартным методом решения такой задачи, приводящим задачу поиска условного экстремума к задаче поиска безусловного, является метод неопределенных множителей Лагранжа.

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

в поиске безусловного экстремума функции Необходимые условия экстремума можно записать следующим образом:

где второе условие есть тождественное равенство. Обозначая (заметим, что число X называется неопределенным множителем Лагранжа), условия (2.8.1) можно привести к виду

Таким образом, для поиска условного экстремума необходимо найти решения относительно переменных х, у и к следующих трех уравнений:

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

В общем случае для функции от переменных при наличии ограничивающих условий метод множителей Лагранжа дает следующие необходимые условия экстремума

из которых определяются значений переменных неопределенных множителей Лагранжа Заметим, что система уравнений имеет решение только в том случае, когда в стационарной точке обе частные производные не равны нулю одновременно. Аналогичное условие для системы (2.8.3) выглядит следующим образом: в стационарной точке одновременно не равны нулю все определители

порядка образованные частными производными функций по из переменных

Метод неопределенных множителей Лагранжа дает один из возможных путей поиска экстремумов функций нескольких переменных при наличии ограничений. Однако условия (2.8.4), при которых этот метод применим, могут не выполняться. С другой стороны, часто встречаются задачи поиска экстремума при ограничениях, представляющих собой неравенства, а не равенства, как в разобранном выше случае. Поэтому желательно иметь необходимые условия экстремума, не зависящие от типа ограничений и от свойств функций, задающих ограничения. Такого сорта задачи составляют предмет теории нелинейного программирования (см., например, [8]). Одним из центральных результатов нелинейного программирования, который широко используется в теории информации, является теорема Куна—Танкера.

Рис. 2.8.1. Градиент и приращение функции по направлению