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

Суть метода состоит во вращении системы координат в соответствии с изменением скорости убывания целевой функции. Новые направления координатных осей определяются таким образом, чтобы одна из них соответствовала направлению наиболее быстрого убывания целевой функции, а остальные находятся из условия ортогональности. Идея метода состоит в следующем (рис. 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умножают на величину> 1;

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

x[kl] =x[k] + 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 до удовлетворения условий сходимости.

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

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