6.1. Метод градиентного спуска
Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента F(х) В текущей точке поиска. Простейший алгоритм поиска Min F(X) записывается в векторной форме следующим образом:
Или в скалярном виде:
Величина рабочего шага в направлении градиента H Grad F(х) Зависит от величины градиента, который заранее учесть трудно, и от коэффициента пропорциональности шага H, с помощью которого можно управлять эффективностью метода.
Поиск каждой новой точки состоит из двух этапов:
1) оценка градиента F(X) Путем вычисления частных производных от F(х) По каждой переменной Хj;
2) рабочий шаг по всем переменным одновременно.
Величина H сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по каждой переменной определяется направляющими косинусами градиента
Где 
В этом случае величина рабочего шага не зависит от величины модуля градиента, и ею легче управлять изменением H. В районе оптимума может возникать значительное "рыскание", поэтому используют различные алгоритмы коррекции H.
Наибольшее распространение получили следующие алгоритмы:
1) 
(без коррекции);
2) 
3) 
Где - угол между градиентами на предыдущем и текущем шаге; 1 и 2 – заданные пороговые значения выбираются субъективно (например, 1=/6, 2=/3).
Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами f(x) большой), поэтому h сокращается (третье выражение).
Для оценки частных производных используются разностные методы:
алгоритм с центральной пробой
алгоритм с парными пробами
Где Gi – пробный шаг по I-й переменной, выбираемый достаточно малым для разностной оценки производной.
Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, и эта погрешность зависит от величины пробного шага.
Условием окончания поиска может являться малость модуля градиента F(X), т. е. |Gradf(X)| < .
Пример 60. Требуется найти минимум функции F(X, Y) = X3+2Y2-3X-4Y, завершив вычисления при погрешности = 0,01, выбрав начальное приближение Х(0) = - 0,5 и У(0) = -1, коэффициент шага H = 0.1.
Решение. Необходимые начальные данные приведены в условии задачи. Для вычислений выберем работу с шагом Без коррекции (H = Const).
Найдем частные производные функции:
Следовательно,
Значит, 
Переменные определяются по формулам:
Результаты вычислений занесем в табл. 17
Таблица 17
|
П |
X |
Y |
F(x, y) |
Df/dx |
Df/dy |
|grad f| |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
-0,500 |
-1,000 |
7,3750 |
-2,2500 |
-8,0000 |
8,3104 |
|
2 |
-0,275 |
-0,200 |
1,6842 |
-2,7731 |
-4,8000 |
5,5435 |
|
3 |
0,002 |
0,280 |
-0,9701 |
-3,0000 |
-2,8800 |
4,1586 |
|
4 |
0,302 |
0,568 |
-2,5061 |
-2,7258 |
-1,7280 |
3,2274 |
|
5 |
0,575 |
0,741 |
-3,4003 |
-2,0085 |
-1,0368 |
2,2603 |
Продолжение табл. 17
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
6 |
0,776 |
0,844 |
-3,8120 |
-1,1947 |
-0,6221 |
1,3469 |
|
7 |
0,895 |
0,907 |
-3,9508 |
-0,5958 |
-0,3732 |
0,7031 |
|
8 |
0,955 |
0,944 |
-3,9877 |
-0,2651 |
-0,2239 |
0,3471 |
|
9 |
0,981 |
0,966 |
-3,9967 |
-0,1111 |
-0,1344 |
0,1744 |
|
10 |
0,992 |
0,980 |
-3,9990 |
-0,0453 |
-0,0806 |
0,0925 |
|
11 |
0,997 |
0,988 |
-3,9997 |
-0,0183 |
-0,0484 |
0,0517 |
|
12 |
0,999 |
0,993 |
-3,9999 |
-0,0073 |
-0,0290 |
0,0299 |
|
13 |
1,000 |
0,996 |
-4,0000 |
-0,0029 |
-0,0174 |
0,0177 |
|
14 |
1,000 |
0,997 |
-4,0000 |
-0,0012 |
-0,0104 |
0,0105 |
|
15 |
1,000 |
0,998 |
-4,0000 |
-0,0005 |
-0,0063 |
0,0063 |
В последней точке модуль градиента меньше заданной погрешности
(0,0063 < 0.01), поэтому поиск прекращается.
Итак, 
И 
Пример 61. Требуется найти минимум функции 
завершив вычисления при погрешности = 0,5, выбрав начальное приближение Х(0) = 0 и У(0) = 0, коэффициент шага H = 0.1.
Решение. Необходимые начальные данные приведены в условии задачи. Для вычислений выберем работу с шагом без коррекции (H = Const).
Результаты вычислений занесем в табл. 18.
Таблица 18
|
П |
X1 |
X2 |
F(X1, X2) |
Df/D x1 |
Df/D x2 |
|Grad f| |
|
1 |
0,0000 |
0,0000 |
1,0000 |
1,0000 |
1,0000 |
1,4142 |
|
2 |
-0,1000 |
-0,1000 |
0,8487 |
0,6187 |
0,4187 |
0,7471 |
|
3 |
-0,1619 |
-0,1419 |
0,8045 |
0,4143 |
0,1706 |
0,4480 |
|
4 |
-0,2033 |
-0,1589 |
0,7880 |
0,2895 |
0,0604 |
0,2957 |
|
5 |
-0,2323 |
-0,1650 |
0,7806 |
0,2077 |
0,0123 |
0,2080 |
|
6 |
-0,2530 |
-0,1662 |
0,7768 |
0,1515 |
-0,0072 |
0,1517 |
|
7 |
-0,2682 |
-0,1655 |
0,7748 |
0,1118 |
-0,0138 |
0,1126 |
|
8 |
-0,2794 |
-0,1641 |
0,7737 |
0,0831 |
-0,0146 |
0,0844 |
|
9 |
-0,2877 |
-0,1626 |
0,7731 |
0,0621 |
-0,0131 |
0,0635 |
|
10 |
-0,2939 |
-0,1613 |
0,7727 |
0,0466 |
-0,0110 |
0,0479 |
В последней точке модуль градиента меньше заданной погрешности, поэтому поиск прекращается.
Итак, 
И 
Рассмотрим Градиентный метод минимизации функции С дроблением шага.
Пусть F(X) выпуклая дифференцируемая во всем N-Мерном пространстве 
Функция и требуется найти её точку минимума Х*. Выбрав произвольное начальное приближение 
, построим последовательность
(9)
Где величины Hk (параметрические шаги) выбираются достаточно малыми для того, чтобы выполнялось условие
(10)
В качестве условия окончания вычислений обычно используется близость к нулю градиента 
, т. е. выполнение неравенств
Или 
(11)
( - заданное достаточно малое число), после чего полагают 
Если при некотором K Условие (10) нарушается, то шаг Hk уменьшают (дробят) в заданное число раз до выполнения неравенства (10) и продолжают вычисления.
Пример 62. Минимизировать функцию 
Методом градиентного спуска с дроблением шага, завершив вычисления при 
Решение. Выбрав начальное приближение Х(0) = (0, 0) и H0 = 1, построим последовательность (9), записывая результаты вычислений в табл. 19
Таблица 19
|
K |
|
|
F(X(K)) |
|
|
Hk |
|
Примечание |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Условие (10) нарушено. Уменьшаем H0 в 2 раза. |
|
|
-1 |
-1 |
3,1353 |
- |
- |
|
| |
|
| ||||||||
|
|
0 |
0 |
1 |
1 |
1 |
0,5 |
|
Условие (10) нарушено. Уменьшаем H0 в 2 раза. |
|
|
-0,5 |
-0,5 |
1,118 |
- |
- |
|
| |
|
| ||||||||
|
1 |
0 |
0 |
1 |
1 |
1 |
0,25 |
|
Условие (10) выполнено |
|
-0,25 |
-0,25 |
0,794 |
0,1065 |
-0,3935 |
0,25 |
0,4077 | ||
|
2 |
-0,2766 |
-0,1516 |
0,7741 |
0,0984 |
0,0451 |
0,25 |
0,1082 |
Условие (10) выполнено |
|
3 |
-0,3012 |
-0,1629 |
0,7725 |
0,0262 |
-0,023 |
0,25 |
0,0349 |
Точность достигнута(11) |
Итак, 
Пример 63. Минимизировать функцию F(X, Y) = X3+2Y2-3X-4Y, методом градиентного спуска с дроблением шага, завершив вычисления при
Решение. Выбрав начальное приближение Х(0) = (-0.5, -1) и H0 = 0.1, построим последовательность (9), записывая результаты вычислений в табл. 20.
Таблица 20
|
K |
X |
Y |
F(x, y) |
|
|
Hk |
|
Примечание |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
-0,5000 |
-1,0000 |
7,3750 |
-2,2500 |
-8,0000 |
0,1 |
| |
|
-0,2750 |
-0,2000 |
1,6842 |
-2,7731 |
-4,8000 |
0,1 |
5,5435 |
Условие (10) выполнено | |
|
2 |
0,0023 |
0,2800 |
-0,9701 |
-3,0000 |
-2,8800 |
0,1 |
4,1586 |
Условие (10) выполнено |
Продолжение табл. 20
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
3 |
0,3023 |
0,5680 |
-2,5061 |
-2,7258 |
-1,7280 |
0,1 |
3,2274 |
Условие (10) выполнено |
|
4 |
0,5749 |
0,7408 |
-3,4003 |
-2,0085 |
-1,0368 |
0,1 |
2,2603 |
Условие (10) выполнено |
|
5 |
0,7757 |
0,8445 |
-3,8120 |
-1,1947 |
-0,6221 |
0,1 |
1,3469 |
Условие (10) выполнено |
|
6 |
0,8952 |
0,9067 |
-3,9508 |
-0,5958 |
-0,3732 |
0,1 |
0,7031 |
Условие (10) выполнено |
|
7 |
0,9548 |
0,9440 |
-3,9877 |
-0,2651 |
-0,2239 |
0,1 |
0,3471 |
Условие (10) выполнено |
|
8 |
0,9813 |
0,9664 |
-3,9967 |
-0,1111 |
-0,1344 |
0,1 |
0,1744 |
Условие (10) выполнено |
|
9 |
0,9924 |
0,9798 |
-3,9990 |
-0,0453 |
-0,0806 |
0,1 |
0,0925 |
Условие (10) выполнено |
|
10 |
0,9969 |
0,9879 |
-3,9997 |
-0,0183 |
-0,0484 |
0,1 |
0,0517 |
Условие (10) выполнено |
|
11 |
0,9988 |
0,9927 |
-3,9999 |
-0,0073 |
-0,0290 |
0,1 |
0,0299 |
Точность достигнута(11) |
Итак, 
| < Предыдущая | Следующая > |
|---|
