Численные методы на основе метода штрафных функций

При этом методе задача (4.2.1) заменяется на задачу

F(X, rs)=f(X)+P(X, rs) ® min, (4.3.2)

где

P(X, rs)= ,

=max{0, }= ,

rs - так называемый параметр штрафа. Функция P(X, rs) называется штрафной функцией. К полученной задаче применяются численные методы безусловной оптимизации (нулевого, первого или второго порядков). При этом начальная точка поиска задаётся обычно вне множества допустимых решений X. На каждой s-й итерации ищется точка X*(rs) минимума вспомогательной функции F(X, rs) при заданном параметре rs с помощью одного из методов безусловной минимизации. Полученная точка X*(rs) используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании rs последовательность точек X*(rs) стремится к точке условного минимума X*.

Более подробно:

1. Задать: начальную точку X0 внутри области X; начальное значение параметра rs³0; число C>1 для уменьшения параметра штрафа; малое число e³0 для остановки алгоритма. Положить s=0.

2. Составить вспомогательную функцию

F(X, rs)=f(X)+ .

3. Найти точку X*(rs) безусловного экстремума функции F(X, rs) по X с помощью какого-либо метода (нулевого, первого или второго порядка):

F(X*(rs), rs)= F(X, rs).

При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять Xs. Вычислить P(X*(rs), rs).

4. Проверить условие окончания:

а) если P(X*(rs), rse, то процесс поиска закончить:

X*=X*(rs), f(X*)=f(X*(rs));

б) если P(X*(rs), rs)<e, то положить: rs+1=Crs, Xs+1=X*(rs), s=s+1 и перейти к шагу 2.

Обычно выбирается r0Î{0,01; 0,1; 1}, а CÎ[4, 10].

Пример I. Исследовать на условный экстремум функцию:

f(X)= ® min

3x1-2x2-5=0.

Решение. Нам потребуется вспомогательная функция F(X, rs) при различных значениях параметра rs и её градиент. Поэтому предварительно выпишем эти элементы задачи в общем виде:

F(X, rs)= + (3x1-2x2-5)2,

=4x1+3rs(3x1-2x2-5), =8x2-2rs(3x1-2x2-5),

ÑF(X, rs)=(4x1+3rs(3x1-2x2-5), 8x2-2rs(3x1-2x2-5)).

Далее действуем пошагово согласно вышеописанной схеме.

Шаг 1. Зададим: начальную точку X0=(1, -1) внутри области X; начальное значение параметра rs=0,1; число C=4 для уменьшения параметра штрафа; малое число e=0,1 для остановки алгоритма. Положить s=0.

Шаг 2. Составим вспомогательную функцию

F(X; 0,1)= +0,05×(3x1-2x2-5)2.

Шаг 3. Найдём точку X*(0,1) безусловного минимума функции F(X, 0,1) по X с помощью метода градиетного спуска:

F(X*(0,1), 0,1)= +0,05×(3x1-2x2-5)2 ® min (4.3.3)

1. Зададим X0=(1, -1), e1=0,1, e2=0,1, k0=10, найдём градиент

ÑF(X; 0,1)=(4x1+0,3×(3x1-2x2-5), 8x2-0,2×(3x1-2x2-5)).

2. Положим k=0.

3.0. Вычислим ÑF(X0; 0,1)=(4; -8).

4.0. Вычислим |ÑF(X0; 0,1)| и проверим критерий окончания: |ÑF(X0; 0,1)|= »8,9443>0,1. Переходим к шагу 5.

5.0. Проверим условие k>k0: k=0<10=k0. Переходим к шагу 6.

6.0. Зададим h0=0,1.

7.0. Вычислим X1=X0-0,1×F(X1; 0,1)=(1; -1)-0,1×(4; -8)=(0,6; -0,2).

8.0. Проверим выполнение условия F(X1; 0,1)-F(X0; 0,1)<0. Так как F(X1; 0,1)=1,272, F(X0; 0,1)=7, то условие выполняется. Переходим к шагу 9.

9.0. Проверим условия r(X1, X0)<0,1 и |F(X1; 0,1)-F(X0; 0,1)|<0,1. Второе условие не выполняется: |F(X1; 0,1)-F(X0; 0,1)|=4,728>0,1. Полагаем k=1 и переходим к шагу 3.

3.1. Вычислим ÑF(X1; 0,1)=(1,56; -1,04).

4.1. Вычислим |ÑF(X1; 0,1)| и проверим критерий окончания: |ÑF(X1; 0,1)|= »1,8749>0,1. Переходим к шагу 5.

5.1. Проверим условие k>k0: k=1<10=k0. Переходим к шагу 6.

6.1. Зададим h1=0,1.

7.1. Вычислим X2:

X2=X1-0,1×ÑF(X1; 0,1)=(0,6; -0,2)-0,1×(1,56; -1,04)=(0,444; -0,096).

8.1. Проверим выполнение условия F(X2; 0,1)-F(X1; 0,1)<0. Так как F(X2; 0,1)=1,0353, F(X1; 0,1)=1,272, то условие выполняется: F(X2; 0,1)-F(X1; 0,1)=1,0353-1,272=-0,2367. Переходим к шагу 9.

9.1. Проверим условия r(X2, X1)<0,1 и |F(X2; 0,1)-F(X1; 0,1)|<0,1. Второе условие не выполняется: |F(X2; 0,1)-F(X1; 0,1)|=0,2367>0,1. Полагаем k=2 и переходим к шагу 3.

3.2. Вычислим ÑF(X2; 0,1)=(0,7332; -0,0728).

4.2. Вычислим |ÑF(X2; 0,1)| и проверим критерий окончания: |ÑF(X2; 0,1)|= =0,7368>0,1. Переходим к шагу 5.

5.2. Проверим условие k>k0: k=2<10=k0. Переходим к шагу 6.

6.2. Зададим h2=0,1.

7.2. Вычислим X3:

X3=X2-0,1×ÑF(X2; 0,1)=(0,444; -0,096)-0,1×(0,7332; -0,0728)=(0,3707;-0,0887).

8.2. Проверим выполнение условия F(X3; 0,1)-F(X2; 0,1)<0. Так как F(X3; 0,1)=0,9947, F(X2; 0,1)=1,0353, то условие выполняется: F(X3; 0,1)-F(X2; 0,1)=-0,0406. Переходим к шагу 9.

9.2. Проверим условия r(X3, X2)<0,1 и |F(X3; 0,1)-F(X2; 0,1)|<0,1. Оба условия выполняются:

r(X3, X2)= =0,0737<0,1,

|F(X3; 0,1)-F(X2; 0,1)|=0,0406<0,1.

Это значит, X*(0,1)=(0,3707; -0,0887) - решение задачи (4.3.3).

Вычислим P(X*(0,1), 0,1)=0,05×(3×0,3707-2×(-0,0887)-5)2=0,6941.

Шаг 4. Проверить условие окончания:

а) если P(X*(rs), rse, то процесс поиска закончить:

X*=X*(rs), f(X*)=f(X*(rs));

б) если P(X*(rs), rs)>e, то положить: rs+1=Crs, Xs+1=X*(rs), s=s+1 и перейти к шагу 2.

Имеем P(X*(0,1), 0,1)=0,6941>0,1. Поэтому полагаем r1=C×r0=4×0,1=0,4, X0=X*(0,1)=(0,3707; -0,0887), и перейти к шагу 2, то есть решаем задачу

F(X*(0,4), 0,4)= +0,2×(3x1-2x2-5)2 ® min (4.3.4)

Ниже приводим только результаты пунктов алгоритма без комментариев:

1. X0=(0,3707; -0,0887), e1=0,1, e2=0,1, k0=10,

ÑF(X; 0,4)=(4x1+1,2×(3x1-2x2-5), 8x2-0,8×(3x1-2x2-5)).

2. k=0.

3.0. ÑF(X0; 0,4)=(-2,9698; 2,2588).

4.0. |ÑF(X0; 0,4)|»3,7312>0,1.

5.0. k>k0? k=0<10=k0. ® 6.

6.0. h0=0,1.

7.0. X1=(0,6677; -0,3146).

8.0. F(X1; 0,1)-F(X0; 0,1)=-0,6511<0. ® 9.

9.0. |F(X1; 0,1)-F(X0; 0,1)|= 0,6511>0,1. k=1 и ® 3.

3.1. ÑF(X1; 0,1)=(-0,1704; -0,6226).

4.1. |ÑF(X1; 0,1)|»0,6456>0,1. ® 5.

5.1. k>k0? k=1<10=k0. ® 6.

6.1. h1=0,1.

7.1. X2=(0,6847; -0,2523).

8.1. F(X2; 0,1)-F(X1; 0,1)=-0,0245. ® 9.

9.1. r(X2, X1)=0,0646<0,1 и |F(X2; 0,1)-F(X1; 0,1)|=0,0245<0,1.

Значит, X*(0,4)=(0,6847; -0,2523) - решение задачи (4.3.4).

Вычислим P(X*(0,4), 0,4)=1,1212.

Шаг 4. Проверим условие окончания: P(X*(0,4), 0,4)=1,1212>0,1. Поэтому полагаем r2=C×r1=4×0,4=1,6, X0=X*(0,4)=(0,6847; -0,2523), и переходим к шагу 2, то есть решаем задачу

F(X*(1,6), 1,6)= +0,8×(3x1-2x2-5)2 ® min (4.3.5)

Ниже в таблице приведены результаты вычислений. В таблице применяются следующие сокращённые обозначения: ÑFkF(Xk; 1,6), Fk=F(Xk; 1,6), DFk=F(Xk+1; 1,6)-F(Xk; 1,6), rk+1=r(Xk+1, Xk).

k Xk ÑFk Fk| Xk+1 Fk+1 DFk rk+1 Pk+1
(0,6847; -0,2523) (-8,9794; 5,9738) 10,6864 (1,5826; -0,8317) 9,3696 9,3696>0 h0=0,05  
  (1,1337; -0,542) 3,9576 -2,0026 0,5343  
(1,1337; -0,542) (2,0633; -2,6883) 3,3888 (1,0305; -0,4076) 3,7446 -0,2131 0,1694 1,1212
(1,0305; -0,4076) (-1,1258; 0,2378) 1,1507 (1,087; -0,4195) 3,7151 -0,0296 0,0575 0,9562

 

Таким образом, X*(1,6)=(1,087; -0,4195) - решение задачи (4.3.5). При этом P(X*(1,6), 1,6)=0,9562>0,1. Полагаем r3=C×r2=4×1,6=6,4, X0=X*(1,6)= =(1,087; -0,4195), и переходим к шагу 2 - решаем задачу

F(X*(6,4), 6,4)= +3,2×(3x1-2x2-5)2 ® min. (4.3.6)

Решение получается за одну итерацию: X*(6,4)=(1,0856; -0,3957). При этом P(X*(6,4), 6,4)=0,648>0,1.

Шаг 4. Так как P(X*(6,4), 6,4)=0,648>0,1, то полагаем r4=C×r3=4×6,4=25,4, X0=X*(6,4)=(1,0856; -0,3957), и переходим к шагу 2 - решаем задачу

F(X*(6,4), 6,4)= +12,8×(3x1-2x2-5)2 ® min (4.3.7)

k Xk ÑFk Fk| Xk+1 Fk+1 DFk rk+1 Pk+1
(1,0856; -0,3957) (-68,7558; 45,5666) 82,4844 (4,5234; -2,674) 2549,104 2534, 525>0 h0=0,025  
  (2,8045; -1,5349) 536,1644 548, 5852>0 h0=0,01  
(1,7732; -0,8514) 61,5308 46,9516>0 h0=0,005  
(1,7294; -0,6235) 9,3079 -5,2713 0,4124  
(1,4294; -0,6235) (42,821; -32,3902) 56,9327 (1,1953; -0,4616) 6,7956 -2,5122 0,2847  
(1,1953; -0,4616) (-32,9199; 21,4413) 39,2868 (1,3599; -0,5688) 5,5973 -1,1971 0,1964  
(1,3599; -0,5688) (22,1282; -15,6762) 27,1183 (1,2493; -0,4904) 5,0261 -0,5711 0,1356  
(1,2493; -0,4904) (-15,8386; 9,9674) 18,7139 (1,3285; -0,5402) 4,7529 -0,2727 0,0936  
(1,3285; -0,5402) (10,3751; -7,6957) 12,9177 (1,2766; -0,5017) 4,6221 -0,1306 0,0646  
(1,2799; -0,5017) (-7,7038; 4,5266) 8,9353 (1,3151; -0,5243) 4,5592 -0,0631 0,0447 0,3561
(1,3151; -0,5243) (4,7919; -3,8821) 6,1671 (1,2911; -0,5049) 4,5284 -0,0307 0,0308 0,0005

 

На последних двух шагах получаем r(Xk+1, Xk)<0,1 и |f(Xk+1)-f(Xk)|<0,1, а в последнем шаге - P(X*(25,4), 25,4)=0,0005<0,1. Процесс поиска закончен.

Ответ: точкой условного локального минимума является точка X*=(1,2911; -0,5049), f(X*)=4,5284 - условный локальный минимум.

 






©2015-2017 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.


ТОП 5 активных страниц!

...