Метод наискорейшего спуска

Пусть дана следующая задача:

Найти 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( ) ={2x₁-3; 2x₁-2}={-3; -2};grad Z( ) = - 5 0, переходим к п. 4.

4. Осуществляем движение по градиенту :

= + t∙grad Z( )

Получаем ( -3t; -2t).

5. Подставляем в Z( ):

Z( ) = Z(t) = (-3t)²+(-2t)² -3(-3t)-2(-2)t = 9t²+4t²+9t+4t = 13t²+13.

6. Находим t* из условия min Z(t):

∂Z/∂t = 0; 26t+13 = 0; t*= - 13/26; t* = - 0,5.

∂²Z/∂t² = 26 > 0, то есть в точке при t* - минимум целевой функции.

7. Находим Z(t*) = 13·(-0,5)² + 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)² + 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( ) ={2x₁-3; 2x₁-2} = {2·0,75-3; 2·0,5-2} = {-1,5; -1} = - 2,5 0, переходим к п. 4.

4. Осуществляем движение по градиенту:

= + t*grad Z( ); х₁=0,75+t·(-1,5); х₂=0,5+t·(-1)

Получаем ( 0,75 - 1,5t; 0,5 - t).

5. Подставляем в Z( ):

Z( )=Z(t)=(0,75- 1,5t)²+(0,5- t)² –3(0,75- 1,5t)-2(0,5 - t)= 2,25t²+t²-2,25t -t+4,5t+2t+0,5625+0,25-2,25-1=3,25t²+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.

∂²Z/∂t² = 6,5 > 0, то есть в точке при t* - минимум целевой функции.

7. Находим Z(t*) = 3,25t²+3,25t - 2,4375 = 3,25·(-0,5)² +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)²+(0,75)² –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( ₀ ) (градиентный метод движения шагами).

В этом случае координаты новой точки определяем из условия:

= ₀ + ∆t ∙ z ₀ , или

х₁ = х₁⁰ + ∆t∙ ( ₀ );

х₂ = х₂⁰ + ∆t∙ ( ₀ );

…

х_n = х_n⁰ + ∆t∙ ( ₀ ); где ∆t – заданная величина.

3. Если для выбора направления движения используются несколько z , вычисленных на предыдущих шагах, то такой метод получил название метода сопряжённых градиентов. В этом случае учитываются граничные значения нескольких z; новое значение градиента определяется как их линейная комбинация.

Индивидуальные задания 6

В задачах 1 – 12 найти решение методом наискорейшего подъёма (спуска).

1. Найти min z = (х₁ -1)² + (х₂ -1)² ; ₀ (2,2)

2. Найти max z = x₁² + 2x₁ּx₂ + 2x₂² ; ₀ (1,0)

3. Найти max z = x₁² + 4x₁ּx₂ + x₂² ; ₀ (1,0)

4. Найти min z = x₁² - 2x₁ּx₂ + 3x₂² ; ₀ (2,1)

5. Найти max z = x₁² - 2x₁ּx₂ + 2x₂² ; ₀ (2,1)

6. Найти min z = 2x₁ + x₂ - x₂² ; ₀ (1,-1)

7. Найти min z = -x₁² + 2x₁ּx₂ - 4x₂² ; ₀ (1,1)

8. Найти max z = 3x₁² + 4x₁ּx₂ + 6x₂² ; ₀ (-1,-1)

9. Найти min z = 2x₁ + 3x₂ - x₁² - 2x₂² ; ₀ (1,2)

10. Найти max z = (х₁ -2) ² + 2x₂² ; ₀ (2,1)

11. Найти max z = 9x₁ - 8x₂ – 0,5 x₁² - 2x₁ּx₂ ; ₀ (1,2)

12. Найти min z = -10x₁ - x₁² + 2x₁ּx₂ + x₂²; ₀ (1,1)

Индивидуальные задания 7

В задачах 1 – 30 найти решение методом наискорейшего подъёма (спуска). Число неудачных испытаний М = 5. При вычислении производных через конечные разности ∆х = 0,1.

1. Найти max z = 2x₁ + 3x₂ - 2x₂²

при условиях: x₁ + 4x₂ ≤ 4

x₁ + x₂ ≤ 2

x₁ ≥ 0; x₂ ≥ 0

2. Найти max z = 2x₁ + 3x₂ – x₁² - 2x₂²

при условиях: x₁ - x₂ ≥ 0

- x₁ + 2x₂ ≤ 2

x₁ + x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

3. Найти max z = x₁ + 5x₂ – 2x₁² + 2x₁ּx₂ - 2x₂²

при условиях: 2x₁ + x₂ ≥ 2,0

3x₁ + x₂ ≤ 4

x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

4. Найти min z = x₁ - 3x₁ + x₁² - 2x₂²

при условиях: x₁ - 2x₂ ≤ 8

x₂ ≤ 3

x₁ ≥ 0; x₂ ≥ 0

5. Найти max z = x₁² + 4x₂ - x₂²

при условиях: x₁ + x₂ ≤ 6

x₁ - x₂ ≤ 1

x₁ ≥ 0; x₂ ≥ 0

6. Найти min z = x₁² - 4x₂ + x₂² - 3x₂

при условиях: x₁ - x₂ ≤ 3

x₁ ≤ 5

x₁ + 2x₂ ≥ 1

x₁ ≥ 0; x₂ ≥ 0

7. Найти min z = x₁² - 2x₁ + 2x₂² - x₂

при условиях: 2x₁ - 3x₂ ≤ 0

x₂ ≤ 5

x₁ ≥ 0; x₂ ≥ 0

8. Найти max z = x₁² + x₂² - 2x₁ - 2x₂ + 2

при условиях: x₁ + x₂ ≥ 1

2x₁ + x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

9. Найти max z = x₁² + x₂² -2x₁ + 2x₂ + 3

при условиях: x₁ + 2x₂ ≥ 3

2x₁ - x₂ ≤ 1

x₁ + x₂ ≤ 2

x₁ ≥ 0; x₂ ≥ 0

10. Найти min z = 2x₁² + 2x₂² - x₁

при условиях: 2x₁ + x₂ ≤ 3

-x₁ + 2x₂ ≥ 1

x₁ ≥ 0; x₂ ≥ 0

11. Найти min z = x₁² + x₂² - 4x₁ + 1

при условиях: x₁ + x₂ ≤ 10

2x₁ - x₂ ≤ 10

x₁ ≥ 0; x₂ ≥ 0

12. Найти max z = 4x₁² + 4x₂² - 8x₁ - 2 x₂ + 1

при условиях: 5x₁ + x₂ ≥ 6

3x₁ - 2x₂ ≤ 1

x₁ + 2x₂ ≥ 3

x₁ ≥ 0; x₂ ≥ 0

13. Найти max z = 4x₁² + x₂² + 2x₁

при условиях: x₁ - x₂ ≥ 0

x₁ + x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

14. Найти max z = 9x₁² + 4x₂² + 2x₁ – 7

при условиях: x₁ - x₂ ≥ 0

x₁ + x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

15. Найти max z = x₁² + x₂² - 3x₁ - 2 x₂

при условиях: x₁ - x₂ ≥ 0

x₁ + x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

16. Найти max z = 4x₁ + 5x₂ - 2x₂²

при условиях: x₁ + 3x₂ ≤ 6

x₁ + x₂ ≤ 2

x₁ ≥ 0; x₂ ≥ 0

17. Найти max z = 5x₁ + 3x₂ – x₁² - 2x₂²

при условиях: x₁ - x₂ ≥ 0

x₁ + 2x₂ ≤ 6

-x₁ + x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

18. Найти max z =3 x₁ + 5x₂ – 2x₁² + 2x₁ּx₂ - 2x₂²

при условиях: 2x₁ + x₂ ≥ 2

2x₁ + x₂ ≤ 4

x₂ ≤ 5

x₁ ≥ 0; x₂ ≥ 0

19. Найти min z = 3x₁ - 3x₂ + x₁² - 2x₂²

при условиях: x₁ - 2x₂ ≤ 8

x₂ ≤ 4

x₁ ≥ 0; x₂ ≥ 0

20. Найти max z = 2x₁² + 4x₂ -3x₂²

при условиях: x₁ + x₂ ≤ 5

x₁ - x₂ ≤ 1

x₁ ≥ 0; x₂ ≥ 0

21. Найти min z = 2x₁² - 4x₂ + x₂² - 3x₂

при условиях: x₁ - x₂ ≤ 3

x₁ ≤ 4

x₁ + 2x₂ ≥ 1

x₁ ≥ 0; x₂ ≥ 0

22. Найти min z = 4x₁² - 2x₁ + 2x₂² - x₂

при условиях: 2x₁ - 3x₂ ≤ 0

x₂ ≤ 5

x₁ ≥ 0; x₂ ≥ 0

23. Найти max z =3x₁² + x₂² - 2x₁ - 2x₂ + 2

при условиях: x₁ + x₂ ≥ 1

2x₁ + x₂ ≤ 6

x₁ ≥ 0; x₂ ≥ 0

24. Найти max z = 4x₁² + x₂² - 2x₁ + 2x₂ + 3

при условиях: x₁ + 2x₂ ≥ 3

2x₁ - x₂ ≤ 1

x₁ + x₂ ≤ 3

x₁ ≥ 0; x₂ ≥ 0

25. Найти min z = 2x₁² + 2x₂² -x₁ +2x₂

при условиях: 2x₁ + x₂ ≤ 4

-x₁ + 2x₂ ≥ 1

x₂ ≤ 2

x₁ ≥ 0; x₂ ≥ 0

26. Найти min z = x₁² + x₂² - 4x₁ + 2x₂+ 10

при условиях: x₁ + x₂ ≤ 6

2x₁ - x₂ ≤ 1

x₁ ≥ 0; x₂ ≥ 0

27. Найти max z = 2x₁² + 4x₂² - 4x₁ - 2 x₂ + 3

при условиях: 5x₁ + x₂ ≥ 1

3x₁ - 2x₂ ≤ 2

x₁ + 2x₂ ≥ 3

x₁ ≥ 0; x₂ ≥ 0

28. Найти max z = 4x₁² + x₂² + 2x₁+ 3x₂

при условиях: x₁ - x₂ ≥ 0

x₁ + x₂ ≤ 5

x₁ ≥ 0; x₂ ≥ 0

29. Найти max z = 9x₁² + 4x₂² + 2x₁ – x₂ + 5

при условиях: x₁ - x₂ ≥ 0

x₁ + x₂ ≤ 6

x₁ ≥ 0; x₂ ≥ 0

30. Найти max z = x₁² + 3x₂² - 3x₁ - 2 x₂ + 4

при условиях: x₁ - x₂ ≥ 0

x₁ + x₂ ≤ 6

x₁ ≥ 0; x₂ ≥ 0

Задание. Составить блок-схему метода наискорейшего подъема (спуска).