МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
«ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»
Факультет інформатики та управління
Кафедра економічної кібернетики та маркетингового менеджменту
Курсова робота
З математичного програмування
Дослідження методів оптимізації
Харків 2009
РЕФЕРАТ
Дана курсова робота містить: 41 сторінку, 16 таблиць, 6 графіків.
У курсовій роботі розглянуті теоретичні основи двох методів оптимізації математичного програмування:
- Метод Нелдера-Міда;
- Градієнтний метод з подрібненням кроку.
Проведена мінімізація досліджуваної функції зазначеними методами. Виявлено залежність числа ітерацій від заданої точності. Зіставлена трудомісткість і ефективність оптимізації заданої функції різними методами (градієнтним і методом Нелдера-Міда).
Ключові терміни:
Градієнт - вектор перших приватних похідних функції.
Лінії рівня - безлічі точок, в яких функція приймає постійні значення, тобто
Методи нульового порядку - методи, які не передбачають обчислення похідної для пошуку оптимуму.
Методи першого порядку - методи, в яких крім обчислення функції в будь-якій точці пропонується обчислення перших похідних.
ЗМІСТ
1. Введення
2. Математичне опис методів оптимізації
2.1 Метод Нелдера-Міда
2.2 Градієнтний метод з подрібненням кроку
3. Рішення задачі мінімізації для кожного з методів
3.1 Метод Нелдера-Міда
3.2 Градієнтний метод з подрібненням кроку
4. Графічна інтерпретація розв'язання задачі
5. Аналітичне дослідження методів
6. Висновок
7. Додаток
8. Список літератури
СПИСОК УМОВНИХ ПОЗНАЧЕНЬ
- Точка
- Довжина кроку
- Вектор градієнт
E - точність
N - кількість ітерацій
Д - матриця координат симплекса
t - довжина ребра симплекса
1. ВСТУП
Об'єктом дослідження предмета математичне програмування є задачі оптимізації.
Оптимізація передбачає перебування найкращого варіанта серед усіх існуючих. У будь-якої практичної оптимізаційної задачі існує багато співпадаючих етапів. Найбільш важливим етапом є моделювання розглянутої фізичної ситуації з метою отримання математичної функції, яку необхідно мінімізувати, а також визначення обмежень, якщо такі існують. Потім слід вибрати відповідну процедуру для здійснення мінімізації. Ця процедура повинна бути реалізована на практиці, що в багатьох реальних випадках змушує використовувати ЕОМ для виконання великого обсягу обчислень.
Універсальних методів, придатних для пошуку екстремуму абсолютно будь-якої функції не існує. Ця курсова робота ставить собі за мету дослідити метод оптимізації нульового порядку - метод Нелдера-Міда, а також метод оптимізації першого порядку - градієнтний метод з подрібненням кроку на прикладі конкретної функції. Таким чином, отримавши практичні результати, можна буде порівняти ефективність даних методів, що застосовуються до досліджуваної функції.
ПОСТАНОВКА ЗАДАЧІ (Варіант завдання 1)
Дослідити функцію типу:
Використовувані методи його мінімізації :
Метод: Нелдера-Міда.
Метод: Градієнтний з подрібненням кроку.
Необхідно:
Вирішити задачу мінімізації , Почавши ітерації з обраної початкової точки x0 = (1; 1) заданими за варіантом методами, необхідна точність рішення . Привести таблицю результатів розрахунку типу: Ітерація: - Точка: значення: критерій: .
Розрахувати 3 лінії рівня функції і зобразити їх на графіку.
Відобразити на графіках ліній рівня для кожного з заданих методів траєкторію руху по итерациям (траєкторію узвозу).
Виявити залежність числа ітерацій N від заданої точності E, значення точності: , , , , , . Привести таблицю результатів як в п.1 для кожного значення E.
5. Порівняти ефективність розглянутих у варіанті методів за кількістю ітерацій N, побудувати графіки N = F (E).
2. МАТЕМАТИЧНЕ ОПИС МЕТОДІВ ОПТИМІЗАЦІЇ
Вводиться симплекс, координати вершин якого задані таблицею (одна з вершин на початку координат).
t - деяке вибране число.
Якщо n = 2, то при t = 1 маємо
Розташування симплекса показано на малюнку 2.1
Малюнок 2.1-Початкове розташування симплекса
Легко переконатися в тому, що якщо координати вершин симплекса задати відповідно до матриці Д 0, то відстань між двома будь-якими вершинами симплекса завжди дорівнюватиме обраної константі t незалежно від розмірності задачі n.
Дійсно, відстань між будь-вершиною x j, j = 2,3, .., n +1, і вершиною x 1 дорівнює
З іншого боку, відстань між будь-якою парою вершин , , , Так само Задамо початкову точку процедури пошуку мінімуму вектором Перенесемо вихідний симплекс таким чином, щоб вершина, що знаходилася на початку координат, опинилася в точці . Отримаємо матрицю
Обчислимо значення оптимизируемой функції в точках і переномеруем точки так, щоб виконувалися нерівності:
.
Знайдемо координати центру ваги фігури, що виходить в результаті видалення вершини :
Здійснимо відображення вершини відносно центра ваги. Отримаємо точку
Якщо a = 1, то отримаємо дзеркальне відображення. У одномірному випадку процедура відображення, яка забезпечує отримання точки , Симетричної точці щодо ілюструється рис. 2.2
Малюнок 2.2 - Побудова точки
Порівняємо тепер між собою значення
Можливі такі варіанти
а) . У цьому випадку виконується розтягнення симплекса і відшукується точка
Параметр звичайно приймається рівним 1,5.
Отримана крапка замінює , Якщо . В іншому випадку для заміни використовується точка .
б) . При цьому реалізується відображення. Точка замінює .
в) . У цьому випадку здійснюється стиск і відшукується точка
Параметр звичайно приймається рівним 0,5. Точка замінює .
г) . При цьому здійснюється редукція (зменшення розміру симплекса шляхом наближення всіх його вершин до вершини ). Координати вершин нового симплекса розраховуються за формулами
Критерій зупинки обчислювальної процедури має вигляд:
Критерій зупинки J є складовим. При цьому його компоненти мають різну вагу в залежності від того, який характер поведінки оптимизируемой функції в околиці екстремуму. Якщо в районі екстремуму оптимізується функція змінюється за типом «глибока западина», то більший внесок у чисельне значення критерію J вносить перший доданок, а друге при цьому швидко зменшується. Навпаки, якщо оптимізується функція змінюється за типом «пологе плато», то перший доданок швидко стає малим і тому другий доданок вносить більший внесок у величину критерію J.
Модифікація методу
Описаний «класичний» варіант побудови алгоритму методу Нелдера-Міда володіє конструктивним недоліком, який полягає в наступному. Припустимо, що оптимізується функція, для простоти, двох змінних має вигляд глибокого яру з дуже пологим дном. Тоді може трапитися так, що симплекс, який в даному випадку представляє собою трикутник, в якийсь момент двома вершинами ляже на дно яру, а третя опиниться на його схилі. При цьому на черговому кроці відбудеться перекидання цієї вершини на інший схил, а потім редукція чи стиснення симплекса. Якщо схил яру крутий, то ця процедура повториться багато разів, в результаті чого симплекс стиснеться і може спрацювати критерій зупину, хоча до точки мінімуму ще може бути дуже далеко. Природне удосконалення алгоритму полягає в наступному. Після спрацьовування критерію зупину доцільно побудувати над центром тяжіння сжавшегося симплекса новий, розміри якого відповідають вихідного симплекс. Нехай координати центру ваги сжавшегося симплекса утворюють вектор
Знайдемо тепер координати точки такий, що центр ваги симплекса з довжиною ребра, рівною t, що використовує вершину в якості початкової, збігався б з . Матриця координат зазначеного симплекса має вигляд
(2.1)
Координати центра ваги цього симплекса утворюють вектор
Тепер координати точки знайдемо з рівності = , Звідки
де
Підставляючи обчислені значення у вираз (2.1), отримаємо необхідний симплекс, використовуючи який продовжимо процедуру пошуку мінімуму. З іншого боку, для продовження процедури в якості початкової точки може бути використаний центр ваги «сжавшегося» симплекса. Що виникає при цьому зміщення нового симплекса щодо сжавшегося (точки передбачуваного зупинки) у багатьох випадках може навіть виявитися корисним. Цю процедуру вважаємо закінченою, якщо після чергового стиснення алгоритм приведе в точку, відстань від якої до точки попереднього стиснення не перевершує деякого досить малого .
Більшою ефективністю володіють ітераційні процедури, в яких наближення до мінімуму здійснюється одразу по всім змінним. При цьому завдання полягає в знаходженні послідовності векторів таких, що
(2.2)
Методи побудови таких послідовностей називають методами спуску. Нехай Поставимо задачу відшукання послідовності ., Збіжної до .
Виберемо довільним чином крапку , Напрямок і сконструіруем промінь
. (2.3)
Розглянемо питання про вибір напряму , Що забезпечує (2.2). Для цього вивчимо поведінку уздовж променя . Маємо
Введемо
(2.4)
Тут
Відповідно до (2.3)
Тоді
Обчислимо (2.5)
Тепер, щоб для будь-якого забезпечити заперечність (2.5), досить покласти , Де довільна позитивно певна матриця. Тоді
При цьому (2.6)
Вибравши будь-яким чином , Отримаємо Потім аналогічно розрахуємо
Загальне рекурентне співвідношення має вигляд:
(2.7)
Різні варіанти градієнтних процедур відрізняються один від одного способом вибору .
Отримане співвідношення (2.7) забезпечує побудова послідовності точок , Збіжної до точки , Що мінімізує . Зрозуміло, що кожна з точок цієї послідовності може розглядатися як деяке наближення до точки мінімуму , Положення якого, взагалі кажучи, залишається невідомим в ході всієї процедури спуску. Тому для всіх таких процедур принципової залишається проблема зупину. У обчислювальній практиці часто використовуються наступні критерії зупину:
(2.8)
(2.9)
де і -Деякі досить малі числа.
Зрозуміло, що критерій (2.8) гарний у тих випадках, коли функція в околиці мінімуму, використовуючи раніше введену класифікацію, має характер «глибокої» западини. З іншого боку, якщо функція веде себе як «пологе плато», то кращим є критерій (2.9). Аналогом критерію (2.8) є інше часто застосовується правило зупину:
, (2.10)
використовує необхідна умова екстремуму функції. Очевидним недоліком критеріїв (2.8) - (2.10) є те, що їх якість істотно залежить від абсолютних значень величини і компонентів векторів , . Більш універсальними є відносні критерії:
(2.11)
(2.12)
(2.13)
Зауважимо, що дуже часто на практиці використовуються складені критерії, що представляють собою лінійну комбінацію критеріїв (2.11) - (2.13), наприклад,
Іноді застосовують інший варіант побудови складеного критерію:
При реалізації градієнтного методу з подрібненням кроку в якості вибирають одиничну матрицю, тобто
а довжину кроку визначають шляхом перевірки деякого нерівності. При цьому основна рекурентне співвідношення (2.7) набуває вигляду:
Ясно, то якщо , Вибирати досить малим, то це забезпечить спадання , Але потрібно досить велика кількість кроків. Якщо ж необережно вибрати великим, то можна проскочити мінімум, а це небезпечно у зв'язку з можливим осціллірованіем. Для вибору кроку використовується правило Голдстейн-армій:
а) (2.14)
б) (2.15)
Виконання умови а) забезпечує вибір не надто великим. Виконання умови б) не дає можливість вибрати занадто малим.
Практична процедура будується наступним чином. Вибирається початкова точка і деяке початкове значення , Перевіряється (2.14) і, якщо воно виконується, то робиться крок у напрямку У новій точці обчислюється градієнт і знову перевіряється умова (2.14). У разі його задоволення просування до мінімуму триває з тим же кроком. Якщо ж воно не задовольняється, то параметр , Що визначає довжину кроку, ділять навпіл до тих пір, поки це нерівність не буде виконано. Потім виконується черговий крок. Процедура продовжується до виконання критерію зупину.
РІШЕННЯ ЗАДАЧІ МІНІМІЗАЦІЇ ДЛЯ КОЖНОГО З МЕТОДІВ
Метод Нелдера-Міда
Побудуємо симплекс складається з 3-х вершин. Довжину ребра t візьмемо рівною 1.
Початкові координати симплекса:
Проводимо сортування за значеннями функції для пошуку точки з найменшою функцією. Далі записуємо симплекс таким чином, щоб перша точка була кращою, а кожна наступна - гірше.
Для здійснення оптимізації обчислимо нову точку як відбиток самої «поганий» вершини щодо центра ваги симплекса. Формула для обчислення нової точки:
Потім, після порівняння значення функції в новій точці зі значеннями функції в інших трьох, а також після здійснення одного з чотирьох дій (заміни, стиснення, розтягування і редукції), будується новий симплекс.
Одне з чотирьох дій, зазначених вище, виконується відповідно до значенням функції в новій точці, по відношенню до значення функції в старих точках.
Заміна відбувається у випадку, якщо нова точка краще ніж краща.
Якщо виконується умова , То при цьому реалізується відображення. Точка замінює .
При виконанні умови здійснюється стиск і відшукується точка :
Параметр приймається рівним 0,5. Точка замінює . Таким чином отримана точка замінює саму «погану»
Якщо нова точка виявиться самої «поганий», необхідно здійснити редукцію (зменшення розміру симплекса шляхом наближення всіх його вершин до кращої вершині)
Після виконання зазначених дій перевіряється параметр зупину. У випадку, якщо він визнаний великим, ніж вибране значення точності, дії повторюються знову. Параметр зупину розраховується за формулою:
Результат роботи методу представлений в таблиці 3.1
Таблиця 3.1 - Рішення задачі мінімізації за допомогою методу Нелдера-Міда
Номер ітерації
Х1
Х2
Функція
Параметр зупину
1
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.
Градієнтний метод з подрібненням кроку
Для реалізації процедури необхідно обчислити градієнт:
У процедурі використовується критерій зупину, який обчислюється за формулою:
,
де E - задана точність рішення (в даній задачі E = ).
Результат роботи методу представлений в таблиці 3.2
Внаслідок того, що таблиця містить 1263 ітерації, доцільно надати перші і останні 25 ітерацій.
Таблиця 3.2 - Рішення задачі мінімізації за допомогою градієнтного методу
0,992187500
0,976562500
14,872248322711100
5,725771436
0,972112596
0,966700991
14,755778561425900
5,391343315
0,960252606
0,949298075
14,647453457158200
5,170831157
0,944120479
0,937143394
14,545808827169400
4,999364954
0,931250704
0,922455245
14,450015755630300
4,851038521
0,917052669
0,909905567
14,359522419103900
4,715343849
0,904265341
0,896648294
14,273894939963900
4,588117156
0,891210499
0,884368998
14,192768112137200
4,467486611
0,878869537
0,872030350
14,115817843495700
4,352565782
0,866628626
0,860230552
14,042753034754000
4,242801681
0,854831609
0,848589700
13,973308662686200
4,137814211
0,843250897
0,837314037
13,907242987828300
4,037283606
0,832001542
0,826261206
13,844334505896600
3,940936337
0,820995553
0,815497743
13,784380045189000
3,848521743
0,810266979
0,804966957
13,727192808899800
3,759812059
0,799778396
0,794686358
13,672600853099300
3,674595835
0,789535800
0,784630345
13,620445636362400
3,592677880
0,779520366
0,774799711
13,570580790710000
3,513876598
0,769728817
0,765180416
13,522870992857600
3,438023378
0,760149472
0,755767918
13,477190974079800
3,364961115
0,750776352
0,746552749
13,433424623226000
3,294543452
0,741600798
0,737528983
13,391464187766000
3,226633778
0,732616368
0,728689198
13,351209552529500
3,161104506
0,723815911
0,720027406
13,312567592195300
3,097836320
0,715193248
0,711537292
13,275451586431100
3,036717546
1239
0,000042461
12,000000003605800
0,000120097
1240
0,000042129
12,000000003549700
0,000119159
1241
0,000041800
12,000000003494500
0,000118228
1242
0,000041473
12,000000003440100
0,000117304
1243
0,000041149
12,000000003386500
0,000116388
1244
0,000040828
12,000000003333800
0,000115479
1245
0,000040509
12,000000003281900
0,000114576
1246
0,000040192
12,000000003230900
0,000113681
1247
0,000039878
12,000000003180600
0,000112793
1248
0,000039567
12,000000003131100
0,000111912
1249
0,000039258
12,000000003082300
0,000111038
1250
0,000038951
12,000000003034400
0,000110170
1251
0,000038647
12,000000002987100
0,000109309
1252
0,000038345
12,000000002940600
0,000108455
1253
0,000038045
12,000000002894900
0,000107608
1254
0,000037748
12,000000002849800
0,000106767
1255
0,000037453
12,000000002805500
0,000105933
1256
0,000037161
12,000000002761800
0,000105106
1257
0,000036870
12,000000002718800
0,000104285
1258
0,000036582
12,000000002676500
0,000103470
1259
0,000036296
12,000000002634800
0,000102662
1260
0,000036013
12,000000002593800
0,000101860
1261
0,000035731
12,000000002553500
0,000101064
1262
0,000035452
12,000000002513700
0,000100274
1263
0,000035175
12,000000002474600
0,000099491
У результаті реалізації градієнтного методу мінімальне значення функції становить . Даний оптимум досягнутий у точці . Цей метод дозволяє знайти мінімум (при початковій точці Х (1; 1) за 1263 ітерації при точності рішення . При цьому параметр зупину дорівнює 0,000099491.
4. ГРАФІЧНІ Інтерпритація РІШЕННЯ ЗАДАЧІ
Графік досліджуваної функції має вигляд:
Малюнок 4.1 - Графік досліджуваної функції
Зобразимо на малюнку (4.2) лінії рівня функції
Малюнок 4.2 - Лінії рівня досліджуваної функції
Відобразимо на графіках ліній рівня для кожного з заданих методів траєкторію спуску
Малюнок 4.3 - траєкторія спуску (метод Нелдера-Міда)
Малюнок 4.4 - траєкторія спуску (градієнтний метод)
АНАЛІТИЧНЕ ДОСЛІДЖЕННЯ МЕТОДІВ
Для виявлення залежності числа ітерацій від заданої точності методи реалізовані для кожного значення точності. Результати представлені в таблицях (5.1-5.6, 5.8-5.13)
Реалізація методу Нелдера-Міда:
Таблиця 5.1 - Реалізація методу Нелдера-Міда при
Таблиця 5.2 - Реалізація методу Нелдера-Міда при
Таблиця 5.3 - Реалізація методу Нелдера-Міда при
Таблиця 5.4 - Реалізація методу Нелдера-Міда при
Таблиця 5.5 - Реалізація методу Нелдера-Міда при
30
-0,0000145
0,0001182
12,000003012890
0,0000930
31
-0,0005185
-0,0004534
12,000002135678
0,0000765
32
-0,0005149
-0,0004829
12,000001171711
0,0000537
33
-0,0003880
-0,0003474
12,000000755753
0,0000486
34
-0,0002538
-0,0002710
12,000000487650
0,0000301
35
-0,0001568
-0,0001842
12,000000290103
0,0000249
36
-0,0001661
-0,0001816
12,000000155619
0,0000289
37
0,0000186
-0,0000052
12,000000128281
0,0000180
38
0,0000601
0,0000402
12,000000084592
0,0000102
39
0,0000243
0,0000074
12,000000049029
0,0000094
Таблиця 5.6 - Реалізація методу Нелдера-Міда при
40
0,0000716
0,0000655
12,000000032997
0,0000081
41
0,0000636
12,000000017601
0,0000061
42
0,0000522
12,000000011215
0,0000059
43
0,0000267
0,0000299
12,000000007565
0,0000034
44
0,0000136
0,0000178
12,000000004741
0,0000026
45
0,0000167
0,0000194
12,000000002493
0,0000031
46
-0,0000062
-0,0000033
12,000000002045
0,0000021
47
-0,0000104
-0,0000081
12,000000001302
0,0000012
48
-0,0000057
-0,0000037
12,000000000784
0,0000010
49
-0,0000094
-0,0000089
12,000000000507
0,0000009
Дані по кількості ітерацій і заданою точністю для методу Нелдера-Міда зведені в таблицю 5.7
Таблиця 5.7 - Залежність числа ітерацій від точності
Точність
Кількість ітерацій
0,1
0,01
0,001
0,0001
0,00001
0,000001
Малюнок 5.1 - Графічне представлення залежності кількості ітерацій N від точності E для методу Нелдера-Міда.
Для градієнтного методу, беручи до уваги велику кількість ітерацій, доцільно наводити для кожної реалізації перші і останні 25 ітерацій.
Реалізація градієнтного методу:
Таблиця 5.8 - Реалізація градієнтного методу при
358
0,042588763
0,042587983
12,003630828695700
0,120676586
359
0,042255429
0,042254667
12,003574166022100
0,119728711
360
0,041924713
0,041923969
12,003518389968100
0,118788359
361
0,041596595
0,041595868
12,003463486588100
0,117855470
362
0,041271053
0,041270343
12,003409442157800
0,116929982
363
0,040948069
0,040947375
12,003356243171100
0,116011835
364
0,040627620
0,040626943
12,003303876336500
0,115100970
365
0,040309688
0,040309026
12,003252328573200
0,114197326
366
0,039994251
0,039993605
12,003201587008200
0,113300844
367
0,039681292
0,039680660
12,003151638972600
0,112411467
368
0,039370788
0,039370172
12,003102471998700
0,111529137
369
0,039062723
0,039062121
12,003054073816300
0,110653795
370
0,038757075
0,038756487
12,003006432349600
0,109785386
371
0,038453826
0,038453252
12,002959535714300
0,108923853
372
0,038152957
0,038152396
12,002913372214400
0,108069140
373
0,037854448
0,037853901
12,002867930339100
0,107221192
374
0,037558283
0,037557747
12,002823198760000
0,106379954
375
0,037264440
0,037263918
12,002779166327700
0,105545371
376
0,036972904
0,036972393
12,002735822069600
0,104717390
377
0,036683654
0,036683156
12,002693155186500
0,103895956
378
0,036396674
0,036396187
12,002651155050100
0,103081018
379
0,036111944
0,036111468
12,002609811200200
0,102272522
380
0,035829448
0,035828983
12,002569113341800
0,101470417
381
0,035549167
0,035548714
12,002529051343000
0,100674650
382
0,035271085
0,035270642
12,002489615231500
0,099885171
Таблиця 5.9 - Реалізація градієнтного методу при
652
0,004240917
0,004240916
12,000035971071500
0,011995339
653
0,004207784
12,000035411204000
0,011901621
654
0,004174910
12,000034860050800
0,011808634
655
0,004142293
12,000034317476100
0,011716375
656
0,004109931
0,004109930
12,000033783346400
0,011624836
657
0,004077822
0,004077821
12,000033257530400
0,011534012
658
0,004045963
12,000032739898600
0,011443898
659
0,004014354
0,004014353
12,000032230323500
0,011354489
660
0,003982991
0,003982990
12,000031728679900
0,011265777
661
0,003951873
12,000031234844100
0,011177759
662
0,003920999
0,003920998
12,000030748694800
0,011090429
663
0,003890366
0,003890365
12,000030270112300
0,011003781
664
0,003859972
0,003859971
12,000029798978700
0,010917810
665
0,003829815
12,000029335178200
0,010832511
666
0,003799894
12,000028878596500
0,010747878
667
0,003770207
12,000028429121400
0,010663907
668
0,003740752
0,003740751
12,000027986642200
0,010580592
669
0,003711527
0,003711526
12,000027551050000
0,010497927
670
0,003682530
12,000027122237600
0,010415909
671
0,003653760
12,000026700099600
0,010334531
672
0,003625215
0,003625214
12,000026284531900
0,010253790
673
0,003596892
12,000025875432400
0,010173679
674
0,003568791
12,000025472700300
0,010094194
675
0,003540910
0,003540909
12,000025076236600
0,010015330
676
0,003513246
12,000024685943600
0,009937082
Таблиця 5.10 - Реалізація градієнтного методу при
945
0,000426015
12,000000362977700
0,001204953
946
0,000422687
12,000000357328300
0,001195539
947
0,000419385
12,000000351766900
0,001186199
948
0,000416108
12,000000346292000
0,001176932
949
0,000412857
12,000000340902300
0,001167737
950
0,000409632
12,000000335596500
0,001158614
951
0,000406432
12,000000330373300
0,001149562
952
0,000403256
12,000000325231400
0,001140581
953
0,000400106
12,000000320169500
0,001131671
954
0,000396980
12,000000315186400
0,001122829
955
0,000393879
12,000000310280800
0,001114057
956
0,000390801
12,000000305451600
0,001105354
957
0,000387748
12,000000300697600
0,001096718
958
0,000384719
12,000000296017600
0,001088150
959
0,000381713
12,000000291410300
0,001079649
960
0,000378731
12,000000286874800
0,001071214
961
0,000375772
12,000000282409900
0,001062845
962
0,000372837
12,000000278014500
0,001054542
963
0,000369924
12,000000273687500
0,001046303
964
0,000367034
12,000000269427800
0,001038129
965
0,000364166
12,000000265234500
0,001030018
966
0,000361321
12,000000261106400
0,001021971
967
0,000358499
12,000000257042500
0,001013987
968
0,000355698
12,000000253041900
0,001006066
969
0,000352919
12,000000249103600
0,000998206
Таблиця 5.11 - Реалізація градієнтного методу при
Таблиця 5.12 - Реалізація градієнтного методу при
1532
0,000004265
12,000000000036400
0,000012064
1533
0,000004232
12,000000000035800
0,000011970
1534
0,000004199
12,000000000035300
0,000011877
1535
0,000004166
12,000000000034700
0,000011784
1536
0,000004134
12,000000000034200
0,000011692
1537
0,000004101
12,000000000033600
0,000011600
1538
0,000004069
12,000000000033100
0,000011510
1539
0,000004038
12,000000000032600
0,000011420
1540
0,000004006
12,000000000032100
0,000011331
1541
0,000003975
12,000000000031600
0,000011242
1542
0,000003944
12,000000000031100
0,000011154
1543
0,000003913
12,000000000030600
0,000011067
1544
0,000003882
12,000000000030100
0,000010981
1545
0,000003852
12,000000000029700
0,000010895
1546
0,000003822
12,000000000029200
0,000010810
1547
0,000003792
12,000000000028800
0,000010725
1548
0,000003762
12,000000000028300
0,000010641
1549
0,000003733
12,000000000027900
0,000010558
1550
0,000003704
12,000000000027400
0,000010476
1551
0,000003675
12,000000000027000
0,000010394
1552
0,000003646
12,000000000026600
0,000010313
1553
0,000003618
12,000000000026200
0,000010232
1554
0,000003589
12,000000000025800
0,000010152
1555
0,000003561
12,000000000025400
0,000010073
1556
0,000003534
12,000000000025000
0,000009994
Таблиця 5.13-Реалізація градієнтного методу при
1826
0,000000425
12,000000000000400
0,000001202
1827
0,000000422
0,000001193
1828
0,000000419
0,000001184
1829
0,000000415
12,000000000000300
0,000001174
1830
0,000000412
0,000001165
1831
0,000000409
0,000001156
1832
0,000000406
0,000001147
1833
0,000000402
0,000001138
1834
0,000000399
0,000001129
1835
0,000000396
0,000001120
1836
0,000000393
0,000001112
1837
0,000000390
0,000001103
1838
0,000000387
0,000001094
1839
0,000000384
0,000001086
1840
0,000000381
0,000001077
1841
0,000000378
0,000001069
1842
0,000000375
0,000001061
1843
0,000000372
0,000001052
1844
0,000000369
0,000001044
1845
0,000000366
0,000001036
1846
0,000000363
0,000001028
1847
0,000000361
0,000001020
1848
0,000000358
0,000001012
1849
0,000000355
0,000001004
1850
0,000000352
12,000000000000200
0,000000996
Дані по кількості ітерацій і заданою точністю для градієнтного методу зведені в таблицю 5.14
Таблиця 5.14 - Залежність числа ітерацій від точності
Малюнок 5.2 - Графічне представлення залежності кількості ітерацій N від точності E для градієнтного методу.
Таким чином, аналізуючи отримані залежності можна зробити висновок про те, що метод Нелдера-Міда є більш ефективним. Так само слід зазначити, що градієнтний метод швидко наближається до екстремуму, коли поточна точка знаходиться далеко від нього, і різко сповільнюється поблизу екстремуму.
Слід зауважити, що ефективність застосування методів оптимізації перш за все обумовлена видом функції.
6. ВИСНОВОК
У курсовій роботі зроблена мінімізації функції за допомогою методу оптимізації нульового порядку - методу Нелдера-Міда і методу оптимізації першого порядку - градієнтного методу з подрібненням кроку.
У результаті реалізації градієнтного методу мінімальне значення функції становить . Даний оптимум досягнутий у точці . Цей метод дозволяє знайти мінімум (при початковій точці Х (1; 1)) за 1263 ітерації при точності рішення . При цьому параметр зупину дорівнює 0,000099491.
Для кожного з методів була встановлена залежність числа ітерацій від заданої точності. Аналізуючи отримані результати, можна зробити висновок про те, що за кількістю ітерацій більш ефективним є метод Нелдера-Міда. Однак слід зазначити, що ефективність цих методів може змінюватися в залежності від вибору початкового наближення і виду функції. Слід також врахувати, що градієнтний метод може бути непридатний в тих випадках, якщо розрахунок похідних викликає утруднення.
7. ДОДАТОК
У таблицях подано координати точок, що утворюють лінії рівня
У цьому додатку представлена реалізація програмного коду для кожного з методів оптимізації. Використовувана мова програмування - Visual Studio C # 2005.
namespace GradientL
{Public partial class Form1: Form
{Public Form1 ()
{InitializeComponent ();}
public static string [] str = new string [100000];
struct Tk
{Public double x1, x2;
public Tk (double X, double Y)
{X1 = X;
x2 = Y;}
public static Tk operator / (Tk v1, double q)
{Return new Tk (v1.x1 / q, v1.x2 / q);}
public static Tk operator * (Tk v, double d)
{Return new Tk (v.x1 * d, v.x2 * d);}
public static Tk operator * (Tk v1, Tk v2)
{Return new Tk (v1.x1 * v2.x1, v1.x2 * v2.x2);}
public static Tk operator - (Tk v1, Tk v2)
{Return new Tk (v1.x1 - v2.x1, v1.x2 - v2.x2);}
public static Tk operator + (Tk v1, Tk v2)
{Return new Tk (v1.x1 + v2.x1, v1.x2 + v2.x2);}
public static double Dist (Tk v1, Tk v2)
{Return Math.Sqrt ((v1.x1 - v2.x1) * (v1.x1 - v2.x1) + (v1.x2 - v2.x2) * (v1.x2 - v2.x2));}
public override string ToString ()
{Return "(" + this.x1.ToString ("f5") + ";" + this.x2.ToString ("f5") + ")";}}
class Pr
{Public static double f (Tk c)
{Return 12 + c.x1 * c.x1 + (1 + c.x2 * c.x2) * c.x2 * c.x2 + (c.x1 * c.x1 * c.x2 * c.x2 + 100 ) * (c.x1 - c.x2) * (c.x1 - c.x2);}
static Tk gradient (Tk c)
{Tk N = new Tk (2 * c.x1 + 2 * c.x1 * c.x2 * c.x2 *
(C.x1 - c.x2) * (c.x1 - c.x2) + 2 * (c.x1 * c.x1 * c.x2 * c.x2 + 100) * (c.x1 - c.x2 ),
2 * c.x2 * c.x2 * c.x2 +2 * c.x2 * (1 + c.x2 * c.x2) +
2 * c.x2 * c.x1 * c.x1 * (c.x1-c.x2) * (c.x1-c.x2) -2 * (c.x1-c.x2) *
(C.x1 * c.x1 * c.x2 * c.x2 +100));
return N;}
public static double Dl (Tk c)
{Return Math.Sqrt (c.x1 * c.x1 + c.x2 * c.x2);}
public static void Tr (double eps, ref Tk ca, out double fn, out int i)
{Tk cb = new Tk (1, 1), st = new Tk (0.5, 0.5);
Tk step = new Tk (1, 1), eq; i = 0;
do
{While (true)
{Cb = ca - step * gradient (ca);
eq = st * step * gradient (cb) * gradient (cb);
if (f (cb - step * gradient (cb))> = (f (cb) - Dl (eq)))
{Step.x1 / = 2;
step.x2 / = 2;}
else break;}
fn = f (ca);
i + +;
str [i] = String.Format ("{0}" + ")" + "{1}" + ";" +
"{2}" + ";" + "{3}" + ".", I.ToString (), ca.ToString (), fn.ToString ("f6"), Dl (gradient (cb)). ToString ("f6"));
ca = cb;}
while (Dl (gradient (cb))> = eps);
fn = f (cb);}}
private void button1_Click (object sender, EventArgs e)
{ListBox1.Items.Clear ();
double Et = Convert.ToDouble (textBox3.Text);
double fn;
int j;
Tk mas = new Tk (Convert.ToDouble (textBox1.Text), Convert.ToDouble (textBox2.Text));
Pr.Tr (Et, ref mas, out fn, out j);
Min.Visible = true;
Min.Text = String.Format ("{0}" + ";" + "{1}" + ";" +
"{2}", mas.ToString (), fn.ToString (), j.ToString ());
for (int i = 1; i
listBox1.Items.Add (str [i]);}
private void Form1_Load (object sender, EventArgs e ){}}}
namespace Nelder_Method
static double Al = 1.0;
static double Bt = 0.5;
static double Gm = 2.0;
static int n = 0;
static string [] op = new string [1000];
const int cap = 2;
class Cnt
{Public static double function (Tk c)
{Return 12 + c.x1 * c.x1 + (1 + c.x2 * c.x2) * c.x2 * c.x2 + (c.x1 * c.x1 * c.x2 * c.x2 +100 ) * (c.x1-c.x2) * (c.x1-c.x2);}
public static void Pr (ref Tk [] c, ref double [] ot)
{Double fir; Tk tk;
for (int k = 1; k <= cap; k + +)
for (int l = k; l> = 1; l -)
if (ot [l - 1]> ot [l])
{Fir = ot [l];
tk = c [l];
ot [l] = ot [l - 1];
c [l] = c [l - 1];
ot [l - 1] = fir;
c [l - 1] = tk;}
public static bool Ostanov (Tk [] w, double E, double n, Tk c, out double Ost)
{Double Lp;
double d = 0.5;
double p1 = 0;
Tk p2 = new Tk (0, 0);
for (int i = 0; i <= cap; i + +)
{P1 + = (function (w [i]) - function (c)) * (function (w [i]) - function (c));
p2 + = (w [i] - c) * (w [i] - c);}
Lp = Math.Sqrt (p2.x1 * p2.x1 + p2.x2 * p2.x2);
Ost = d * (Math.Sqrt ((1 / (n + 1)) * p1)) + (1 - d) * (Math.Sqrt ((1 / (n + 1)) * Lp));
if (Ost
return true;
else return false;}
public static double Met (Tk [] c, double tchn)
{Double [] f = new double [cap + 1];
double val1 = 0, val2 = 0, val3 = 0, val4, val5, val6, val7;
Tk sim1, sim2, sim3, sim4, sim5, sim6, sim_cen, sim7;
sim_cen.x1 = sim_cen.x2 = 0;
int i;
double J1;
bool flag;
for (i = 0; i <= cap; i + +) / / Обчислення значень функції на початковому симплекс
f [i] = function (c [i]);
while (! Ostanov (c, tchn, n, sim_cen, out J1)) / / Перевірка на умова виходу
{N + +;
/ / Крок 1. Сортування
Pr (ref c, ref f);
sim1 = c [cap]; val1 = f [cap];
sim2 = c [cap - 1]; val2 = f [cap - 1];
sim3 = c [0]; val3 = f [0];
/ / Крок 2. Обчислення центру ваги симплекса
for (i = 0; i
sim_cen = sim_cen + c [i];
sim_cen = sim_cen / cap;
/ / 3Шаг. Відображення
sim4 = sim_cen * (1 + Al) - sim1 * Al; val4 = function (sim4);
/ / Крок 4.
if (val4 <= val3)
{/ / Крок 4a.
sim5 = sim_cen * (1 - Gm) + sim4 * Gm;
val5 = function (sim5);
if (val5
{C [cap] = sim5;
f [cap] = val5;}
else
{C [cap] = sim4;
f [cap] = val4;}}
if ((val3
{/ / Крок 4.b
c [cap] = sim4;
f [cap] = val4;}
flag = false;
if ((val1> = val4) & & (val4> val2))
{/ / Крок 4c.
flag = true;
val7 = val1;
sim7 = sim1;
f [cap] = val4;
sim4 = sim7;
val4 = val7;}
/ / Крок 4d.
if (val4> val1) flag = true;
if (flag)
{/ / Крок 5. Стиснення
sim6 = sim1 * Bt + sim_cen * (1 - Bt);
val6 = function (sim6);
if (val6
{/ / Крок 6.
c [cap] = sim6;
f [cap] = val6;
sim6 = sim7;
val6 = val7;}
{/ / Крок 7. Глобальне стиск
for (i = 0; i <= cap; i + +)
c [i] = sim3 + (c [i] - sim3) / 2;}}
op [n - 1] = Convert.ToString (n) + ";" + sim1.ToString () +
";" + Sim2.ToString () + ";" + sim3.ToString ();}
return (val3 + val1 + val2) / 3;}}
{Tk ta = new Tk (0, 0);
Tk tb = new Tk (0.26, 0.96);
Tk tc = new Tk (0.96, 0.26);
Tk [] t = new Tk [3] {ta, tb, tc};
listBox1.Items.Clear ();
n = 0;
op = new string [200];
double eps1 = Convert.ToDouble (textBox2.Text);
label4.Text = Cnt.Met (t, eps1). ToString ("f5") + ";" + Convert.ToString (n) + ".";
for (int i = 0; i
listBox1.Items.Add (op [i]);}
private void Form1_Load (object sender, EventArgs e) {}}
8. Список використаної літератури
Агуров П.В. C # в оригіналі (програмування на мові С #) - Петербург, 2006
Агуров П.В. Збірник рецептів по C # - Петербург, 2006
Банді Б. Методи оптимізації - Москва, 1988
Базару М, Шетті К. Нелінійне программіроваіне. Теорія і алгоритми - М.: Мир, 1988
Поляк Б.Т. Введення в оптимізацію. - М.: Наука, 1983
Раскін Л.Г. Математичне програмування: Навчальний посібник - Харків: НТУ «ХПІ», 2002
Ріхтер Д. Програмування на платформі Microsoft. NET Freamework для професіоналів - М. Microsoft Press, 2003
Сіра О.В. Методичні вказівки для проведення лабораторних робіт з курсу «Математичне програмування» - Харків: НТУ «ХПІ», 2003
Сухарєв А.Г., Тимохов А.В Курс методів оптимізації - М.: Наука, 1986
Гіммельблау Д. Прикладне нелінійне програмування М.: Світ, 1989