Прямі методи безумовної мінімізації функцій - Курсовая работа

Так як поведінку будь-якого фізичного обєкта можна описати певною функціональною залежністю (тобто створити математичну модель реального обєкта), то питання найоптимальнішого використання даного обєкта призводить до необхідності розвязання відповідної задачі оптимізації. Кожну задачу оптимізації, зрештою, можна звести до розвязання задачі мінімізації (для того, щоб знайти максимум функції f(x) достатньо знайти мінімум функції-f(x)). Для реалізації мети визначено наступні завдання: 1. проаналізувати прямі методи одновимірної безумовної мінімізації такі як метод дихотомії та золотого перерізу, 2. проаналізувати прямі методи багатовимірної безумовної мінімізації такі як метод покоординатного циклічного спуску, алгоритм Хука-Дживса, метод правильного і деформованого симплексу, 3. для зазначених методів описати покроково відповідні алгоритми. Обєктом дослідження даної курсової роботи виступають прямі методи безумовної одно-і багатовимірної мінімізації функцій, предметом же дослідження є такі методи як: метод дихотомії, метод золотого перерізу, метод покоординатного циклічного спуску, алгоритм Хука-Дживса, методи правильного і деформованого симплексу.У досить загальному вигляді математичну задачу мінімізації можна сформулювати наступним чином: мінімізувати цільову функцію з урахуванням обмежень, накладених на змінні. Під мінімізацією функції n змінних f (x) = f(x1,.., xn) на заданій множині U n-мірного векторного простору En розуміють визначення хоча б однієї з точок мінімуму цієї функції на множині U, а також, якщо це необхідно, і мінімального на U значення f(x). Записуючи математичні задачі мінімізації в загальному вигляді, зазвичай, використовують наступну символіку: f(x) ®min, XI U, де f(x) - цільова функція, U - множина допустимих значень змінних. Якщо функція f(x) - скалярна, то завдання її мінімізації носить назву задачі математичного програмування. Якщо ж обмежень немає, тобто областю визначення є область існування функції f(x), то така мінімізація називається безумовною.Будемо розглядати функції багатьох змінних f = f(x1, …, xn) як функції, задані в точках х n-вимірного евклідового простору En: f =f(х). Точка х*IEN, називається точкою глобального мінімуму функції f(х), якщо для всіх х*IEN виконується нерівність f(x*) ? f(х).Якщо функція f(x) на множині U має, крім глобального, локальні мінімуми, відмінні від нього, то мінімізація f(x), як правило, сильно ускладнюється. Функція f(x) називається унімодальною на відрізку [а; b], якщо вона неперервна на [а; b] і існують числа a та b, , такі, що: 1) якщо а <a, то на відрізку [a; a] функція f(x) монотонно спадає; 2) якщо b <b, то на відрізку [b; b] функція f(x) монотонно зростає; Множину унімодальних на відрізку [а; b] функцій ми будемо позначати через Q [а; b].Функція f(x), задана на відрізку [a; b], називається опуклою на цьому відрізку, якщо для всіх х", х" [а; b] і для довільного числа [0; 1] виконується нерівність f [ax" (1-a) x"] ? af(x") (1 - a) f(x"). Якщо функція f(x) опукла на [a; b], то на будь-якому відрізку [х"; х"] I [a; b] її графік розташований не вище хорди, проведеної через точки графіка з абсцисами х" і х" (рисунок 2). Легко перевірити, що при будь-якому a I [0; 1] точка xa = ax" (1 - a) x" лежить на відрізку [x"; х"] і при неперервній зміні a від 0 до 1 точка xa пробігає цей відрізок від точки х" (при a = 0) до точки x" (при a = 1). З курсу математичного аналізу відомі наступні умови опуклості функції: а) для того щоб дифференційовна на відрізку [а; b] функція f(x) була опуклою на цьому відрізку, необхідно і достатньо, щоб похідна f "(x) не спадала на [а; b]; Умова опуклості для дифференційовної на відрізку [а; b] функції f(x) означає, що на цьому відрізку будь дотична до графіка f(x) лежить не вище цього графіка (рисунок 3).Методи, які використовують тільки значення функції і не потребують обчислення її похідних, називаються прямими методами мінімізації. Великою перевагою прямих методів є те, що від цільової функції не вимагається дифференційовність і, більше того, вона може бути не заданою в аналітичному вигляді.Порівнявши значення f(x) в точках x1 і х2 (пробних точках), можна скоротити відрізок пошуку точки х*, перейшовши до відрізка [а; х2], якщо або до відрізка [x1; b] якщо (рисунок 5). Описану процедуру можна повторити необхідну кількість разів, послідовно зменшуючи відрізок, що містить точку мінімуму. Коли довжина останнього із знайдених відрізків стане досить малою, слід покласти , де - одна з точок цього відрізка, наприклад, його середина.Потім у кожній з половин відрізка [а; с] і [с; b] вибирають по одній точці x1 і х2, і в них обчислюють значення функції, проводять порівняння отриманих значень, і в результаті порівняння встановлюють відрізок, в якому мінімуму бути не може. Відкинувши його, продовжують ту ж процедуру з отриманим відрізком до тих пір, поки знову отриманий відрізок не стане менше по довжині деякої наперед заданої величини

ЗМІСТ

Вступ

І. Формулювання задачі мінімізації. Основні поняття

1.1 Формулювання задачі мінімізації

1.2 Мінімум функції однієї змінної

1.3 Мінімум функції багатьох змінних

1.4 Унімодальні функції

1.5 Опуклі функції

1.6 Прямі методи безумовної мінімізації

ІІ. Прямі методи одновимірної безумовної оптимізації

2.1 Метод дихотомії

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

ІІІ. Прямі методи безумовної мінімізації функцій багатьох змінних

3.1 Метод покоординатного циклічного спуску

3.2 Алгоритм Хука-Дживса

3.3 Метод правильного симплексу

3.5 Метод деформованого симплексу

Висновки

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