Відмінності між версіями «Метод Девідона – Флетчера – Пауела»
(Не показано 13 проміжних версій цього користувача) | |||
Рядок 1: | Рядок 1: | ||
+ | {{Завдання|Храплива У.В.|Назаревич О. Б.|20 березня 2012}} | ||
{|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px" | {|border=2 style="float: right; margin-left: 1em; margin-bottom: 0.5em; width: 242px; border: #99B3FF solid 1px" | ||
Рядок 6: | Рядок 7: | ||
| '''Ім'я''' || Уляна | | '''Ім'я''' || Уляна | ||
|- | |- | ||
− | | '''По | + | | '''По батькові''' || Вікторівна |
|- | |- | ||
| '''Факультет''' || ФІС | | '''Факультет''' || ФІС | ||
Рядок 14: | Рядок 15: | ||
| '''Залікова книжка''' || СНм-11-253 | | '''Залікова книжка''' || СНм-11-253 | ||
|} | |} | ||
− | |||
− | |||
= Початковий етап = | = Початковий етап = | ||
Рядок 23: | Рядок 22: | ||
Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1.<br> | Крок 1. Якщо <math>$\left\| {\left. {\nabla f({y_i})} \right\| < \varepsilon } \right.$</math>, то зупинитися; в іншому випадку <math>${d_i} = - {D_i}\nabla f({y_i})$</math> і узяти в якості <math>${\lambda _i}$</math> оптимальне рішення задачі мінімізації <math>$f({y_i} + \lambda {d_i})$</math> при <math>$\lambda \ge 0$</math>. Покласти <math>${y_{i + 1}} = {y_i} + {\lambda _i}{d_i}$</math>. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти <math>${y_1} = {x_{k + 1}} = {y_{n + 1}}$</math>, замінити k на k+1, покласти j=1 і повторити крок 1.<br> | ||
Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином:<br> | Крок 2. Побудувати <math>${D_{j + 1}}$</math> таким чином:<br> | ||
− | <center><math>${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}}}},$</math></center><br> | + | <center><math>${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}}}},$</math>(1)</center><br> |
− | <center>де <math>${p_i} = {\lambda _i}{d_i},$</math></center><br> | + | <center>де <math>${p_i} = {\lambda _i}{d_i},$</math>(2)</center><br> |
− | <center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math></center><br> | + | <center>де <math>${q_i} = \nabla f({y_{i + 1}}) - \nabla f({y_i}).$</math>(3)</center><br> |
Замінити j на j+1 і перейти до кроку 1. | Замінити j на j+1 і перейти до кроку 1. | ||
Рядок 163: | Рядок 162: | ||
</center><br> | </center><br> | ||
На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1.<br> | На кожній ітерації вектор<math>${d_j}$</math> для j=1,2 визначається у вигляді <math>$ - {D_j}\nabla f({y_j})$</math>, де <math>${D_1}$</math> одинична матриця, а <math>${D_2}$</math> обчислюється по формулах (1) - (3). При k = 1 маємо <math>${p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}$</math>. На другій ітерації <math>${p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}$</math> і, нарешті, на третій ітерації <math>${p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}$</math>. Точка <math>${y_{j + 1}}$</math> обчислюється оптимізацією уздовж напряму <math>${d_j}$</math> при початковій точці <math>${y_j}$</math> для j = 1, 2. Процедура зупинена в точці <math>${y_2} = {(2.115, 1.058)^T}$</math> на четвертій ітерації оскільки норма <math>$\left\| {\left. {f({y_2})} \right\| = 0.006} \right.$</math> досить мала. Траєкторія руху, отримана методом, показана на рисунку 1.<br> | ||
− | Рисунок 1 - Метод | + | Рисунок 1 - Метод Девідона - Флетчера - Пауелла.<br> |
<center>[[Файл:Рисунок_1.gif]]</center><br> | <center>[[Файл:Рисунок_1.gif]]</center><br> | ||
Рядок 174: | Рядок 173: | ||
Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску.<br> | Нехай <math>${y_1} \in {E_n}$</math>, а <math>${D_1}$</math> – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо <math>${y_{j + 1}} = {y_j} + {\lambda _j}{d_j}$</math>, де <math>${d_j} = - D\nabla f({y_j})$</math>, а <math>${\lambda _j}$</math> є оптимальним рішенням задачі мінімізації <math>$f({y_j} + \lambda {d_j})$</math> при <math>$\lambda \ge 0$</math>. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо <math>$\nabla f({y_j}) \ne 0$</math> для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску.<br> | ||
− | + | '''Доведення'''<br> | |
− | Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math></math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math></math>, і покажемо, що воно справедливе для j+1. | + | Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <math> |
− | </math> | + | \nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) < 0</math>, оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого <math> j \le n - 1</math>, і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо<br> |
+ | <center><math>{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}}}}</math>(4)</center><br> | ||
+ | Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця <math>D_j^{1/2}</math>, така, що <math>{D_j} = D_j^{1/2}D_j^{1/2}</math>. Нехай <math>a = D_j^{1/2}x</math> і <math>b = D_j^{1/2}{q_j}</math>. Тоді <math>{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</math>. Підставляючи ці вирази в (4), отримуємо: <br> | ||
+ | <center><math>{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}}}}</math>(5)</center><br> | ||
+ | По нерівності Шварця маємо <math>({a^T}a)({b^T}b) \ge {({a^T}b)^2 </math>. Так, щоб довести, що<math>{x^T}{D_{j + 1}}x \ge 0</math>, досить показати, що <math>p_j^T{q_j} \ge 0,{b^T}b > 0</math>. З (2) і (3) витікає, що <br> | ||
+ | <center><math>p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right]</math>(6)</center>.<br> | ||
+ | По припущенню <math>\nabla f({y_j}) \ne 0</math>, і Dj позитивно визначена, так що<math>\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) > 0</math> | ||
+ | Крім того, dj - напрямок спуску, і <math>{\lambda _j} > 0</math>. Тоді із (6) слідує, що <math>p_j^T{q_j} > 0</math>. Крім того <math>{q_j} \ne 0</math> і <math>{b^T}b = q_j^T{D_j}{q_j} > 0</math><br> | ||
+ | Видно тепер, що <math>{x^T}{D_{j + 1}}x > 0</math>. Взяти <math>{x^T}{D_{j + 1}}x = 0</math>. Це можливо тільки в тому випадку якщо <math>({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0</math>. Видно, що <math>({a^T}a)({b^T}b) = {({a^T}b)^2}</math> тільки при <math>a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}</math>. Таким чином <math>x = \lambda {q_i}</math>. Так як <math>x \ne 0</math>то<math>\lambda \ne 0</math>. Дальше, <math>0 = p_j^Tx = \lambda p_j^T{q_j}</math>заперечує тому, що <math>p_j^T{q_j} > 0,\lambda \ne 0</math>. <br> | ||
+ | Отже, <math>{x^T}{D_{j + 1}}x > 0</math>, матриця <math>{D_{j + 1}}</math> позитивно визначена.<br> | ||
+ | Оскільки <math>\nabla f({y_{j + 1}}) \ne 0</math> і Dj+1 позитивно визначена, маємо <math>\nabla f{({y_{j + 1}})^T}{d_{j + 1}} = - \nabla f{({y_{j + 1}})^T}{D_{j + 1}}\nabla f({y_{j + 1}}) < 0</math>. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску.<br> | ||
+ | '''Лема доведена!!!''' <br> | ||
+ | |||
+ | = Список використаної літератури = | ||
+ | 1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 <br> | ||
+ | 2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975<br> | ||
[[Категорія:Планування експерименту]] | [[Категорія:Планування експерименту]] |
Поточна версія на 15:02, 6 березня 2012
Дана стаття являється неперевіреним навчальним завданням.
До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону. |
Прізвище | Храплива |
Ім'я | Уляна |
По батькові | Вікторівна |
Факультет | ФІС |
Група | СНм-51 |
Залікова книжка | СНм-11-253 |
Початковий етап
Нехай [math]\varepsilon \succ 0[/math] - константа для зупинки. Вибрати точку [math]{x_1}[/math] і початково симетричну позитивно визначену матрицю [math]{D_1}[/math]. Покласти [math]{y_1} = {x_1}[/math], k = j = 1 і перейти до основного етапу.
Основний етап
Крок 1. Якщо [math]\left\| {\left. {\nabla f({y_i})} \right\| \lt \varepsilon } \right.[/math], то зупинитися; в іншому випадку [math]{d_i} = - {D_i}\nabla f({y_i})[/math] і узяти в якості [math]{\lambda _i}[/math] оптимальне рішення задачі мінімізації [math]f({y_i} + \lambda {d_i})[/math] при [math]\lambda \ge 0[/math]. Покласти [math]{y_{i + 1}} = {y_i} + {\lambda _i}{d_i}[/math]. Якщо j < n, то перейти до кроку 2. Якщо j = n, то покласти [math]{y_1} = {x_{k + 1}} = {y_{n + 1}}[/math], замінити k на k+1, покласти j=1 і повторити крок 1.
Крок 2. Побудувати [math]{D_{j + 1}}[/math] таким чином:
Замінити j на j+1 і перейти до кроку 1.
Приклад
Мінімізувати [math]{({x_1} - 2)^4} + {({x_1} - 2{x_2})^2}.[/math]
Результати обчислень методом Девідона - Флетчера - Пауелла приведені в таблиці 1.
k | [math]{x_k}[/math] [math]f({x_k})[/math] |
j | [math]{y_j}[/math] [math]f({y_j})[/math] |
[math]\nabla f({y_j})[/math] | [math]\left\| {\left. {\nabla f({y_j})} \right\|} \right.[/math] | D | [math]{d_j}[/math] | [math]{\lambda _j}[/math] | [math]{y_{j + 1}}[/math] |
---|---|---|---|---|---|---|---|---|---|
1 | (0.00,3.00) (52.00) |
1 | (0.00,3.00) (52.00) |
(-44.00,24.00) | 50.12 | [math]$\left[ 1|0\\ 0|1 \right]$[/math] | (44.00,-24.00) | 0.062 | (2.70, 1.51) |
2 | (2.70,1.51) (0.34) |
(0.73,1.28) | 1.47 | [math]$\left[ 0.25|0.38\\ 0.38|0.71 \right]$[/math] | (-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 | [math]$\left[ 1|0\\ 0|1 \right]$[/math] | (-0.89,0.44) | 0.11 | (2.45,1.27) |
2 | (2.45,1.27) (0.0490) |
(0.18,0.36) | 0.40 | [math]$\left[ 0.65|0.45\\ 0.45|0.46 \right]$[/math] | (-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 | [math]$\left[ 1|0\\ 0|1 \right]$[/math] | (-0.18,0.20) | 0.10 | (2.25,1.13) |
2 | (2.25,1.13) (0.004) |
(0.04,0.04) | 0.06 | [math]$\left[ 0.80|0.38\\ 0.38|0.31 \right]$[/math] | (-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 | [math]$\left[ 1|0\\ 0|1 \right]$[/math] | (-0.05,0.08) | 0.10 | (2.115,1.058) |
2 | (2.115,1.058) (0.0002) |
(0.004,0.004) | 0.006 |
На кожній ітерації вектор[math]{d_j}[/math] для j=1,2 визначається у вигляді [math] - {D_j}\nabla f({y_j})[/math], де [math]{D_1}[/math] одинична матриця, а [math]{D_2}[/math] обчислюється по формулах (1) - (3). При k = 1 маємо [math]{p_1} = {(2.7, - 1.49)^T},{q_1} = {(44.73, - 22.72)^T}[/math]. На другій ітерації [math]{p_1} = {(-0.1, 0.05)^T},{q_1} = {(-0.7, 0.8)^T}[/math] і, нарешті, на третій ітерації [math]{p_1} = {(-0.02, 0.02)^T},{q_1} = {(-0.14, 0.24)^T}[/math]. Точка [math]{y_{j + 1}}[/math] обчислюється оптимізацією уздовж напряму [math]{d_j}[/math] при початковій точці [math]{y_j}[/math] для j = 1, 2. Процедура зупинена в точці [math]{y_2} = {(2.115, 1.058)^T}[/math] на четвертій ітерації оскільки норма [math]\left\| {\left. {f({y_2})} \right\| = 0.006} \right.[/math] досить мала. Траєкторія руху, отримана методом, показана на рисунку 1.
Рисунок 1 - Метод Девідона - Флетчера - Пауелла.
Лема показує, що кожна матриця [math]{d_j}[/math] позитивно визначена і [math]{d_j}[/math] є напрямом спуску. Для доказу леми нам знадобиться :
Теорема 1. Нехай S - непорожня безліч в Еn, точка [math]x \in cl[/math] S. Конусом можливих напрямів в точці x називається безліч [math]D = \left\{ {d:d \ne 0,x + \lambda d \right \in S[/math]при всіх [math]\lambda \in (0,\delta )[/math] для деякого [math]\delta \gt 0}[/math].
Визначення.Нехай x і y - вектори з Еn і [math]\left| {{x^T}y} \right|[/math] - абсолютне значення скалярного відтворення [math]\left {{x^T}y} \right[/math]. Тоді виконується наступна нерівність, звана нерівністю Шварца:
Лема 1
Нехай [math]{y_1} \in {E_n}[/math], а [math]{D_1}[/math] – початкова позитивно певна симетрична матриця. Для j = 1 ..., n покладемо [math]{y_{j + 1}} = {y_j} + {\lambda _j}{d_j}[/math], де [math]{d_j} = - D\nabla f({y_j})[/math], а [math]{\lambda _j}[/math] є оптимальним рішенням задачі мінімізації [math]f({y_j} + \lambda {d_j})[/math] при [math]\lambda \ge 0[/math]. Нехай, крім того, для j = 1 ..., n – 1 матриця Dj+1 визначається по формулах (1) - (3). Якщо [math]\nabla f({y_j}) \ne 0[/math] для j = 1 ..., n, то матриці D1 ...,Dn симетричні і позитивно визначені, так що d1 ..., dn – напрями спуску.
Доведення
Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, [math]\nabla f{({y_1})^T}{d_1} = - \nabla f{({y_1})^T}{D_1}\nabla f({y_1}) \lt 0[/math], оскільки D1 позитивно визначена. Тоді по теоремі 1 вектор d1 визначає напрям спуску. Передбачимо, що затвердження леми справедливе для деякого [math]j \le n - 1[/math], і покажемо, що воно справедливе для j+1. Нехай x – ненульовий вектор з En, тоді з (1) маємо
Оскільки Dj – симетрична позитивно певна матриця, то існує позитивно визначена матриця [math]D_j^{1/2}[/math], така, що [math]{D_j} = D_j^{1/2}D_j^{1/2}[/math]. Нехай [math]a = D_j^{1/2}x[/math] і [math]b = D_j^{1/2}{q_j}[/math]. Тоді [math]{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[/math]. Підставляючи ці вирази в (4), отримуємо:
По нерівності Шварця маємо [math]({a^T}a)({b^T}b) \ge {({a^T}b)^2[/math]. Так, щоб довести, що[math]{x^T}{D_{j + 1}}x \ge 0[/math], досить показати, що [math]p_j^T{q_j} \ge 0,{b^T}b \gt 0[/math]. З (2) і (3) витікає, що
По припущенню [math]\nabla f({y_j}) \ne 0[/math], і Dj позитивно визначена, так що[math]\nabla f{({y_j})^T}{D_j}\nabla f({y_j}) \gt 0[/math]
Крім того, dj - напрямок спуску, і [math]{\lambda _j} \gt 0[/math]. Тоді із (6) слідує, що [math]p_j^T{q_j} \gt 0[/math]. Крім того [math]{q_j} \ne 0[/math] і [math]{b^T}b = q_j^T{D_j}{q_j} \gt 0[/math]
Видно тепер, що [math]{x^T}{D_{j + 1}}x \gt 0[/math]. Взяти [math]{x^T}{D_{j + 1}}x = 0[/math]. Це можливо тільки в тому випадку якщо [math]({a^T}a)({b^T}b) = {({a^T}b)^2},p_j^Tx = 0[/math]. Видно, що [math]({a^T}a)({b^T}b) = {({a^T}b)^2}[/math] тільки при [math]a = \lambda b,D_j^{1/2}x = \lambda D_j^{1/2}{q_j}[/math]. Таким чином [math]x = \lambda {q_i}[/math]. Так як [math]x \ne 0[/math]то[math]\lambda \ne 0[/math]. Дальше, [math]0 = p_j^Tx = \lambda p_j^T{q_j}[/math]заперечує тому, що [math]p_j^T{q_j} \gt 0,\lambda \ne 0[/math].
Отже, [math]{x^T}{D_{j + 1}}x \gt 0[/math], матриця [math]{D_{j + 1}}[/math] позитивно визначена.
Оскільки [math]\nabla f({y_{j + 1}}) \ne 0[/math] і Dj+1 позитивно визначена, маємо [math]\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[/math]. Звідси по теоремі 1 слідує, що dj+1 - напрямок спуску.
Лема доведена!!!
Список використаної літератури
1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982
2. Химмельблау Д. Прикладное нелинейное программирование. М., 1975