Алгоритм метода Зойтендейка случай нелинейных ограничений-неравенств. Начальный этап. Выбрать начальную точку х1, для которой gixi0 при i 1, m. Положить k 1 и перейти к основному этапу.
Основной этап. Шаг 1. Положить и решить следующую задачу Пусть zk, dk оптимальное решение. Если zk0, то остановиться xk является точкой Ф. Джона. Если zk 0, то перейти к шагу 2. Шаг 2. Взять в качестве оптимальное решение следующей задачи одномерной минимизации где. Положить . заменить k на k1 и перейти к шагу 1. ПРИМЕР. Рассмотрим задачу Решим эту задачу методом Зойтендейка.
Начнем процесс из точки. Отметим, что Итерация 1 Поиск направления. В точке х1 0.00, 0.75T имеем а множество индексов активных ограничений есть I 3. При этом Задача нахождения направления имеет вид Можно легко проверить, используя симплекс-метод, что оптимальным решением этой задачи является вектор Линейный поиск. Любая точка по направлению d1 1.00, 1.00T из точки xi 0.00, 0.75T может быть представлена в виде, а соответствующее ей значение целевой функции равно. Максимальное значение, для которого остается допустимой точкой, равно 0.414. При этом значении l активным становится ограничение. Значение l получается из решения следующей задачи одномерной минимизации минимизировать 6l2 2.5l 3.375 при условии 0l0.414 Оптимальное значение равно l1 0.2083. Следовательно, х2 x1 l1d1 -0.2083,0.5417T. Итерация 2 Поиск направления.
В точке x2 0.2083, 0.5417T имеем х2 4,2500, 4.2500T Активных ограничений в этой точке нет, и поэтому задача определения направления имеет вид минимизировать z при условиях 4.25d1 4.25d2 z0, -1 d1 1, j1,2. Оптимальным решением является вектор d21, 1T, а z2 -8.50. Линейный поиск.
Можно легко проверить, что максимальное l, при котором точка x2ld2 допустима, равно lmax 0.3472. При этом активным становится ограничение. Значение l2 получается минимизацией при условии и, очевидно, равно l2 0.3472, так что хз х2 l2d2 0.5555, 0.8889T. Итерация 3 Поиск направления.
В точке xз 0,5555, 0.8889T имеем хз 3.5558, 3.5554, а множество индексов активных ограничений есть I 1. Задача определения направления имеет вид Оптимальным решением является вектор. Линейный поиск. Максимальное значение l при котором точка xз ldз допустима, равно lmax 0,09245. При этом l активным становится ограничение. Значение l3 получается минимизацией при условии 0,09245. Оптимальным решением этой задачи является l3 0.09245, так что 0.6479, 0.8397T. Итерация 4 Поиск, направления.
Для точки х4 0.6479, 0.8397T имеем 3.0878, 3.9370 а I2. Задача определения направления имеет вид Оптимальным решением этой задачи является вектор d4 -0.5171, 1.0000T и z4 2.340. Линейный поиск. Максимальное значение К, для которого точка х4 ld4 допустима, равно lmах 0.0343. При этом ограничение становится активным. Значение l4 получается минимизацией fx4 ld4 3,569l2 2.340l 6.4681 при условии и равно l4 0.0343. Следовательно, новой точкой является x5x4 l4d4 0.6302, 0.8740T. Значение целевой функции в этой точке равно -6.5443, т. е. сравняю со значением 6.5590 в оптимальной точке 0.658872, 0.808226T . В табл. 2 приведены результаты вычислений на первых четырех итерациях метода.
На рис. 7 показан процесс поиска оптимума. Таблица 2 Рис 7