Метод Зойтендейка (стр. 3 из 4)

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

Начальный этап. Выбрать начальную точку х₁, для которой g_i(x_i)£0 приi= 1, ...,m. Положить k= 1 и перейти к основному этапу.

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

Пусть (z_k, d_k) — оптимальное решение. Если z_k=0, то остановиться; x_kявляется точкой Ф. Джона. Если z_k< 0, то перейти к шагу 2.

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

где. Положить . заменить k на k+1 и перейти к шагу 1.

ПРИМЕР. Рассмотрим задачу

Решим эту задачу методом Зойтендейка. Начнем процесс из точки .Отметим, что

Итерация 1

Поиск направления. В точке х₁= (0.00, 0.75)^Tимеем а множество индексов активных ограничений есть I={3}. При этом Задача нахождения направления имеет вид

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

Линейный поиск. Любая точка по направлению d₁== (1.00, —1.00)^T из точки x_i= (0.00, 0.75)^T может быть представлена в виде ,а соответствующее ей значение целевой функции равно . Максимальное значение, для которого остается допустимой точкой, равно == 0.414. При этом значенииl активным становится ограничение . Значение l получается изрешения следующей задачи одномерной минимизации:

минимизировать 6l²—2.5l—3.375

при условии 0£l£0.414

Оптимальное значение равно l₁= 0.2083. Следовательно, х₂= (x₁+l₁d₁) -(0.2083,0.5417)^T.

Итерация 2

Поиск направления. В точке x₂= (0.2083, 0.5417)^T имеем (х₂)=(—4,2500, —4.2500)^T Активных ограничений в этой точке нет, и поэтому задача определения направления имеет вид

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

при условиях —4.25d₁—4.25d₂—z£0,

-1<d₁<1, j=1,2.

Оптимальным решением является вектор d₂=(1, 1)^T, а z₂= -8.50.

Линейный поиск. Можно легко проверить, что максимальное l, при котором точка x₂+ld₂ допустима, равно l_max== 0.3472. При этом активным становится ограничение . Значение l₂ получается минимизацией при условии и, очевидно, равно l₂ = 0.3472, так что х_з=х₂ +l₂d₂= (0.5555, 0.8889)^T.

Итерация 3

Поиск направления. В точке x_з= (0,5555, 0.8889)^Tимеем (х_з)=(—3.5558, —3.5554)", а множество индексов активных ограничений есть I ={1}. Задача определения направления имеет вид

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

Линейный поиск. Максимальное значение l при котором точка x_з+ld_з допустима, равно l_max= 0,09245. При этом l активным становится ограничение . Значение l₃ получается минимизациейпри условии 0,09245. Оптимальным решением этой задачи являетсяl₃= 0.09245, так что = (0.6479, 0.8397)^T.

Итерация 4

Поиск, направления. Для точки х₄= (0.6479, 0.8397)^T имеем =(— 3.0878, —3.9370)^ а I={2}. Задача определения направления имеет вид

Оптимальным решением этой задачи является вектор d₄= (-0.5171, 1.0000)^T и z₄=— 2.340.

Линейный поиск. Максимальное значение К, для которого точках₄+ld₄ допустима, равно l_mах= 0.0343. При этом ограничение становится активным. Значение l₄ получается минимизацией f(x₄+ ld₄) == 3,569l²— 2.340l —6.4681 при условии и равно l₄= 0.0343. Следовательно, новой точкой является x₅==x₄+l₄d₄= (0.6302, 0.8740)^T.Значение целевой функции в этой точке равно -6.5443, т. е. сравняю со значением —6.5590 в оптимальной точке (0.658872, 0.808226)^T.

В табл. 2 приведены результаты вычислений на первых четырех итерациях метода. На рис. 7 показан процесс поиска оптимума.

Таблица 2

Рис 7

Учет нелинейных ограничений-равенств

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

Рис. 8. Нелинейные ограничения-равенства. 1—касательное направление; 2 — корректирующее движение в допустимую область.

Чтобы быть более точным, рассмотрим следующую задачу:

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

при условиях g_i(х)£0, i= 1,...,m,

h_i(х)=0, i=1, ...,i.

Пусть x_k—допустимая точка и l= {i. g_i(х_k)==0}. Решим следующую задачу линейного программирования:

Искомое направление d_k является касательным к ограничениям-равенствам и к некоторым активным нелинейным ограничениям-неравенствам. Линейный поиск вдоль d_kн последующее возвращение в допустимую область приводят в точку х_k+1, после чего процесс повторяется.

Рис. 9. Использование почти активных ограничений. 1 — оптимальное решение; 2— линии уровня целевой функции; 3—1-е ограничение; 4— 2-е ограничение.

Использование почти активных ограничений

Напомним задачу определения направления как для случая линейных, так и нелинейных ограничений-неравенств. Если заданная точка близка к границе, определяемой одним из ограничений, и если это ограничение не используется в процессе нахождения направления движения, то может случиться так, что удастся сделать только маленький шаг и мы окажемся на границе, определяемой этим ограничением. На рис. 9 в точке х активным является только первое ограничение. Однако точка х близка к границе, определяемой вторым ограничением. Если множество I в задаче определения направления задать в виде I={1}, то оптимальным будет направление d и до выхода на границу допустимой области можно сделать только маленький шаг. Если же в множество активных ограничений включить оба ограничения, т. е. положить I={1, 2), то решение задачи Р