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

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

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

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

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

ТЕОРЕМА. Рассмотрим задачу минимизации f(х) при условиях g_i (х)£0, i=1, ...,m.. Пусть х—допустимая точка, а I—множество индексов активных в этой точке ограни­чений, т. е.                        . Предположим, кроме того, что функции f и g_i для                дифференцируемы в х, а функции g_i для             непрерывны в этой точке. Если                                                при            , то вектор d является возможным на­правлением спуска.

Рис. 6. Совокупность возможных направлений спуска в задаче с нелиней­ными ограничениями. 1— 1-е ограничение; 2—3-е ограничение; 3—4-е ограни­чение; 4— 2-е ограничение; 5— возможные направления спуска; 6— линии уровня целевой функции.

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

где              при            . Так как              , то                                 при достаточно малых       . Следовательно,                  при i = 1, . . .,m, т.е. точка             допустимая для достаточно малых положительных значений  . Аналогично из                       следует, что для достаточно малых  > 0 имеем                                                          . Следовательно, вектор и является возможным направлением спуска.

На рис. 6 показана совокупность возможных направлений спуска в точке х. Вектор d, удовлетворяющий равенству                         , является касательным к множеству                             в точке х. Поскольку функции g_i нелинейны, движение вдоль такого вектора d  может привести в недопустимую точку, что вы­нуждает нас требовать выполнения строгого неравенства              .

Пусть (z, d)—оптимальное решение этой задачи линейного про­граммирования. Если z<0, то очевидно, что d—возможное направление спуска. Если же z = 0, то, как показано ниже, те­кущая точка является точкой Ф. Джона.

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

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

Это и есть условие Ф. Джона.

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

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

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

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

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

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

Итерация 1

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

Линейный поиск. Любая точка по направлению 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

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

Линейный поиск. Максимальное значение 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