Метод наискорейшего спуска
Пусть дана следующая задача:
Найти min F=Z( 
) при условиях
Воспользуемся для решения данной задачи градиентным методом.
1.Выбирается точка 
, удовлетворяющая системе ограничений (т.е. принадлежащая области допустимых решений).
2.Введем счетчик числа неудачных испытаний: S=0.
3. Подсчитывается Z( 
) и grad Z( ).
Если grad Z( )=0, то переход к пункту 11, иначе к пункту 4.
4.Осуществляется движение по градиенту, т.е.
= + t·grad Z( ) (этой формуле соответствует n координатных неравенств):
5.Подсчитаем Z( 
)=Z(t) (при подстановке в функцию Z).
6. Определяем число t* из условия minZ(t).
7. Сравним Z( )=Z(t) и Z( ).
Если Z( )> Z( ), то испытание оказалось неудачным, переходим к п.8; если же испытание удачно, т.е. Z( 
)<Z(t), то проверяем, принадлежит ли новая точка области допустимых решений (ОДР). Если принадлежит, т.е. испытание удачное, то переходим к пункту 9, иначе к пункту 8.
8. Испытание оказалось неудачным S=S+1, проверяем, сколько неудачных испытаний произошло. Если S<M (заданное число неудачных итераций), то переходим к поиску следующей точки, для этого полагаем 
и вновь подсчитываем координаты точки 
(переход к пункту 7).
Если S ≥ M, то переходим к пункту 10.
9. Если испытание оказалось удачным, то найденную точку принимаем за начальную: = 
; Z( )=Z( ) и далее переходим к пункту 3.
10. Если S 
M, то за заданное число итераций оптимальное решение не найдено ( за конечный результат принимают в этом случае точку последней итерации).
11. Если найдено оптимальное решение задачи в точке *,
grad Z( 
*) = 0, то вычисления завершаются.
Рассмотрим пример 17:
Найти minZ= 
1. Выбираем точку (0;0) и проверим: принадлежит ли точка 
(0,0) области допустимых решений?
Да, принадлежит.
2. S=0 (введем счетчик неудачных испытаний и зададим число таких испытаний М =5).
I итерация.
3. Подсчитаем Z( )= 
и grad Z( ) ={2x1-3; 2x1-2}={-3; -2};grad Z( ) = - 5 
0, переходим к п. 4.
4. Осуществляем движение по градиенту :
= + t∙grad Z( ) 
Получаем ( -3t; -2t).
5. Подставляем в Z( ):
Z( ) = Z(t) = (-3t)2+(-2t)2 -3(-3t)-2(-2)t = 9t2+4t2+9t+4t = 13t2+13.
6. Находим t* из условия min Z(t):
∂Z/∂t = 0; 26t+13 = 0; t*= - 13/26; t* = - 0,5.
∂2Z/∂t2 = 26 > 0, то есть в точке при t* - минимум целевой функции.
7. Находим Z(t*) = 13·(-0,5)2 + 13· (-0,5) =3,25 – 6,5 = - 3,25,
Z(t*)< Z( ) (-3,25<0), то есть испытание удачное, S=0.
Определяем координаты точки = ( -3t; -2t) = (-3·(-0,5); - 2· (-0,5)); (1,5; 1).
Подсчитаем Z( ) = Z(t) = - 3,25.
Проверим: принадлежит ли точка (1,5; 1) области допустимых решений?
2·1,5 + 1≤ 5? →4<5
1,5 + 3·1≤ 4? →4,5>4
1,5≥0; 1≥0.
Как видим, (1,5; 1) не принадлежит ОДР, т.е. испытание оказалось неудачным, переходим к п. 8.
8. S=S+1; S=0+1=1. Так как S<M (1<4), то полагаем t*= t*/2 = - 0,5 / 2; t*= - 0,25, переходим к п. 7.
7. Находим Z(t*) = 13·(-0,25)2 + 13· (-0,25) =0,8125 – 3,25 =- 2,4375,
Z(t*)< Z( ) (-2,4375<0), то есть испытание удачное, S=1.
II итерация.
1. Определяем координаты точки :
( -3t; -2t) = (-3·(-0,25); -2· (-0,25)) = (0,75; 0,5);
(0,75; 0,5).
2. Проверим: принадлежит ли точка (0,75; 0,5) области допустимых решений?
2·0,75 + 0,5≤ 5? →2<5
0,75 + 3·0,5≤ 4? →2,25<4
0,75≥0; 0,5≥0
(0,75; 0,5) принадлежит ОДР, т.е. испытание оказалось удачным (S=S+0; S=1). S=1+0;
S=1. Так как S<M (1<4), определяем = 0,75; 0,5) то переходим к п. 3.
3. Z( ) = Z( ) = Z(t) = -2,4375.
III итерация.
3. Подсчитаем
gradZ( ) ={2x1-3; 2x1-2} = {2·0,75-3; 2·0,5-2} = {-1,5; -1} = - 2,5 0, переходим к п. 4.
4. Осуществляем движение по градиенту:
= + t*grad Z( ); х1=0,75+t·(-1,5); х2=0,5+t·(-1)
Получаем ( 0,75 - 1,5t; 0,5 - t).
5. Подставляем в Z( ):
Z( )=Z(t)=(0,75- 1,5t)2+(0,5- t)2 –3(0,75- 1,5t)-2(0,5 - t)= 2,25t2+t2-2,25t -t+4,5t+2t+0,5625+0,25-2,25-1=3,25t2+3,25t - 2,4375.
6. Находим t* из условия min Z(t):
∂Z/∂t = 0; 6,5t+3,25 = 0; t*=-3,25/6,25; t* = - 0,5.
∂2Z/∂t2 = 6,5 > 0, то есть в точке при t* - минимум целевой функции.
7. Находим Z(t*) = 3,25t2+3,25t - 2,4375 = 3,25·(-0,5)2 +3,25·(-0,5) - 2,4375; 3,25·0,25 +3,25(-0,5) - 2,4375 = - 0,8125 –2,4375 = -3,25,
Z(t*) < Z( ) (-3,25<-2,4375), то есть испытание удачное,
(S=S+0; S=1. S=1+0=1);
IV итерация.
1. Определяем координаты точки :
( 0,75 - 1,5t; 0,5 - t). ( 0,75 - 1,5·(-0,5); 0,5 – (-0,5)).
( 1,5; 1)
2. Проверим: принадлежит ли точка (1,5; 1) области допустимых решений?
2·1,5 + 1≤ 5? →4<5
1,5 + 3·1≤ 4? →4,5>4
1,5≥0; 1≥0
(1,5; 1) не принадлежит ОДР, т.е. испытание оказалось неудачным (S=S+1; S=1; S=1+1 S=2; S<M; 2<4).
Полагаем t*= t*/2 = - 0,5 / 2; t*= - 0,25, переходим к п. 7.
( 0,75 - 1,5t; 0,5 - t). =(0,75 – 1,5×(-0,25); 0,5 + 0,25).
(0,75 + 0,375; 0,75); (1,125; 0,75).
Проверим: принадлежит ли точка (1,125; 0,75) ОДР?
2·1,125 + 0,75≤ 5? → 3 < 5
1,125 + 3·0,75≤ 4? →3,375 < 4
1,125≥0; 0,75≥0.
Точка (1,125; 0,75) Î ОДР.
Z( )=(1,125)2+(0,75)2 –3 × 1,125 - 2× 0,75 = 1,265625 + 0,5625 – 3,375 – 1,5 = = - 3,609375.
Z( ) < Z( ) (- 3,609375 < -2,4375), то есть испытание удачное, поэтому попрежнему S=2; S<M; 2<4.
Присваиваем ( ) = (1,125; 0,75); Z( ) = Z( ) = - 3,609375.
На этом заканчивается IV итерация: (1,125; 0,75);
Z( ) = -3,609375.
Далее процесс повторяется с п. 3, нахождения gradZ( ) и т.д.
Различные алгоритмы градиентного метода (для самостоятельного изучения)
В любых алгоритмах используется движение по направлению вектора градиента, но алгоритмы отличаются по способу движения по направлению градиента.
1. Движение осуществляется до критической точки (как это осуществлялось в алгоритме наискорейшего подъёма или наискорейшего спуска). В этом случае определяется величина t* , которая задаёт глубину продвижения.
2. Движение осуществляется на заданный шаг ∆t , после чего снова определяется градиент z( 
0 ) (градиентный метод движения шагами).
В этом случае координаты новой точки определяем из условия:
= 
0 + ∆t ∙ 
z 0 , или
х1 = х10 + ∆t∙ 
( 0 );
х2 = х20 + ∆t∙ 
( 0 );
…
хn = хn0 + ∆t∙ 
( 0 ); где ∆t – заданная величина.
3. Если для выбора направления движения используются несколько z , вычисленных на предыдущих шагах, то такой метод получил название метода сопряжённых градиентов. В этом случае учитываются граничные значения нескольких z; новое значение градиента определяется как их линейная комбинация.
Индивидуальные задания 6
В задачах 1 – 12 найти решение методом наискорейшего подъёма (спуска).
1. Найти min z = (х1 -1)2 + (х2 -1)2 ; 0 (2,2)
2. Найти max z = x12 + 2x1ּx2 + 2x22 ; 0 (1,0)
3. Найти max z = x12 + 4x1ּx2 + x22 ; 0 (1,0)
4. Найти min z = x12 - 2x1ּx2 + 3x22 ; 0 (2,1)
5. Найти max z = x12 - 2x1ּx2 + 2x22 ; 0 (2,1)
6. Найти min z = 2x1 + x2 - x22 ; 0 (1,-1)
7. Найти min z = -x12 + 2x1ּx2 - 4x22 ; 0 (1,1)
8. Найти max z = 3x12 + 4x1ּx2 + 6x22 ; 0 (-1,-1)
9. Найти min z = 2x1 + 3x2 - x12 - 2x22 ; 0 (1,2)
10. Найти max z = (х1 -2) 2 + 2x22 ; 0 (2,1)
11. Найти max z = 9x1 - 8x2 – 0,5 x12 - 2x1ּx2 ; 0 (1,2)
12. Найти min z = -10x1 - x12 + 2x1ּx2 + x22; 0 (1,1)
Индивидуальные задания 7
В задачах 1 – 30 найти решение методом наискорейшего подъёма (спуска). Число неудачных испытаний М = 5. При вычислении производных через конечные разности ∆х = 0,1.
1. Найти max z = 2x1 + 3x2 - 2x22
при условиях: x1 + 4x2 ≤ 4
x1 + x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
2. Найти max z = 2x1 + 3x2 – x12 - 2x22
при условиях: x1 - x2 ≥ 0
- x1 + 2x2 ≤ 2
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
3. Найти max z = x1 + 5x2 – 2x12 + 2x1ּx2 - 2x22
при условиях: 2x1 + x2 ≥ 2,0
3x1 + x2 ≤ 4
x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
4. Найти min z = x1 - 3x1 + x12 - 2x22
при условиях: x1 - 2x2 ≤ 8
x2 ≤ 3
x1 ≥ 0; x2 ≥ 0
5. Найти max z = x12 + 4x2 - x22
при условиях: x1 + x2 ≤ 6
x1 - x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
6. Найти min z = x12 - 4x2 + x22 - 3x2
при условиях: x1 - x2 ≤ 3
x1 ≤ 5
x1 + 2x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
7. Найти min z = x12 - 2x1 + 2x22 - x2
при условиях: 2x1 - 3x2 ≤ 0
x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
8. Найти max z = x12 + x22 - 2x1 - 2x2 + 2
при условиях: x1 + x2 ≥ 1
2x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
9. Найти max z = x12 + x22 -2x1 + 2x2 + 3
при условиях: x1 + 2x2 ≥ 3
2x1 - x2 ≤ 1
x1 + x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
10. Найти min z = 2x12 + 2x22 - x1
при условиях: 2x1 + x2 ≤ 3
-x1 + 2x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
11. Найти min z = x12 + x22 - 4x1 + 1
при условиях: x1 + x2 ≤ 10
2x1 - x2 ≤ 10
x1 ≥ 0; x2 ≥ 0
12. Найти max z = 4x12 + 4x22 - 8x1 - 2 x2 + 1
при условиях: 5x1 + x2 ≥ 6
3x1 - 2x2 ≤ 1
x1 + 2x2 ≥ 3
x1 ≥ 0; x2 ≥ 0
13. Найти max z = 4x12 + x22 + 2x1
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
14. Найти max z = 9x12 + 4x22 + 2x1 – 7
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
15. Найти max z = x12 + x22 - 3x1 - 2 x2
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
16. Найти max z = 4x1 + 5x2 - 2x22
при условиях: x1 + 3x2 ≤ 6
x1 + x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
17. Найти max z = 5x1 + 3x2 – x12 - 2x22
при условиях: x1 - x2 ≥ 0
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
18. Найти max z =3 x1 + 5x2 – 2x12 + 2x1ּx2 - 2x22
при условиях: 2x1 + x2 ≥ 2
2x1 + x2 ≤ 4
x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
19. Найти min z = 3x1 - 3x2 + x12 - 2x22
при условиях: x1 - 2x2 ≤ 8
x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
20. Найти max z = 2x12 + 4x2 -3x22
при условиях: x1 + x2 ≤ 5
x1 - x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
21. Найти min z = 2x12 - 4x2 + x22 - 3x2
при условиях: x1 - x2 ≤ 3
x1 ≤ 4
x1 + 2x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
22. Найти min z = 4x12 - 2x1 + 2x22 - x2
при условиях: 2x1 - 3x2 ≤ 0
x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
23. Найти max z =3x12 + x22 - 2x1 - 2x2 + 2
при условиях: x1 + x2 ≥ 1
2x1 + x2 ≤ 6
x1 ≥ 0; x2 ≥ 0
24. Найти max z = 4x12 + x22 - 2x1 + 2x2 + 3
при условиях: x1 + 2x2 ≥ 3
2x1 - x2 ≤ 1
x1 + x2 ≤ 3
x1 ≥ 0; x2 ≥ 0
25. Найти min z = 2x12 + 2x22 -x1 +2x2
при условиях: 2x1 + x2 ≤ 4
-x1 + 2x2 ≥ 1
x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
26. Найти min z = x12 + x22 - 4x1 + 2x2+ 10
при условиях: x1 + x2 ≤ 6
2x1 - x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
27. Найти max z = 2x12 + 4x22 - 4x1 - 2 x2 + 3
при условиях: 5x1 + x2 ≥ 1
3x1 - 2x2 ≤ 2
x1 + 2x2 ≥ 3
x1 ≥ 0; x2 ≥ 0
28. Найти max z = 4x12 + x22 + 2x1+ 3x2
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
29. Найти max z = 9x12 + 4x22 + 2x1 – x2 + 5
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 6
x1 ≥ 0; x2 ≥ 0
30. Найти max z = x12 + 3x22 - 3x1 - 2 x2 + 4
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 6
x1 ≥ 0; x2 ≥ 0
Задание. Составить блок-схему метода наискорейшего подъема (спуска).