Методы безусловной многомерной оптимизации. Шипилов С.А. - 5 стр.

                                       5
        4.1. Методы на основе пошаговой одномерной оптимизации

           4.1.1. Метод Гаусса- Зейделя (покоординатного спуска)
      В основу метода Гаусса- Зейделя положены принципы более раннего ме-
тода поочередного изменения переменных. Идея последнего заключается в сле-
дующем: из начальной точки делается шаг по первой переменной, если он
«удачный», то переходят к следующей переменной. Если шаг оказался «не-
удачным», то делается шаг в противоположном направлении. Эта процедура
повторяется до тех пор, пока во всех направлениях не будут получаться одни
«неудачные шаги». В этом случае величина шага уменьшается. Поиск продол-
жается до тех пор, пока абсолютное значение величины шага оказывается
меньше заданной точности.
      В методе Гаусса- Зейделя при выполнении шага по каждой переменной
ищут минимум целевой функции в ее направлении, при этом значения осталь-
ных переменных остаются постоянными. Этот поиск по направлению можно
производить любым известным методом одномерной оптимизации ( например,
методом обратного переменного шага, методом «золотого сечения» и т.п.). Та-
ким образом, в методе Гаусса-Зейделя задача многомерной оптимизации сво-
дится к многократному использованию метода одномерной оптимизации. Оче-
редность варьирования переменных при этом устанавливается произвольно и
обычно не меняется в процессе оптимизации.
      Таким образом, алгоритм метода заключается в следующем.
    1. Для некоторого начального значения x(0) фиксируют все координаты
       вектора x , кроме одной (для определенности x1) и проводят операцию
       одномерного поиска минимума функции F(x1)=f(x1, x2(0), x3(0), … xn(0)),
       в результате чего получают точку x(1)=(x1*, x2(0), x3(0), … xn(0)), где
        x1* = arg min F ( x1 ) .
                 x1
    2. Фиксируя в точке x(1) все координаты кроме второй, повторяют п. 1 по
       x2. И так до последней составляющей xn. Цикл алгоритма завершается
       после n – кратной операции одномерной оптимизации вдоль каждой из
       координат, после чего этот цикл повторяют, получая точки x(1), x(2), …, в
       каждой из которых значение целевой функции не больше, чем в преды-
       дущей.
      Условием прекращения вычислительной процедуры при достижении за-
данной точности ε может служить неравенство x ( k ) − x ( k −1) < ε . При пошаго-
вом движении, например, в алгоритме поочередного изменения переменных
поиск прекращается в точке, для которой x(k) совпало с x(k-1), т.е. цикл оказался
нерезультативным.
      Недостатком метода Гаусса-Зейделя является жесткое направление изме-
нения каждой из составляющих решения, не зависящее от характера функции,
что может привести к неоправданной остановке алгоритма в случае “овраж-
ных” функций.