2.4. НЕОБХОДИМЫЕ УСЛОВИЯ КУНА—ТАККЕРА

Если оптимальная точка задачи НЛП, то при умеренных предположениях условия Куна — Таккера с необходимостью удовлетворяются. Напомним, что следствие 2.1.1 дает необходимые условия, чтобы х была точкой максимума при отсутствии ограничений. Мы употребляем термин «отсутствие ограничений» потому, что х максимизирует на всем а не только на части, выделенной ограничениями. Отсутствие ограничений сыграло решающую роль при доказательстве следствия

2.1.1, так как из точки х можно было двигаться в направлении Если были бы ограничения, движение в направлении могло бы нарушить какое-либо ограничение и доказательство было бы неверным. Ограничения вызывают значительные трудности, и этот параграф посвящен их рассмотрению.

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

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

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

Если выразить это словами, то направление принадлежит если можно двинуться от на небольшое расстояние в направлении оставаясь в допустимом множестве (рис. 2.3). Здесь обозначение выражает «существует», «такое, что», а символ означает «следует».

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

Рис. 2.3. (см. скан) Примеры множеств возможных направлений.

Лемма 2.11. Пусть оптимальная точка для задачи НЛП. Тогда для всех

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

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

Напомним, что множество является замыканием если любая точка является предельной точек Хотя любая точка из входит также в некоторые точки могут не принадлежать Однако если — замкнутое множество, то . К сожалению, не обязательно замкнуто, так как некоторые касательные направления могут не входить в него (см. рис. 2.3).

Следствие 2.11.1. Пусть х — оптимальная точка для задачи НЛП. Тогда

Доказательство. Направление может быть представлено как предельное для направлений из

Так как то по лемме 2.11

Переход к пределу дает

и так как была произвольной точкой из следствие доказано.

Таким образом, мы видим, что лемма 2.11 справедлива для так же, как и для Мы теперь подошли к доказательству теоремы Куна — Таккера.

Доказательство этой теоремы содержит два основных момента. Сначала мы выразим множество через ограничения. Затем с помощью леммы Фаркаша можно переформулировать следствие 2.11.1, используя ограничения задачи. Отсюда непосредственно будет следовать теорема Куна — Таккера.

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

Чтобы выразить через ограничения, необходимо рассмотреть лишь активные ограничения. Действительно, предположим, что Благодаря непрерывности мы можем переместиться от х на небольшое расстояние в любом направлении, не нарушая это ограничение. Поэтому неактивные ограничения не влияют на

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

Лемма

Доказательство. Рассмотрим множество возможных направлений Пусть и предположим, что Если то по теореме 2.1 для всех достаточно малых Так как такое направление не является возможным, то Следовательно, Но множество замкнуто, так что (упр.

Условия регулярности. К сожалению, существуют случаи (упр. 12), когда имеются направления из которые не принадлежат Однако эти случаи обычно представляют собой искусственные математические построения, и кажется мало вероятным, чтобы они могли возникнуть на практике. Поэтому предположение, что , следовательно, может вызвать лишь небольшую потерю общности. Это предположение очень важно и известно как условие регулярности.

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

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

Резюмируя эти результаты и воспользовавшись следствием 2.11.1, получаем следующее утверждение.

Лемма 2.13. Пусть х — оптимальная точка задачи НЛП. Тогда при наличии условия регулярности для любого для всех

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

Утверждение, что для любого для всех эквивалентно существованию множителей таких, что

Отсюда непосредственно следует теорема Куна — Таккера.

Теорема 2.14. Рассмотрим задачу НЛП нахождения

где все функции дифференцируемы.

Пусть х — оптимальная точка (решение) и предположим, что имеет место условие регулярности. Тогда справедливы следующие три утверждения:

1) х — допустимая точка. Существуют множители такие, что

Доказательство. Условия 1 теоремы Куна — Таккера тривиальны, а 2 и 3 являются просто переформулировкой равенства (2.14). Действительно, если то и условия 2 Куна — Таккера означают, что Поэтому условия 3 в точности совпадают с равенством (2.14).

Условия 1—3 называются условиями Куна — Таккера. По существу условия Куна — Таккера заменяют заявление о том, что оптимальная точка, уравнениями и неравенствами. Из оптимальности х было выведено, что для всех а фактически и для всех . Далее приравнивание дает, что для всех После этого лемма Фаркаша приводит к условиям Куна — Таккера. Следует обратить внимание, однако, на то, что лемма Фаркаша дает более сильный результат, т. е. условия Куна — Таккера эквивалентны утверждению, что для всех

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

Геометрическая интерпретация условий Куна — Таккера дана на рис. 2.4. В оптимальной точке х отрицательный градиент лежит в геометрическом конусе градиентов активных в х ограничений. Под этим конусом подразумевается

Условия Куна — Таккера для ограничений-равенств.

Часто задача НЛП пишется с ограничениями как в виде равенств, так и в виде неравенств: найти при

Рис. 2.4. Геометрическая интерпретация условий Куна—Таккера.

В качестве упр. 2.16 предлагается показать, что условиями Куна — Таккера для этой задачи являются

1) х — допустимая точка. Существуют множители и неограниченные по знаку множители такие, что

Следует обратить внимание, что неотрицательные множители соответствуют ограничениям-неравенствам, тогда как множители для ограничений-равенств допускаются отрицательными, положительными или нулевыми. Условия Куна — Таккера 2 относятся к ограничениям-неравенствам.

Условия Куна—Таккера имеют важнейшее значение в НЛП, и мы будет постоянно пользоваться ими в книге.

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