Метод циклического покоординатного спуска

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

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

Шаг 0. Выбрать х Î E _n,критерий достижения точности (напри­мер, (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) =x ²₁ +х ²₂ ® min, х Î Е ₂ методом циклического покоординатного спуска.

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

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

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

Сначала заметим, что поворот системы координат на угол - 45° (замена переменных x ₁ =(y ₁+ y ₂) / и x ₁ =(- y ₁+ y ₂) / приводит функцию к виду f ₁(y) = y ²₁+9 y ²₂. Очевидно, линии уровня целевой функции — эллипсы y ²₁/9+ y ²₂=c² (рис. 3.8). Результаты расчетов по приведенному выше алгоритму представлены в табл. 3.2.

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

Тaблицa 3.2

Номер итерации	x 1	x 2	f (x)
		5
	-4	5
	-4	3,2	28,8
	-2,56	3,2	18,43
	-2,56	2,05	11,8
5'	-1,64	2,05	7,55
	-1,64	1,31	4,83
	-1,05	1,31	3,09
	-1,05	0,84	1,98
	-0,67	0,84	1,27
	-0,67	0,54	0,81

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

Из примера 3.6 видно, что эффективность решения задачи методом циклического покоординатного спуска можно повысить, если дополнить его алгоритм периодически повторяющимся поиском точки минимума в направлениях p ⁱ = x ⁱ -x ^{i- 1} из точек x ⁱ. Так, например, если из точки х⁴ провести исчерпывающий спуск в направлении p⁴ = х⁴ - х² (координаты точек см. в табл. 3.2), то получим точку (-2,2 ×10^-5; 5,6 × 10^-3), распо­ложенную значительно ближе к точке минимума х^*=(0,0), чем точки х⁵, х⁶, х⁷.

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