31. Основы квазиньютоновских методов

Модифицированный метод Ньютона с одномерным поиском (2.5) для минимизации целевой функции с представляется итерационной формулой

, (4.1)

Где – значение параметра одномерной минимизации целевой функции из точки в направлении , – матрица Гессе, – градиент. Модифицированный метод Ньютона – это метод второго порядка. Для многих задач оптимизации вычисление матрицы Гессе, состоящей из вторых частных производных, требует больших затрат машинного времени.

Квазиньютоновские методы также основаны на итерационной формуле (4.1). Однако при вычислении направления одномерного поиска выполняется аппроксимация матрицы Гессе или обратной к ней матрицы с использованием значений градиента. Таким образом, все квазиньютоновские методы – это методы первого порядка.

Рассмотрим принципы построения аппроксимирующей матрицы для обратной матрицы Гессе . Поскольку матрицы и симметрические, то начальное приближение матрицы задается в виде некоторой симметрической положительно определенной матрицы .

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

, .

В точке вычисляется значение градиента целевой функции . Для последующих итераций построение аппроксимирующей матрицы основано на свойстве (3.8) квадратичной функции (3.1) с

. (4.2)

С обозначениями

, (4.3)

Свойство (4.2) примет вид

. (4.4)

Умножая это равенство слева на обратную матрицу Гессе , получим . Если известна аппроксимация матрицы Гессе в точке , то следующее ее приближение в точке должно удовлетворять уравнению

. (4.5)

Это матрично-векторное уравнение называется Квазиньютоновским условием. Оно представляет собой систему линейных алгебраических уравнений. С учетом свойства симметричности матрица имеет

Неизвестных элементов, то есть система линейных алгебраических уравнений (4.5) содержит больше неизвестных, чем уравнений. Для ее решения необходимо дополнительное условие, которое записывается в виде Уравнения коррекции

. (4.6)

Здесь – симметрическая матрица, называемая Поправкой и формируемая так, чтобы выполнялась система уравнений (4.5). Различные квазиньютоновские методы отличаются между собой формулами для поправки .

После определения аппроксимирующей матрицы на последующих итерациях квазиньютоновского метода направление одномерного поиска определяется по формуле

. (4.7)

В этом направлении из точки выполняется одномерный поиск:

, . (4.8)

Итерации продолжаются, пока не выполнится условие окончания процесса оптимизации

,

Где – допустимая погрешность.

Направление поиска (4.7) отличается от направления метода наискорейшего спуска в формуле (1.20) умножением на изменяющуюся на каждой итерации матрицу . Направление (4.7) можно представить как направление метода наискорейшего спуска в пространстве переменных с измененной метрикой. Поэтому квазиньютоновские методы называются также Методами переменной метрики.

< Предыдущая		Следующая >