Курсовая работа: Исследование методов оптимизации

Если новая точка окажется самой «плохой», необходимо осуществить редукцию (уменьшение размера симплекса путем приближения всех его вершин к лучшей вершине)

После выполнения указанных действий проверяется параметр останова. В случае, если он признан большим, чем выбранное значение точности, действия повторяются снова. Параметр останова рассчитывается по формуле :

Результат работы метода представлен в таблице 3.1

Таблица 3.1 – Решение задачи минимизации при помощи метода Нелдера-Мида

Номер итерации	Х1	Х2	Функция	Параметр останова
1	0,4066667	0,4066667	45,631123492267	14,5885289
2	0,4433333	0,2683333	29,870063661634	2,8471538
3	0,3141667	0,2704167	16,456883364840	0,8308005
4	0,2495833	0,2714583	13,667862520021	0,3301516
5	0,2194792	0,2030729	12,662220410942	0,1540974
6	0,1796615	0,1864974	12,281326901893	0,0870517
7	0,1546549	0,1481608	12,136891733007	0,0558708
8	0,1284945	0,1302889	12,072845463097	0,0394655
9	0,1094511	0,1066526	12,044325208099	0,0355389
10	0,0380868	0,0472725	12,032057545239	0,0204381
11	0,0107240	0,0206094	12,021017539213	0,0124410
12	0,0217244	0,0287886	12,011093940034	0,0130068
13	-0,0220008	-0,0163585	12,008732867306	0,0089109
14	-0,0274319	-0,0235556	12,005248404276	0,0053110
15	-0,0178584	-0,0140681	12,003293104515	0,0042019
16	-0,0191470	-0,0189750	12,002069416305	0,0030794
17	-0,0146824	-0,0154579	12,001121615618	0,0025320
18	-0,0132441	-0,0133520	12,000655246493	0,0026725
19	-0,0028766	-0,0042119	12,000504634754	0,0015212
20	0,0004344	-0,0008739	12,000339347268	0,0009248
21	-0,0013297	-0,0023245	12,000183034613	0,0009948
22	0,0035282	0,0029010	12,000137117579	0,0007582
23	0,0038607	0,0034821	12,000078476732	0,0004900
24	0,0027293	0,0023210	12,000050320679	0,0004156
25	0,0022628	0,0023222	12,000031684386	0,0002830
26	0,0015804	0,0017419	12,000017894979	0,0002411
27	0,0015265	0,0015966	12,000009969113	0,0002705
28	0,0001079	0,0002907	12,000008036464	0,0001594
29	-0,0002737	-0,0001084	12,000005403290	0,0000921

В результате решения задачи минимизации с помощью метода Нелдера-Мида получено следующее значение функции : . Данный оптимум достигается в точке . Этот метод позволяет найти минимум (при начальной точке Х (1 ; 1)) за 29 итераций при точности решения . При этом параметр останова равен 0,0000921.

3.2 Градиентный метод с дроблением шага

Для реализации процедуры необходимо вычислить градиент:

В процедуре используется критерий останова, который вычисляется по формуле:

,

где E – заданная точность решения (в данной задаче E=).

Результат работы метода представлен в таблице 3.2

Вследствие того, что таблица содержит 1263 итерации, целесообразно предоставить первые и последние 25 итераций.

Таблица 3.2 – Решение задачи минимизации при помощи градиентного метода

Номер итерации	Х1	Х2	Функция	Параметр останова
1	0,992187500	0,976562500	14,872248322711100	5,725771436
2	0,972112596	0,966700991	14,755778561425900	5,391343315
3	0,960252606	0,949298075	14,647453457158200	5,170831157
4	0,944120479	0,937143394	14,545808827169400	4,999364954
5	0,931250704	0,922455245	14,450015755630300	4,851038521
6	0,917052669	0,909905567	14,359522419103900	4,715343849
7	0,904265341	0,896648294	14,273894939963900	4,588117156
8	0,891210499	0,884368998	14,192768112137200	4,467486611
9	0,878869537	0,872030350	14,115817843495700	4,352565782
10	0,866628626	0,860230552	14,042753034754000	4,242801681
11	0,854831609	0,848589700	13,973308662686200	4,137814211
12	0,843250897	0,837314037	13,907242987828300	4,037283606
13	0,832001542	0,826261206	13,844334505896600	3,940936337
14	0,820995553	0,815497743	13,784380045189000	3,848521743
15	0,810266979	0,804966957	13,727192808899800	3,759812059
16	0,799778396	0,794686358	13,672600853099300	3,674595835
17	0,789535800	0,784630345	13,620445636362400	3,592677880
18	0,779520366	0,774799711	13,570580790710000	3,513876598
19	0,769728817	0,765180416	13,522870992857600	3,438023378
20	0,760149472	0,755767918	13,477190974079800	3,364961115
21	0,750776352	0,746552749	13,433424623226000	3,294543452
22	0,741600798	0,737528983	13,391464187766000	3,226633778
23	0,732616368	0,728689198	13,351209552529500	3,161104506
24	0,723815911	0,720027406	13,312567592195300	3,097836320
25	0,715193248	0,711537292	13,275451586431100	3,036717546
1239	0,000042461	0,000042461	12,000000003605800	0,000120097
1240	0,000042129	0,000042129	12,000000003549700	0,000119159
1241	0,000041800	0,000041800	12,000000003494500	0,000118228
1242	0,000041473	0,000041473	12,000000003440100	0,000117304
1243	0,000041149	0,000041149	12,000000003386500	0,000116388
1244	0,000040828	0,000040828	12,000000003333800	0,000115479
1245	0,000040509	0,000040509	12,000000003281900	0,000114576
1246	0,000040192	0,000040192	12,000000003230900	0,000113681
1247	0,000039878	0,000039878	12,000000003180600	0,000112793
1248	0,000039567	0,000039567	12,000000003131100	0,000111912
1249	0,000039258	0,000039258	12,000000003082300	0,000111038
1250	0,000038951	0,000038951	12,000000003034400	0,000110170
1251	0,000038647	0,000038647	12,000000002987100	0,000109309
1252	0,000038345	0,000038345	12,000000002940600	0,000108455
1253	0,000038045	0,000038045	12,000000002894900	0,000107608
1254	0,000037748	0,000037748	12,000000002849800	0,000106767
1255	0,000037453	0,000037453	12,000000002805500	0,000105933
1256	0,000037161	0,000037161	12,000000002761800	0,000105106
1257	0,000036870	0,000036870	12,000000002718800	0,000104285
1258	0,000036582	0,000036582	12,000000002676500	0,000103470
1259	0,000036296	0,000036296	12,000000002634800	0,000102662
1260	0,000036013	0,000036013	12,000000002593800	0,000101860
1261	0,000035731	0,000035731	12,000000002553500	0,000101064
1262	0,000035452	0,000035452	12,000000002513700	0,000100274
1263	0,000035175	0,000035175	12,000000002474600	0,000099491

В результате реализации градиентного метода минимальное значение функции составляет . Данный оптимум достигнут в точке . Этот метод позволяет найти минимум (при начальной точке Х(1;1) за 1263 итерации при точности решения . При этом параметр останова равен 0,000099491.

4. ГРАФИЧЕСКАЯ ИНТЕРПРИТАЦИЯ РЕШЕНИЯ ЗАДАЧИ

График исследуемой функции имеет вид :

Рисунок 4.1 – График исследуемой функции

Изобразим на рисунке (4.2) линии уровня функции

Рисунок 4.2 – Линии уровня исследуемой функции

Отобразим на графиках линий уровня для каждого из заданных методов траекторию спуска

Рисунок 4.3 – траектория спуска (метод Нелдера-Мида)

Рисунок 4.4 – траектория спуска (градиентный метод)

5. АНАЛИТИЧЕСКОЕ ИССЛЕДОВАНИЕ МЕТОДОВ

Для выявления зависимости числа итераций от заданной точности методы реализованы для каждого значения точности. Результаты представлены в таблицах (5.1-5.6, 5.8-5.13)

Реализация метода Нелдера-Мида :

Таблица 5.1 – Реализация метода Нелдера-Мида при

Номер итерации	Х1	Х2	Функция	Параметр останова
1	0,4066667	0,4066667	45,631123492267	14,5885289
2	0,4433333	0,2683333	29,870063661634	2,8471538
3	0,3141667	0,2704167	16,456883364840	0,8308005
4	0,2495833	0,2714583	13,667862520021	0,3301516
5	0,2194792	0,2030729	12,662220410942	0,1540974
6	0,1796615	0,1864974	12,281326901893	0,0870517

Таблица 5.2 – Реализация метода Нелдера-Мида при

Номер итерации	Х1	Х2	Функция	Параметр останова
1	0,4066667	0,4066667	45,631123492267	14,5885289
2	0,4433333	0,2683333	29,870063661634	2,8471538
3	0,3141667	0,2704167	16,456883364840	0,8308005
4	0,2495833	0,2714583	13,667862520021	0,3301516
5	0,2194792	0,2030729	12,662220410942	0,1540974
6	0,1796615	0,1864974	12,281326901893	0,0870517
7	0,1546549	0,1481608	12,136891733007	0,0558708
8	0,1284945	0,1302889	12,072845463097	0,0394655
9	0,1094511	0,1066526	12,044325208099	0,0355389
10	0,0380868	0,0472725	12,032057545239	0,0204381
11	0,0107240	0,0206094	12,021017539213	0,0124410
12	0,0217244	0,0287886	12,011093940034	0,0130068
13	-0,0220008	-0,0163585	12,008732867306	0,0089109

Таблица 5.3 – Реализация метода Нелдера-Мида при

Номер итерации	Х1	Х2	Функция	Параметр останова
1	0,4066667	0,4066667	45,631123492267	14,5885289
2	0,4433333	0,2683333	29,870063661634	2,8471538
3	0,3141667	0,2704167	16,456883364840	0,8308005
4	0,2495833	0,2714583	13,667862520021	0,3301516
5	0,2194792	0,2030729	12,662220410942	0,1540974
6	0,1796615	0,1864974	12,281326901893	0,0870517
7	0,1546549	0,1481608	12,136891733007	0,0558708
8	0,1284945	0,1302889	12,072845463097	0,0394655
9	0,1094511	0,1066526	12,044325208099	0,0355389
10	0,0380868	0,0472725	12,032057545239	0,0204381
11	0,0107240	0,0206094	12,021017539213	0,0124410
12	0,0217244	0,0287886	12,011093940034	0,0130068
13	-0,0220008	-0,0163585	12,008732867306	0,0089109
14	-0,0274319	-0,0235556	12,005248404276	0,0053110
15	-0,0178584	-0,0140681	12,003293104515	0,0042019
16	-0,0191470	-0,0189750	12,002069416305	0,0030794
17	-0,0146824	-0,0154579	12,001121615618	0,0025320
18	-0,0132441	-0,0133520	12,000655246493	0,0026725
19	-0,0028766	-0,0042119	12,000504634754	0,0015212
20	0,0004344	-0,0008739	12,000339347268	0,0009248