Алгоритм безусловной векторной оптимизации

Предлагаемый ниже алгоритм является развитием градиентных методов и метода возможных направлений Зойтендейка. Так задача ZS(y) для однокритериальной задачи безусловной оптимизации в качестве направления S вырабатывает S= в однокритериальной задаче возможное подходящее направление.

Алгоритм.

0-ой шаг. В качестве х₀ задаем произвольную точку из E_n.

………

k - ый шаг (k= 0, 1, 2, …).

Полагаем x _k+1= x _k + l s _ks _k , (3.50)

где значения s _k , s _k получены из решения задачи ZS(x _k ).

l_k выбирается следующим образом:

1. Выбираем некоторое l (одно на всех итерациях) и полагаем l_k = l.

2. Вычисляем j _i (x) =j _i (x _k + l s _ks _k), iÎ M.

3. Если для всех j _i (x) - j _i (x_k)£ - e l _k s _k ², eÎ (0, 1), (3.51)

то l _k является искомым, в противном случае полагаем l_k =a l_k ,

где aÎ (0, 1) и переходим к шагу 2.

Последовательности {x _k }, { s _k }, { s _k } обрываем, если для некоторого k в точке x_k оказалось s _k=0, в этом случае при выполнении достаточных условий точка x_k являются оптимумом по Слейтеру.

Пример. 3.1.

Для задачи

j₁(x)= x₁² + x₂² ® min,

j₂(x)= x₁² + (x₂ -4)² ® min,

j₃(x)= (x₁ -4)² + x₂² ® min,

j₄(x)= (x₁ -4)² + (x₂ -4)² ® min.

проверить на оптимальность точку y = (2, 2)^T.

Решение. В этой задаче множество I=Æ, поэтому задача ZS(y) примет вид:

Задача ZS(y).

max s,

< j_i'(y), s> + s £ 0, iÎ [1..4], (3.52)

-1 £ s(j) £ 1, j Î [1..2],

s ³ 0.

Подставляя в (2.9) значения градиентов j _i(y) в точке у = (2, 2), получим

max s,

4s(1) + 4s(2) + s £ 0,

4s(1) - 4s(2) + s £ 0,

-4s(1) + 4s(2) + s £ 0,

-4s(1) - 4s(2) + s £ 0,

-1 £ s(1) £ 1,

-1 £ s(2) £ 1.

Проведя замену переменных s(j) = s'(j) -1, j Î [1..2], получим max s,

4s'(1) + 4s'(2)+ s £ 8,

4s'(1) - 4s'(2)+ s £ 0,

-4s'(1) + 4s'(2)+ s £ 0,

-4s'(1) - 4s'(2)+ s £ -8,

s'(1) £ 2,

s'(2) £ 2,

s'(1) ³ 0,

s'(2) ³ 0,

s ³ 0.

Решая эту задачу симплекс-методом, получаем, что максимальное значение s =0. Это означает, что точка y = (2, 2) оптимальна по Слейтеру