2.3 Методы с использованием производных 1-го порядка
2.3.1 Градиентный метод
Стратегия обычного градиентного метода оптимизации без ограничений использует только первые производные целевой функции. На k-м этапе переход из точки Х(k) в точку Х(k+1) описывается следующим соотношением:
X(k+1) = X(k) +
X(k)
= X(k) + (k)
(k),
где X(k) - вектор перехода из точкиХ(k)в точкуХ(k+1);
(k)- единичный
вектор в направленииX(k);
(k)- скаляр, равный величине шага.
Величина шага (k) в процессе движения остается постоянной. В ряде случаев предусматривается адаптация к топологии поверхности. Градиент целевой функции f(Х) в любой точке Х есть вектор в направлении наибольшего локального увеличения f(Х). Следовательно, нужно двигаться в направлении, противоположном градиенту f(Х), поскольку отрицательный градиент f(Х) в точке Х(k) направлен в сторону наибольшего уменьшения f(Х) по всем компонентам Х и ортогонален линии уровня f(Х) в точке Х(k). Введение направления, противоположного нормированному (единичному) градиенту f(Х), определяемого в точке Х(k) определяется по формуле
,
тогда
.
При расчете экстремума функции градиентным методом при переходе к минимуму или в овражных ситуациях возникает характерный случай, который заключается в зигзагообразном движении. Поэтому величину шага необходимо уменьшать. Одним из возможных подходов к адаптации является расчет угла между последовательными векторами шагов. При малых величину шага следует уменьшать, а при больших соответственно увеличивать. Это позволяет сократить число шагов и повышает работоспособность метода.
Алгоритм градиентного метода.
Начальный этап. Выбрать начальную точку X(1),шаг и 0 - скаляр, используемый в критерии остановки. Положить k = 1 и перейти к основному этапу.
Основной
этап. Шаг
1. Вычислить
f(X(k)),
и
. Перейти к шагу 2.
Шаг 2. Если ||X(k+1) - X(k)|| , то остановиться; в противном случае заменить k на k + 1и перейти к шагу 1.
Пример расчета минимума функции градиентным методом.
Постановка задачи. Найти минимум функции f(x) = (x1 - 2)4 + (х1 - 2х2)2. Начальное приближение принять равным Х(1) = [2,5 2,5]Т. Величина шага = 0,5.
Определяем первые производные и норму вектора градиента для исследуемой функции:
; 
;
.
Результаты восьми первых расчетов представлены в таблице 2.6.
Расчет минимума функции f(x) = (x1 - 2)4 + (х1 - 2х2)2 градиентным методом.
Таблица 2.6
|
№ |
х1 |
х2 |
f(X) |
|
|
|
Величина шага | |
|
х1 |
х2 | |||||||
|
1 |
2.500 |
2.500 |
6.313 |
-4.500 |
10.000 |
10.966 |
0.205 |
-0.456 |
|
2 |
2.705 |
2.044 |
2.160 |
-1.363 |
5.532 |
5.697 |
0.120 |
-0.485 |
|
3 |
2.825 |
1.559 |
0.548 |
1.660 |
1.169 |
2.030 |
-0.409 |
-0.288 |
|
4 |
2.416 |
1.271 |
0.046 |
0.038 |
0.501 |
0.502 |
-0.037 |
-0.499 |
|
5 |
2.379 |
0.772 |
0.717 |
1.886 |
-3.338 |
3.834 |
-0.246 |
0.435 |
|
6 |
2.133 |
1.207 |
0.080 |
-0.555 |
1.128 |
1.257 |
0.221 |
-0.449 |
|
7 |
2.353 |
0.759 |
0.714 |
1.848 |
-3.344 |
3.820 |
-0.242 |
0.438 |
|
8 |
2.111 |
1.196 |
0.079 |
-0.557 |
1.125 |
1.255 |
0.222 |
-0.448 |
Из таблицы видно, что, начиная с 6-го этапа, возникает зигзагообразное движение, которое при = 0,5 не приведет к оптимуму. Необходимо уменьшить величину шага, однако при этом движение в направлении Х* остается очень медленным.
Траектория поиска минимума функции градиентным методом приведена на рис.2.6.
Рис.2.6 Графическая иллюстрация поиска минимума функции градиентным методом.