Квазиньютоновские методы минимизации

Рассмотрим класс алгоритмов, которые основаны на квадратичной аппроксимации минимизируемой функции Q (х) в Δ-окрестности каждого приближения xr разложением в ряд Тейлора. В связи с тем, что для определения очередного приращения Δr эти алгоритмы требуют вычисления первых и вторых производных функций Q (х), они получили название методов второго порядка.

В том случае, когда гессиан G (хr) является положительно определенной матрицей, приращение Δr, обеспечивающее наибольшую скорость уменьшения функции Q (х) при постоянном значении квадратичной части разложения в ряду Тейлора, определяется из решения экстремальной задачи:

min (∇QTr, Δ) при условии, что ΔTG(хrΔ = К. (5.45)

Оптимальным решением задачи (5.45) является вектор

Δr = — G-1(xr)∇Q(хr), (5.46)

где G-1r) — матрица, обратная гессиану, вычисленному в точке хr.

В тех случаях, когда обращение матрицы G(xr) может привести к большим ошибкам вычисления в силу того, что ее определитель близок к нулю, приращение Δr можно находить из решения системы линейных уравнений:

G(хr)Δ = — ∇Q(хr).

Алгоритм F25, основанный на использовании итерационной формулы (5.45), где процедуры выбора длины шага λr и направления поиска Si совмещены и сводятся к вычислению приращения Δr по формуле (5.46), является реализацией широко распространенного метода Ньютона. Основная идея этого метода заключается в том, что на каждой итерации осуществляется выбор приращения Δr, соответствующего расстоянию до минимального значения квадратичной формы, аппроксимирующей функцию Q (х) в точке xr (рис. 5.2).



Рис. 5.2. Геометрическая интерпретация метода Ньютона с точки зрения квадратичной аппроксимации функции Q(x) в точках х0, x1 и х2 (пунктирные кривые)

При минимизации квадратичной функции Q (х) = хTAx + bTх + a, независимо от значения коэффициента обусловленности матрицы А, метод Ньютона позволяет найти точку минимума х* из любого начального приближения х0 за одну итерацию.

Для нелинейной функции Q (х) точка минимума х* не может быть получена за одну итерацию. Однако направление поиска Δr из (5.46) значительно ближе к направлению на точку минимума х*, чем антиградиент, что и обеспечивает более высокую скорость сходимости метода Ньютона по сравнению с методом наискорейшего спуска.

Недостатком метода Ньютона является требование, чтобы начальное приближение х0 лежало в достаточно малой окрестности точки локального минимума x*. При выполнении этого требования алгоритм обладает квадратичной скоростью сходимости. Однако на практике это условие часто трудно выполнить, в связи с чем при неудачном начальном приближении x0 использование метода F25 может привести к расходящемуся процессу.

Для обеспечения сходимости метода Ньютона к точке минимума х* независимо от значения начального приближения х0 будем определять приращение Δr из выражения

Δr = — λrG-1(xr)∇Q(xr). (5.49)

где длина шага λr является оптимальным решением задачи одномерного поиска:

Q(xr — λrG-1(xr)∇Q(xr) = min Q(xr — λG-1(xr)∇Q(xr). (5.50)

Вместо решения экстремальной задачи (5.50) параметр λr, можно выбирать из условия

Q(xr — λrG-1(xr)∇Q(xr) < Q (хr). (5.51)

Для этого на каждой итерации, начиная о λr = 1, уменьшают значение λr до тех пор, пока не выполнится неравенство (5.51). Если приближение xr находится далеко от точки минимума х*, то длина шага λr, будет выбираться небольшой, при приближении точки хr к точке х* длина шага λr будет стремиться к единице.

Алгоритм F26, основанный на итерационной формуле (5.45), в которой приращение Δr определяется выражением (5.49), а длина шага λr — условием (5.50) или (5.51), называется методом Ньютона с регулируемым шагом.

Общим недостатком методов F25 и F26 является то, что в них процесс поиска минимума х* может расходиться, если гессиан G(хr) не является положительно-определенной матрицей.

Для обеспечения требования, чтобы на каждой итерации гессиан G(хr) был положительно-определенной матрицей, можно использовать следующий прием:

G*(xr) = G (хr) + ρI, (5.52)

где I — единичная матрица; ρ — достаточно большое положительное число. Тогда существует ортогональная матрица V такая, что

VTG*(xr)V = VTG(хr)V + ρI = D(хr) + ρI. (5.53)

где D(хr) — диагональная матрица, элементы которой равны собственным значениям гессиана G (хr).

Алгоритм F27, реализующий метод Ньютона с регулируемым шагом, в котором используется преобразованная матрица G*(xr‘) из (5.52), называется модифицированным методом Ньютона.

Процедура поиска точки минимума х* по алгоритму F27 считается законченной, если выполняется условие:

l|∇Q(xr+1)|| ≤ ε.

Общим недостатком алгоритмов F26 и F27, реализующих различные модификации метода Ньютона F25, является то, что в них требуется вычислять матрицу вторых производных G (хr) и осуществлять обращение этой матрицы. В связи с этим рассмотрим класс алгоритмов, обладающих, так же как и метод Ньютона, квадратичной скоростью сходимости, но не требующих вычисления матриц G(xr) и G-1r). Алгоритмы этого класса основаны на формировании специальным образом последовательности матриц {Нr}. Эта последовательность обладает тем свойством, что каждый ее элемент аппроксимирует на r-м шаге соответствующий элемент матрицы G-1r), но вычисляется только на основании информации о значениях первых производных функций Q (х).

Как было показано выше, для квадратичной функции метод Ньютона F25 позволяет получить точку минимума х* из любого начального приближения (например, хr+1 и хr) за одну итерацию.

Гессиан квадратичной функции являетая симметрической матрицей (A = AT‘), поэтому потребуем, чтобы каждая из матриц Нr также была симметрической. Для того чтобы сохранить это свойство у матрицы Hr+1, необходимо, чтобы для поправки ΔHr выполнялось условие

ΔHr = ΔHrT. (5.64)

В том случае, когда алгоритм поиска образует релаксационную последовательность, говорят, что он устойчив (сходится к точке минимума x*). На практике условие, обеспечивающее устойчивость поиска, выполняется на каждой итерации лишь тогда, когда длина шага Δr определяется из решения одномерной задачи оптимизации min Q{xr — λHr∇Q(xr) точно. В противном случае процесс поиска точки минимума x* может стать расходящимся. Поэтому после проведения n итераций по алгоритму процесс поиска целесообразно «обновлять» («восстанавливать»), т. е. начать сначала, приняв в качестве H0 единичную матрицу I, а в качестве начального приближения х0— точку хn+1.

Теоретическое сравнение методов сопряженных направлений и квазиньютоновских методов минимизаций показывает, что при минимизации квадратичных функций они полностью совпадают. При минимизации нелинейных «овражных» функций квазиньютоновские методы оказываются предпочтительнее методов сопряженных направлений, если «дно оврага» не очень извилистое. Однако их программная реализация требует больших затрат оперативной памяти, чем при реализации методов сопряженных направлений.


Оставить комментарий





Статистика

Рейтинг@Mail.ru