Одношаговый квазиньютоновский метод и сопряженные градиенты

В тех случаях, когда является положительно определенной матрица

вторых производных оценки

, наилучшим считается ньютоновское направление

С использованием этой формулы квадратичные формы минимизируются за один шаг, однако, применять эту формулу трудно по следующим причинам:

1. Время. Поиск всех вторых производных функции
   
   и обращение матрицы
   
   требует больших вычислительных затрат.
2. Память. Для решения задач большой размерности
   
   требуется хранить
   
   элементов матрицы
   
   — это слишком много.
3. Матрица
   
   не всегда является положительно определенной.

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

Простейший и весьма эффективный метод основан на

формуле (Брайден-Флетчер-Гольдфард-Шанно) и использует результаты предыдущего шага. Обозначим:

- направление спуска на -шаге;

- величина шага (-й шаг - сдвиг на );

- градиент функции оценки в начальной точке -го шага;

- изменение градиента в результате -го шага.

- формула для направления спуска на -м шаге имеет вид:

где

- скалярное произведение векторов и .

Если одномерную оптимизацию в поиске шага проводить достаточно точно, то новый градиент

будет практически ортогонален предыдущему направлению спуска, т.е. . При этом формула для упрощается:

Это - формула метода сопряженных градиентов (МСГ), которому требуется достаточно аккуратная одномерная оптимизация при выборе шага.

В описанных методах предполагается, что начальное направление спуска

. После некоторой последовательности из шагов целесообразно возвращаться к наискорейшему спуску - проводить рестарт. Он используется в тех случаях, когда очередное - плохое направление спуска, т.е. движение вдоль него приводит к слишком маленькому шагу либо вообще не дает улучшения.

Содержание раздела

---

---