1.3 Методы оптимизации 0-го порядка

1.3.1 Метод покоординатного поиска

В методе покоординатного поиска или методе Гаусса-Зейделя в качестве поисковых направлений выбираются координатные оси. Если обозначить e_i={0,..,0,1 ,0,..,0}^T - единичный вектор, направленный вдоль i- той координаты, то направление P_i - совпадает с этим направлением:

P_i=e_i, i=1..n. (1.3.1)

Алгоритм метода покоординатного поиска будет выглядеть следующим

образом.

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

1) Полагаем i=1, X_i=X_init .

2) Задаем поисковое направление P_i=e_i. Осуществляем поиск минимума целевой функции в заданном направлении P_i:

_i: min_(J(X_i+P_i)).

3) Если |_iP_i|<, то процедура оптимизации заканчивается, иначе рассчитываем новое значение вектора поисковых параметров X_i+1=X_i+_iP_i, увеличиваем i на единицу и если in то переходим к пункту 2), иначе полагаем i=1 и также переходим к пункту 2).

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

Графически работа метода в двумерном случае показана на рис. 1.3.1. Метод Гаусса-Зейделя легко программируется, но обладает низкой скоростью сходимости. На практике этот метод широко применяют, когда производят настройку какого-нибудь прибора или устройства на оптимальный режим работы, перебирая по очереди ручки настройки.

Рис.1.3.1

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

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

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

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

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

2) Выбираем поисковое направление P_i из матрицы P и ищем минимум в этом направлении: _i: min_J(X_i+_iP_i ). Рассчитываем новое приближение вектора поисковых параметров X_i+1=X_i+_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|, то поиск заканчивается, иначе полагаем i=1 и идем на пункт 2).

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

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

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

Рис.1.3.2

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