НТУУ «Киевский политехнический институт»
Факультет Электроники
Кафедра Электронных приборов и устройств
Вычислительная математика
Й семестр
Индивидуальное практическое задание №14
По теме: «Метод скорейшего спуска (градиента) для решения системы нелинейных уравнений»
Выполнил: ст. гр. ДЕ-72
Щерба Станислав Витальевич
Градиентный спуск — метод нахождения локального минимума (максимума) функции с помощью движения вдоль антиградиента (градиента). Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
Пусть целевая функция имеет вид:
И задача оптимизации задана следующим образом:
Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом 
:
где λ[j] выбирается
— постоянной, в этом случае метод может расходиться;
— дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
— наискорейшим спуском: 
Алгоритм
Задают начальное приближение и точность расчёта 
Рассчитывают , где
Проверяют условие останова:
Если 
, то j = j + 1 и переход к шагу 2.
Иначе 
и останов.
Пример
Применим градиентный метод к функции
Тогда последовательные приближения будут выглядеть так:
Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.
Градиентный метод с дроблением шага.
В этом варианте градиентного метода величина шага α n на каждой итерации выбирается из условия выполнения неравенства
| f (xn +1) = f (xn - a nf ¢(xn)) £ f (xn) - ea n || f ¢(xn)||2, |
где e Î (0, 1) — некоторая заранее выбранная константа. Условие гарантирует (если, конечно, такие a n удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого a n обычно оформляют так.
Выбирается число d Î (0, 1) и некоторый начальный шаг a0. Теперь для каждого n полагают a n = a0 и делают шаг градиентного метода. Если с таким a n условие выполняется, то переходят к следующему n. Если же условие не выполняется, то умножают a n на d ("дробят шаг") и повторяют эту процедуру до тех пор пока равенство
| f ¢(xn) = | ò | 1 0 | f ¢¢[ x * + s (xn - x *)](xn - x *) ds |
не будет выполняться. В условиях теоремы об условной сходимости градиентного метода с постоянным шагом эта процедура для каждого n за конечное число шагов приводит к нужному a n.
Можно показать, что в условиях теоремы (о линейной сходимости градиентного метода с постоянным щагом) градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора a на каждом шаге, заменяя ее на проблему выбора параметров e, d и a0, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
Метод наискорейшего спуска.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = { x Î R m: x = xn - a f ¢(xn); a ³ 0}:
| a n = argminaÎ[0, ¥) f (xn - a f ¢(xn)). |
Рис. 1
Другими словами, a n выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис.1). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция j: a ® f (xn - a f ¢(xn)) достигает минимума при a = a n, точка a n является стационарной точкой функции j:
|
| = (f ¢(xn - a nf ¢(xn)), - f ¢(xn)) = -(f ¢(xn +1), f ¢(xn)). |
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.