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

Этот метод является простейшим численным методом безусловной оптимизации целевой функции переменных и основан на одномерной минимизации функции последовательно по каждой из переменных. Метод заключается в последовательном проведении одномерного поиска в направлениях каждой из координатных осей. Для этого задаются единичные векторы – орты координатных осей:

, , …, .

Вначале проводится одномерный поиск из заданной начальной точки в направлении орта , и вычисляется точка минимума функции скалярного аргумента

.

Затем определяется следующая точка поиска

.

Из точки проводится одномерный поиск в направлении орта :

, .

Аналогично проводится одномерный поиск в направлениях всех остальных ортов. После таких одномерных поисков получаем точку

.

На этом первый цикл метода заканчивается, и переходят к следующему циклу. При этом из точки опять проводится одномерный поиск в направлении орта и так далее. Вычисления производятся до тех пор, пока расстояние между лучшими точками последовательных циклов поиска не превысит заданной допустимой погрешности .

Алгоритм метода покоординатного спуска.

Входные параметры: – начальная точка поиска; – процедура вычисления функции; – допустимая погрешность.

Выходной параметр – конечная точка поиска.

1. Положить .

2. Положить , .

3. Вычислить .

4. Положить .

5. Если , то положить и перейти к шагу 3.

6. Если , то перейти к шагу 2.

7. Остановиться.

В этом алгоритме шаги 3–5 производят последовательный одномерный поиск в направлениях ортов осей координат. Шаги 2–6 составляют итерационный цикл метода. Одномерный поиск обычно проводится комбинированным алгоритмом, включающим алгоритм метода Свенна для нахождения интервала неопределенности, содержащего минимум, и один из алгоритмов уменьшения этого интервала. Уменьшение интервала проводится до тех пор, пока точность вычисления параметра не превысит заданного малого числа . Приведенный алгоритм прост в реализации, но эффективен лишь в случаях, когда целевая функция является Сепарабельной, то есть представляет собой сумму функций, каждая из которых зависит лишь от одной переменной.

Пример 1.5. На рис. 1.6 представлена траектория поиска минимума квадратичной функции (1.3) методом циклического покоординатного спуска, включающая все точки поиска. Начальная точка отмечена кругом, конечная точка указана ромбом. Лучшие точки итераций соединены жирной линией. Для нахождения точки минимума с допустимой погрешностью 10–3 метод затратил 9 итераций с двумя одномерными поисками на каждой итерации. Значения целевой функции были вычислены 76 раз.

Здесь и в последующих вычислительных примерах одномерный поиск при начальном единичном шаге и допустимой погрешности производится комбинацией метода Свенна и метода квадратичной интерполяции с тремя точками. Погрешность одномерного поиска задана на два порядка выше допустимой погрешности метода многомерной минимизации . Повышенная точность одномерного поиска используется для сопоставления теоретических свойств методов, обоснованных при условии выполнения точного одномерного поиска, и результатов их численной реализации. Для уменьшения количества вычислений функции и во избежание преждевременного уменьшения шага начальный шаг одномерного поиска задавался как взвешенная сумма двух выполненных предыдущих шагов , начиная со второй итерации при .

Пример 1.6. На рис. 1.7 представлена траектория поиска минимума функции Розенброка (1.4) методом циклического покоординатного спуска, включающая лучшие точки итераций. Процесс минимизации занял 355 итераций и прекратился при уменьшении величины шага до 10–3. Было произведено 3164 вычисления функции. Точка минимума, отмеченная звездочкой, не была найдена.

Рис. 1.6. Минимизация квадратичной функции методом циклического покоординатного спуска

Рис. 1.7. Минимизация функции Розенброка методом покоординатного спуска

Достоинством метода циклического покоординатного спуска является его простота. Недостатком метода является его неэффективность при минимизации овражных функций. Однако это фундаментальный метод многомерной оптимизации, поскольку идея этого метода о последовательном применении одномерного поиска в направлениях используется в других более эффективных методах оптимизации.

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

< Предыдущая		Следующая >