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

Пример 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-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].

Дата добавления: 2014-12-27