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

Дана стаття являється неперевіреним навчальним завданням. Студент: Цубера М. М. Викладач: Назаревич О. Б. Термін до: 20 березня 2012 До вказаного терміну стаття не повинна редагуватися іншими учасниками проекту. Після завершення терміну виконання будь-який учасник може вільно редагувати дану статтю і витерти дане попередження, що вводиться за допомогою шаблону.

Прізвище	Цубера
Ім'я	Марія
По батькові	Миколаївна
Факультет	ФІС
Група	СНм-51
Залікова книжка	СНм-11-255

Метод конфігурацій Хука-Дживса

Метод конфігурації Хука-Дживса був розроблений в 1961 році Цей метод полегшує пошук і не вимагає обчислення похідних. Пошук ведеться вздовж ліній розриву похідних у припущенні, що зміщення в просторі проектування, які опинилися вдалими на ранній стадії пошуку, можуть призвести до успіху і на його більш пізніх стадіях. Метод Хука – Дживса перевизначений для пошуку мінімуму унімодальної функції багатьох змінних [math]M=F(x_1, x_2,...,x_N)[/math] при відсутності обмежень.

Стратегія пошуку

Метод являє собою комбінацію досліджуючого пошуку з циклічною зміною змінних і пришвидшую чого пошуку за зразком. Мета досліджуючого пошуку - виявлення локальної поведінки цільової функції і визначення напрямку її спадання. Ця інформація використовується при пошуку за зразком вздовж напрямку спадання цільової функції.

Досліджуючий пошук починається з деякої початкової точки [math]x_0[/math], яку називаютьї старим базисом. В якості множини напрямків пошуку вибирається множина координатних напрямків. Задається величина кроку, яка може бути різною для різних координатних напрямків. Фіксується перший координатний напрямок і робиться крок у сторону збільшення відповідної змінної. Якщо значення вихідної функції [math]f (x)[/math] в пробній точці менше за значення функції у вихідній точці, то крок вважається вдалим. Інакше, з вихідної точки робиться крок в протилежному напрямку з подальшою перевіркою поведінки функції. Якщо і в цьому випадку не відбувається зменшення функції, то відбувається зменшення кроку і процедура повторюється. Досліджуючий пошук по даному напрямку закінчується, коли поточна величина кроку стає менше деякої величини. Після перебору всіх координат досліджуючий пошук завершується, отримана точка називається новим базисом.

Пошук за зразком полягає в русі по напрямку від старого базису до нового. Величина прискорюючого кроку задається прискорюючим множником [math]\lambda[/math]. Успіх пошуку за зразком визначається за допомогою досліджуючого пошуку з отриманої точки. Якщо значення функції в найкращій точці менше, ніж у точці попереднього базису, то пошук за зразком вдалий, в іншому випадку відбувається повернення в новий базис, де триває досліджуючий пошук зі зменшеним кроком. Позначимо через [math]e_1, e_2,..., e_n[/math] - координатні напрямки:

[math]{{e}_{1}}=\left[ \begin{matrix} 1 \\ 0 \\ {} \\ ... \\ 0 \\ \end{matrix} \right][/math], [math]{{e}_{2}}=\left[ \begin{matrix} 0 \\ 1 \\ {} \\ ... \\ 0 \\ \end{matrix} \right][/math], ..., [math]{{e}_{n}}=\left[ \begin{matrix} 0 \\ 0 \\ {} \\ ... \\ 1 \\ \end{matrix} \right][/math]

Зазначимо, що при пошуку за напрямом [math]e_i[/math] змінюється тільки змінна [math]x_i[/math], а інші змінні залишаються зафіксованими.

Алгоритм методу

Крок 1. Задати початкову точку [math]{{x}^{0}}[/math], число [math]\varepsilon[/math] - для зупинки алгоритму, початкові значення приростів по координатним приростам [math]\Delta _{1}^{0},\Delta _{2}^{0},...,\Delta _{n}^{0}\ge \varepsilon[/math], прискорюючий множник [math]\lambda \succ 0,i=1,k=0[/math].

Крок 2. Провести досліджуючий пошукпо вибраному координатному напрямку:

[math]x_{i}^{k+1}=\left\{ \begin{align} & x_{i}^{k}+\Delta _{i}^{k},\text{ }f\left( x_{1}^{k},...,x_{i}^{k}+\Delta _{i}^{k},...,x_{n}^{k} \right)\lt f(x_{1}^{k},...,x_{i}^{k},...,x_{n}^{k}) \\ & x_{i}^{k}-\Delta _{i}^{k},\text{ }f\left( x_{1}^{k},...,x_{i}^{k}-\Delta _{i}^{k},...,x_{n}^{k} \right)\lt \min f\left( x_{1}^{k},...,x_{i}^{k},...,x_{n}^{k} \right),\left( x_{1}^{k},...,x_{i}^{k}-\Delta _{i}^{k},...,x_{n}^{k} \right) \\ & x_{i}^{k},\text{ } \\ \end{align} \right.[/math]

Крок 3. Перевірити умови:

  а) Якщо [math]i\lt n[/math], то продовжити [math]i=i+1[/math] і перейти до кроку 2. (продовжити досліджуючий пошук по напрямкам, які залишилися)

  а) Якщо 

Крок 4.

Крок 5.

Приклад

Мінімізувати [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]. Тоді виконується наступна нерівність, звана нерівністю Шварца:

[math]\left| {{x^T}y} \right| \le \left\| x \right\|\left\| 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) маємо

[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)

Оскільки 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]{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)

По нерівності Шварця маємо [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]p_j^T{q_j} = {\lambda _j}d_j^T\left[ {\nabla f({y_{j + 1}}) - \nabla f({y_j})} \right][/math](6).

По припущенню [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