Метод Дэвидона-Флетчера-Пауэлла

Преподаватель: Ренин Сергей Васильевич. Дата: 19 октября 1997 года.

Новосибирск Введение.

Первоначально метод был предложен Дэвидоном (Davidon [1959] ) , а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963] ). Метод Дэвидона - Флетчера - Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде - D j f(y). Направление градиента является, таким образом, отклоненным в результате умножения на - D j , где D j - положительно определенная симметрическая матрица порядка n х n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица D j +1 представляется в виде суммы D j и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

Алгоритм Дэвидона - Флетчера - Пауэлла.

Рассмотрим алгоритм Дэвидона - Флетчера - Пауэлла минимизации дифференцируемой функции нескольких переменных. В частности, если функция квадратичная, то, как будет показано позднее, метод вырабатывает сопряженные направления и останавливается после выполнения одной итерации, т.е. после поиска вдоль каждого из сопряженных направлений.

Начальный этап . Пусть > 0 - константа для остановки.

Выбрать точку х 1 и начальную симметрическую положительно определенную матрицу D 1 . Положить y 1 = x 1 , k = j = 1 и перейти к основному этапу.

Основной этап . Шаг 1. Если f(y j ) e , то остановиться; в противном случае положить d j = - D j f(y j ) и взять в качестве l j оптимальное решение задачи минимизации f(y j + l d j ) при l ³ 0. Положить y j+1 = y j + l j d j . Если j n, то перейти к шагу 2. Если j = n, то положить y 1 = x k+1 = y n+1 , заменить k на k+1 , положить j=1 и повторить шаг 1. Шаг 2. Построить D j +1 следующим образом : (1) где p j = l j d j , (2) q j = f(y j+1 ) - f(y j ). (3) Заменить j на j + 1 и перейти к шагу 1. Пример.

Рассмотрим следующую задачу : минимизировать (x 1 - 2) 4 + (x 1 - 2x 2 ) 2 . Результаты вычислений методом Дэвидона - Флетчера - Пауэлла приведены в таблице 1. Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера - Пауэлла.

k	x k f(x k )	j	y j f(y j )	f(y j )	f(y j )	D	d j	l j	y j+1
1	(0.00, 3.00) (52.00)	1 2	(0.00, 3.00) (52.00) (2.70, 1.51) (0.34)	(-44.00, 24.00) (0.73, 1.28)	50.12 1.47		(44.00, -24.00) (-0.67, -1.31)	0.062 0.22	(2.70, 1.51) (2.55, 1.22)
2	(2.55, 1.22) (0.1036)	1 2	(2.55, 1.22) (0.1036) (2.45, 1.27) (0.0490)	(0.89, -0.44) (0.18, 0.36)	0.99 0.40		(-0.89, 0.44) (-0.28, -0.25)	0.11 0.64	(2.45, 1.27) (2.27, 1.11)
3	(2.27, 1.11) (0.008)	1 2	(2.27, 1.11) (0.008) (2.25, 1.13) (0.004)	(0.18, -0.20) (0.04, 0.04)	0.27 0.06		(-0.18, 0.20) (-0.05, -0.03)	0.10 2.64	(2.25, 1.13) (2.12, 1.05)
4	(2.12, 1.05) (0.0005)	1 2	(2.12, 1.05) (0.0005) (2.115, 1.058) (0.0002)	(0.05, -0.08) (0.004, 0.004)	0.09 0.006		(-0.05, 0.08)	0.10	(2.115, 1.058)

Траектория движения, полученная методом, показана на рисунке 1. Рисунок 1. Метод Дэвидона - Флетчера - Пауэлла . Лемма 1 показывает, что каждая матрица D j положительно определена и d j является направлением спуска. Для доказательства леммы нам понадобится : Теорема 1 . Пусть S - непустое множество в Е n , точка x cl S. Конусом возможных направлений в точке x называется множество D = {d : d ¹ 0, x + l d S при всех l (0, d ) для некоторого d > 0}. Определение. Пусть x и y - векторы из Е n и | x T y | - абсолютное значение скалярного произведения x T y . Тогда выполняется следующее неравенство, называемое неравенством Шварца : | x T y | | | x | | | | y | | . Лемма 1. Пусть y 1 Е n , а D 1 – начальная положительно определенная симметрическая матрица. Для j = 1, ..., n положим y j+1 = y j + l j d j , где d j = – D j f(y j ), а l j является оптимальным решением задачи минимизации f(y j + l d j ) при l ³ 0. Пусть, кроме того, для j = 1, ..., n – 1 матрица D j+1 определяется по формулам (1) - (3). Если f(y j ) ¹ 0 для j = 1, ..., n, то матрицы D 1 , ..., D n симметрические и положительно определенные, так что d 1 , ..., d n – направления спуска.

Доказательство.

Проведем доказательство по индукции. При j = 1 матрица D 1 симметрическая и положительно определенная по условию леммы. Кроме того, f(y 1 ) T d 1 = – f(y 1 ) T D 1 f(y 1 ) 0 , так как D 1 положительно определена. Тогда по теореме 1 вектор d 1 определяет направление спуска.

Предположим, что утверждение леммы справедливо для некоторого j n – 1, и покажем, что оно справедливо для j+1. Пусть x – ненулевой вектор из E n , тогда из (1) имеем (4) Так как D j – симметрическая положительно определенная матрица, то существует положительно определенная матрица D j 1 /2 , такая, что D j = D j 1 /2 D j 1 /2 . Пусть a = D j 1 /2 x и b = D j 1 /2 q j . Тогда x T D j x = a T a, q j T D j q j = b T b и x T D j q j = a T b . Подставляя эти выражения в (4), получаем : (5) По неравенству Шварца имеем (a T a)(b T b) ³ (a T b) 2 . Таким образом, чтобы доказать, что x T D j+1 x ³ 0, достаточно показать, что p j T q j > 0 и b T b > 0 . Из (2) и (3) следует, что p j T q j = l j d j T [ j+1 ) – j )]. (6) По предположению f(y j ) ¹ 0, и D j положительно определена, так что j ) T D j j ) > 0. Кроме того, d j – направление спуска, и, следовательно, l j > 0. Тогда из (6) следует, что p j T q j > 0 . Кроме того, q j ¹ 0, и , следовательно, b T b= q j T D j q j > 0 . Покажем теперь, что x T D j+1 x > 0. Предположим, что x T D j+1 x = 0. Это возможно только в том случае, если (a T a)(b T b) = (a T b) 2 и p j T x = 0. Прежде всего заметим, что (a T a)(b T b) = (a T b) 2 только при a = l b , т.е. D j 1 /2 x = l D j 1 /2 q j . Таким образом, x = l q j . Так как x ¹ 0, то l ¹ 0. Далее, 0 = p j T x = l p j T q j противоречит тому, что p j T q j > 0 и l ¹ 0 . Следовательно, x T D j+1 x > 0 , т.е. матрица D j+1 положительно определена.

Поскольку f(y j +1 ) ¹ 0 и D j+1 положительно определена, имеем f(y j +1 ) T d j+1 = – f(y j +1 ) T D j+1 f(y j +1 ) . Отсюда по теореме 1 следует, что d j+1 – направление спуска. Лемма доказана.

Квадратичный случай. В дальнейшем нам понадобиться : Теорема 2. Пусть f(x) = c T x + 1 x T Hx, где Н - симметрическая матрица порядка n x n . Рассмотрим Н - сопряженные векторы d 1 , …, d n и произвольную точку x 1 . Пусть l k для k = , …, n - оптимальное решение задачи минимизации f(x k + l d k ) при l Е 1 и x k+1 = x k + l d k . Тогда для k = 1, …, n справедливы следующие утверждения : 1. k+1 ) T d j = 0, j = 1, …, k ; 2. 1 ) T d k = k ) T d k ; 3. x k+1 является оптимальным решением задачи минимизации f(x) при условии x - x 1 L(d 1 , …, d k ), где L(d 1 , …, d k ) – линейное подпространство, натянутое на векторы d 1 , …, d k , то есть В частности, x n+1 – точка минимума функции f на Е n . Если целевая функция f квадратичная, то в соответствии со сформулированной ниже теоремой 3 направления d 1 , …, d n , генерируемые методом Дэвидона - Флетчера - Пауэлла, являются сопряженными.

Следовательно, в соответствии с утверждением 3 теоремы метод останавливается после завершения одной итерации в оптимальной точке. Кроме того, матрица D n+1 , полученная в конце итерации, совпадает с обратной к матрице Гессе Н. Теорема 3 . Пусть Н – симметричная положительно определенная матрица порядка n x n . Рассмотрим задачу минимизации f(x) = c T x + 1 x T Hx при условии x E n . Предположим, что задача решена методом Дэвидона - Флетчера - Пауэлла при начальной точке y 1 и начальной положительно определенной матрице D 1 . В частности, пусть l j , j = 1, …, n, – оптимальное решение задачи минимизации f(y j + l d j ) при l ³ 0 и y j +1 = y j + l j d j , где d j = -D j f(y j ), а D j определяется по формулам (1) – (3). Если f(y j ) ¹ 0 для всех j , то направления d 1 , …, d n являются Н - сопряженными и D n+1 = H -1 . Кроме того, y n+1 является оптимальным решением задачи.

Доказательство.

Прежде всего покажем, что для j , такого, что 1 j n, справедливы следующие утверждения : 1. d 1 , …, d j линейно независимы. 2. d j T Hd k = 0 для i ¹ k; i, k j. 3. D j+1 Hp k , или, что эквивалентно, D j+1 Hd k = d k для 1 k j, p k = l k d k . Проведем доказательство по индукции. Для j = 1 утверждения 1 и 2 очевидны. Чтобы доказать утверждение 3, заметим прежде всего, что для любого k справедливы равенства Hp k = H( l k d k ) = H(y k+1 - y k ) = k+1 ) – k ) = q k . (7) В частности, Hp 1 = q 1 . Таким образом, полагая j = 1 в (1), получаем т.е. утверждение 3 справедливо при j = 1. Теперь предположим, что утверждения 1, 2 и 3 справедливы для j n – 1. Покажем, что они также справедливы и для j + 1. Напомним, что по утверждению 1 теоремы 2 d i T j+1 ) = 0 для i j. По индуктивному предположению d i = D j+1 Hd i , i j. Таким образом, для i j имеем 0 = d i T j+1 ) = d i T HD j+1 j+1 ) = –d i T Hd j+1 . Ввиду предположения индукции это равенство показывает, что утверждение 2 также справедливо для j+1. Теперь покажем, что утверждение 3 справедливо для j+1. Полагая k j+1, имеем (8) Учитывая (7) и полагая k = j + 1 в (8), получим, что D j+2 Hp j+1 = p j+1 . Теперь пусть k j. Так как утверждение 2 справедливо для j + 1 , то p j+1 T Hp k = l k l j+1 d j+1 T Hd k = 0. (9) По предположению индукции из (7) и вследствие того, что утверждение 2 справедливо для j + 1, получаем . (10) Подставляя (9) и (10) в (8) и учитывая предположение индукции, получаем Таким образом, утверждение 3 справедливо для j+1 . Осталось показать, что утверждение 1 справедливо для j+1 . Предположим, что j+1 , получаем, что положительно определена, так что H положительно определена, то и, следовательно, d 1 , …, d j линейно независимы по предположению индукции, то для i = 1, …, j. Таким образом, d 1 , …, d j +1 линейно независимы и утверждение 1 справедливо для j+1 . Следовательно, утверждения 1, 2 и 3 выполняются. В частности сопряжённость d 1 , …, d n следует из утверждений 1 и 2, если положить j = n. Пусть теперь j = n в утверждении 3. Тогда для k = 1, …, n. Если в качестве D взять матрицу, столбцами которой являются векторы d 1 , …, d n , то D имеет обратную, то является оптимальным решением по теореме 2. Теорема доказана.