Методы градиентного спуска

Общая схема градиентных методов.
Понятие функции релаксации

Пусть решается задача

(5.1)

Рассмотрим класс матричных градиентных методов вида

(5.2)

где — матричная функция от Предполагается, что в некоторой -окрестности точки функционал J (x) достаточно точно аппроксимируется параболоидом

(5.3)

где — симметричная, не обязательно положительно определенная матрица. Без существенного ограничения общности можно считать, что Действительно, полагая получим представление

(5.4)

При этом константа может не учитываться как не влияющая на процесс оптимизации.

Формула (5.2) обладает свойством инвариантности относительно смещения начала координат: будучи записанной для f (x), она преобразуется в аналогичное соотношение для f 1(z). А именно, имеем для f (x)

(5.5)

Полагая получим из (5.5): А это есть запись метода (5.2) для функционала f 1.

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

Определение 5.1. Скалярная функция называется функцией релаксации метода (5.2), а ее значения R h (λ i) на спектре матрицы — множителями релаксации для точки .

В ряде случаев для сокращения записи индекс «h» в выражении для функции релаксации будет опускаться.

Здесь Н (λ, h) означает скалярную зависимость, отвечающую матричной функции H (G, h) в представлении (5.2).

Если G — симметричная матрица и

G = T diag (λ1, λ2,... λ n) T T,

где Т — ортогональная матрица, столбцы которой есть собственные векторы матрицы G, то любая матричная функция F (G) представима в виде

F (G) = T diag(F (λ1), F (λ2),... F (λ n)) T T,

Матричная функция F (G) имеет смысл, если скалярная функция F (λ) определена в точках λ1, λ2,... λ n.

Теорема 5.1. Для выполнения условия

(5.6)

при необходимо и достаточно, чтобы

(5.7)

для всех собственных чисел λ i, i ∈ [1: n ], матрицы .

Замечание 1. Для строгого выполнения неравенства (5.6) необходимо и достаточно кроме (5.7) потребовать, чтобы существовал такой i = i 0, для которого и соответствующее неравенство (5.7) было строгим.

Замечание 2. Выражения (5.8) позволяют оценить скорость убывания функционала f в зависимости от «запаса», с которым выполняются неравенства (5.7). Действительно, обозначим через положительные и отрицательные собственные числа матрицы . Этими же индексами снабдим соответствующие собственные векторы. Суммирование по соответствующим i будем обозначать Σ+, Σ–. Тогда

Из полученного выражения следует, что наибольшее подавление будут испытывать слагаемые, для которых значение множителя релаксации наиболее существенно отличается от единицы (при выполнении условий (5.7)).

Далее будут рассматриваться в основном зависимости Rh (λ), обладающие свойством

Rh (λ) → 1, h → 0, (5.9)

В этом случае из равенства

следует, что для всегда можно выбрать такой , что Таким образом, с помощью параметра можно регулировать норму вектора продвижения в пространстве управляемых параметров с целью предотвращения выхода из области справедливости локальной квадратичной модели (5.3).

Иногда для ограничения нормы (5.10) параметр h может вводиться в схему оптимизации как множитель в правой части (5.2):

(5.11)

При этом а второе равенство (5.8) трансформируется к виду

где Таким образом, новые множители релаксации принимают промежуточные значения между 1 и R (λ i), что и требуется для обеспечения свойства релаксационности, определяемого требованиями (5.9).

Введенное понятие функции релаксации позволяет с единых позиций оценить локальные свойства различных градиентных схем поиска. Удобство такого подхода заключается также в возможности использования наглядных геометрических представлений. Подобно областям устойчивости методов численного интегрирования обыкновенных дифференциальных уравнений, построенных на основе «тестового» (линейного, скалярного) уравнения, мы можем для любого метода (5.2) построить функцию релаксации, характеризующую область его релаксационности в множестве собственных чисел матрицы Гессе аппроксимирующего параболоида. При этом роль тестового функционала играет квадратичная зависимость (5.3). Требуемый характер функции релаксации представлен на рис. 5.1; заштрихована «запрещенная» область, где условия релаксационности (5.7) не выполняются.

Рис. 5.1. Общий вид функции релаксации

Важное свойство функций релаксации заключается в возможности использования соответствующих представлений для синтеза новых процедур (5.2), обладающих некоторыми желательными свойствами при решении конкретных классов задач параметрической оптимизации.