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

 

Рассмотрим функцию φ_n (α) = f( x ⁽ⁿ⁾ - α g ⁽ⁿ⁾) одной скалярной переменной α ³; 0 и выберем в качестве α _n то значение, для которого выполняется равенство

φ_n (α _n) = φ_n (α). (3.13)

Этот метод, предложенный в 1845 г. О. Коши, принято теперь называть методом наискорейшего спуска.

Рисунок 3.6

На рис.3.6 изображена геометрическая иллюстрация этого метода для минимизации функции двух переменных. Из начальной точки x ⁽⁰⁾ перпендикулярно линии уровня f( x ) = f( x ⁽⁰⁾) в направлении p ⁽⁰⁾ = - g ⁽⁰⁾ спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча x ⁽⁰⁾ - α p ⁽⁰⁾ (α > 0) значение функции f. В найденной точке x ⁽¹⁾ этот луч касается линии уровня
f( x ) = f( x ⁽¹⁾). Затем из точки x ⁽¹⁾ проводят спуск в перпендикулярном линии уровня направлении p ⁽¹⁾ = - g ⁽¹⁾ до тех пор, пока соответствующий луч не коснётся в точке x ⁽²⁾ проходящей через эту точку линии уровня, и т. д.

Отметим, что на каждой итерации выбор шага α _n предполагает решение задачи одномерной минимизации (3.13).

Пример 3. Рассмотрим методнаискорейшего спуска для минимизации квадратичной функции

f(x, y) = x² + 2y² – 4x – 4y

Вектор-градиент для этой функции будет выглядеть следующим образом:

Для вычисления координат точки очередного приближения к точке минимума будут использоваться формулы

x = x – α^.G1(x,y)

y = y – α^.G2(x,y)

Тогда функция φ_n (α), которую необходимо минимизировать на каждом шаге итерации для очередной точки с координатами (x, y), для данного случая имеет вид:

FI(α, x, y) = (x – α^.G1(x,y))² + 2(y – α^.G2(x,y))² - 4(x – α^.G1(x,y)) – 4(y – α^.G2(x,y))

На рис.3.7 приведена блок-схема алгоритма основной программы метода наискорейшего спуска для минимизации рассмотренной в этом примере квадратичной функции f(x, y) = x² + 2y² – 4x – 4y.

Входные данные: X, Y – координаты точки начального приближения из заданной области Х0 £ Х £ ХN, Y0 £ Y £YN;

Eps – заданная точность вычислений;

F(x, y) – заданная целевая функция – должна быть описана отдельно;

G1(x, y) – функция - частная производная функции F(x, y) по переменной х;

G2(x, y) – функция - частная производная функции F(x, y) по переменной y;

Результаты: X, Y - приближение к искомым значениям координат точки минимума;

F(X,Y) – значение целевой функции в точке минимума.

Начало

Ввод Х, Y, Eps

MINALFA(X, Y, Eps, Alfa)

X1 = X

Y1 = Y

X = X – Alfa^.G1(X)

Y = Y – Alfa^.G2(Y)

---

< Eps

+

Вывод (X, Y), F(X, Y)

end

 

Рисунок 3.7 - Блок-схема алгоритма основной программы метода наискорейшего спуска для функции двух переменных

 

На рис.3.8 приведена блок-схема алгоритма процедуры MINALFA, осуществляющая поиск значения переменной α; > 0, при котором функция FI(α, x, y) принимает наименьшее значение при фиксированных значениях переменных х и y. В данном примере в процедуре MINALFA для решения одномерной задачи минимизации используется метод дихотомии.

Входные параметры: X, Y – координаты точки очередного приближения к точке минимума;

Eps – заданная точность вычислений;

Выходные параметры: T – значение шага α; для вычисления очередного приближения к точке минимума;

FI(α, x, y) – функция, для которой решается задача одномерной минимизации относительно переменной α; при фиксированных значениях переменных х и y.

MINALFA(X, Y, Eps, T)

A = 0

B = 2

Здесь параметр метода выбрали δ = ε/3 < ε/2

Alfa = (A + B)/2 – Eps/3

Beta = (A + B)/2 + Eps/3

FA = FI(Alfa, X, Y)

FB = FI(Beta, X, Y)

+

-

FA £ FB

B = Beta A = Alfa

 

-

|B – A| < Eps

+

T = (A + B)/2

end

 

Рисунок 3.8 - Блок-схема алгоритма процедуры MINALFA