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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-шаге;

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

- величина

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

шага (

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

-й шаг - сдвиг на

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

);

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

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

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

-го шага;

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

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

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

-го шага.

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

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

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

-м шаге имеет вид:

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

где

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

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

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

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

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

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

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

. При этом формула для

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

упрощается:

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

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

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

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

. После некоторой последовательности из

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

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

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

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

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

Главная сайта