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

Матеріал з Вікі-знання або навчання 2.0 в ТНТУ
Перейти до: навігація, пошук
Blue check.png Дана стаття являється неперевіреним навчальним завданням.
Студент: Храплива У.В.
Викладач: Назаревич О. Б.
Термін до: 20 березня 2012

До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону.


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

Зміст

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

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

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

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

LaTeX: ${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)

де LaTeX: ${p_i} = {\lambda _i}{d_i},$(2)

де LaTeX: ${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$(3)

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

Приклад

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

k LaTeX: ${x_k}$
LaTeX: $f({x_k})$
j LaTeX: ${y_j}$
LaTeX: $f({y_j})$
LaTeX: $\nabla f({y_j})$ LaTeX: $\left\| {\left. {\nabla f({y_j})} \right\|} \right.$ D LaTeX: ${d_j}$ LaTeX: ${\lambda _j}$ LaTeX: ${y_{j + 1}}$
1 (0.00,3.00)
(52.00)
1 (0.00,3.00)
(52.00)
(-44.00,24.00) 50.12 LaTeX: $\left[
<p>1|0\\
</p>
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 LaTeX: $\left[
<p>0.25|0.38\\
</p>
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 LaTeX: $\left[
<p>1|0\\
</p>
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 LaTeX: $\left[
<p>0.65|0.45\\
</p>
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 LaTeX: $\left[
<p>1|0\\
</p>
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 LaTeX: $\left[
<p>0.80|0.38\\
</p>
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 LaTeX: $\left[
<p>1|0\\
</p>
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

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

Рисунок 1.gif

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

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

Лема 1

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

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

LaTeX: {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 – симетрична позитивно певна матриця, то існує позитивно визначена матриця LaTeX: D_j^{1/2}, така, що LaTeX: {D_j} = D_j^{1/2}D_j^{1/2}. Нехай LaTeX: a = D_j^{1/2}x і LaTeX: b = D_j^{1/2}{q_j}. Тоді LaTeX: {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), отримуємо:

LaTeX: {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)

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

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

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

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

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

Особисті інструменти
Google AdSense
реклама