Метод градиентного спуска с дроблением шага

 

На каждой итерации шаг спуска l_k выбирается таким образом, чтобы выполнялось условие:

( 6.8.3-1 )

 

Выбор шага в методе ГДШ заключается в следующем.

Задается начальное значение шага l_k = l₀ (как правило, l₀=0, 5). Проверяется условие сходимости, приведенное выше. Если условие сходимости выполняется, то шаг спуска для данной итерации выбран, а если оно не выполняется, то принимают новый шаг l_k = l_k/2, и снова проверяют условие сходимости (и т.д.).

Алгоритм метода ГДШ можно описать следующей последовательностью действий:

1. При k = 0 задаемся начальной точкой спуска (x_k, y_k), требуемой точностью e и начальным шагом l₀ (пусть l₀ =0, 5).

2. Вычисляем значения

 

( 6.8.3-2 )

3. Вычисляем новые значения переменных

( 6.8.3-3 )

4. Проверяем условие сходимости:

 

( 6.8.3-4 )

Если условие выполняется, то полагаем величину шага равной l_k, в противном случае l_k = l_k/2 и переходим к п.3.

5. Проверка окончания процесса итераций (необходимого условия существования минимума):

 

( 6.8.3-5 )

 

Если условие выполнено, то минимум найден, а если нет - вычисление координат следующей точки (k=k+1) и передача управления п.2.

 

Рис. 6.8.3-1. Траектория спуска ГДШ

Алгоритм выбора шага в градиентном методе дробления шага приведен на
рис. 6.8.3-2.

 

Рис. 6.8.3-2. Схема алгоритма выбора шага в градиентном методе дробления шага

Пример 6.8.3-1. Найти минимум функции Q(x, y) методом ГДШ.

Пусть Q(x, y) = x² +2y²; x₀ = 2; y₀ = 1.

Проверим достаточные условия существования минимума:

Проделаем одну итерацию согласно алгоритму.

 

1. Q(x₀, y₀) = 6.

2. При х = x₀ и y = y₀,

3. Шаг l_k = l₀ = 0, 5

4.

Таким образом, 4 < 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

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

 

Суть метода состоит в следующем. Из выбранной точки (x₀, y₀) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча (рис. 6.8.4-1). В найденной точке луч касается линии уровня. Затем из этой точки спуск проводится в направлении антиградиента (перпендикулярном линии уровня) до тех пор, пока соответствующий луч не коснется в новой точке проходящей через нее линии уровня, и т.д.

Рис. 6.8.4-1

 

Выразим целевую функцию Q(x, y) через шаг l. При этом представим целевую функцию на определенном шаге как функцию одной переменной, т.е. величины шага

 

 

Величина шага на каждой итерации определяется из условия минимума функции :

= min( (l)) l_k = l*(x _k, y _k), l > 0.

 

Таким образом, на каждой итерации выбор шага l_k предполагает решение задачи одномерной оптимизации. По способу решения этой задачи различают:

- аналитический метод (НСА);

- численный метод (НСЧ).

В методе НСА значение шага получают из условия , а в методе НСЧ величину l_k находят на отрезке [0; 1] c заданной точностью, используя один из методов одномерной оптимизации.

 

Алгоритм выбора шага в методе наискорейшего спуска с использованием метода золотого сечения приведен на рис. 6.8.4-2.

 

Рис. 6.8.4-2. Алгоритм выбора шага в численном методе наискорейшего спуска НСЧ

с использованием метода золотого сечения

 

Пример 6.8.4-1. Найти минимум функции Q(x, y)=x² + 2y² с точностью e=0.1, при начальных условиях: x₀=2; y₀=1.

Проделаем одну итерацию методом НСА.

Выразим целевую функцию через величину l:

=(x-2lx)²+2(y-4ly) ² = x²-4lx²+4l²x²+2y²-16ly²+32l²y².

 

Из условия ¢ (l)=0 найдем значение l*:

Полученная функция l=l(x, y) позволяет найти значение l. При x=2 и y=1 имеем l=0.3333.

 

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

Проверим выполнение критерия окончания итераций при k=1:

Поскольку |2*0.6666|> 0.1 и |-0.3333*4|> 0.1, то условия окончания процесса итераций не выполнены, т.е. минимум не найден. Поэтому следует вычислить новое значение l при x=x₁ и y=y₁ и получить координаты следующей точки спуска. Вычисления продолжаются до тех пор, пока не выполнятся условия окончания спуска.

 

Отличие численного метода НС от аналитического состоит в том, что поиск значения l на каждой итерации происходит одним из численных методов одномерной оптимизации (например, методом дихотомии или методом золотого сечения). При этом в качестве интервала неопределенности служит диапазон допустимых значений l - [0; 1].

 

 

⇐ Предыдущая123Следующая ⇒

Поделиться: