Метод вращающихся координат (метод Розенброка)

Суть метода состоит во вращении системы координат в соответствии с изменением скорости убывания целевой функции. Новые направления координатных осей определяются таким образом, чтобы одна из них соответствовала направлению наиболее быстрого убывания целевой функции, а остальные находятся из условия ортогональности. Идея метода состоит в следующем (рис. 7.6).

Рис. 7.6 ‑ Геометрическая интерпретация метода Розенброка

Из начальной точки х[0] осуществляют спуск в точку х[1] по направлениям, параллельным координатным осям. На следующей итерации одна из осей должна проходить в направлении y₁ = х[1] ‑ х[0], а другая - в направлении, перпендикулярном к у₁ . Спуск вдоль этих осей приводит в точку х[2] , что дает возможность построить новый вектор х[2] ‑ х[1] и на его базе новую систему направлений поиска. В общем случае данный метод эффективен при минимизации овражных функций, так как результирующее направление поиска стремится расположиться вдоль оси оврага.

Алгоритм метода вращающихся координат состоит в следующем.

1. Обозначают через р₁[k], ..., р_n[k] направления координатных осей в некоторой точке х[k] (на к-й итерации). Выполняют пробный шаг h₁ вдоль оси р₁[k], т. е.

x[kl] = x[k] + h₁p₁[k].

Если при этом f(x[kl]) < f(x[k]), то шаг h умножают на величину b > 1;

Если f(x[kl]) > f(x[k]), - то на величину (-b), 0 < |b| < 1;

x[kl] = x[k] + b h₁p₁[k].

Полагая ?h₁ = а₁ .получают

x[kl] = x[k] + a₁p₁[k].

2. Из точки х[k1] выполняют шаг h₂ вдоль оси р₂[k]:

x[k2] = x[k] + a₁p₁[k] + h₂p₂[k].

Повторяют операцию п. 1, т. е.

x[k2] =x[k] + а₁р₁[k] +а₂p₂[k].

Эту процедуру выполняют для всех остальных координатных осей. На последнем шаге получают точку

х[kn] = х[k+1] = х[k] + .

3. Выбирают новые оси координат p₁[k+1], …, р_n[k+1]. В качестве первой оси принимается вектор

р₁[k+1] = x[k+l] ‑ x[k].

Остальные оси строят ортогональными к первой оси с помощью процедуры ортогонализации Грама - Шмидта. Повторяют вычисления с п. 1 до удовлетворения условий сходимости.

Коэффициенты b подбираются эмпирически. Хорошие результаты дают значения b = - 0,5 при неудачных пробах (f(x[ki]) > f(x[k])) и b = 3 при удачных пробах (f(x[ki]) < f(x[k])).

В отличие от других методов нулевого порядка алгоритм Розенброка ориентирован на отыскание оптимальной точки в каждом направлении, а не просто на фиксированный сдвиг по всем направлениям. Величина шага в процессе поиска непрерывно изменяется в зависимости от рельефа поверхности уровня. Сочетание вращения координат с регулированием шага делает метод Розенброка эффективным при решении сложных задач оптимизации.