Глава 13. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ И ЯВЛЕНИЕ ЗАКЛИНИВАНИЯ

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

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

13.1. ОТОБРАЖЕНИЕ М3

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

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

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

Математически определяем как множество всех точек у, таких, что

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

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

где при заданном х отображение определяет направление

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

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

Рис. 13.1. Пример с нелинейными ограничениями.

Рис. 13.2. Пример с линейными ограничениями.

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

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

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

Мы построили такую последовательность что Однако

Поэтому отображение в точке не замкнуто.

Пример 2. Приведенный пример обладает одной особенностью: так как участок границы допустимой области представляет собой кривую, то направление может привести к тому, что будут находиться на одном и том же участке границы. Для линейных ограничений этого не может быть, но даже в случае линейных ограничений не обязательно должно быть замкнутым. Рассмотрим второй пример (рис. 13.2), где допустимая область представляет собой прямоугольник Последовательность направления , очевидно,

Если направлено вверх, то из вытекает Но и, очевидно, Поэтому в точке отображение незамкнуто.

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