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

1. Задаются координаты начальной точки x ⁽⁰⁾

2. В точке x ^(k), k = 0, 1, 2,... вычисляется значение градиента f'(x ^(k))

3. Определяется величина шага λ_k путем одномерной минимизации по λ функции φ(λ) = f(x^(k) − λf′(x^(k)))

4. Определяются координаты точки x ^(k+1)= x ^(k)−λ_kf'(x ^(k))

5. Проверяются условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

Критерии окончания итераций могут быть следующие

1. условие малости приращения аргумента |x^(k+1) − x^(k)| <ε₁

2. условие малости приращения значения функции |f(x^(k+1)) − f(x^(k))| <ε₂

3. условие малости градиента |f′(x^(k))|<ε₃

Здесь ε₁, ε₂, ε₁ − заданные малые величины. Возможен и комбинированный критерий, состоящий в одновременном выполнении некскольких из указанных выше условий.
К сожалению, надежные критерии окончания счета, которые были бы применимы к широкому классу задач и гарантировали достижение нужной точности, пока неизвестны. По сходимости, метод наискорейшего спуска ничем не отличается от метода спуска по координатам: при попадании траектории спуска в истинный овраг счет останавливается, а в разрешимом овраге сильно замедляется.
В некоторых случаях величина шага нормируется по модулю градиента, в результате чего в расчетные формулы входят не значения компонент вектора-градиента, а направляющие косинусы этих компонент. В других случаях скорость спуска, наоборот, увеличивается на каждой итерации для того, чтобы "побыстрее добежать" до дна.

11.8.3.3. Метод дробления шага
Метод дробления шага применяется в ситуациях, когда нерегулируемый шаг приводит к постоянному прыганию над лункой по принципу: туда-сюда, туда-сюда. В этом случае необходимо уменьшить размер шага до такой степени, чтобы не перепрыгнуть лунку.
Выбираются две константы, α и β, такие, что α>0 и 0<β<1. Для коэффициента λ=α проверяется выполнение условия
f(x^(k) − λf′(x^(k))) <f(x^(k))
Если оно выполнено, то полагается λ^(k)=α. Если нет, то производится дробление шага, т.е. принимается λ=αβ и вновь проверяестся выполнение условия f(x^(k) − λf′(x^(k))) <f(x^(k)). Процесс дробления, т.е. умножения текущего значения λ на β, продолжается до тех пор, пока условие уменьшения значения функции на шаге не окажется выполненным. Очевидно, что этот процесс не может быть бесконечным, потому что направление антиградиента задает направление убывания функции. Первое же значение λ, при котром условие уменьшения значения функции выполняется, и принимается за λ^(k).

11.8.3.4. Метод спуска с ускорением
В обратном предельном случае может возникнуть ситуация, при которой спуск в направлении антиградиента идет успешно, но чрезвычайно медленно. Образно выражаясь, можно сказать, что в этом случае мы спускаемся в долину по очень пологой тропе, и шаг наш слишком мал, чтобы осуществить быстрый спуск. В этом случае можно побежать по дороге вприпрыжкуу, постоянно увеличивая скорость бега.
Для улучшения метода наискорейшего спуска предлагают самые разнообразные поправки к алгоритму: например, совершают по каждому направлению спуск не точно до минимума. В некоторых случаях по направлению антиградиента делается только один маленький шаг, после чего меняют направление спуска. Это приводит к движению по некоторой кривой r (t), являющейся решением системы обыкновенных дифференциальных уравнений d r /dt=−gradФ(r (t)). Вдоль этой кривой dФ/dt=dФ/d r d r /dt=−(gradФ)²<0, т.е. функция гарантированно убывает. Недостатком такого метода является необходимость дополнительного интегрирования системы дифференциальных уравнений, что сильно отягощает алгоритм.
В более упрощенном варианте шаг может увеличиваться на каждой итерации на некоторую заданную величину до тех пор, пока не будет нарушено условие
f(x^(k) − λf′(x^(k)))<f(x^(k))
После этого пересчитывается градиент и направление спуска изменяется, причем шаг опять начинает увеличиваться от некоторого начального значения, являющегося в данном случае параметром метода.

Метод Ньютона

Линеаризация функции

Введем обозначения: пусть f(x) функция n-переменных, т.е. x=x₁,x₂,...,x_n. Разложим функцию f(x) в ряд Тейлора вблизи точки k-того приближения x^(k).
f(x) = f(x^(k)) + f′(x^(k))·(x − x^(k)) + (1/2)·f″(x^(k))·(x − x^(k))² +...
Здесь f′ − вектор первых производных в точке x^(k), f″(x^(k)) − Матрица Гессе функции в точке x^(k). Продифференцируем обе части этог разложения по x:
f′(x) = f′(x^(k)) + f″(x^(k))·(x − x^(k)) +...
Для того чтобы найти очередное, (k+1)-ое приближение, воспользуемся необходимым условием экстремума функции многих переменных
f′(x^(k+1)) = f′(x^(k)) + f″(x^(k))·(x^(k+1) − x^(k)) +... = 0
Если ограничиться в этом разложении первыми двумя членами разложения, получим
f′(x^(k)) + f″(x^(k))·(x^(k+1) − x^(k)) = 0
Этот шаг иногда называют линеаризацией, а сам метод Ньютона − методом линеаризации. Если речь идет о функции одной переменной, то можно выразить из полученного выражения (k+1)-ое приближение в виде: x^(k+1) = x^(k) − f′(x^(k))/f″(x^(k)), который совпадает с аналогичным выражением для случая скалярной функции, полученным в п. 8.3.6 лекции 8.
Однако в данном случае речь идет о функции n переменных f(x₁,x₂,...,x_n). В этом случае мы имеем не одно уравнение относительно одной неизвестной, из которого легко выразить это неизвестное, а линейную систему из n алгебраических уравнений относительно неизвестного вектора x^(k+1) = (x_1(k+1),x_2(k+1),...,x_n(k+1)):
f″(x^(k))·(x^(k+1) − x^(k)) = −f′(x^(k))
Матрица системы представляет собой матрицу Гессе функции f(x) в точке k-того приближения, а правая часть − антиградиент этой функции в той же точке. Если Матрица Гессе невырождена (гессиан не равен нулю), то полученная система уравнений имеет единственное решение, которое можно найти численным методом решения систем линейных уравнений (метод Гаусса, формулы Крамера, матричный метод и др.).
Решение полученной системы уравнений может быть представлено также в виде:
x^(k+1) = x^(k) − [f″(x^(k))]⁻¹f′(x^(k))
где [f″(x^(k))]⁻¹ − матрица, обратная матрице Гессе функции f(x) в точке k-того приближения x^(k). Заметим, что в одномерном случае это выражение совпадает с аналогичным выражением, полученным п. 8.3.6 лекции 8 и по этой причине может рассматриваться как его обощение на случай n переменных.
В литературе такой итерационный процесс иногда называют методом Ньютона−Рафсона.