Метод конфігурації Хука-Дживса. - Історія редагувань

Mari TS SV: перейменував «Користувач:Mari TS SV» на «Метод конфігурації Хука-Дживса.»

2012-03-06T16:39:36Z

перейменував «Користувач:Mari TS SV» на «Метод конфігурації Хука-Дживса.»

Mari TS SV: /* Список використаної літератури */

2012-03-06T16:37:45Z

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

Mari TS SV: /* Список використаної літератури */

2012-03-06T16:37:07Z

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

Mari TS SV: /* Лема 1 */

2012-03-06T16:28:21Z

‎Лема 1

Mari TS SV: /* Розвязок */

2012-03-06T16:27:54Z

‎Розвязок

Mari TS SV: /* Розвязок */

2012-03-06T16:15:07Z

‎Розвязок

Mari TS SV: /* Розвязок */

2012-03-06T16:04:25Z

‎Розвязок

Mari TS SV: /* Розвязок */

2012-03-06T15:52:33Z

‎Розвязок

Mari TS SV: /* Розвязок */

2012-03-06T15:44:39Z

‎Розвязок

Mari TS SV: /* Розвязок */

2012-03-06T15:41:56Z

‎Розвязок

@@ Рядок 180: / Рядок 180: @@
 . Банди Б.,Методы оптимизации. Вводный курс. М., 1988 <br>
-. Методы оптимизации систем автоматизированого проектирования [http://www.optimizaciya-sapr.narod.ru/] <br>
+.  [http://www.optimizaciya-sapr.narod.ru/ Методы оптимизации систем автоматизированого проектирования] <br>
 [[Категорія:Планування експерименту]]

@@ Рядок 179: / Рядок 179: @@
 = Список використаної літератури =
-. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М., 1982 <br>
+. Банди Б.,Методы оптимизации. Вводный курс. М., 1988 <br>
-. Химмельблау Д. Прикладное нелинейное программирование. М., 1975<br>
+. Методы оптимизации систем автоматизированого проектирования [http://www.optimizaciya-sapr.narod.ru/] <br>
 [[Категорія:Планування експерименту]]

← Попередня версія		Версія за 16:28, 6 березня 2012
Рядок 176:		Рядок 176:

	Мінімум досягається в точці <math>{{X}^{*}}=(5,6)</math>.		Мінімум досягається в точці <math>{{X}^{*}}=(5,6)</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 – напрями спуску.<br>
−
−	~~'''Доведення'''<br>~~
−	Проведено доведення по індукції. При j = 1 матриця D1 симетрична і позитивно визначена по умові леми. Крім того, <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>~~

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

@@ Рядок 169: / Рядок 169: @@
-''Крок <math>{{3}^{5}}</math>'
+''Крок <math>{{3}^{5}}</math>'. Так як <math>i=2=n</math> і <math>f(4,5)=5>f(5,5)=1</math>, то пошук за зразком на кроці  <math>{{4}^{1}}</math> пройшов неуспішно. Переходимо до кроку 5.
+Мінімум досягається в точці <math>{{X}^{*}}=(5,6)</math>.
 =Лема 1=

← Попередня версія		Версія за 16:15, 6 березня 2012
Рядок 156:		Рядок 156:
	''Крок <math>{{4}^{1}}</math>''. Поставимо <math>i=1,k=k+1=2</math>,		''Крок <math>{{4}^{1}}</math>''. Поставимо <math>i=1,k=k+1=2</math>,
	<math>{{X}^{zr}}={{X}^{2}}+({{X}^{2}}-{{X}^{1}})={{(5,5)}^{T}}-\left[ {{(5,5)}^{T}}-{{(7,7)}^{T}} \right]={{(3,3)}^{T}}</math> і перейдемо до кроку 2.		<math>{{X}^{zr}}={{X}^{2}}+({{X}^{2}}-{{X}^{1}})={{(5,5)}^{T}}-\left[ {{(5,5)}^{T}}-{{(7,7)}^{T}} \right]={{(3,3)}^{T}}</math> і перейдемо до кроку 2.
		+
		+
		+	''Крок <math>{{2}^{4}}</math>''.
		+	<math>f(3,3)=25</math>. Оскільки <math>f(3-{{\Delta }_{1}},3)=f(4,3)=13<f(3,3)=25</math>, то крок успішний.
		+
		+
		+	''Крок <math>{{3}^{4}}</math>''. Так як
		+	<math>i=1<n=2</math>, то поставимо <math>i=i+1=2.</math> і перейдемо до кроку 2.
		+
		+
		+	''Крок <math>{{2}^{5}}</math>''. Оскільки <math>f(4,3+{{\Delta }_{2}})=f(4,5)=5<f(4,3)=13</math>, то крок успішний.
		+
		+
		+	''Крок <math>{{3}^{5}}</math>'
		+
		+

← Попередня версія	Версія за 16:39, 6 березня 2012
(Немає відмінностей)

@@ Рядок 144: / Рядок 144: @@
-''Крок <math>{{2}^{3}}</math>''. Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr}+{{\Delta }_{2}})=(5,7)=1=f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1</math>, то крок неуспішний.
+''Крок <math>{{2}^{3}}</math>''. Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr}+{{\Delta }_{2}})=f(5,7)=1=f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1</math>, то крок неуспішний.
 Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr}-{{\Delta }_{2}})=f(5,3)=9>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1</math>, то крок неуспішний.
-''Крок <math>{{3}^{2}}</math>''. Оскільки
+''Крок <math>{{3}^{2}}</math>''. Оскільки <math>i=2=n</math> і <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1<f({{X}^{dp}})=f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{1}})=f(7,7)=17</math>, то пошук за зразком на кроці 40 пройшов успішно.

← Попередня версія		Версія за 15:52, 6 березня 2012
Рядок 144:		Рядок 144:


−	''Крок <math>{{2}^{3}}</math>''.	+	''Крок <math>{{2}^{3}}</math>''. Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr}+{{\Delta }_{2}})=(5,7)=1=f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1</math>, то крок неуспішний.
		+
		+	Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr}-{{\Delta }_{2}})=f(5,3)=9>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1</math>, то крок неуспішний.
		+
		+
		+	''Крок <math>{{3}^{2}}</math>''. Оскільки
		+
		+

@@ Рядок 136: / Рядок 136: @@
 <math>f({{X}^{zr}})=f(6.5)=5</math>.
- Оскільки <math>f(x_{1}^{zr}+{{\Delta }_{1}},x_{2}^{zr0})=(7,5)=17>f(X_{{}}^{zr})</math>, то крок неуспішний.
+Оскільки <math>f(x_{1}^{zr}+{{\Delta }_{1}},x_{2}^{zr0})=(7,5)=17>f(X_{{}}^{zr})</math>, то крок неуспішний.
 Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=(5,5)=1<f(X_{{}}^{zr})</math>, то крок успішний.

@@ Рядок 131: / Рядок 131: @@
 <math>{{X}^{zr}}={{X}^{dp}}+1({{X}^{dp}}-{{X}^{0}})={{(7,7)}^{T}}-\left[ {{(7,7)}^{T}}-{{(8,9)}^{T}} \right]={{(6,5)}^{T}}</math>.
 Перейдемо до кроку 2.
 ''Крок <math>{{2}^{2}}</math>''. Виконаємо досліджуючий пошук з точки <math>{{X}^{zr}}</math>.
-<math>f({{X}^{zr}})=f(6.5)=5</math>. Оскільки <math>f(x_{1}^{zr}+{{\Delta }_{1}},x_{2}^{zr0})=(7,5)=17>f(X_{{}}^{zr})</math>, то крок неуспішний.
+<math>f({{X}^{zr}})=f(6.5)=5</math>.
 Оскільки <math>f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=(5,5)=1<f(X_{{}}^{zr})</math>, то крок успішний.