Метод Девідона – Флетчера – Пауела

Прізвище	Храплива
Ім'я	Уляна
По-батькові	Вікторівна
Факультет	ФІС
Група	СНм-51
Залікова книжка	СНм-11-253

Розглянемо алгоритм Девідона - Флетчера - Пауелла мінімізації функції, що диференціюється, декілька змінних. Зокрема, якщо функція квадратична, то, як буде показано пізніше, метод виробляє зв'язані напрями і зупиняється після виконання однієї ітерації, тобто після пошуку уздовж кожного із зв'язаних напрямів.

Початковий етап

Нехай $\varepsilon \succ 0$ - константа для зупинки. Вибрати точку ${x_1}$ і початково симетричну позитивно визначену матрицю ${D_1}$. Покласти ${y_1} = {x_1}$, k = j = 1 і перейти до основного етапу.

Основний етап

Крок 1. Якщо $\left\| {\left. {\nabla f({y_i})} \right\| \lt \varepsilon } \right.$, то зупинитися; в іншому випадку ${d_i} = - {D_i}\nabla f({y_i})$ і узяти в якості ${\lambda _i}$ оптимальне рішення задачі мінімізації $f({y_i} + \lambda {d_i})$ при $\lambda \ge 0$. Покласти ${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти ${y_1} = {x_{k + 1}} = {y_{n + 1}}$, замінити k на k+1, покласти j=1 і повторити крок 1.
Крок 2. Побудувати ${D_{j + 1}}$ таким чином:

${D_{j + 1}} = {D_j} + {\textstyle{{{p_j}p_j^T} \over {p_j^T{p_j}}}} - {\textstyle{{{D_j}{q_j}q_j^T{D_j}} \over {q_j^T{D_j}{q_j}}}},$(1)
де ${p_i} = {\lambda _i}{d_i},$(2)
де ${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$(3)

Замінити j на j+1 і перейти до кроку 1.

Приклад

Мінімізувати ${({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.$
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1.

k	${x_k}$ $f({x_k})$	j	${y_j}$ $f({y_j})$	$\nabla f({y_j})$	$\left\| {\left. {\nabla f({y_j})} \right\|} \right.$	D	${d_j}$	${\lambda _j}$	${y_{j + 1}}$
1	(0.00,3.00) (52.00)	1	(0.00,3.00) (52.00)	(-44.00,24.00)	50.12	$$\left[ 1|0\\ 0|1 \right]$$	(44.00,-24.00)	0.062	(2.70, 1.51)
		2	(2.70,1.51) (0.34)	(0.73,1.28)	1.47	$$\left[ 0.25|0.38\\ 0.38|0.71 \right]$$	(-0.67,-1.31)	0.22	(2.55,1.22)
2	(2.55,1.22) (0.1036)	1	(2.55,1.22) (0.1036)	(0.89,-0.44)	0.99	$$\left[ 1|0\\ 0|1 \right]$$	(-0.89,0.44)	0.11	(2.45,1.27)
		2	(2.45,1.27) (0.0490)	(0.18,0.36)	0.40	$$\left[ 0.65|0.45\\ 0.45|0.46 \right]$$	(-0.28,-0.25)	0.64	(2.27,1.11)
3	(2.27,1.11) (0,008)	1	(2.27,1.11) (0,008)	(0.18,-0.20)	0.27	$$\left[ 1|0\\ 0|1 \right]$$	(-0.18,0.20)	0.10	(2.25,1.13)
		2	(2.25,1.13) (0.004)	(0.04,0.04)	0.06	$$\left[ 0.80|0.38\\ 0.38|0.31 \right]$$	(-0.05,-0.03)	2.64	(2.12,1.05)
4	(2.12,1.05) (0,0005)	1	(2.12,1.05) (0,0005)	(0.05,-0.08)	0.09	$$\left[ 1|0\\ 0|1 \right]$$	(-0.05,0.08)	0.10	(2.115,1.058)
		2	(2.115,1.058) (0.0002)	(0.004,0.004)	0.006

На кожній ітерації вектор${d_j}$ для j=1,2 визначається у вигляді $- {D_j}\nabla f({y_j})$, де ${D_1}$ одинична матриця, а ${D_2}$ обчислюється по формулах (1) - (3). При k = 1 маємо ${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$. На другій ітерації ${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$ і, нарешті, на третій ітерації ${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$. Точка ${y_{j + 1}}$ обчислюється оптимізацією уздовж напряму ${d_j}$ при початковій точці ${y_j}$ для j = 1, 2. Процедура зупинена в точці ${y_2} = {(2.115, 1.058)^T}$ на четвертій ітерації оскільки норма $\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$ досить мала. Траєкторія руху, отримана методом, показана на рисунку 1.
Рисунок 1 - Метод Дэвидона - Флетчера - Пауэлла.

Лема показує, що кожна матриця ${d_j}$ позитивно визначена і ${d_j}$ є напрямом спуску. Для доказу леми нам знадобиться :
Теорема 1. Нехай S - непорожня безліч в Еn, точка $x \in cl$ S. Конусом можливих напрямів в точці x називається безліч $D = \left\{ {d:d \ne 0,x + \lambda d \right \in S$при всіх $\lambda \in (0,\delta )$ для деякого $\delta \gt 0}$.
Визначення.Нехай x і y - вектори з Еn і $\left| {{x^T}y} \right|$ - абсолютне значення скалярного відтворення $\left {{x^T}y} \right$. Тоді виконується наступна нерівність, звана нерівністю Шварца:

$\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$.

Лема 1

Нехай ${y_1} \in {E_n}$, а ${D_1}$ – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо ${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$, де ${d_j} = - D\nabla f({y_j})$, а ${\lambda _j}$ є оптимальним рішенням задачі мінімізації $f({y_j} + \lambda {d_j})$ при $\lambda \ge 0$. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо $\nabla f({y_j}) \ne 0$ для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску.

Доведення
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, $\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) \lt 0$, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого $j \le n - 1$, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо

${x^T}{D_{j + 1}}x = {x^T}{D_j}x + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{D_j}{q_j}}}}$(4)

Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця $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), отримуємо:

${x^T}{D_{j + 1}}x = {\textstyle{{({a^T}a)({b^T}b) - {{({a^T}b)}^2}} \over {{b^T}b}}} + {\textstyle{{{{({x^T}{p_j})}^2}} \over {p_j^T{q_j}}}}$(5)

По нерівності Шварця маємо $({a^T}a)({b^T}b) \ge {({a^T}b)^2$. Так, щоб довести, що${x^T}{D_{j + 1}}x \ge 0$, досить показати, що $p_j^T{q_j} \ge 0,{b^T}b \gt 0$. З (2) і (3) витікає, що

$p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]$(6).

По припущенню $\nabla f({y_j}) \ne 0$, і Dj позитивно визначена, так що$\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) \gt 0$ Крім того, dj - напрямок спуску, і ${\lambda _j} \gt 0$. Тоді із (6) слідує, що $p_j^T{q_j} \gt 0$. Крім того ${q_j} \ne 0$ і ${b^T}b = q_j^T{D_j}{q_j} \gt 0$
Видно тепер, що ${x^T}{D_{j + 1}}x \gt 0$. Взяти ${x^T}{D_{j + 1}}x = 0$. Це можливо тільки в тому випадку якщо $({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0$. Видно, що $({a^T}a)({b^T}b) = {({a^T}b)^2}$ тільки при $a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}$. Таким чином $x = \lambda {q_i}$. Так як $x \ne 0$то$\lambda \ne 0$. Дальше, $0 = p_j^Tx = \lambda p_j^T{q_j}$заперечує тому, що $p_j^T{q_j} \gt 0,\lambda \ne 0$.
Отже, ${x^T}{D_{j + 1}}x \gt 0$, матриця ${D_{j + 1}}$ позитивно визначена.
Оскільки $\nabla f({y_{j + 1}}) \ne 0$ і Dj+1 позитивно визначена, маємо $\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) \lt 0$. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску.
Лема доведена!!!

Список використаної літератури

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975