Покоординатный спуск

В методе покоординатного спуска в качестве очередного направления спуска выбирают направление одной из координатных осей. Наиболее известным является метод циклического покоординатного спуска. Опишем очередной (n + 1)-й цикл одного из вариантов этого метода, считая приближение x ^{( n )} уже найденным.

Цикл с номером n + 1 состоит из m шагов.

На первом шаге производят спуск по координате х ₁. Значения х ₂ = х ₂^{( n )}, …,
х_m = х_m ^{( n )} остальных координат фиксируют, а х ₁^{( n+ 1)} выбирают из условия

.

Фактически решается задача минимизации функции одной переменной

.

На втором шаге производят спуск по координате х ₂. Значения х ₁ = х ₁^{( n +1)}, х ₃ = х ₃^{( n )}, …, х_m = х_m ^{( n )} остальных координат фиксируют и х ₂^{( n+ 1)} выбирают как решение задачи одномерной минимизации

.

Аналогично осуществляют остальные шаги.

В результате получается очередное приближение x ^{( n +1)} к точке минимума. Далее цикл метода снова повторяют.

На рис.3.2 изображена геометрическая иллюстрация циклического покоординатного спуска для m =2.

Рисунок 3.2 - Геометрическая иллюстрация циклического покоординатного спуска

Приведём блок-схему алгоритма основной программы метода циклического покоординатного спуска для m =2 (рис.3.3).

Начало

Ввод Х0, ХN, Y0, YN, Eps

X = XN

Y = YN

X1 = X

Y1 = Y

MINX(X0, XN, Eps, Y1, X)

MINY(Y0, YN, Eps, X, Y)

---

< Eps

+

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

end

 

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

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

Входные данные: Х0, ХN, Y0, YN – граничные значения переменных x и y;

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

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

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

 

На рис.3.4 приведена блок-схема алгоритма процедуры MINX, осуществляющая поиск значения переменной Х, при котором целевая функция F(x, y) принимает наименьшее значение при фиксированном значении переменной Y. В данном примере в процедуре MINX для решения одномерной задачи минимизации используется метод дихотомии.

Входные параметры: А, B – границы изменения значений переменной Х;

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

Выходные параметры: XМ - приближение к искомому значению X точки минимума;

MINX (A, B, Eps, Y, XM)

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

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

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

FA = F(Alfa, Y)

FB = F(Beta, Y)

-

+

FA £ FB

B = Beta A = Alfa

 

-

|B – A| < Eps

+

XM = (A + B)/2

end

 

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

Аналогично, для поиска значения переменной Y, при котором целевая функция F(x, y) принимает наименьшее значение при фиксированном значении переменной X, составляется блок-схема алгоритма процедуры MINY (рис.3.5).

Входные параметры: А, B – границы изменения значений переменной Y;

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

Выходные параметры: YМ - приближение к искомому значению Y точки минимума;

MINY (A, B, Eps, X, YM)

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

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

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

FA = F(X, Alfa)

FB = F(X, Beta)

-

+

FA £ FB

B = Beta A = Alfa

 

-

|B – A| < Eps

+

YM = (A + B)/2

end

 

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