13.4. МЕТОД r-ВОЗМУЩЕНИЙ

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

Рассмотрим задачу НЛП

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

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

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

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

Рассмотрим эту подзадачу несколько подробнее. Следует обратить внимание на то, что точка всегда является допустимой, поэтому

Пусть тогда

и

Согласно выражению (13.23) перемещение в направлении приведет к возрастанию Кроме того, из (13.22) следует, что небольшое перемещение в направлении увеличит для . Другими словами, перемещаясь на небольшое расстояние вдоль , мы одновременно сохраняем допустимость и увеличиваем Следовательно, если то направление является хорошим направлением для продвижения.

При услойия Куна — Таккера выполняются. Пусть тогда при некотором для всех направлении для которых

и

Кроме того, выбирая масштаб для находим, что при некотором , для всех для которых

и, значит, утверждения (13.24) и (13.25) эквивалентны. Но согласно положениям, высказанным в гл. 2, (13.25) равносильно утверждению, что в точке х выполняются условия Куна — Таккера.

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

Следующие две леммы также разъясняют поведение подзадачи. Первая из них анализирует множество .

Лемма 13.3. Пусть Определим

где если в точке все ограничения активны.

а) Если , то

Кроме того, при достаточно больших

для любого где

б) Если дано фиксированное то для достаточно больших

Доказательство, а. Для любого

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

Для всех достаточно больших из непрерывности ограничений Для всех не входящих Поэтому при если не входит в то не может входить в . Это доказывает . Доказательство оставляется в виде упр. 5 (см. также рис. 13.4).

Следующая лемма дает более подробное описание решений подзадач.

Лемма 13.4. Пусть Тогда существует такое что при достаточно больших

для любого

Кроме того, существует такое , что где

Рис. 13.4. Геометрическая иллюстрация соотношения ,

Доказательство. Определим в так же, как в части (а) леммы 13.3. Сначала анализируем задачу

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

удовлетворяет условиям

Из непрерывности вытекает, что для достаточно больших

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

Теперь рассмотрим для достаточно больших подзадачу

Пусть решение.

Согласно части (а) леммы для так что подзадача (13.28) имеет более слабую систему ограничения, чем подзадача (13.27). Поэтому значение целевой функции для ее решения будет не меньше, чем для решения задачи (13.27). Но решение задачи (13.27) не меньше, чем а. Следовательно, в

при Достаточно Этим установлена справедливость первой части леммы.

Для завершения доказательства рассмотрим ограничения в (13.28).

Очевидно

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

Лемма доказана.

Замечание. Лемма 13.4 дает определяющее свойство, необходимое в предположениях теоремы 13.2. В частности, предположим, что

Если не удовлетворяет условиям Куна — Таккера, то, как было отмечено ранее, , как было показано в лемме

Таким образом, из теоремы 13.2 заключаем, что

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

Если

При полагаем

Далее вычисляется согласно соотношению

Поиск завершается, если удовлетворяет условиям Куна — Таккера.

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

Нетрудно видеть, что условие 1 теоремы сходимости выполняется. Установим выполнение условия 2.

Пусть

где не является подходящей точкой. Так как то все входят в компактное множество. Значит, существует такое что

Справедливость условия 2а установлена.

Для того, чтобы убедиться в соблюдении условий 2б и 2в, мы должны сначала проанализировать последовательность Ясно, что эта последовательность невозрастающая и ограничена снизу нулем. Поэтому она имеет предел (упр.

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

Теперь рассмотрим произвольную подпоследовательность, сходящуюся к Согласно лемме 13.4 и неравенству (13.30) существует такое ччто

где

Отсюда, воспользовавшись теоремой 13.2, получим, что вся последовательность сходится к

Пусть

Из леммы 13.4 уравнений (13.31) и (13.32) следует, что для всех достаточно больших Тогда неравенство не может иметь места бесконечное число раз. Поэтому согласно построению в алгоритме

не может быть равным бесконечно много Следовательно, невозможно, чтобы т. е.

Из (13.33) непосредственно вытекает следующее: поскольку и согласно правилу получения из должно существовать такое Р, что для

Более того, так как неравенство влечет за собой соотношение

то

Условие 26. Из выражения (13.35) легко следует условие 26. Анализ ограничений подзадачи обнаруживает, что

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

Условие 2в. Благодаря части (б) леммы 13.3 и соотношению (13.34) для всех достаточно больших

Вследствие того, что

Учитывая далее непрерывность, видим, что не только

но также существует такое что при и для достаточно больших

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

Рис. 13.5. Геометрическая иллюстрация процедуры -возмущений.

Интерпретируя этот результат, видим, что если достаточно большое, то для любого удовлетворяющего условию точка не встретится с ограничением для Более того, так как нет других ограничений, активных в точке то имеется возможность свободного перемещения вблизи без препятствий со стороны каких-либо других ограничений. В математических терминах это можно сформулировать так: существует такое при котором для достаточно больших точка допустима, если Условие 2в выполняется и, следовательно, метод -возмущений сходится (рис. 13.5) Теорема доказана. На рисунке кружки указывают на то, что все ничения, участки границы которых входят в кружок, включаются в множество индексов . Видно, что в точке в подзадаче рассматриваются оба ограничения и Однако не находится на участке границы Точка не попадает ни на один из участков границы. Операция состоит в максимизации внутри допустимой области.

Замечания. Значительную часть доказательства составляет установление положительности По существу условие гарантирует, что любая подзадача рассматривает все ограничения вблизи (рис. 13.5). Если станет равным нулю, то мог бы стать столь малым, что не содержало бы индексов участков границ, близких к Чтобы избежать заклинивания, следует учитывать все участки границы, проходящие через точку и вблизи нее.

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Примечания и ссылки

§ 13.1 и 13.2. Здесь употребляется слово «заклинивание», хотя ранее Зойтендейк (1960) предложил выражение «зигзагообразное движение». Термин «заклинивание» кажется более выразительным, поскольку показывает, что что-то не работает — произошло заклинивание или, если использовать НЛП, нет сходимости. Многие алгоритмы приводят к зигзагообразному движению в смысле геометрического описания пути, но все же сходятся. Наиболее ранние обсуждения явления заклинивания содержатся в работах Зойтендейка (1960) и Розена (1961). См. также работы Вольфа (1966) и Зангвилла (1967h).

То, что отображение М, не будучи замкнутым, может вызвать заклинивание, является новым наблюдением. Пример процедуры, которая приводит к заклиниванию, был предложен Вольфом (1966). Упражнение 13.1 оснозано на его примере. Другой пример, сформулированный в геометрических терминах, см. в работе Зангвилла (1967h).

§ 13.3. В работе Топкиса и Вейнотта приведена теорема, родственная теореме сходимости для методов возможных направлений, но несколько отличная от нее. Упр. 13.10 также основано на этой работе Топкиса и Вейнотта.

§ 13.4. Несмотря на то, что доказательство является новым, этот метод был предложен в работе Зойтендейка (1960).