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

  • Просмотров 4963
  • Скачиваний 284
  • Размер файла 62
    Кб

= Dj1/2qj. Тогда xTDjx = aTa, qjTDjqj = bTb и xTDjqj = aTb. Подставляя эти выражения в (4), получаем : (5) По неравенству Шварца имеем (aTa)(bTb) ³ (aTb)2. Таким образом, чтобы доказать, что xTDj+1x ³ 0, достаточно показать, что pjTqj > 0 и bTb > 0. Из (2) и (3) следует, что pjTqj = ljdjT[j+1) – j)]. (6) По предположениюf(yj) ¹ 0, и Dj положительно определена, так что j)TDjj) > 0. Кроме того, dj – направление спуска, и, следовательно, lj > 0. Тогда из (6) следует, что pjTqj > 0. Кроме того, qj ¹ 0, и ,

следовательно, bTb= qjTDjqj > 0. Покажем теперь, что xTDj+1x > 0. Предположим, что xTDj+1x = 0. Это возможно только в том случае, если (aTa)(bTb) = (aTb)2 и pjTx = 0. Прежде всего заметим, что (aTa)(bTb) = (aTb)2 только при a = lb, т.е. Dj1/2x = lDj1/2qj. Таким образом, x = lqj. Так как x ¹ 0, то l ¹ 0. Далее, 0 = pjTx = l pjTqj противоречит тому, что pjTqj > 0 и l ¹ 0. Следовательно, xTDj+1x > 0, т.е. матрица Dj+1 положительно определена. Поскольку f(yj+1) ¹ 0 и Dj+1 положительно определена, имеем f(yj+1)Tdj+1 =

–f(yj+1)T Dj+1f(yj+1) < 0. Отсюда по теореме 1 следует, что dj+1 – направление спуска. Лемма доказана. Квадратичный случай. В дальнейшем нам понадобиться : Теорема 2. Пусть f(x) = cTx + 1 xTHx, где Н - симметрическая матрица порядка n x n. Рассмотрим Н - сопряженные векторы d1, …, dn и произвольную точку x1. Пусть lk для k = 1, …, n - оптимальное решение задачи минимизации f(xk + ldk) при l Î Е1 и xk+1 = xk + ldk. Тогда для k = 1, …, n справедливы следующие

утверждения : 1. k+1)Tdj = 0, j = 1, …, k; 2. 1)Tdk = k)Tdk; 3. xk+1 является оптимальным решением задачи минимизации f(x) при условии x - x1 Î L(d1, …, dk), где L(d1, …, dk) – линейное подпространство, натянутое на векторы d1, …, dk, то есть В частности, xn+1 – точка минимума функции f на Еn. Если целевая функция f квадратичная, то в соответствии со сформулированной ниже теоремой 3 направления d1, …, dn, генерируемые методом Дэвидона - Флетчера - Пауэлла, являются

сопряженными. Следовательно, в соответствии с утверждением 3 теоремы 2 метод останавливается после завершения одной итерации в оптимальной точке. Кроме того, матрица Dn+1, полученная в конце итерации, совпадает с обратной к матрице Гессе Н. Теорема 3. Пусть Н – симметричная положительно определенная матрица порядка n x n. Рассмотрим задачу минимизации f(x) = cTx + 1 xTHx при условии x Î En. Предположим, что задача решена методом

Дэвидона - Флетчера - Пауэлла при начальной точке y1 и начальной положительно определенной матрице D1. В частности, пусть lj, j = 1, …, n, – оптимальное решение задачи минимизации f(yj + ldj) при l ³ 0 и yj+1 = yj + ljdj, где dj = -Djf(yj), а Dj определяется по формулам (1) – (3). Если f(yj) ¹ 0 для всех j, то направления d1, …, dn являются Н - сопряженными и Dn+1 = H-1. Кроме того, yn+1 является оптимальным решением задачи. Доказательство. Прежде всего покажем, что для j,