Методы оптимизации. Азарнова Т.В - 32 стр.

                                       34

Шаг 1. Проверить условия останова и, если они выполнены, вычисления
прекратить и взять точку x k в качестве искомого решения.
Шаг 2. Зафиксировать ненулевой вектор y k в качестве направления
      поиска.
Шаг 3. Выбрать число α k −величину шага.
Шаг 4. Положить x k +1 =x k +α k y k

Для проверки условий останова на шаге 1 на практике часто используются
следующие критерии:
            ||xk+1 - xk||< ε , |f(xk+1) - f(xk)|<ε , || ∇ f ( x k ) ||< ε,
где ε - заданный параметр точности. Кроме того, при практической
реализации эти алгоритмы полезно дополнять "дежурным" критерием
останова k ≤N max , где N max − задаваемое заранее максимальное число
итераций.
В качестве вектора y k на шаге 2 могут выбираться единичные орты
(покоординатный спуск), антиградиент в точке xk (градиентные методы) и
другие направления. Величина шага α k , как правило, выбирается так,
чтобы выполнялось условие          f ( x k +1 ) ≤ f ( x k ) . В частности, чтобы
гарантировать выполнение этого неравенства,                     можно выбирать
                   k    k
α k = arg min f ( x +α y ) ( будем в дальнейшем это называть правилом
       α
наискорейшего спуска). Для численного отыскания        α k может быть
использован один из методов, описанных в предыдущем параграфе.
     Рассмотрим примеры алгоритмов, построенных в соответствии с
предложенной схемой.
                    Метод покоординатного спуска.
     Этот метод заключается в последовательной минимизации целевой
функции f(x) сначала по направлению первого базисного вектора е1 ,затем
второго е2 и т.д. Таким образом, здесь y k =e k , α k выбирается в
соответствии с правилом наискорейшего спуска. После окончания
минимизации по направлению последнего базисного вектора еn цикл может
повторяться. Метод покоординатного спуска может быть методом нулевого
порядка, т.к. он может не использовать в работе производных функции f(x).
Таким образом, он может применяться для оптимизации
недифференцируемых функций.
                                     Алгоритм.
  Шаг 0. Выбрать начальное приближение х0 в пространстве R n ,
           задать параметр точности ε . Найти f(x0),положить j=1.
  Шаг 1. Pешить задачу одномерной минимизации