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

Согласно этому методу направления спуска выбирается параллельно координатным осям. Т.е. сначала спуск осуществляется вдоль первой оси ОХ1, затем вдоль оси ОХ2 и т.д. до последней оси ОХn. Потом эти действия повторяются в цикле вплоть до достижения оптимума. Варианты метода отличаются выбором шага a. На рис. 1.7. приведена схема метода циклического покоординатного спуска с постоянным шагом.

Пусть x(0) – начальная точка, a – некоторое положительное число, выбранное как начальное значение шага. Вычисляют значение функции в этой точке f(x(0)). Далее вычисляют значение функции при измененном значении аргумента x1=x1+a. Если значение функции уменьшилось, то полагают, что точка первого приближения x(1) сдвинута от начальной точки в направлении оси ОХ1 на величину a.

Рис. 1.7. Геометрическая интерпретация метода циклического покоординатного спуска с постоянным (малым) шагом

Иначе вычисляют значение функции при x1=x1-a. Если значение функции уменьшилось, то полагают, что точка первого приближения x(1) сдвинута от начальной точки против направления оси ОХ1 на величину a. Если и в этом направлении значение функции не уменьшилось то точку не сдвигают из начального направления вдоль оси ОХ1 .

Аналогичным образом осуществляют передвижение точки вдоль других осей. В этом состоит первая итерация. Если в результате одной итерации точка не сдвинулась из того положения, где она находилась до начала цикла по координатным осям, следует уменьшить величину шага, например разделив его на 2. Схема сходимости таких модификаций метода циклического покоординатного спуска приведена на рис. 1.8

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

Рис. 1.8. Геометрическая интерпретация метода циклического покоординатного спуска с дробным шагом

Рис. 1.9. Схема сходимости метода циклического покоординатного спуска с решением задачи одномерной оптимизации на каждом шаге

На рис. 1.9а показан один шаг итерации, состоящий из двух этапов. Сначала фиксируется значение координаты х2 и решается задача одномерной оптимизации по координате х1. Т. е. определяется минимум одномерной функции, изображенной на выносном графике слева. Далее фиксируется значений координаты х1, сообщающее минимум этой функции. И отыскивается минимум однопараметрической функции, график которой показан на выносном элементе внизу.

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

Рис. 1.10 "Застревание" покоординатного спуска на дне оврага (а) и схема сходимости при благоприятной ориентации осей оврага (б)

В то же время при благоприятной ориентации дна оврага, а именно при положении одной из координатных осей, близком к параллельности с дном оврага, поиск оказывается весьма быстрым. Эта ситуация показана на рис. 1.10б.