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

Этот класс методов решения задач НП основан на движении из одной допустимой точки к другой с лучшим значением целевой функции.

Типичная стратегия поиска в алгоритмах этого класса состоит в следующем. Возьмем текущую допустимую точку  и найдем направление  такое, что при достаточно малых  выполняются следующие два условия: 1) точка  является допустимой; 2)

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

Метод Зойтендейка

Типичным представителем класса методов возможных направлений является метод Зойтендейка. На каждой итерации метода находят возможное направление спуска, а затем проводят оптимизацию вдоль этого направления. Для изложения идеи метода введем ряд необходимых понятий [2; 8].

Определение 6.1. Рассмотрим задачу минимизаци  при условии, что , где – непустое множество.

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

Вначале рассмотрим случай, когда ограничения линейные и задача НП имеет вид:

минимизировать                              (6.5.1)

при условиях                               (6.5.2)

                                          (6.5.3)

где  – матрица порядка ;  – матрица порядка ;
 — -мерный вектор;  — -мерный вектор.

Справедливо следующее утверждение.

Лемма 6.1. Рассмотрим задачу минимизаци (6.5.1)-(6.5.3). Пусть  – допустимая точка и предположим, что , где , а .

Ненулевой вектор  является возможным направлением в точке  в том и только в том случае, если  и . Если, кроме того, , то  является возможным направлением спуска.

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

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

Пример 6.3. Минимизировать   при условиях

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

На рис. 6.11. изображена совокупность этих направлений, образующая конус возможных направлений. Здесь 1 – конус возможных направлений; 2 – конус возможных направлений спуска;  3 – линии уровня целевой функции; 4 – полупространство направлений спуска.

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

Построение возможных направлений спуска

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

Следовательно, в задачу должно быть  включено условие, которое бы ограничивало вектор . Такое ограничение называют нормирующим. Возможны различные формы нормирующего ограничения. Ниже приведены три задачи отыскания (наилучшего) направления спуска, в каждой из которых используются различные условия нормировки [4].

Задача :      минимизировать       

при условиях

.

,

,

 

Задача : минимизировать

при условиях

,

,

.

Задача : минимизировать

при условиях

.

,

,

Задачи  и  являются задачами ЛП и, следовательно, их можно решить симплекс-методом.

Так как  является допустимой точкой в каждой из приведенных выше задач, а значение целевой функции в этой точке равно 0, то ее оптимальное значение в задачах , ,  не может быть положительным. Если минимальное значение ц.ф. в задачах , ,  отрицательно, то по лемме 6.1 нами построено возможное направление спуска. С другой стороны, если минимальное значение целевой функции равно нулю, то, как будет показано ниже, точка x является точкой Куна-Таккера.

Лемма 6.2. Рассмотрим задачу минимизаци  при условиях . Пусть  – допустимая точка, в которой ,

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

Доказательство. Как следует из теоремы Куна-Таккера (гл.5),  будет точкой Куна-Таккера тогда и только тогда, когда существуют векторы  такие, что

 .                          (6.5.4)

Согласно следствию из леммы Фаркаша система (6.5.4) разрешима тогда и только тогда, когда система неравенств  не имеет решений, т.е. когда оптимальное значение целевой функции в задачах , ,  равно нулю.

Итак, мы показали, как найти возможное направление спуска.

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

минимизировать  по                 (6.5.5)

при условиях

,                                    (6.5.6)

.                                   (6.5.7)

Предположим, что . Тогда задачу (6.5.5)-(6.5.7) можно упростить следующим образом. Заметим, что . Значит, ограничение (6.5.7) излишне. Так как , то  для всех . Итак, остается только одно ограничение , и задача оптимизации (6.5.5)-(6.5.7) приводится к следующей задаче одномерной оптимизации:

минимизировать  по                 (6.5.8)

при условии

 ,

где                                             (6.5.9)

 .                         (6.5.10)

Алгоритм метода Зойтендейка в случае
линейных ограничений

Пусть требуется найти  при условиях .

Алгоритм метода состоит из предварительного и основного этапов. Последний в свою очередь состоит из однотипных итераций.

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

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

минимизировать                              (6.5.11)

при условиях

,

                                       (6.5.12)

,

.                              (6.5.13)

Если , то остановиться, и – оптимальное решение (точка Куна-Таккера). В противном случае перейти ко второму шагу.

Второй шаг. Положить  равным оптимальному решению приведенной ниже задачи одномерной оптимизации:

минимизировать

при условии                          ,

где  задается формулой (6.5.9).

Для решения этой задачи можно применить любой метод одномерного поиска, например метод Фибоначчи.

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

Задачи с нелинейными ограничениями-неравенствами

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

минимизировать                            (6.5.14)

при условиях                                                   (6.5.15)

В следующей теореме формулируются достаточные условия, при которых вектор  является возможным направлением спуска. [2; 18].

Теорема 6.2. Рассмотрим задачу НП (6.5.14), (6.5.15). Пусть  – допустимая точка, а  – множество индексов активных  в этой точке ограничений, т.е.. Предположим, кроме того, что функции  для  дифференцируемы в точке , а функции  для  непрерывны в этой точке. Если ,  при , то вектор  является возможным направлением спуска.

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

Таким образом, вектор  является возможным направлением спуска.

На рис. 6.12 показана совокупность возможных направлений в точке . Здесь использованы такие обозначения: 1 – первое ограничение, 2 – третье ограничение, 3 – четвертое ограничение, 4 – второе ограничение, 5 – возможные направления спуска, 6 – линии уровня целевой функции. Вектор ,  удовлетворяющий равенству , является касательным к кривой линии (или поверхности) . Поскольку функции  нелинейны, то движение вдоль такого

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

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

минимизировать                            (6.5.16)

при условиях

,                             (6.5.17)

,                      (6.5.18)

.                         (6.5.19)

Пусть  – оптимальное решение этой задачи ЛП. Если , то, очевидно,  – возможное направление спуска. Если же , то, как будет показано ниже, точка  является точкой Куна-Таккера.

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

                     (6.5.20)

и либо , либо  для некоторого , а это одно из условий оптимальности теоремы Куна-Таккера.

Алгоритм Зойтендейка в случае нелинейных
ограничений-неравенств

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

Основной этап. Первый шаг. Положить  и решить задачу:

минимизировать                            (6.5.20)

при условиях

,                             (6.5.21)

.          (6.5.22)

Пусть  – оптимальное решение задачи (6.5.20) – (6.5.22). Если , то конец алгоритма и точка  – оптимальное решение такой задачи одномерной оптимизации. Если , то перейти ко второму шагу.

Второй шаг.

минимизировать                  (6.5.23)

при условии ,                      (6.5.24)

где                              .     (6.5.25)

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

Пример 6.4. Рассмотрим задачу:

минимизировать  

при условиях

  

Будем решать эту задачу методом Зойтендейка, начиная поиск из точки . Заметим, что  

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

минимизировать

при условиях

 

Можно проверить, решая эту задачу симплекс-методом, что оптимальным решением этой задачи является вектор  и .

Второй шаг. Линейный поиск. Любая точка по направлению  из точки  может быть представлена в виде , а соответствующее ей значение целевой функции равно . Максимальное значение , для которого точка  остается допустимой, равно . Итак, решаем задачу одномерной минимизации:

минимизировать

при условии                                     

Оптимальное значение . Итак, .

Вторая итерация. Первый шаг. В точке  имеем . Активных ограничений в этой точке нет, поэтому задача определения направления спуска имеет вид:

минимизировать

при условиях

 

Оптимальным решением является вектор , а .

Второй шаг. Легко проверить, что , при котором точка  допустима, равна 0.3472. При этом активным становится ограничение . Оптимальное значение  находим в результате решения задачи:

минимизировать  

при условии                                 

Оно равно 0.3472, так что . Остальные итерации проводятся аналогично. Результаты вычислений на первых четырех итерациях метода приведены в табл. 6.5.

На рис. 6.13 показан процесс поиска оптимума. Заметим, что следующей точкой будет , а значение целевой функции в этой точке равно –
  –6.544, тогда как в оптимальной точке  значение ц.ф. равно –6.559.

Таблица 6.5

			Поиск направления                                Линейный поиск
1	0.00;–0.75	-3.375	-5.50;–3.00	1.000;–1.000	-1.000	0.4140	0.2088	0.2083;–0.5417
2	0.208;–0.541	-3.635	-4.25;–4.25	1.000;–1.000	-8.5	0.3472	0.3472	0.555;–0.889
3	0.555;–0.889	-6.346	-3.556;–3.555	1.000;–0.533	-1.663	0.0924	0.0924	0.648;–0.840
4	0.648;–0.840	-6.468	-3.088;–3.937	-0.517; 1.000	-2.340	0.0343	0.0343	0.630;–0.874

Метод возможных направлений для нелинейных ограничений-неравенств и равенств

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

Поясним этот подход на примере:

минимизировать                   (6.5.26)

при условиях

       ,

.                        (6.5.27)

Пусть  – допустимая точка и . Будем решать следующую задачу ЛП:

минимизировать                      (6.5.28)

при условиях

,                           (6.5.29)

.                        (6.5.30)

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

 , где  – достаточно малое число.

Модификация метода возможных направлений

Анализ алгоритма Зойтендейка показал, что он может не  сходиться к точке Куна-Таккера. Трудность здесь заключается в том, что длина шагов вдоль генерируемых направлений  стремится к нулю, вызывая “заедание” процесса в неоптимальной точке. Во избежание этого Топкинс и Кейнотт [4] разработали модификацию метода возможных направлений. Эта модификация гарантирует сходимость алгоритма к точке Куна-Таккера. Итак, рассмотрим задачу:

минимизировать

при условиях                 .

При заданной допустимой точке  возможное направление находят, решая следующую задачу ЛП:

минимизировать                            (6.5.31)

при условиях

,                                    (6.5.32)

,                         (6.5.33)

 .                             (6.5.34)

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

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

Дадим описание модифицированного алгоритма возможных направлений.

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

Основной этап. Первый шаг. Положить  равным оптимальному решению задачи ЛП:

минимизировать                            (6.5.35)

при условиях ,                      (6.5.36)

,                   (6.5.37)

.                             (6.5.38)

Если , то остановиться,  является точкой Куна-Таккера. В противном случае (при ) перейти ко второму шагу.

Второй шаг. Положить  равным оптимальному решению задачи:

минимизировать              (6.5.39)

при условии ,

где .  (6.5.40)

Положить , заменить  на  и перейти к первому шагу.

Пример 6.5. Рассмотрим задачу:

минимизировать

при условиях

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

Первая итерация. Первый шаг. В точке  имеем . Задача поиска направления спуска имеет вид:

минимизировать

при условиях

            

В правой части ограничений этой задачи, кроме первого, стоят значения . Заметим, что одно из ограничений ( ) повторяется дважды, следовательно, одно из ограничений можно опустить. Оптимальным решением этой задачи является вектор , при котором .

Второй шаг (линейный поиск). Решаем задачу:

минимизировать

Максимальное значение , для которого точка  допустима, определяется соотношением (6.5.40) и равно . Тогда оптимальным решением задачи (6.5.41) будет .

Таким образом, .

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

минимизировать

при условиях

Оптимальным решением этой задачи является вектор .

Второй шаг. Максимальное значение , для которого точка  допустима, равно . Легко можно проверить, что  достигает минимума на отрезке  в точке . Следовательно, . Далее этот процесс повторяется. В табл. 6.6 приведены результаты вычислений на первых пяти итерациях. Траектория движения точки,  задающей текущее решение, показана на рис. 6.15. В конце пятой итерации получена точка  со значением целевой функции –6.559. Заметим, что в оптимальной точке  значение целевой функции равно –6.613.

Таблица 6.6        

			Первый шаг                                   Второй шаг
1	0.00;–0.75	-3.375	-5.50;–3.00	0.714;-0.0357	-0.714	0.84	0.84	0.600;–0.720
2	0.600;–0.720	-5.827	-3.04; -4.32	-0.0712; –0.117	-0.288	1.562	1.562	0.489;–0.902
3	0.489;–0.902	-6.145	-3.849;–3.369	0.0957;–0.0555	-0.1816	1.564	1.564	0.6385;–0.8154
4	0.6385;–0.8154	-6.343	-5.63 ;–4.02	-0.016;–0.0433	-0.0840	1419	1.419	0.616;– 0.877
5	0.616;–0.877	-6.508	-3.29;–3.725	0.0268;–0.0132	-0.0303	1.455	1.455	0.655;–0.858