Метод дробления шага

Как нетрудно понять, на каждой итерации было бы желательно выбирать направление спуска p ^{( n )}, близкое к тому направлению, перемещение вдоль которого приводит из точки х ^{( n )} в точку . К сожалению, антиградиент p ^{( n )} = - g ^{( n )} является, как правило, неудачным направлением спуска. Особенно ярко это проявляется для овражных функций. Поэтому возникает сомнение в целесообразности тщательного поиска решения задачи одномерной минимизации (3.13) и появляется желание сделать в направлении p ^{( n )} лишь такой шаг, который бы обеспечил «существенное убывание» функции f. Более того, на практике иногда довольствуются определением значения
α_n > 0, которое просто обеспечивает уменьшение значения целевой функции.

В одном из простейших алгоритмов (типа дробления шага) такого выбора шага α_n фиксируют начальное значение α; > 0 и значение параметра γ, 0 < γ < 1. За α_n принимают α_n = , где i_n – первый из номеров i = 0, 1, 2, …, для которого выполнено условие убывания

. (3.14)

Однако при таком выборе α_n нет гарантии, что последовательность х ^{( n )} будет сходиться к точке минимума даже для простой квадратичной функции. Условие (3.14) является слишком слабым: последовательность х ^{( n )}, незначительно уменьшая значения функции f, может «останавливаться», не доходя до точки . Такое поведение последовательности х ^{( n )} можно предотвратить, если заменить условие (3.14) условием «существенного убывания» функции f на каждой итерации:

. (3.15)

Здесь β; (0 < β; < 0) – дополнительный параметр.

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

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

α_i = α; γ ⁱ, х ^{( n,i )} = х ^{( n )} - α_i g ^{( n )} , где g ^{( n )} = (2 x ^{( n )} – 4, 4 y ^{( n )} – 4)^T.

Выберем начальное приближение х ⁽⁰⁾ = (0, 0)^Т, начальное значение шага
α; = α₀ = 1, значения параметров γ = ½, β = ¾;.

Вычислим значения f(х ⁽⁰⁾ ) = 0, g ⁽⁰⁾ = (-4, -4)^Т.

1-я итерация. Вычисляем х ^(0,0) = х ⁽⁰⁾ – α₀ g ⁽⁰⁾ = (4, 4)^Т, f(х ^(0,0) ) = 16. Так как значение функции не уменьшилось, то следует уменьшить шаг: α;₁ = α₀ /2 = 0.5.

1) Вычисляем х ^(0,1) = х ⁽⁰⁾ – α₁ g ⁽⁰⁾ = (2, 2)^Т, f(х ^(0,1) ) = -4.

Поскольку, f(х ^(0,1) ) - f(х ⁽⁰⁾ ) = -4 > - β α;₁| g ⁽⁰⁾|² = -12, условие (3.15) не выполняется и следует снова уменьшить шаг: α;₂ = α;₁ /2 = 0.25.

2) Вычисляем х ^(0,2) = х ⁽⁰⁾ – α₂ g ⁽⁰⁾ = (1, 1)^Т, f(х ^(0,2) ) = -5.

Имеем f(х ^(0,2) ) - f(х ⁽⁰⁾ ) = -5 > - β α;₂| g ⁽⁰⁾|² = -6, т.е. условие (3.15) не выполняется. Уменьшаем шаг: α;₃ = α;₂ /2 = 0.125.

3) Вычисляем х ^(0,3) = х ⁽⁰⁾ – α₃ g ⁽⁰⁾ = (0.5, 0.5)^Т, f(х ^(0,3) ) = -3.25.

Так как f(х ^(0,3) ) - f(х ⁽⁰⁾ ) = -3.25 < - β α;₃| g ⁽⁰⁾|² = -3, то условие (3.15) выполнено.

4) Положим х ⁽¹⁾ = х ^(0,3) = (0.5, 0.5)^Т, f(х ⁽¹⁾ ) = -3.25.

Вычислим g ⁽¹⁾ = (-3, -2)^Т и положим α₀ = 1.

Далее вычисления следует продолжить до выполнения какого-либо принятого критерия окончания итераций.

На рис.3.9 приведена блок-схема алгоритма метода дробления шага для минимизации рассмотренной в этом примере квадратичной функции.

 

Начало

Ввод Х, Y, Eps, B, G

F0 = F(X, Y)

A = 2

F1 = G1(X, Y)

F2 = G2(X, Y)

M = F1² + F2²

A = A * G

X1 = X – A * F1

Y1 = Y – A * F2

FI = F(X1, Y1)

---

FI – F0 < -B*A*M

+--

T =

X = X1

Y = Y1

F0 = FI

	---

+--

T < Eps

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

end

 

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

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

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

B – дополнительный параметр метода β; (в примере β; = ¾);

G – параметр γ (0 < γ < 1), обеспечивающий дробление шага;

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

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

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

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

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