Лекция: МЕТОД ЦИКЛИЧЕСКОГО ПОКООРДИНАТНОГО СПУСКА

Этот метод заключается в последовательной минимизации целе­вой функции f(x) сначала по направлению первого базисного вектора е1, затем второго — е2 и т.д. После окончания минимизации по направ­лению последнего базисного вектора еn цикл повторяется.

Опишем этот алгоритм.

Шаг 0. Выбрать х ÎEn, критерий достижения точности (напри­мер, (3.28) или (3.29)), величину e. Найти f(x), положить j= 1.

Шаг 1. Решить задачу одномерной минимизации Ф(a) = f(х + aеj)® min, a Î R, т.е. найти a*. Положить = х +a*еj, вычис­лить f(х).

Шаг 2. Если j < п, то положить х =, j=j+1 и перейти к шагу 1, иначе — перейти к шагу 3.

Шаг 3. Проверить условие достижения точности ||х-|| < e

или | f(x) — f()| <e. Если оно выполняется, то положить х* =, f *=f() и закончить поиск. Иначе — положитьх =, f(х) = f(), j = 1 и перейти к шагу 1.

Замечание. Для приближенного решения вспомогательной задачи одномерной минимизации на шаге 1 алгоритма на практике, как правило, используют метод поразрядного поиска (см. разд. 2.2.2).

Эффективность метода циклического покоординатного спуска существенно зависит от свойств целевой функции.

Пример 3.5. Решить задачуf(x)=x21+х22® min, х ÎЕ2 методом циклического покоординатного спуска.

Линии уровня этой целевой функции — окружности с центром в начале координат (рис. 3.7). Выберем произвольную начальную точку х, например х=(3,3). Очевидно, два шага исчерпывающего спуска сначала по направлению е1, затем — е2 приведут в точку минимума х* = (0,0).

В примере 3.5 точку минимума функции удалось найти точно за конечное число шагов. Это скорее исключение, чем правило.

Пример 3.6. Решить задачуf(x)=5x21+5х22+8x1х2® min, х ÎЕ2 методом циклического покоординатного спуска.

Сначала заметим, что поворот системы координат на угол — 45° (замена переменных x1 =(y1+y2) / и x1 =(-y1+y2) / приводит функцию к виду f1(y) =y21+9y22. Очевидно, линии уровня целевой функции — эллипсы y21/9+y22=c2 (рис. 3.8). Результаты расчетов по приведенному выше алгоритму представлены в табл. 3.2.

Рис. 3.7. К примеру 3.5. Рис. 3.8. К примеру 3.6.

Тaблицa 3.2

Из табл. 3.2 и рис. 3.8 видно, что минимизирующая последовательность {хk} сходится к точке минимума х* = (0,0). Однако в отличие от решения за­дачи из примера 3.5 достижение точки минимума за конечное число шагов не гарантируется. Траектория поиска точки минимума в данной задаче имеет ярко выраженный зигзагообразный характер.

Из примера 3.6 видно, что эффективность решения задачи методом циклического покоординатного спуска можно повысить, если дополнить его алгоритм периодически повторяющимся поиском точки минимума в направлениях pi = xi-xi-1 из точек xi. Так, например, если из точки х4 провести исчерпывающий спуск в направлении p4 = х4- х2 (координаты точек см. в табл. 3.2), то получим точку (-2,2 ×10-5; 5,6 × 10-3 ), распо­ложенную значительно ближе к точке минимума х*=(0,0), чем точки х5, х6, х7.

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