Численные методы оптимизации (продолжение).

Метод сопряженных градиентов (МСГ).

Этот метод относится к группе методов сопряженных направлений (МСН).

Подобно градиентным методам МСГ является методом многомерной безусловной оптимизации первого порядка. Однако, в отличие от градиентных методов, МСГ имеют скорость сходимости более высокую; при некоторых предположениях о свойствах целевой функции скорость сходимости МСГ равна скорости сходимости МН (с квадратичной скоростью сходимости).

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

 

А. Сопряженность и сопряженные направления. Итерационная формула методов сопряженных направлений.

Система линейно независимых векторов образует систему сопряженного направления:

, , (1)

(т.е. скалярное произведение (1) равно 0).

Условие (1) представляет сопряженность векторов и относительно матрицы .

Предположим, что матрица - единичная, тогда (1) преобразуется к виду: , , . (2)

Очевидно, что (2) является условием ортогональности векторов.

Понятие ортогональности векторов является в частном случае по отношению к понятию " сопряженность векторов".

Итерационная формула методов сопряженных направлений имеет вид:

, (3)

где определяется в результате решения оптимизационной задачи:

(4)

и векторы образуют систему сопряженных направлений, т.е.:

 

 

, , (5)

 

Б. Теорема о минимизации квадратичной формы переменных методом сопряженных направлений не более чем за шагов.

Теорема: Квадратичная форма переменных

, (1)

- симметрична, положительно определяется размерности матрица квадратичной формы. Методом сопряженных направлений с известными формулами:

, (2)

(3)

, , (4)

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

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

Преобразуем (1) для целевой функции квадратичной формы таким образом, чтобы в нем присутствовал параметр .

(5)

Для решения задачи минимизации необходимо решить уравнение: . (6)

Из (6) с учетом (5) легко получить уравнение для :

. (7)

Из (7) с очевидностью следует:

. (8)

Учитывая, что (9) получаем выражение для из (8) в виде:

 

ЛК №2

10.03.2003

 

. (10)

Далее представим выражение для в виде, удобном для реализации доказательства второй части доказательства:

(11)

Заметим, что в (11) определяющая значение вектора определяется по формуле (10).

Формулы (10), (11) завершают первую часть доказательства теоремы.

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

Поскольку система векторов - линейно независимая система векторов, образующая базис в пространстве . Поэтому правомерно выражение:

; (12)

. (13)

Легко понять, что если будет доказано равенство (14), то будет доказана и сформулированная выше теорема, т.е. равенство . (15)

Поскольку выражения для существуют – это выражение (10), то следует получить выражение для , используя (12) или (13).

Умножим слева обе части (12) на матрицу (квадратичную форму), а затем скалярно на вектор :

. (16)

Преобразуем (16) используя известные выражения:

. (17)

Левая часть станет в виде:

 

. (18)

Правая часть с учетом известности сопряженности векторов:

, (19)

. (20)

Приравнивая (18) и (20) находим :

. (21)

Как видно из (10) и (21), известное равенство будет выполняться, если будет доказано равенство числителей в (10) и (21), т.е. будет доказано равенство вида:

. (22)

Преобразуем (22) используя известное выражение:

(23) – выражение для градиента квадратичной формы.

- итерационная формула МСН. (24)

(25)

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

Для реализации МСН необходимо построить систему сопряженных направлений .

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: