ПЗ 8

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

ИУС

2. Общая схема градиентных методов

x
где
k +1
= x − H J ( x )
k
k
H - матричная функция от матрицы Гессе J''
Классические представители семейства:
1. Градиентный метод наискорейшего спуска H = hE,
(где h –ИУС
скаляр, Е – единичная матрица).
2. Метод Ньютона:
''
k −1
H = J (x )

3. Метод наискорейшего спуска

J (x
k +1
) = min J ( x − h J ( x ))
k
k
h
− J (x )
'
k
ИУС
x
k +1
x
k
− J (x
'
k +1
)

4. Упражнение. Доказать, что:

• Угол между соседними звеньями
ломаной, построенной МНС – прямой
• Точки излома траектории спуска
являются точками касания траектории
к соответствующим линиям
ИУС
(поверхностям) уровня

5. Метод простого градиентного спуска:

x
k +1
= x − h J ( x )
k
k
Здесь h – постоянная величина, подбираемая
из условияИУС
убывания функционала.
Это простейшая версия градиентных методов

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

x
k +1
−1
= x − J (x ) J (x )
k
''
k
'
k
(*)
J ( x) = J ( x ) + (( x − x ), J ( x )) +
k
k
'
k
0.5( J ( x )( x − x ), x − x ) + R
''
k
k
k
J ( x) = f ( x) + R , где f (x ) - параболоид
'
Из условия
ИУСf ( x) = 0 получаем (*)
Упражнение: докажите последнее
утверждение

7. Реализация – решение системы линейных алгебраических уравнений:

A x = − J
k
'
k
где
x = x
ИУС
''
A = Jk
k
k +1
−x
k
Обратная матрица не ищется!

8. Геометрическая иллюстрация: одномерный случай

A)
B)
Аппроксимирующие
параболоиды
ИУС
Сходимость
Используется
необходимое
условие
экстремума
Расходимость

9. Невыпуклость в двумерном случае

J
p
p
ИУС
x1
x2
Ньютоновское направление Р здесь указывает
«наверх», а не «вниз»

10. Выпуклый квадратичный случай: минимум находится за один шаг

Упражнение:
р
ИУС
докажите это
утверждение

11. Пример: трудности в реализации метода Ньютона (квадратичный выпуклый случай)

1
1
(b, u )
1
−1
−1 T
x = A b = TD T b = T ........ , T = (u1 , u 2 ,..., u n )
1 (b, u n )
n
0.5
0.50001
5
A = 10 ИУС
; 1 = 1, 2 = 10 + 1
0.5
0.50001
5
После округления: 1 = 0, 2 = 105

12. Обсуждение

• Сам метод Ньютона и основанные на нем
ньютоновские методы широко применяются
на практике
• Решающий недостаток – неприменимость в
невыпуклом случае. Попытки устранить этот
недостаток в некоторых модификациях метода
не вполне успешны
• Реализация метода для овражных (даже
ИУС
выпуклых)
функционалов связана с решением
плохо обусловленных систем линейных
алгебраических уравнений – это тоже
недостаток

13. Задание

• Из вашей начальной точки для вашего
параболоида построить две траектории
спуска: Методом наискорейшего
градиентного спуска (НГС) и методом
Ньютона (МН)
• Траектория НГС должна содержать 5
звеньев ломаной
ИУС привести к результату за
• МН должен
один шаг