13.2. ЯВЛЕНИЕ ЗАКЛИНИВАНИЯ В МЕТОДЕ ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

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

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

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

вырабатывается последовательность При этом не существует такой подпоследовательности которая одновременно удовлетворяет следующим трем условиям:

в) существует такой скаляр что для всех и любого точка является допустимой.

Доказательство. Из условия (б) следует, что существует такое, что

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

если достаточно большое и

Выберем так, чтобы

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

Кроме того, согласно выбору

Отсюда, применяя разложение в ряд Тейлора, находим, что

где

Тогда из (13.2) следует, что для достаточно больших

Теперь обратимся к лемме 4.1. Поскольку и целевая функция монотонна, то

Отсюда получаем для достаточно больших

Теперь выберем так, чтобы выполнялись (13.4) и (13.6). Очевидно,

Но методы возможных направлений монотонны, поэтому неравенство (13.7) невозможно. Таким образом, три условия леммы одновременно удовлетворяться не могут. Лемма доказана.

Теорема 13.2, доказательство которой связано с доказательством леммы. 13.1, утверждает следующее: допустим, что некоторая подпоследовательность сходится к и что для любой подпоследовательности, сходящейся к соответствующие направления имеют сходящуюся подпоследовательность такую, что При этих условиях при По существу теорема дает условия, которые гарантируют сходимость всей последовательности к некоторой точке, если к этой точке сходится какая-нибудь подпоследовательность.

Теорема 13.2. Рассмотрим метод возможных направлений для задачи НЛП, в которой целевая функция является непрерывно дифференцируемой.

Пусть существует произвольная подпоследовательность, сходящаяся к

существует такое , что

и

При этих предположениях последовательность в целом также сходится к

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

Из предположений теоремы следует (см. упр. 13) существование таких положительных что если соответствует для которого то

Кроме того, для этих (упр. 14) существует положительное М, при котором

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

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

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

Так

Применяя несложное преобразование и используя последовательно соотношение (13.12), разложение в ряд Тейлора, неравенства (13.8) и (13.9), получаем

Но из оценки следует, что

Рассуждая так же, как и при доказательстве леммы 13.1, видим, что соотношение (13.13) не может иметь места для бесконечно больших Это противоречие доказывает теорему.

Интерпретация. Для интерпретации теоремы допустим, что имеется подпоследовательность которая сходится к и обладает свойством

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

Благодаря (13.14) последовательность где

тоже должна сходиться к так как, переходя к пределу в (13.15), мы приходим к соотношению

Если направления для последовательности ведут себя подобно направлениям для то при определении любой точки мы перемещаемся от в направлении на небольшое

Стояние сразу наталкиваемся на границу. Опять

Итак, подпоследовательность также сходится к Интуитивно представляется, что, продолжая таким образом, можно установить сходимость всей последовательности к (теоремой 13.2 это доказывается строго).

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

На рис. 13.1 приведена ситуация, когда это не имеет места.

Заклинивание. Выбор направлений не соответствующих границе вблизи может привести к нарушению сходимости. Это явление называется заклиниванием, так как согласно теореме 13.2 все точки, образно говоря, «заклиниваются» в окрестности некоторой точки на границе допустимой области.

Рис. 13.3. Выбор . В a) выбран, чтобы дать хорошее направление относительно границы выбран после того, как мы наблюдали, что, хотя достаточно близка к 0. Поэтому граница близка к Тогда был выбран так, чтобы отклониться от границы

Как избежать зйклйнивания. Одной из обычных бок, которая может привести к заклиниванию, является то, что определяется учетом только тех ограничений, которые активны в точке При этом выбирается так, чтобы обеспечить возрастание и избежать встречи только с теми ограничениями, которые активны в Так как некоторые участки границы, близкие к не учитываются, выбранное таким образом, может быть направлено на эти близкие участки, в результате чего может произойти заклинивание (рис. 13.3).

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

где непрерывно дифференцируема.

При произвольно заданной точке выберем направление следующим образом:

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

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

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

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

Но процедура выбирает Разрывность очевидна.

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

То, что эта процедура может не сходиться, показано на примере (упр. 1), в котором происходит заклинивание, и процедура не сходится.

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