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

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

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

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

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

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

x[kl] = x[k] + h1p1[k].

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

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

x[kl] = x[k] + α h1p1[k].

Полагая h1 = а1 .получают x[kl] = x[k] + a1p1[k].

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

x[k2] = x[k] + a1p1[k] + h2p2[k].

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

x[k2] =x[k] + а1р1[k] +а2p2[k].

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

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

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

р1[k+1] = x[k+l] - x[k].

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

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

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

Выше было показано, что метод прямого поиска (Хука-Дживса) также может плохо оптимизировать «овражные» функции. Но имеется более удачная модификация метода покоординатного спуска, известная под названием «метод конфигураций Хука-Дживса». В соответствии с этим методом вначале выполняют обычную серию из шагов покоординатного спуска, затем делают дополнительный шаг в направлении вектора , как показано на рис. 1.12, где дополнительный шаг выполняют в направлении вектора , что и приводит в точку .

Рис. 1.12. Иллюстрация метода конфигураций