Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



При этом методе задача (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 - условный локальный минимум.

 


Метод проекции градиента.

Метод применяется в задачах поиска условного экстремума с ограничениями типа равенство и неравенств. Мы ограничимся рассмотрением поиска экстремума с ограничениями типа равенства.

Требуется решить задачу

(4.4.1)

где функции f(X), ji(X) - выпуклые дифференцируемые функции.

Поиск решения состоит в построении последовательности точек {Xk}, вычисляемых по правилу

Xk+1=Xk+dXk (k=0, 1, …), (4.4.2)

где dXk - вектор, вычисляемый для каждого значения k из условия проекции вектора -Ñf(Xk), k=0, 1, …, на аппроксимирующую плоскость, задаваемую уравнением

AkdXk =Tk, (4.4.3)

которая аппроксимирует в точке Xk (k=0, 1, …) поверхность П, задаваемую уравнениями ji(X)=0 (i=1, …, m). Здесь Ak - матрица

A(X)= ,

вычисленная в точке X=Xk, Tk=-(j1(Xk), …, jm(Xk))T.

Вектор dXk определяется по формуле

dXk=d1Xk+d2Xk (4.4.4)

где

d1Xk=-hk[E- (Ak ) Akf(Xk)=-hkDXk (4.4.5)

- градиентная составляющая приращения, d2Xk= (Ak ) Tk - компенсационная составляющая приращения.

Величина hk шага может выбираться как из условия убывания функции f(X) при переходе из точки Xk в точку Xk-hk[E- (Ak ) Akf(Xk), так и из условия

y(hk)=f(Xk-hk[E- (Ak ) Akf(Xk))® (4.4.6)

Задача (4.4.6) может решаться либо с использованием необходимых и достаточных условий минимума, либо с использованием численных методов.

Расчёт заканчивается в точке Xk, в которой |DXke, |d2Xke, где e - заданное число. В полученной точке обязательна проверка выполнения достаточных условий минимума функции в исходной задаче (4.4.1). Если будет выполнено точное равенство d1Xk=-hk[E- (Ak ) Akf(Xk)= , то это означает, что выполнены точные необходимые условия экстремума. При этом вектор Lk множителей Лагранжа определяется по формуле

Lk=-(Ak ) AkÑf(Xk) (4.4.7)

Если в задаче (4.4.1) ограничения линейны, то матрица A постоянна. При этом начальная точка X0 попадает в ОДР за одну итерацию. В дальнейшем требуется вычисление только d1Xk.

Таким образом, алгоритм решения задачи - следующий:

1. Задать X0, e³0, k0 - число итераций.

2. Найти A(X), Ñf(X), DX=-[E- (A ) Af(X), d2X=AT(AAT) T(X) где T(X)=-(j1(Xk), …, jm(Xk))T.

3. Положить k=0.

4. Проверить выполнение условия k³k0:

а) если неравенство выполнено, то расчёт окончен. Вычислить Lk=-(Ak ) AkÑf(Xk), проверить необходимое условие минимума, оценить результаты;

б) если неравенство не выполнено, то перейти к шагу 5.

5. Вычислить матрицу Ak=A(Xk).

6. Вычислить d2Xk.

7. Вычислить |d2Xk|.

8. Вычислить DXk.

9. Вычислить |DXk|.

10. Проверить выполнение условий |DXke и |d2Xke:

а) если условия выполняются, то расчёт окончен. Вычислить Lk и проверить достаточные условия минимума;

б) если |DXk|>e, |d2Xke, то положить d2Xk=0 и перейти к шагу 11;

в) если |DXke и |d2Xk|>e, то положить DXk=0 и перейти к шагу 13;

г) если |DXk|>e, |d2Xk|>e, то перейти к шагу 11.

11. Получить выражение для точки Xk+ DXk.

12. Определить из условия f(Xk+hkDXk .

13. Вычислить Xk+1=Xk+ DXk+d2Xk. Положить k=k+1 и перейти к шагу 4.

Если ограничения в задаче линейны, то при k³1 на шаге 4 переходим к шагу 8. При этом на шаге 10 полагаем |d2Xk|=0.

Пример II. Найти условный экстремум функции:

f(X)= ® min

3x1-2x2-5=0.

Решение. 1. Задаём X0=(1, -1) e=0,1, k0=10 - число итераций.

2. Найдём A(X)= =(3; -2), Ñf(X)=(4x1, 8x2)Т,

DX=-[E- (A ) Af(X)=- =

=- =- =

=- =- = ,

то есть DX» ,

T(X)=-j1(Xk)=-3x1+2x2+5,

d2X=AT(AAT) T(X)= (-3x1+2x2+5)=

= (-3x1+2x2+5)= = ,

то есть d2X» .

3. Полагаем k=0.

4.0. Проверим выполнение условия k³k0: k=0<10=k0 - неравенство не выполнено. Поэтому идём к пункту 5.

5.0. Вычисляем матрицу A0=A(X0)=(3; -2).

6.0. Вычисляем d2X0= = .

7.0. Вычисляем |d2X0|= =0.

8.0. Вычисляем DX0= » .

9.0. Вычисляем |DX0|= »0,832.

10.0. Проверяем выполнение условий |DX0|£0,1 и |d2X0|£0,1. Имеем |DX0|>0,1 и |d2X0|£0,1. Поэтому полагаем d2X0=0 и переходим к шагу 11.

11.0. Получим выражение для точки X0+h0DX0:

X0+h0DX0=(1; -1)+h0(2,462; 3,692)=(1+2,462h0; -1+3,692h0).

12.0. Определяем h0 из условия f(X0+h0DX0 . Имеем

f(X0+h0DX0)=2×(1+2,462h0)2+4×(-1+3,692h0)2=

=2×(1+4,924h0+6,061 )+4×(1-7,384h0+13,631 )=

=66,646 -19,688h0+6.

Так как f(X0+h0DX0) - квадратный трёхчлен относительно h0 с положительным коэффициентом при , то минимум f(X0+h0DX0) достигается при h0, удовлетворяющем уравнению (X0+h0DX0)=0. Имеем

(X0+h0DX0)=133,292h0-19,688=0 Û h0»0,15.

13.0. Вычисляем X1:

X1=X0+h0DX0+d2X0=X0+h0DX0=(1+2,462×0,15; -1+3,692×0,15)=(1,3693; -0,4462).

Положим k=1 и перейдём к шагу 4.

4.1. Проверим выполнение условия k³k0: k=1<10=k0 - неравенство не выполнено. Поэтому идём к пункту 5.

5.1. Вычисляем матрицу A1=A(X1)=(3; -2).

6.1. Вычисляем d2X1= = .

7.1. Вычисляем |d2X1|= »0.

8.1. Вычисляем DX1= » .

9.1. Вычисляем |DX1|= »0,0677.

10.1. Проверяем выполнение условий |DX1|£0,1 и |d2X1|£0,1. Имеем |DX1|£0,1 и |d2X1|£0,1. Поэтому расчёт окончен. Вычисляем L1 для проверки необходимых и достаточных условий экстремума в найденной точке X1=(1,3693; -0,4462):

L1=-(A1 ) A1Ñf(X1)= =-1,8135.

Выпишем необходимые условия экстремума с учётом функции Лагранжа: L(X, L)= +l1(3x1-2x2-5):

=4x1+3l1, =8x2-2l1,

Û (4.4.6)

Будем считать, что необходимые условия выполнены, если уравнения системы (4.4.6) выполняются с точностью до 0,1. Подставляем X1=(1,3693; -0,4462) и l1=-1,8135 в систему (4.4.6):

Следовательно, необходимые условия экстремума в точке X1 выполнены. Проверим достаточные условия экстремума. Имеем

=4, =8, = =0, d2L=4d +8d >0,

то есть достаточное условие минимума выполняется. Таким образом,

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


 

Приложения

Приложение 1. Варианты индивидуальных заданий

Задания 1 - 5решить с использованием необходимых и достаточных условий

Задание НП-1

Дана функция y=f(x) (таблица). Найти:

а) Безусловные экстремумы функции y=f(x).

б) Условные экстремумы функции y=f(x) на отрезке [a, b]:

Вар-т Функция [a, b]   Вариант Функция [a, b]
y=ln(x2-2x+2) [0; 3]   y= [1; 3]
y=3x/(x2+1) [0; 5]   y=(x5-8)/x4 [-3; -1]
y=(2x-1)/(x-1)2 [-1/2; 0]   y=(e2x+1)e-x [-1; 2]
y=(x+2)e1-x [-2; 2]   y=xlnx [1/e2; 1]
y=ln(x2-2x+4) [-1; 3/2]   y=x3ex+1 [-4; 0]
y=x3/(x2-x+1) [-1; 1]   y=x2-2x+2/(x-1) [-1; 3]
y=((x+1)/x)3 [1; 2]   y=(x+1) [-4/5; 3]
y= [-2; 2]   y= [-3; 3]
y=4- [0; 1]   y=(lnx)/x [1; 4]
y=(x3+4)/x2 [1; 2]   y=3x4-16x3+2 [-3; 1]
y=xex [-2; 0]   y=x5-5x4+5x3+1 [-1; 2]
y=(x-2)ex [-2; 1]   y=(3-x)e-x [0; 5]
y=(x-1)e-x [0; 3]   y= +cosx [0; p/2]
y=x/(9-x2) [-2; 2]   y=108x-x4 [-1; 4]
y=(1+lnx)/x [1/e; e]   y=x4/4-6x3 [14; 20]

 

Задание НП-2

 

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

а) f(x, y)=ax2+2xy+by2-2x-3y:

№ в-та a b № в-та a b № в-та a b № в-та a b

 


б) f(x, y)=ax3+ax2y+bx+ y3+cy:

№ в-та a b c № в-та a b c

 

в) f(X)=a +b +c -2x1x2-x1+3x2:

№ в-та a b c № в-та a b c

г) f(X)=a +b +c +3x1x3-4x1+2x3:

№ в-та a b c № в-та a b c
-2 -4
-9 -2
-3 -2
-3 -4
-2 -2
-2 -2
-2 -4
-6 -2
-2 -2
-2 -4

 

д) f(X)=a +b +c -x2x3+2x2-3x3:


Эта страница нарушает авторские права

allrefrs.ru - 2017 год. Все права принадлежат их авторам!