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

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

Крок [math]{{3}^{1}}[/math]. Оскільки [math]i=2=n[/math] і [math]f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{2}})=f(7,7)=17\lt f(x_{1}^{0},x_{2}^{0})=45[/math], то перейдемо до кроку 4.

Крок [math]{{4}^{0}}[/math]. Проведемо пошук за зразком з точки [math]{{X}^{dp}}(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{2}})=(7,7)[/math]. Поставимо [math]i=1,k=k+1=1[/math].

[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\gt f(X_{{}}^{zr})[/math], то крок неуспішний.

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

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

Крок [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\gt f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1[/math], то крок неуспішний.

Крок [math]{{3}^{2}}[/math]. Оскільки [math]i=2=n[/math] і [math]f(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=f(5,5)=1\lt f({{X}^{dp}})=f(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{1}})=f(7,7)=17[/math], то пошук за зразком на кроці 40 пройшов успішно.

Точка [math]{{X}^{2}}=(x_{1}^{zr}-{{\Delta }_{1}},x_{2}^{zr})=(5,5)[/math] стає новим базисом, а точка [math]{{X}^{1}}=(x_{1}^{0}-{{\Delta }_{1}},x_{2}^{0}-{{\Delta }_{1}})=(7,7)[/math] стає старим базисом. Виконаємо пошук за зразком з нового базису. Перейдем до кроку 4.

Крок [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]{{2}^{4}}[/math]. [math]f(3,3)=25[/math]. Оскільки [math]f(3-{{\Delta }_{1}},3)=f(4,3)=13\lt f(3,3)=25[/math], то крок успішний.

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

Крок [math]{{2}^{5}}[/math]. Оскільки [math]f(4,3+{{\Delta }_{2}})=f(4,5)=5\lt f(4,3)=13[/math], то крок успішний.

Крок [math]{{3}^{5}}[/math]'. Так як [math]i=2=n[/math] і [math]f(4,5)=5\gt f(5,5)=1[/math], то пошук за зразком на кроці [math]{{4}^{1}}[/math] пройшов неуспішно. Переходимо до кроку 5.

Крок [math]{{5}^{0}}[/math]'. Оскільки [math]{{\Delta }_{1}}=1\gt \varepsilon =0.3,{{\Delta }_{2}}=1\gt \varepsilon =0.3[/math], то необхідно зменшити крок. Поставимо [math]{{\Delta }_{1}}=0.5,{{\Delta }_{2}}=1,k=k+1=3[/math], за базис візьмем точку [math](5,5)[/math] і повторимо цикл розрахунків з новим базисом і новими значеннями кроків.

Мінімум досягається в точці [math]{{X}^{*}}=(5,6)[/math].

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

1. Банди Б.,Методы оптимизации. Вводный курс. М., 1988
2. Методы оптимизации систем автоматизированого проектирования