Нейрокомпьютерные системы

       

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


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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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



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