1.4. Многошаговые ( двухшаговые ) методы.
1.3.1. Метод тяжелого шарика
Общий вид метода тяжелого шарика:
xk+1= xk - f(xk)+(xk-xk-1)
Это разностное уравнение, полученное из дифференциального уравнения, которое описывает движение шарика, катящегося по некоторой поверхности с постоянным трением. Введение инерции (xk-xk-1) увеличивает скорость сходимости.
Теорема(о скорости сходимости метода тяжелого шарика):
Пусть 0 l I 2f(x) L I (сильная выпуклость)
0 1, 0 2(1+)/L,
тогда
существует с=const
такая, что || xk
- x*
||
cqk
,
Без доказательства
Таким образом, метод сходится не быстрее геометрической прогрессии, как и градиентный метод; показатель геометрической прогрессии тот же, только с корнями, т.е. применение двухшагового метода при плохой обусловленности позволяет уменьшить эту обусловленность.
Модификация двухшагового метода- метод сопряженных градиентов.
1.3.2. Метод сопряженных градиентов
xk+1 = xk - k f(xk) + k (xk-xk-1)
Отличается тем, что î k è k зависят от шага и выбираются следующим образом:
(k , k) = argmin f(xk - f(xk)+(xk-xk-1))
{,}
Для
квадратичной функции
Метод сходится за конечное число шагов, не превосходящее размерности пространства состояний.
Градиенты в методе попарно ортогональны (f(xi), f(xk))=0, ik
Но в Rn не может существовать более n ортогональных ненулевых векторов, поэтому для некоторого k n будет f(xk)=0, то есть точка xk- точка минимума.
Последовательные направления движения pk=xk-xk-1 удовлетворяют соотношению (Api, pj ) =0 ij
Определение:
Векторы pi , связанные соотношением (Api, pj ) =0, называются сопряженными или А-ортогональными.
В методе сопряженных градиентов xk является точкой минимума квадратичной функции f(x) на подпространстве, порожденном первыми k градиентами. Следовательно, никакой метод, использующий только градиенты функции (точнее, в котором шаг делается по линейной комбинации предыдущих градиентов), не может сходиться быстрее, то есть метод сопряжённых градиентов является оптимальным по скорости сходимости в классе методов первого порядка.
1.3.3. Модификация Полака-Ривьера
xk+1= xk+ kpk , где k = argmin f(xk+ pk ), >0
pk= -f(xk)+kpk-1
0
= 0
Для квадратичной функции последовательность точек xi, определённая этими формулами, совпадает с последовательностью, полученной методом сопряжённых градиентов.
Эту модификацию удобнее применять для произвольных (неквадратичных) функций.
Рекомендуется применять процедуру обновления, т.е. через каждые n-шагов происходит сдвиг в направлении антиградиента.
То есть 0 = 0, затем n=0,..., mn=0, следовательно, pk= -f(xk)+0*pk-1= -f(xk)
(сдвиг в направлении антиградиента).
По скорости сходимости n шагов методы сопряженного градиента эквивалентны одному шагу метода Ньютона (для квадратичной функции метод сходится за один шаг).
1.5. Квазиньютоновские методы
Общая структура: xk+1 = xk - kkf(xk)
Если Hk =I , то это градиентный метод.
Если Hk = (2f(xk))-1, то это метод Ньютона.
Если Hk = Hk (f(xi), i=1..k) (2f(xk))-1, т.е. матрица Hk пересчитывается рекурентным способом на основе информации, полученной на k-й итерации.
Достоинство:
Не надо вычислять обратную матрицу вторых производных.
Обозначим pk = -Hkf(xk)
yk= f(xk+1) -f(xk),
,
A>0
Тогда для квадратичной функции имеем
yk = A(xk+1-xk) = kApk
k pk = ykA-1,
поэтому матрицу Hk+1 (необязательно для квадратичной функции) выбирают так, чтобы выполнялось так называемое квазиньютоновское условие:
Hk+1yk= kpk (Hk - должна стремиться к (2f(xk))-1
Проверим выполнение квазиньютоновского условия:
Для квадратичной функции метод сходится за n шагов, ãäå n – размерность пространства состояний. Скорость сходимости этого метода сверхлинейная (быстрее любой геометрической прогрессии). Сходимость глобальная. Объединяет достоинства градиентных методов и метода Ньютона.
Процедура применения:
На очередном шаге, имея Hk, делаем шаг в направлении pk. Получаем k (например, по методу наискорейшего спуска), получаем xk+1 , вычисляем yk и пересчитываем Hk+1 для следующего шага.
Недостаток: (по сравнению с методом сопряженных градиентов). Надо хранить и пересчитывать Hk размерности mn.
Метод Бройдена-Флетчера –Шенно.
где
Примечание:
Последовательности xk, генерируемые каждым вариантом, для квадратичной функции совпадают. Существует много других модификаций приведенных квазиньютоновских методов.