Eng | Rus | Ukr
Исследование операций
04.10.2008

<< prev | ^up^ | next >>

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004