Метод Розенброка

В методе Розенброка [13] первые n итераций полностью соответствуют n итерациям метода Гаусса-Зейделя. Затем производится расчет новых n поисковых направлений так, чтобы первое направление совпадало с направлением полного прохода за предыдущий цикл итераций, а остальные направления были бы взаимо-ортогональны и через n циклов они все бы совпадали с направлениями осей квадратичного приближения целевой функции вблизи минимума. Алгоритм этого метода следующий.

{{{ Начало алгоритма.

1) Полагаем i=1 и X _i= X _init. Запоминаем начальные направления в матрице P={ e _i}, i=1..n.

2) Выбираем поисковое направление P _i из матрицы P и ищем минимум в этом направлении: a_i: min_aJ(X _i+a_i× P _i). Рассчитываем новое приближение вектора поисковых параметров X _i+1= X _i+a_i× P _i. Увеличиваем i на единицу и если i£n, то идем в начало пункта 2).

3) Производим пересчет направлений поиска по формуле:

(1.3.2)

Выполняем процедуру ортогонализации и нормировки направлений (процесс ортогонализации Грамма-Шмидта [15] стр.460, ф.15.2-10):

(1.3.3)

(1.3.4)

Заносим найденные направления в матрицу P.

4) Если | A _i|£e, то поиск заканчивается, иначе полагаем i=1 и идем на пункт 2).

}}} Конец алгоритма.

Метод Розенброка иногда называют методом вращающихся координат. Через n циклов итераций (т.е. через n итераций) для квадратичной функции все поисковые направления будут направлены вдоль осей функции. Если же все поисковые направления совпадают с направлениями осей функции, то как это следует из рис.(1.1.1) минимум может быть достигнут за n итераций (для квадратичной функции). Графически работа метода Розенброка для двумерной функции показана на рис.1.3.2.

Этот метод является одним из лучших методов 0-го порядка, он обладает хорошей скоростью сходимости и является устойчивым к вырождению методом за счет процедуры ортогонализации направлений (1.3.3).

Рис.1.3.2

Поиск минимума методом Розенброка

Метод ДСК

Имя метода образовано по начальным буквам фамилий авторов -Девис-Свен-Кэмпей [32]. По своей сути он является усеченным методом Розенброка, в котором отсутствует процедура ортогонализации направлений (1.3.3). Он обладает почти такой же скоростью сходимости, что и метод Розенброка, однако он может вырождаться, т.е. терять какое-либо измерение в n мерном пространстве параметров когда два поисковых направления почти совпадают.

Дата добавления: 2015-11-14