МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
«ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»
Факультет інформатики та управління
Кафедра економічної кібернетики та маркетингового менеджменту
Курсова робота
З математичного програмування
Дослідження методів оптимізації
Харків 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. МАТЕМАТИЧНЕ ОПИС МЕТОДІВ ОПТИМІЗАЦІЇ
2.1 Метод Нелдера-Міда
Вводиться симплекс, координати вершин якого задані таблицею (одна з вершин на початку координат).
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.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 | 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 - Рішення задачі мінімізації за допомогою градієнтного методу
Номер ітерації | Х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 |