Метод Нелдера-Міда

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»

Кафедра прикладної математики

КУРСОВА РОБОТА

з дисципліни «Методи оптимізації»

на тему: «Метод Нелдера-Міда»

Виконала: Кравченко А.Д.

Група КМ-32 факультет ФПМ

№ залікової книжки КМ-3209

Допущений до захисту ______

Керівник ___________ (Ладогубець Т.С.)

КИЇВ

2016

ЗМІСТ

• ПОСТАНОВКА ЗАДАЧІ
• 1. ТЕОРЕТИЧНІ ВІДОМОСТІ
• 2. ПРАКТИЧНІ РЕЗУЛЬТАТИ
• 2.1 Безумовна оптимізація
• 2.2 Умовна оптимізація
• ВИСНОВКИ
• СПИСОК ВИКОРИСТАНИХ ЛІТЕРАТУРНИХ ДЖЕРЕЛ
• ДОДАТКИ
• Постановка задачі
• Метою роботи є дослідження збіжності методу Нелдера-Міда в контексті безумовної та умовної оптимізації.
• Безумовна оптимізація

- Дослідити збіжність методу без обмежень на прикладі функції Розенброка

Умовна оптимізація

Розглянути роботу методу для допустимих областей:

- Опуклої;

- Не випуклої;

- З лінійними обмеженнями із застосуванням методу ДСК-П;

- З лінійними обмеженнями із застосуванням методу золотого перерізу;

Також необхідно визначити більш оптимальний для даної задачі метод одномірного пошуку з методів ДСК-П та золотого перерізу, визначити оптимальну точність цих методів одномірного пошуку.

Для виконання поставлених задач необхідно виділити основні підзадачі:

- здійснити пошук мінімуму для кожної з даних функцій при відповідних обмеженнях;

- обрати оптимальну довжину ребра початкового симплексу;

- покращити алгоритм методу при точності 10-1...10-8 (кількість обчислень функції не повинна перевищувати 600-1000);

- порівняти отримані значення мінімуму з величинами, знайденими аналітично;

- зробити висновки щодо доцільності використання методу для різних областей.

метод нелдер міда симплекс

1. Теоретичні відомості

Метод Нелдера-Міда відноситься до категорії евристичних методів. Процес пошуку ґрунтується на властивостях симплексу. Регулярний симплекс в N- мірному просторі - це многогранник , що містить N+1 рівновіддалену одна від одної вершини. Очевидно, що у випадку 2-х змінних це правильний трикутник.

Новий симплекс можна побудувати на будь-якій грані початкового симплексу шляхом перенесення вибраної вершини на відповідну відстань вздовж прямої, проведеної через центр тяжіння решти вершин. Отримана таким чином точка стає вершиною нового симплексу, а стара (обрана для побудови) вершина симплексу виключається. Тобто для переходу до нового симплексу необхідно здійснити лише одне обчислення цільової функції.

На першому етапі методу необхідно, маючи початкову точку та масштабний множник, побудувати регулярний симплекс. Масштабний множник визначає довжину ребра симплексу.

Координати вершин регулярного симплексу, визначаються наступною матрицею D, в якій стовпцями є вершини, пронумеровані від 1 до (n+1), а рядки - координати i-ї змінної (i = 1, ..., n).

Або, в загальному випадку, якщо початкова точка має ненульові координати, тоді координати вершин симплексу обчислюються за формулою:



d1=;

d2=;

t - масштабний множник (довжина ребра);

n - кількість змінних, n+1 - кількість вершин,

x(0) = (x1(0), x2(0), ..., xj(0), ...,xn(0)) - початкова точка;

x(i) = (x1(i), x2(i), ..., xj(i), ...,xn(i)), де i, j = 1, ..., n.

Після побудови симплексу обчислюються значення цільової функції в кожній вершині симплексу. Розглянемо симплекс для функції від двох змінних - трикутник. Вершину с найбільшим значенням функції позначимо h, з найменшим - l, із середнім - g. Далі знайдемо середину ребра проти xh і позначимо її xc. Проведемо проектуючи пряму через точки xh і xc. На такій самій відстані від xc побудуємо нову точку xn. Порівняємо значення в цій точці з fh fg fl:

- Якщо fс - найбільша, обираємо коефіцієнт в = -0.5, сильно зменшуючи розмір симплекса;

- Якщо fс - найменша, обираємо коефіцієнт г = 2, сильно збільшуючи розмір симплекса;

- Якщо fс лежить між найбільшим та середнім значеннями, обираємо коефіцієнт в = 0.5, помірно зменшуючи розмір симплекса;

- Якщо fс лежить між найменшим та середнім значеннями, обираємо коефіцієнт б = 1, не змінюючи розмір симплекса.

Ці коефіцієнти (загальне їх позначення - И) суттєво пришвидшують процес пошуку точки мінімуму. З їх врахуванням шукаємо нову вершину симплексу за формулою:

.

f(x2)= max{f(x1), f(x2), f(x3)}

Новий симплекс - x1, x3, x4 при б = 1:

xc - центр тяжіння.

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

Ітерації продовжуються аж поки:

1. Не буде покрита точка мінімуму;

2. Не почнеться циклічний рух по 2-х або більше симплексу.

У цих ситуаціях використовують наступні правила.

Правило 1. Накриття точки мінімуму.

Якщо вершина, якою відповідає найбільше значення цільової функції, побудована на попередній ітерації, то замість неї береться вершина, якою відповідає наступне по величині значення цільової функції.

Правило 2. Циклічний рух.

Якщо деяка вершина симплексу не виключається впродовж більш, ніж M ітерацій, необхідно зменшити розміри симплексу за допомогою коефіцієнта редукції, і побудувати новий симплекс, вибравши базисною точку, якій відповідає мінімальне значення цільової функції.

Спендіш, Хекст і Хімсворт запропонували обчислювати M, як M = 1,65 N + 0,05N2, де N - розмірність завдання.

Правило 3. Критерій закінчення.

Пошук завершується, коли 1) розміри симплексу стають досить малими 2) різниці між значеннями цільової функції у вершинах симплексу менше заданої величини або з використанням інших критеріїв, наприклад, середньоквадратичного відхилення.

Переваги методу:

- Мала кількість початкових даних: параметри величини симплексу t, параметри зменшення симплексу, параметри закінчення пошуку;

- Невеликий вплив помилки обчислень значень цільової функції на ефективність пошуку, оскільки основними даними є максимальні значення цільової функції, а не мінімальні;

- Простота розрахунків і логічної структури, невеликий об'єм коду програми обчислень;

Недоліки методу:

- Необхідне введення масштабування, аби значення змінних були порівнянні по величині, оскільки вершини симплексу залежать від одного масштабного множника.

2. Практичні результати

2.1 Безумовна оптимізація

Аналітичний розрахунок мінімуму функції Розенброка дає результат f(x) = 0 при x = (1;1). Розглянемо розрахунки мінімуму функції Розенброка методом Нелдера-Міда за різних умов. В усіх таблицях t - довжина ребра регулярного симплексу, сount - кількість обчислень цільової функції, х1 та х2 - координати точки мінімуму, f(x1;x2) - локальний мінімум функції.

1) Дані розрахунків, проведених із точністю е=10-3 наведені в таблиці 2.1.1

Таблиця 2.1.1 - дані розрахунків з точністю 10-3

t	сount	f(x1; x2)	x1; x2
0.001	53	2.351833235771263019842081121169	0.5282 0.2918
0.01	45	2.3731519815891104485672258306295	0.5363 0.299
0.1	97	0.85050032528462238268218698067358	0.1449 0.0135
1	171	0.10106756440559097609543925955222	0.6959 0.4741
10	115	5.4982518121351562356835529499222	1.2319 1.4456
0.5	267	0.016873455331054797168288672537528	0.6726 0.4780

Згідно з даними, представленими в таблиці 2.1.1, точність 10-3 занадто низька для коректної роботи методу.

2) Дані розрахунків, проведених із точністю е=10-6 наведені в таблиці 2.1.2

Таблиця 2.1.2 - дані розрахунків з точністю 10-6

t	count	f(x1; x2)	x1; x2
0.001	591	0.00051212007958092791663068377161494	0.9978 0.9934
0.01	477	0.013718720571803087737716708716107	0.8897 0.7876
0.1	429	0.000000154472354704593817689814612417	0.9997 0.9995
1	287	0.000000779438128619230353514549421158	1.0005 1.0009
10	201	5.4916272242766037692263125791214	1.2120 1.3916
100	1321	0.000000241848910772895940249636913618	0.9995 0.9991
1000	665	0.000065037051123411528520505686667974	1.0077 1.0153
5000	313	0.028264065745328866008367896256459	0.8516 0.7173
4499	307	0.000000421009385248898224582392822712	1.0002 1.0003

Згідно з даними таблиці 2.1.2 кращий результат можна отримати при стандартному значенні масштабного множника (t=1). Зі зменшенням довжини ребра збільшується кількість обчислень функції. При збільшенні масштабного множника до t=100 отримаємо найменшу точність обчислення - рахуємо значення цільової функції 1321 раз. Проте під час подальшого збільшення довжини ребра точність обчислень знову зростає, наприклад, при t=4499 рахуємо цільову функцію лише 307 разів.

3) Дані розрахунків, проведених із точністю е=10-8 наведені в таблиці 2.1.3

Таблиця 2.1.3 - дані розрахунків з точністю 10-

t	count	f(x1; x2)	x1;x2
0.001	787	0.00000001232552451237797332636534903931	1 0.9999
0.01	507	0.013718476819046011849767552348567	0.8899 0.7879
0.1	439	0.0000000002632431957530018240493184088907	1 1
1	315	0.0000000005498911394647540303484406787337	1 1
10	2333	0.0000000040079500007574848550494971350169	0.9999 0.9999
100	1339	0.0000000031421414983789602263770598006591	1 1.001
4499	319	0.0000000057895816563369023427827330004203	0.9999 0.9999

8

Дані з таблиці 2.1.3 ілюструють високу точність знаходження мінімуму. При деяких значеннях t за допустиму кількість підрахування значення функції знаходимо мінімум в точках (1;1), тобто у власне точці локального мінімуму. Аналогічно випадку з е = 10-6 найбільш точні значення досягаються в точках з довжиною ребра t = 1, та t = 4499, де функцію рахуємо приблизно лише 300 разів.

2.2 Умовна оптимізація

2.2.1 Опукла допустима область

Задамо таку область за допомогою наступного рівняння: x12 + (x2-1) =< 0.52 . Аналітично знайдений мінімум на границі обмеження знаходиться в точці (0.18475; 0.5354), де значення функції становить 25.79.

Під час дослідження допустимої області відслідковувались як виконання критерію закінчення, так і потрапляння точки на границю допустимої області (саме допустимої області без застосуванням «майже» допустимої області). Нижче наведені таблиці ілюструють результати дослідження з точністю 10-3 та 10-6 .

1) Розглянемо таблицю 2.2.1.1 - отримані результати за умов точності е = 10-3 та початкової точки х0 = (0; 1) в допустимій області.

Таблиця 2.2.1.1 - дані розрахунків з точністю 10-3, х0 = (0; 1)

t	count	f(x1; x2)	(x1; x2)
0.001	101	26.115743792106064378788753432092	0.0537 0.5029
0.01	111	26.120397451568539283673522698269	0.0564 0.5032
0.1	103	25.973967216317845766796149537427	0.1429 0.5002
1	199	31.910329380568404576357447328043	0.4325 0.7491
10	135	39.454868757547251745189451162717	0.4783 0.8548
100	163	33.53937283495660817347876031342	0.4472 0.7765
0.15	91	26.17404381618605587779308301076	0.0777 0.5061

Оскільки допустима область - коло з радіусом 0.5, то очевидно, що кращі результати отримаємо при довжині ребра t < 0.5, що, власне, підтверджують дані таблиці. При t = 0.1 отримаємо точку, найближчу до глобального мінімуму на границі. А при t = 0.15 рахуватимемо значення функції лише 91 раз.

2) Розглянемо таблицю 2.2.1.2 - отримані результати за умов точності е=10-6 та початкової точки х0 = (0; 1) в допустимій області.

Таблиця 2.2.1.2 - дані розрахунків з точністю 10-6, х0 = (0; 1)

t	count	f(x1;x2)	(x1;x2)
0.001	177	26.11126035112447952900432313801	0.0537 0.5029
0.01	173	26.117105146273103762495594975987	0.0564 0.5032
0.1	171	25.971863284987095896205912870323	0.0142 0.5002
1	187	31.909995828446457251276723604199	0.4325 0.7491
10	203	39.446912881408620698234131527638	0.4783 0.8548
100	245	33.536139019938827229833451323577	0.4472 0.7765

Ситуація аналогічна попередньому випадку - найкраще значення при t = 0.1 (точне попадання в точку глобального мінімуму за 171 підрахування функції). Зі збільшенням довжини ребра точність результатів погіршується, при зменшенні - не покращується, майже не змінюється.

Очевидно, що при збільшенні точності збільшуватиметься лише кількість підрахунку функції (див. Таблиця 2.2.1.4 і 2.2.1.5), тож не розглядатимемо е=10-8. Також цікаво відмітити, що при е=1 можна за лише 25 підрахунків функції потрапити в точку, де значення функції становить 29.4.

Розглянемо тепер точку х0=(-0.2; 1.4) в тій самій допустимій області

3) Таблиця 2.2.1.3 - отримані результати за умов точності е = 10-3 та початкової точки х0=(-0.2; 1.4) в допустимій області.

Таблиця 2.2.1.3 - дані розрахунків з точністю 10-3, х0 = (-0.2; 1.4)

t	count	f(x1; x2)	(x1; x2)
0.001	119	27.610658423306177979150230332343	0.2947 0.5961
0.01	121	27.544642859402292160746716137568	0.2908 0.5932
0.1	109	26.507904061425076814473964835978	0.1804 0.5337
1	135	29.511186664416271413893183888445	0.3669 0.6604
10	137	26.407079885288309858714417526257	0.1580 0.5256
100	153	26.664241977881687566272135445376	0.2072 0. 0545
1000	197	29.293714798660124924768276827143	0.3613 0.6544

Оскільки допустима область - коло з радіусом 0.5, то очевидно, що кращі результати отримаємо при довжині ребра t < 0.5, що, власне, підтверджують дані таблиці. При t = 0.1 отримаємо точку, найближчу до глобального мінімуму на границі і найменшу кількість підрахунків функції. Аналогічно дослідженню іншої точки з цієї області, зі збільшенням довжини ребра точність результатів погіршується, при зменшенні - не покращується, майже не змінюється.

4) Порівняємо таблиці 2.2.1.4 і 2.2.1.5 відповідно результати, отримані з точністю е=10-6 та з точністю е=10-8 при х0 = (-0.2; 1.4)

Таблиця 2.2.1.4 - дані розрахунків з точністю 10-6, х0 = (-0.2; 1.4)

t	count	f(x1; x2)	(x1; x2)
0.001	189	27.608628946924989170404404566515	0.2947 0.5961
0.01	203	27.54356915429051515593974275635	0.2908 0.5932
0.1	189	26.507187770367285358337259145472	0.1804 0.5337
1	207	29.506218786318459253078940735743	0.3669 0.6603
10	217	26.406682808586871467053797107041	0.1580 0.5256
100	223	26.660420587855176884349279580066	0.2072 0.0545
1000	273	29.292902275253868016642507309791	0.3613 0.6544

Таблиця 2.2.1.5 - дані розрахунків з точністю 10-8, х0 = (-0.2; 1.4)

t	count	f(x1; x2)	(x1; x2)
0.001	251	27.60862642387442083520118016408	0.2947 0.5961
0.01	235	27.543568525390022946586607485773	0.2908 0.5933
0.1	245	26.507187118170539084927025565048	0.1804 0.5337
1	247	29.506213616499864317679802607137	0.3669 0.6603
10	261	26.406679770020612071784632928683	0.1580 0.5256
100	263	26.660420350569983139688107795215	0.2072 0.0545
1000	325	29.292901891507385369662072544436	0.3613 0.6544

Дані цих двох таблиць відрізняються лише показником кількості підрахунків цільової функції - зі збільшенням точності розрахунків в 10-2 соunt збільшується приблизно на 20-40 разів. Інші результати аналогічні випадку з е=10-3.

2.2.2 Невипукла допустима область

Задамо таку область за допомогою наступних рівнянь (х1+7)2 + x22 = 82 та (x1+4)2+(x2-2)2=22 . Аналітично знайдений мінімум на границі обмеження знаходиться в точці (0.9491; 0.901), де значення функції становить 0.00258855569.

Під час дослідження допустимої області відслідковувались як виконання критерію закінчення, так і потрапляння точки на границю допустимої області (саме допустимої області без застосуванням «майже» допустимої області). Нижче наведені таблиці ілюструють результати дослідження з точністю 10-3, 10-6 та 10-8 .

1) Розглянемо таблицю 2.2.2.1 - отримані результати за умов точності е = 10-3 та початкової точки х0 = (-4; -4) в невипуклій допустимій області.

Таблиця 2.2.2.1 - дані розрахунків з точністю 10-3, х0 = (-4; -4)

t	count	f(x1; x2)	(x1; x2)
0.001	140	0.0034067424034683225313416973536096	0.9442 0.8933
0.01	167	0.2949732756675845224414445056027	0.4690 0.2085
0.1	78	0.21692157777473924928912651921564	0.5358 0.2833
1	123	0.60850358078669819494876946919248	0.2544 0.0418
10	202	1.5575654321575382876829962697229	0.2185 0.0208
100	104	5.8428620257878316479605018685106	-1.3641 1.8105
1000	148	0.0078691685266584331798211948694188	0.9129 0.8351

Аналогічно випадку безумовної оптимізації з такою ж точністю, е=10-3 занадто низька для коректної роботи методу.

2) Розглянемо таблицю 2.2.2.2 - отримані результати за умов точності е = 10-6 та початкової точки х0 = (-4; -4) в невипуклій допустимій області.

Таблиця 2.2.2.2 - дані розрахунків з точністю 10-6, х0 = (-4; -4)

t	count	f(x1; x2)	(x1; x2)
0.001	178	0.002602691926502102327811716264705	0.9491 0.901
0.01	261	0.0028323607015104312542574938049711	0.9492 0.8994
0.1	163	0.0043057286247929135725165394887881	0.9417 0.8839
1	327	0.0026213997336092397134887921339441	0.9491 0.9003
10	478	0.0029034118872556854279443072641698	0.9493 0.8993
100	578	0.002829619561743920708174471201346	0.9493 0.8995
0.099	98	0.0026035707144936846325899981735574	0.9492 0.9005

При всіх розглянутих значеннях множника t метод знаходить точку, близьку до точки глобального мінімуму. При t=0.001 за 178 підрахувань функції потрапляємо в точку власне глобального мінімуму, а при t=0.099 - в точку (0.9492; 0.9005) лише за 98 підрахунків цільової функції.

3) Розглянемо таблицю 2.2.2.3 - отримані результати за умов точності е = 10-8 та початкової точки х0 = (-4; -4) в невипуклій допустимій області.

Таблиця 2.2.2.3 - дані розрахунків з точністю 10-8, х0 = (-4; -4)

t	count	f(x1; x2)	(x1; x2)
0.001	221	0.00259842726985952702720150675475	0.9491 0.901
0.01	341	0.0025926928817205669580703286669632	0.9491 0.9007
0.1	258	0.0038751435506290204079105077283884	0.9495 0.8978
1	376	0.0026174232370318123788721642597466	0.9492 0.9003
10	498	0.0029024013088871192071749316454543	0.9493 0.8993
100	660	0.0027743986543043224965443549479005	0.9493 0.8997
0.99	138	0.0026017642930352231564472553770884	0.9492 0.9005

Найкращий результат отримаємо при t=0,001 і count=221. Проте, в загальному, при такому значенні е цільову функцію доводиться рахувати більше разів.

Розглянемо тепер точку х0=(-8; 4) в тій самій невипуклій допустимій області. Одразу зазначимо (спойлер), що при збільшенні значення масштабного множника до 10 і далі отримаємо дві точки за межами допустимої облисті і значення кількості підрахунків цільової функції count досягне 1300 і більше, тому для випадків t>=10 дані роботи методу не наводяться.

4) Розглянемо таблицю 2.2.2.4 - отримані результати за умов точності е = 10-3 та початкової точки х0 = (-8; 4) в невипуклій допустимій області.

Таблиця 2.2.2.4 - дані розрахунків з точністю 10-3, х0 = (-8; 4)

t	сount	f(x1; x2)	(x1; x2)
0.001	53	12.407113176149865196862265293021	-2.5215 6.3658
0.01	49	12.43648494543506899390195030719	-2.5251 6.3863
0.1	51	12.56225784007041212930744222831	-2.5435 6.4771
1	111	19.205417753027596461379289394245	-2.6362 6.7050

Метод завершує роботу на границі області, котра є діркою в допустимій, тобто працює некоректно.

5) Розглянемо таблицю 2.2.2.5 - отримані результати за умов точності е = 10-6 та початкової точки х0 = (-8; 4) в невипуклій допустимій області.

Таблиця 2.2.2.5 - дані розрахунків з точністю 10-6, х0 = (-8; 4)

t	сount	f(x1; x2)	(x1; x2)
0.001	69	12.406859823848071400220760551747	-2.5217 6.3657
0.01	545	0.0028370089298723304149785207073364	0.9492 0.8994
0.1	495	0.31241250451474478211366658797488	0.3124 0.2077
1	617	19.204808868087496875887154601514	-2.6362 6.7050

При значенні t=0.01за 545 підрахунків цільової функції досягнемо точки, що знаходиться близько до точки глобального мінімуму. В інших випадках метод працює некоректно.

6) Розглянемо таблицю 2.2.2.6 - отримані результати за умов точності е = 10-8 та початкової точки х0 = (-8; 4) в невипуклій допустимій області.

Таблиця 2.2.2.5 - дані розрахунків з точністю 10-8, х0 = (-8; 4)

t	сount	f(x1; x2)	(x1; x2)
0.001	94	12.406858545564141138584091095254	-2.5217 6.3657
0.01	575	0.0028355456180588238176976112470129	0.9493 0.8995
0.1	913	0.0037905727810734215176002859237769	0.9494 0.8979
1	177	19.204805474389097241783019853756	-2.6362 6.7050

При значенні множинного множника t=0.01 за 575 підрахунків функції отримуємо точку, близьку до точки мінімуму. При t=0.1 отримуємо гірші, але також відносно коректні результати. В інших випадках метод працює некоректно.

2.2.3 Область з лінійним обмеженням

Задамо таку область за допомогою наступного рівняння: 2x1+x2>=5 .

Спростимо умови задачі: вважаємо, що границя - це проміжок в межах від 4.999 до 5.001. Аналітично знайдений мінімум на границі обмеження знаходиться в точці (1.4493; 2.1013), де значення функції становить 0.2019.

Під час дослідження допустимої області відслідковувались лише потрапляння точки на границю допустимої області.

Розглянемо Таблицю 2.2.3.1 - дані, отримані при початковій точці х0(5;5) із допустимої області. При довжині ребра 1 за 331 підрахування функції досягаємо власне границі, а не області навколо неї і значення функції 0.2038. При довжині ребра 0.1 підходимо ще ближче до глобального мінімуму - значення функції 0.2021, пороте доводиться рахувати функцію 639 разів. В загальному, з цієї точки знаходимо коректу точку мінімуму.

Таблиця 2.2.3.1 - дані розрахунків з точки х0 = (5; 5)

t	сount	f(x1; x2)	(x1; x2)
0.001	783	0.2071	1.4509 2.0989
0.01	249	0.2267	1.4526 2.0955
0.1	639	0.2021	1.4494 2.1020
1	311	0.2038	1.4503 2.1001
10	345	0.223	1.4524 2.0960
100	445	0.2062	1.4507 2.0991
1000	671	0.2026	1.449 2.1027

Розглянемо тепер іншу початкову точку з цієї ж області (Таблиця 2.2.3.2). Нехай х0=(6;1). В цьому випадку при довжині ребра t=1 отримаємо f(2.3199;0.3603)=2513.3589. Проте коректне значення також можна отримати при значенні t=10. Причому зі збільшенням значення t результати сильно покращуються, що ілюструє таблиця 2.2.3.2

Таблиця 2.2.3.2 - дані розрахунків з точки х0 = (6; 1)

t	сount	f(x1; x2)	(x1; x2)
0.001	109	1895.6089	2.2175 0.5655
0.01	135	1836.4428	2.2069 0.5868
0.1	97	2068.4921	2.2475 0.5051
1	121	2523.35891	2.3199 0.3603
10	589	0.2047	1.4505 2.0997
100	211	20.0841	-3.4587 11.9188
1000	405	20.0283	-3.4576; 11.9156

Візьмемо точку, отриману при стандартному значенні t=1 і підемо по границі допустимої області використовуючи лопт і методи золотого перерізу та ДСК-П для пошуку Дл на кожному кроці. Дані, отримані за таких умов наведені в таблиці 2.2.3.3.

Згадаємо, що наша границя має вигляд 2x1+x2=5. Використовуючи напрямок S = (-2.5;5)T. Для поставленої задачі оберемо Дл0=0.

Таблиця ілюструє, що метод ДСК-П працює краще за метод золотого перерізу, а також те, що кожен з методів знаходить точку мінімуму на границі функції, хоча метод золотого перерізу рахує функцію 36 разів, а метод ДСК-П - 33 рази. Під час проведення розрахунків е = 10-5.

Таблиця 2.2.3.23- дані, отримані під час пошуку мінімуму на границі

Метод	ЗС	ДСК-П
е=10-5
f(x0)	2523.35891	2523.35891
x0	(2.3199;0.3603)	(2.3199;0.3603)
Дл	0.2348	0.2348
л0	0.8706	0.8706
count	36	33
f(x1)	0.201976479	0.201976479
x1	(1.4493; 2.1015)	(1.4493; 2.1015)

Висновки

На основі проведених розрахунків можна сказати, що під час використання методу Нелдера-Міда для знаходження локального мінімуму функції найкращі результати можна отримати за наступних умов: t=1, e=10-6. В цьому випадку отримаємо f(1.0005;1.0009) = 0.000000779 при кількості підрахунку функції рівній 287 (див. таблицю 2.1.2). За умов е=10-8, t=1 або t=0.1метод потрапляє в точку мінімуму з точністю виводу 30 знаків після крапки (див. таблицю 2.1.3). Цікаво відмітити, що при значенні t=10 або кількість підрахунків значення цільової функції різко зростає, або в результаті отримується некоректне значення функції (див. таблиці 2.1.1, 2.1.2, 2.1.3)

При наявності опуклої допустимої області важливу роль грає розмір області. В даній роботі було розглянуто коло з радіусом 0.5 і найкращі результати були отримані за умови t=0.1 без відчутого впливу значення параметру е на кінцеве значення цільової функції. Проте е впливає на кількість підрахувань функції - 103 при е=10-3 (див. таблицю 2.2.1.1) і 171 при е=10-6 (див. таблицю 2.2.1.2). Також хороше значення можна отримати при t=0.15 (див. таблицю 2.2.1.1). Очевидно, що точка має знаходитись в допустимій області, бажано не біля самої границі.

Під час роботи з не випуклою допустимою областю коректність роботи методу в першу чергу залежить від вибору початкової точки. В залежності від її положення в допустимій області на коректність і точність роботи методу впливає значення е, наприклад, якщо на прямій між початковою точкою та точкою глобального мінімуму немає перешкод у вигляді недопустимої області, то при точності 10-8 отримуємо хороший результат при довжині ребра 0.01 та 0.001 (див. таблицю 2.2.2.3). При зменшенні точності обчислень до 10-6 хоч і знижується кількість підрахувань значення функції, проте і знайдена точка на 0.0001 більша, ніж точка глобального мінімуму (див. таблицю 2.2.2.2)

Якщо ж точка має пройти по відносно вузькій смузі між недопустимим областями (тобто між недопустимою областю то діркою в допустимій), то велике значення має значення довжини ребра. Воно має бути «середнім». Наприклад, при необхідності проходження по смузі шириною 1, значення, близьке до мінімуму досягається при t=0.1 та 0.001(див. таблиці 2.2.2.5 і 2.2.2.6) за 495 та 913 підрахувань функції і за 545 та 575 підрахувань функції при точностях 10-6 та 10-8 відповідно.

При дослідженні в області з лінійним обмеженням також важливе положення точки області. При однакових умовах ( t = 1) із вдало обраної точки (5; 5) за 311 підрахунків функції можна дійти достатньо близько до глобального мінімуму - в точку зі значенням 0.038 функції і ній, а з точки (6; 1) вийти на границю, де значення функції дорівнює 2523.35891.

Під час руху по лінійній границі методами одномірного пошуку виявлено, що метод ДСК-П дає кращі результати, ніж метод золотого перерізу.

Список використаних літературних джерел

1. Д. Хіммельблау, «Прикладне нелінійне програмування». М.; «Мир», 1975.

2. http://www.100byte.ru/stdntswrks/hj/nm.html

3. Рейклетіс Г., Рейвиндран А., Регсдейл К., «Оптимізація в техніці», том 2; М. «Мир», 1986.

Додатки

Код програми, написаної на MatLab, що проводить розрахунки за алгоритмом методу Нелдера-Міда

function [x1,x2] = BO_noVpa (e,t)

count = 0;

a1=-1.2;

a2=0;

b1=a1+((1+sqrt(3))/(2*sqrt(2)))*t;

b2=a2+((-1+sqrt(3))/(2*sqrt(2)))*t;

c1=a1+((-1+sqrt(3))/(2*sqrt(2)))*t;

c2=a2+((1+sqrt(3))/(2*sqrt(2)))*t;

i=1;j=2;k=3;

loop=0;

RMSkrit=e+1;%для входа в цикла проверки

secondVectorForRed=[0,0,0];

thirdVectorForRed=[0,0,0];

fourthVectorForRed=[i,j,k];

[fa,count]=f(a1,a2,count);

[fb,count]=f(b1,b2,count);

[fc,count]=f(c1,c2,count);

while (e<RMSkrit)

loop=loop+1

massfun=[fa, fb, fc];

massSort = sort(massfun);

fh = massSort(3);

fg = massSort(2);

fl = massSort(1);

massForRed = [i,j,k];

T=max(massForRed)

if fh==fa && fg==fb && fl==fc

xh1=a1;xh2=a2;xg1=b1;xg2=b2;xl1=c1;xl2=c2;

i=T+1; genius=1;%j=j;k=k;

end

if fh==fa && fg==fc && fl==fb

xl2=b2;xh1=a1;xg1=c1;xl1=b1;xh2=a2;xg2=c2;

i=T+1;genius=2;%j=j;k=k;

end

if fh==fb && fg==fa && fl==fc

xh1=b1;xg1=a1;xl1=c1;xh2=b2;xg2=a2;xl2=c2;

j=T+1;genius=3;%k=k;i=i;

end

if fh==fb && fg==fc && fl==fa

xh1=b1;xg1=c1;xl1=a1;xh2=b2;xg2=c2;xl2=a2;

j=T+1;genius=6;%i=i;k=k;

end

if fh==fc && fg==fa && fl==fb

xh1=c1;xg1=a1;xl1=b1;xh2=c2;xg2=a2;xl2=b2;

k=T+1;genius=4;% i=i;j=j;

end

if fh==fc && fg==fb && fl==fa

xh1=c1;xg1=b1;xl1=a1;xh2=c2;xg2=b2;xl2=a2;

k=T+1;genius=5;%i=i;j=j;

end

newLineMassForRed=[i,j,k];

firstVectorForRed=secondVectorForRed

secondVectorForRed=thirdVectorForRed

thirdVectorForRed=fourthVectorForRed

fourthVectorForRed=newLineMassForRed

I1 = firstVectorForRed(1); %Номер Fa на первой интерации

I2 = secondVectorForRed(1); %Номер Fa на второй интерации

I3 = thirdVectorForRed(1); %Номер Fa на третьей интерации

I4 = fourthVectorForRed(1); %Номер Fa на чертвертой интерации

II1 = firstVectorForRed(2); %Номер Fb на первой интерации

II2 = secondVectorForRed(2);%Номер Fb на воторой интерации

II3 = thirdVectorForRed(2);%Номер Fb на третьей интерации

II4 = fourthVectorForRed(2);%Номер Fb на четвертой интерации

III1 = firstVectorForRed(3); %Номер Fc на первой интерации

III2 = secondVectorForRed(3);%Номер Fc на второй интерации

III3 = thirdVectorForRed(3);%Номер Fc на третьей интерации

III4 = fourthVectorForRed(3);%Номер Fc на четвертлй интерации

if ((I1==I2)&&(I2==I3)&&(I3==I4))||((II1==II2)&&(II2==II3)&&(II3==II4))||((III1==III2)&&(III2==III3)&&(III3==III4))

disp('THIS IS REDUCTION');

b1=(xh1+xl1)/2;

b2=(xh2+xl2)/2;

c1=(xg1+xl1)/2;

c2=(xg2+xl2)/2;

a1=xl1;

a2=xl2;

[fb,count]=f(b1,b2,count);

[fc,count]=f(c1,c2,count);

i=1;j=2;k=3;

firstVectorForRed=[0,0,0];

secondVectorForRed=[0,0,0];

thirdVectorForRed=[0,0,0];

fourthVectorForRed=[i,j,k];

massfun=[fa, fb, fc];

massSort = sort(massfun);

fh = massSort(3);

fg = massSort(2);

fl = massSort(1);

massForRed = [i,j,k];

T=max(massForRed);

if fh==fa && fg==fb && fl==fc

xh1=a1;xh2=a2;xg1=b1;xg2=b2;xl1=c1;xl2=c2;

i=T+1; genius=1;%j=j;k=k;

end

if fh==fa && fg==fc && fl==fb

xl2=b2;xh1=a1;xg1=c1;xl1=b1;xh2=a2;xg2=c2;

i=T+1;genius=2;%j=j;k=k;

end

if fh==fb && fg==fa && fl==fc

xh1=b1;xg1=a1;xl1=c1;xh2=b2;xg2=a2;xl2=c2;

j=T+1;genius=3;%k=k;i=i;

end

if fh==fb && fg==fc && fl==fa

xh1=b1;xg1=c1;xl1=a1;xh2=b2;xg2=c2;xl2=a2;

j=T+1;genius=6;%i=i;k=k;

end

if fh==fc && fg==fa && fl==fb

xh1=c1;xg1=a1;xl1=b1;xh2=c2;xg2=a2;xl2=b2;

k=T+1;genius=4;% i=i;j=j;

end

if fh==fc && fg==fb && fl==fa

xh1=c1;xg1=b1;xl1=a1;xh2=c2;xg2=b2;xl2=a2;

k=T+1;genius=5;%i=i;j=j;

end

newLineMassForRed=[i,j,k];

firstVectorForRed=secondVectorForRed;

secondVectorForRed=thirdVectorForRed;

thirdVectorForRed=fourthVectorForRed;

fourthVectorForRed=newLineMassForRed;

end

xc1=(xl1+xg1)/2; %Средина отрезка напротив xh по первой

xc2=(xl2+xg2)/2;% и по второй координатах

xnew1=2*xc1-xh1;xnew2=2*xc2-xh2;

[fnew,count]=f(xnew1, xnew2,count);%Пробная точка, значение ф-ции в ней

if (fnew>=fh)

O=-1/2 %gamma

end

if (fnew<=fl)

O=2 %alpha

end

if (fnew>fl)&&(fnew<=fg)

O=1 %beta1

end

if (fnew<fh)&&(fnew>=fg)

O=1/2 %beta2

end

x1=(1+O)*(xc1-xh1)+xh1;

x2=(1+O)*(xc2-xh2)+xh2;

[fun,count]=f(x1,x2,count);

xKrit1=(xg1+xl1+x1)/3;

xKrit2=(xg2+xl2+x2)/3;

[fKrit,count]=f(xKrit1,xKrit2,count);

count = count - 1;

value = sqrt(((fg-fKrit)^2+(fl-fKrit)^2+(fun-fKrit)^2)/3);

RMSkrit=value

if genius==1

a1=x1;a2=x2; fa=fun;

b1=xg1;b2=xg2; fb=fg;

c1=xl1;c2=xl2; fc=fl;

end

if genius==2

a1=x1;a2=x2; fa=fun;

b1=xl1;b2=xl2; fb=fl;

c1=xg1;c2=xg2; fc=fg;

end

if genius==3

a1=xg1;a2=xg2; fa=fg;

b1=x1;b2=x2; fb=fun

c1=xl1;c2=xl2; fc=fl;

end

if genius==4

a1=xg1;a2=xg2; fa=fg;

b1=xl1;b2=xl2; fb=fl;

c1=x1;c2=x2; fc=fun;

end

if genius==5

a1=xl1;a2=xl2; fa=fl;

b1=xg1;b2=xg2; fb=fg;

c1=x1;c2=x2; fc=fun;

end

if genius==6

a1=xl1;a2=xl2; fa=fl;

b1=x1;b2=x2; fb=fun;

c1=xg1;c2=xg2; fc=fg;

end

end

finalMassFunValue = [fa,fb,fc]

disp('ans');

if min(finalMassFunValue)==fa

x1=a1;x2=a2;fa=vpa(fa)

end

if min(finalMassFunValue)==fb

x1=b1;x2=b2;fb=vpa(fb)

end

if min(finalMassFunValue)==fc

x1=c1;x2=c2;fc=vpa(fc)

end

count

end

Цільова функція - функція Розенброка

function [currentFunction, counterFunCalculate] = f (x1, x2,calc)

%Функция Розенброка, минимум которой ищем

counterFunCalculate=calc+1;

currentFunction = 100*(x1^2-x2)^2+(x1-1)^2

end

Метод ДСК-П

function approximationMethodValue = metAppro (x0, absDelta, e)

function F = fun (x) %Исходная функция

F = 100*((2.3199+x*(-2))^2-(0.3603+(-1)*x))^2 + ((2.3199+x*(-2))-1)^2;

end

count=0;

initialValue = fun(x0)

count=count+1;

plusValue = fun(x0+absDelta),count=count+1;

minusValue = fun(x0-absDelta),count=count+1;

if (minusValue>=initialValue)&(initialValue<=plusValue)

A=x0-absDelta

B=x0+absDelta

disp('Получен интервал')

delta=absDelta;

elseif(minusValue>=initialValue)&(initialValue>=plusValue)

delta=absDelta

disp('Шаг положительный')

lseif(minusValue<=initialValue)&(initialValue<=plusValue)

delta=-absDelta

disp('Шаг отрицательный')

elseif(minusValue<=initialValue)&(initialValue>=plusValue)

disp('Противоречит унимодальности')

end

xPrev=x0;

fPrev=fun(xPrev);count=count+1;

i=0;

xNext=xPrev+delta*2^i;

fNext=fun(xNext);count=count+1;

while (fPrev>=fNext)

xPrev=xNext;

fPrev=fNext;

i=i+1;

xNext=xPrev+delta*2^i

fNext=fun(xNext);count=count+1;

end

%Полшага назад

xBack=(xPrev+xNext)/2

fBack=fun(xBack);count=count+1;

xPrev

xPrevPrev=xPrev-(xNext-xBack)

fPrevPrev=fun(xPrevPrev);count=count+1;

[A, B, C] = ExeptInt (xPrevPrev,fPrevPrev,xPrev,fPrev,xBack,fBack,xNext,fNext)

kritEnd1=e+1 %Для входа в цикл

kritEnd2=2+e %Для входа в цикл

while (abs(kritEnd1)>e)&&(abs(kritEnd2)>e)

x1=A

x2=B

x3=C

[xS, fS, fx2] = findStar (A, B, C)

kritEnd1=x2-xS

kritEnd2=fx2-fS

allPoint=[x1, x2, x3, xS]

sortAllPoint=sort(allPoint)

x1=sortAllPoint(1)

x2=sortAllPoint(2)

x3=sortAllPoint(3)

x4=sortAllPoint(4)

[A, B, C] = ExeptInt (x1,fun(x1),x2,fun(x2),x3,fun(x3),x4,fun(x4))

count=count+4;

end

disp('Ответ:');

count

approximationMethodValue=vpa(xS);

end

Функція, яка використовується в методі ДСК-П

%Исключения интервала для 3х точек

function [leftLim, middlePoint, rightLim]=ExeptInt (a,fa,x1,fx1,x2,fx2,b,fb)

if (fx1>fx2)

leftLim=x1;

middlePoint=x2;

rightLim=b;

elseif (fx1==fx2)

leftLim=x1;

middlePoint=(x1+x2)/2 rightLim=x2;

else (fx1<fx2)

leftLim=a;

middlePoint=x1;

rightLim=x2;

end

if a>b

forHelp=leftLim;

leftLim=rightLim;

rightLim=forHelp;

end

end

Функція, яка використовується в методі ДСК-П

function [xStar, fStar, fx2]=findStar (a, b, c)

function F = fun (x) %Исходаная функция

F = 100*((2.3199+x*(-2))^2-(0.3603+(-1)*x))^2 + ((2.3199+x*(-2))-1)^2;

end

jk=abs(a-b);

j=round(jk*1000)/1000 %Округление до нужного, 4 порядка

ik=abs(c-b);

i=round(ik*1000)/1000 %Округление до нужного, 4 порядка

fx1=fun(a)

fx2=fun(b)

fx3=fun(c)

if i==j

xStar=(b+(i*(fx1-fx3)/(2*(fx1-2*fx2+fx3))))

else

a1=(fx2-fx1)/(b-a),

a2=(1/(c-b))*(((fx3-fx1)/(c-a))-((fx2-fx1)/(b-a))),

xStar=(a+b)/2-a1/(2*a2)

end

fStar=fun(xStar)

end

Метод золотого перерізу

function [leftLim,rightLim] =goldenSectionMethod (a, b, e)

Length=abs(b-a);

%Исходная функция. Другая каждую задачу

function F = fun (x)

F = 100*((0.25505290+x*(-2))^2-(-0.67212305+(-1)*x))^2 + ((0.25505290+x*(-2))-1)^2;

end

count=1;

x1=a+Length*0.382

x2=a+Length*0.618

while (Length>e)

fx1=fun(x1)

fx2=fun(x2),count=count+1;

if (fx1<fx2)

b=x2

Length=b-a

x2=x1

x1=a+Length*0.382

elseif (fx1>=fx2)

a=x1

Length=b-a

x1=x2

x2=a+Length*0.618

else disp('Что-то пошло не так');

end

end

disp('Ответ:');

count

leftLim=vpa(a);

rightLim=vpa(b);

end

Модифікації коду цільової функції для умовної оптимізації з опуклою допустимою областю

function [currentFunction, counterFunCalculate] = f (x1, x2,calc)

if (x1^2+(x2-1)^2)>0.25

disp('Вне области');

currentFunction=10^10;

elseif (x1^2+(x2-1)^2)<=0.25

disp('В области');

currentFunction = 100*(x1^2-x2)^2+(x1-1)^2

end

counterFunCalculate=calc+1;

end

Модифікації коду цільової функції для умовної оптимізації з невипуклою допустимою областю

function [currentFunction, counterFunCalculate] = f (x1, x2,calc)

if (((x1+7)^2 + (x2)^2) > 64)||((x1+4)^2 + (x2-2)^2 < 4)

disp('Вне области');

currentFunction=10^10;

else)

disp('В области');

currentFunction =100*(x1^2-x2)^2+(x1-1)^2

end

counterFunCalculate=calc+1;

end

Модифікації коду цільової функції для умовної оптимізації з лінійним обмеженням

function [currentFunction, counterFunCalculate] = f (x1, x2,calc)

if (2*x1+x2) < 4.999999

disp('Вне области');

currentFunction=10^10;

elseif (2*x1+x2) > 5.001

disp('В области');

currentFunction = 100*(x1^2-x2)^2+(x1-1)^2

disp('На границе');

currentFunction = 0;

end

counterFunCalculate=calc+1;

end

Размещено на Allbest.ru