Лекция: Метод циклического покоординатного спуска
Этот метод заключается в последовательной минимизации целевой функции сначала по направлению первого базисного вектора е1, затем второго – е2 и т. д. После окончания минимизации по направлению последнего базисного вектора е1 цикл повторяется.
Шаг 0. Выбрать критерий достижений точности величину. найти f(x), положить j =1.
Шаг 1. Решить задачу одномерной минимизации, т.е.
найти. Положить, вычислить .
Шаг 2. Если j <n, то положить x =, j = j+1 и перейти к шагу 1. Иначе — перейти к
шагу 3.
Шаг 3. Проверить условие достижения точности || x — || < или. Если оно выполняется, то положить x* =, f*= и закончить поиск. Иначе — положить x* =,, j = 1 и перейти к шагу 1.
Замечание. Для приближенного решения вспомогательной задачи одномерной минимизации на шаге 1 алгоритма на практике как правило используют метод поразрядного поиска. Эффективность метода циклического покоординатного спуска существенно зависит от свойств целевой функции.
Пример 1. Решить задачу методом циклического покоординатного спуска.
Линии уровни этой целевой функции — окружности с центром в начале координат (рис. 4.5). Выберем произвольную начальную точку х, например х = x°. Очевидно, два шага исчерпывающего спуска сначала по направлению e1, затем – е2 приведут в точку минимума х* = (0,0).
В примере 1 точку минимума функции удалось найти точно за конечное число шагов. Это скорее исключение, чем правило.
Пример 2. Решить задачу методом циклического покоординатного спуска.
Сначала заметим, что поворот системы координат на угол -45° (замена переменных и приводит функцию к виду. Очевидно, линии уровня целевой функции — эллипсы (рис. 4.6). Результаты расчетов по приведенному выше алгоритму представлены в табл.
4.1)
Из рис. 4.4 видно, что минимизирующая последовательность {xk } сходиться к точке минимума x* = (0; 0). Однако, в отличие от решения задачи из примера 1, достижение точки минимума за конечное число шагов не гарантируется. Траектория поиска точки минимума в данной задаче имеет ярко выраженный зигзагообразный характер.