вектора
Если для некоторого направления
выполняется неравенство
то найдется окрестность точки х, в которой функция
возрастает в направлении вектора
рис, 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). Отсюда также следует, что для всех
имеет место равенство
Теорема доказана.