Градиентные методы спуска

Определение минимального значения многопараметрической функции Q (х), заданной в n-мерном евклидовом пространстве связано с решением задачи безусловной оптимизации:

min Q(x1, х2,…, xn). (5.1)

Здесь каждая переменная xi, i= 1, 2, …, n, может принимать значения от -∞ до +∞. Предположим, что функция Q (х) является унимодальной функцией, для которой в каждой точке х может быть получено с помощью градиента ∇Q(х)= {∂Q/∂x1, …, ∂Q/∂xn), а при необходимости и гессиана (матрицы вторых производных)

G(х) = {∂2Q/∂xi∂xj}.

Рассмотрим класс алгоритмов, осуществляющих последовательный поиск точки минимума х* функции Q (х) из заданного начального приближения х° по итерационной формуле

xr+1 = xr + Δr = xr + λrSr, r = 0,1,… (5.2)

где xr — приближенное решение задачи (5.1), полученное на r-й итерации; Δr= (хr+1 — хr) — приращение варьируемых параметров на r-й итерации; Sr — единичное направление, ведущее к уменьшению функции Q (х); λr — длина шага вдоль направления Sr. Последовательность точек испытаний {хr}, полученная по формуле (5,2) и удовлетворяющая цепочке неравенств

Q(х0) > Q(x1) > … > Q (xk). (5.3)

называется релаксационной последовательностью.

Разложим функцию Q (х) относительно точки хr в ряд Тейлора, ограничиваясь членами первого порядка

Q(xr+1) ≈ Q(xr) + (∇QT(xr), Δr). (5.4)

Из условия (5.3) следует, что на каждой итерации приращение А’ должно выбираться таким образом, чтобы выполнялось неравенство: Q (хr+1) — Q (хr) < 0. Учитывая соотношение (5.4), получаем, что

(∇QT(xr), Δr) = λr(∇QT(xr), Sr) < 0. (5.5)

Для обеспечения наибольшей скорости уменьшения функции Q (х) вдоль единичного направления последнее должно совпадать с нормализованным значением антиградиента:

Sr = -∇Q(xr)/||∇Q(xr||. (5.6)

Из (5.4) с учетом неравенства (5.5) следует, что единичное направление Sr, обеспечивающее наибольшую скорость уменьшения функции Q (х), является решением экстремальной задачи

min (∇QT(xr), S) при условии что (ST‘, S)= 1.

Методы построения релаксационной последовательности (5.3) с помощью итерационной формулы (5.2), в которой направление поиска Sr зависит от значения антиградиента, называются градиентными методами спуска. При заданном направлении поиска Sr выбор точки очередного испытания согласно (5.2) сводится к определению положительного значения шага λr вдоль этого направления. Реализация градиентного метода спуска, в которой оптимальная длина шага λr вдоль направления антиградиента (5.6) является решением одномерной задачи минимизации:

Q{xr + λrSr) = min Q(xr + λSr), (6.10)

называется методом наискорейшего спуска.

Алгоритмы, реализующие метод наискорейшего спуска, отличаются друг от друга способом. решения экстремальной задачи (5.10). Если функция Q (х) является дважды дифференцируемой (Q(х)∈С2), то ее можно аппроксимировать в точке (r + 1)-го приближения полиномом второй степени

Q(xr+1) ≈ Q (хr) + λr(∇QTr), Sr) + λr2(Sr)TG(хr)Sr.

Отсюда получаем, что оптимальным решением задачи (5.10) является выражение

λr = —(∇QTr), Sr)/(Sr)TG(хr)Sr. (5.13)

Достоинством метода наискорейшего спуска является его простота. Однако он имеет ряд существенных недостатков, среди которых необходимо отметить следующие. Во-первых, это — одношаговый метод, в котором при выборе точки очередного испытания хr+1 не используется информация о предыдущих испытаниях, кроме испытания в точке xr. Во-вторых, если гессиан G (х) минимизируемой функции Q (х) является плохо обусловленной матрицей, наименьшее и наибольшее собственные значения которой сильно отличаются друг от друга, то процесс поиска замедляется в связи с зигзагообразностью траектории проводимых испытаний х0, х1,…,хk (рис. 5.1).



Рис. 5.1. Зигзагообразная траектория приближения к точке минимума x* квадратичной функции с помощью метода наискорейшего спуска

При этом может потребоваться недопустимо большое число итераций, прежде чем будет получена требуемая точность локализации точки локального минимума х*.
Q(x) = xTAx+bTx + a

Рассмотренное свойство метода привод к тому, что он позволяет получить оптимальное решение х* задачи безусловной минимизаций (5.1) за конечное число итераций и в качестве условия окончания поиска обычно используется неравенство

||∇Q(xr)|| ≤ ε.

Для устранения недостатка метода F22, связанного с игнорированием информации о предыдущих испытаниях, рассмотрим алгоритм, реализующий градиентный метод с памятью, в котором при выборе очередного приращения Δr учитывается информация о приращении Δr-1 на предыдущем шаге. Для этого потребуем, чтобы на каждой итерации приращение Δr выбиралось таким образом, чтобы обеспечивалась наибольшая скорость уменьшения функции Q (х) при условии, что квадрат модуля разности приращения Δr и взвешенного приращения βΔr-1 оставался равным постоянной величине К:

min (∇QT(xr), Δ). (5.17)

Оптимальным решением задачи (5.17) является линейная комбинация антиградиента функции Q (х), вычисленного в точке хr и приращения, полученного на предыдущей итерации:

Δr = — λr∇Q(xr) + βrΔr-1. (5.18)

Значения коэффициентов λr и βr в формуле (5.18), полученной для построения очередного приращения Δr, могут быть выбраны из условия обеспечения минимального значения функцир Q (х) вдоль направления Δr:

Q(xr — λr∇Q(xr) + βrΔr-1) = min Q (r — λr∇Q(xr) + βrΔr-1). (5.21)

Алгоритмы, реализующие градиентный метод в памятью, отличаются друг от друга способом решения экстремальной задачи (5.21). В качестве одного из подходов к численному решению задачи (5.21) рассмотрим метод квазилинеризации решения эквивалентной ей системы нелинейных уравнений.

О градиентных методах спуска, которые позволяют найтаточку минимума x* = (х1, …, x1) квадратичной функции (5.14) не больше, чем за n итераций, говорят, что они обладают квадратичной скоростью сходимости. Более подробно методы локальной оптимизации, обладающие квадратичной скоростью сходимости, будут рассмотрены в следующем посте.


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





Статистика

Рейтинг@Mail.ru