2.8.2. Необходимые условия Куна-Таккера.

Обозначим через пространство всех -мерных действительных векторов. Элементы будем называть векторами или точками. Каждый ненулевой вектор можно рассматривать как некоторое направление. Пусть некоторая фиксированная точка из а — скалярная величина, изменяющаяся от 0 до бесконечности. Тогда каждая из точек вида представляет собой вектор, проходящий через точку х и имеющий направление

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

Нетрудно проверить, что для произвольного направления

где в правой части равенства написано матричное произведение вектора-строки на вектор-столбец Градиент определяет тем самым скорость роста функции в направлении

вектора Если для некоторого направления выполняется неравенство то найдется окрестность точки х, в которой функция возрастает в направлении вектора рис, 2.8.1). Как следует из соотношения (2.8.6), величина приращения при малых примерно равна

Предположим, что задана функция а также функции причем все функции дифференцируемы в Рассмотрим задачу

при ограничениях

В этой задаче условий имеют вид неравенств и условий — вид равенств.

Заметим, что ограничение эквивалентно ограничению а минимизация функции при некоторых ограничениях эквивалентна максимизации функции при тех же ограничениях, поэтому достаточно всегда рассматривать задачу (2.8.7) при ограничениях (2.8.8).

Если ограничения в задаче поиска максимума отсутствуют, то в точке максимума Другими словами, движение из X в любом направлении не увеличивает значение функции в некоторой окрестности точких. Если же ограничения имеются, то в точке максимума х градиент не обязательно равен нулю и, вообще говоря, может найтись направление в котором функция возрастает. Однако теперь следует учитывать не все возможные направления, а лишь те, движения в направлении которых не нарушают заданных ограничений. Для каждой точки удовлетворяющей условиям (2.8.8) (такие точки будем называть допустимыми), и некоторого а имеется множество допустимых направлений:

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

Условия Куна-Таккера позволяют строго сформулировать приведенные выше соображения, а также придать им более удобную форму.

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

Определим множество следующим образом:

Лемма Для каждой допустимой точки и любого а имеет место включение

Доказательство. Пусть зафиксировано а Покажем, что Предположим вначале, что хотя бы для одного индекса Тогда, из следует, что Это противоречит предположению о том, что допустимая точка. Следовательно, Аналогично доказывается, что Окончательно имеем для всех Предположим теперь, что для некоторого} . Тогда из (2.8.6) следует, что Это противоречит предположению, что Следовательно, для всех Лемма доказана.

Следует сказать, что в общем случае имеются направления из которые не принадлежат ни при каком а (см. задачу 2.8.1). Вместе с тем для широкого класса функций существует для которого в оптимальной точке

Говорят, что выполнено условие регулярности, если для некоторого в оптимальной точке х имеет место равенство

В дальнейшем мы будем предполагать, что условие регулярности выполняется. Заметим, что в случае, когда представляют собой ограничения, которым удовлетворяют только вероятностные векторы, выполнение условия регулярности (2.8.12) может быть легко показано (см. задачу 2.8.2).

Таким образом, из (2.8.10) и условия регулярности вытекает, что для оптимальной точки х

Теперь будет приведено без доказательства утверждение, известное под названием леммы Фаркаша.

Лемма 2.8.2. Пусть множество векторов из Для того чтобы существовали неотрицательных чисел таких, что необходимо и достаточно, чтобы для любого вектора для которого выполнялось неравенство

Из этой леммы и определения множества непосредственно следует теорема Куна-Таккера, дающая необходимые условия решения задачи (2.8.7) при ограничениях (2.8.8).

Теорема 2.8.1 (Куна-Таккера). Пусть решение задачи (2.8.7) при ограничениях (2.8.8) и выполнело условие регулярности. Тогда существуют числа неопределенные множители Лагранжа), такие, что

2) имеет место равенство

Доказательство. Заметим, что ограничение можно записать с помощью двух ограничений — неравенств, а именно Поэтому множество (см. (2.8.11)) можно определить следующим образом:

Теперь из (2.8.13) следует, что для векторов

выполнены условия леммы Фаркаша и поэтому существуют такие неотрицательные числа что

Если обозначить и положить для всех то последнее соотношение примет вид (2.8.11). Отсюда также следует, что для всех имеет место равенство Теорема доказана.