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

Дана стаття являється неперевіреним навчальним завданням. Студент: Цубера М. М. Викладач: Назаревич О. Б. Термін до: 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. (продовжити досліджуючий пошук по напрямкам, які залишилися)

б) Якщо [math]i=n[/math], перевірити успішність досліджуючого пошуку: - якщо [math]f({{X}^{k+1}})\lt f({{X}^{k}})[/math], перейти до кроку 4; - якщо [math]f({{X}^{k+1}})\ge f({{X}^{k}})[/math], перейти до кроку 5.

Крок 4. Провести пошук за зразком:

[math]{{X}^{zr}}={{X}^{k+1}}+\lambda ({{X}^{k+1}}-{{X}^{k}})[/math]

В точці [math]{{X}^{zr}}[/math] провести досліджуючий пошук, в результаті якого отримується точка [math]{{X}^{dp}}[/math]. Якщо [math]{{X}^{dp}}\ne {{X}^{zr}}[/math], то точка [math]{{X}^{k+1}}={{X}^{dp}}[/math] стає точкою нового базису, а [math]{{X}^{k}}[/math] - точкою старого базису. Перейти до кроку 5. Якщо [math]{{X}^{dp}}={{X}^{zr}}[/math], то пошук за зрозком вважається неуспішним, точки [math]{{X}^{dp}},{{X}^{zr}}[/math] анулюються, точка [math]{{X}^{k+1}}[/math] залишається точкою нового базису, а [math]{{X}^{k}}[/math] - точкою старого базису. Перейти до кроку 2.

Крок 5. Перевірити умову завершення обрахунку: а) Якщо всі [math]{{\Delta }_{i}}\lt \varepsilon[/math] то пошук закінчити [math]{{X}^{*}}={{X}^{k}}[/math].

б) Для тих і, для яких [math]{{\Delta }_{i}}\gt \varepsilon[/math], зменшити величину кроку іперейти до кроку 2.

Приклад

Знайти мінімум функції [math]f(x)=4{{({{x}_{1}}-5)}^{2}}+{{({{x}_{1}}-6)}^{2}}[/math]

Розвязок

Крок 1. Задамо початкову точку [math]{{X}^{0}}=(x_{_{1}}^{0},x_{2}^{0})=(8,9)[/math]; числа [math]\varepsilon =0.3;{{\Delta }_{1}}=1;{{\Delta }_{2}}=2;\lambda =1.[/math] Поставимо [math]i=1,k=0.[/math]

Крок [math]{{2}^{0}}[/math]. [math]f(x_{1}^{0},x_{2}^{0})=45.[/math]

[math]f(x_{1}^{0}+{{\Delta }_{1}},x_{2}^{0})=f(9,9)=73[/math]. Оскільки [math]f(x_{1}^{0}+{{\Delta }_{1}},x_{2}^{0})\gt f(x_{1}^{0},x_{2}^{0})[/math], то крок неуспішний.

[math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0})=f(7,9)=25[/math]. Оскільки [math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0})\lt f(x_{1}^{0},x_{2}^{0})[/math], то крок успішний.

Крок [math]{{3}^{0}}[/math]. Оскільки [math]i=1\lt 2=n[/math], то поставимо [math]i=2[/math] і перейдемо до кроку 2.

Крок [math]{{2}^{1}}[/math].

[math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}+{{\Delta }_{2}})=f(7,11)=41[/math] Оскільки [math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}+{{\Delta }_{2}})\gt f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0})=25[/math], то крок неуспішний.

[math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{2}})=f(7,7)=17[/math]. Оскільки [math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{2}})\lt f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0})[/math], то крок успішний.

Крок3.

Крок4.

Крок5.

Лема 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