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 |
