По неравенству Шварца имеем (aTa)(bTb) ³ (aTb)2. Таким образом, чтобы доказать, что xTDj+1x ³ 0, достаточно показать, что pjTqj > 0 и bTb > 0. Из (2) и (3) следует, что
pjTqj = ljdjT[
f(yj+1) – f(yj)]. (6)По предположению
f(yj) ¹ 0, и Dj положительно определена, так что Покажем теперь, что 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 положительно определена, имеемЛемма доказана.
Квадратичный случай.
В дальнейшем нам понадобиться :
Теорема 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.
f(xk+1)Tdj = 0, j = 1, …, k;2.
f(x1)Tdk = f(xk)Tdk;3. xk+1 является оптимальным решением задачи минимизации f(x) при условии
x - x1 Î L(d1, …, dk), где L(d1, …, dk) – линейное подпространство, натянутое на векторы d1, …, dk, то есть
Если целевая функция 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 = -Dj
f(yj), а Dj определяется по формулам (1) – (3). Если f(yj) ¹ 0 для всех j, то направленияДоказательство.
Прежде всего покажем, что для j, такого, что 1 £ j £ n, справедливы следующие утверждения :
1. d1, …, dj линейно независимы.
2. djTHdk = 0 для i ¹ k; i, k £ j.
3. Dj+1Hpk, или, что эквивалентно, Dj+1Hdk = dk для 1 £ k £ j, pk = lkdk.
Проведем доказательство по индукции. Для j = 1 утверждения 1 и 2 очевидны. Чтобы доказать утверждение 3, заметим прежде всего, что для любого k справедливы равенства
Hpk = H(lkdk) = H(yk+1 - yk) =
f(yk+1) – f(yk) = qk. (7)В частности, Hp1 = q1. Таким образом, полагая j = 1 в (1), получаем
,т.е. утверждение 3 справедливо при j = 1.
Теперь предположим, что утверждения 1, 2 и 3 справедливы для j £ n – 1. Покажем, что они также справедливы и для j + 1. Напомним, что по утверждению 1 теоремы 2 diT
f(yj+1) = 0 для i £ j. По индуктивному предположению di = Dj+1Hdi, i £ j. Таким образом, для i £ j имеем0 = diT
f(yj+1) = diTHDj+1 f(yj+1) = –diTHdj+1.Ввиду предположения индукции это равенство показывает, что утверждение 2 также справедливо для j+1.
Теперь покажем, что утверждение 3 справедливо для j+1.
Полагая k £ j+1, имеем
. (8)Учитывая (7) и полагая k = j + 1 в (8), получим, что Dj+2Hpj+1 = pj+1. Теперь пусть k £ j. Так как утверждение 2 справедливо для j + 1, то
pj+1THpk = lklj+1dj+1THdk = 0. (9)
По предположению индукции из (7) и вследствие того, что утверждение 2 справедливо для j + 1, получаем
. (10)Подставляя (9) и (10) в (8) и учитывая предположение индукции, получаем
.
Таким образом, утверждение 3 справедливо для j+1.
Осталось показать, что утверждение 1 справедливо для j+1. Предположим, что
. Умножая это равенство на и учитывая, что утверждение 2 справедливо для j+1, получаем, что . По условию теоремы , а по лемме 1 матрица положительно определена, так что . Так как H положительно определена, то и, следовательно, . Отсюда следует, что , и так как d1, …, dj линейно независимы по предположению индукции, то для i = 1, …, j. Таким образом, d1, …, dj+1 линейно независимы и утверждение 1 справедливо для j+1. Следовательно, утверждения 1, 2 и 3 выполняются. В частности сопряжённость d1, …, dn следует из утверждений 1 и 2, если положить j = n.Пусть теперь j = n в утверждении 3. Тогда
для k = 1, …, n. Если в качестве D взять матрицу, столбцами которой являются векторы d1, …, dn, то . Так как D имеет обратную, то , что возможно только в том случае, если . Наконец, является оптимальным решением по теореме 2.Теорема доказана.
Список литературы.
1. Базара М., Шетти К. «Нелинейное программирование. Теория и алгоритмы». М., 1982.
2. Химмельблау Д. «Прикладное нелинейное программирование». М., 1975.