Воронезький інститут високих технологій
Факультет заочного та післявузівської навчання
Кафедра математики та інформатики
Курсова робота
З дисципліни: Методи оптимізації
На тему: Мінімізація функцій кількох змінних. Метод спуску
Воронеж 2010
Введення
Метод оптимізації як розділ математики існує досить давно. Оптимізація - це вибір, тобто те, чим постійно доводиться займатися в повсякденному житті. Терміном "оптимізація" в літературі позначають процес або послідовність операцій, що дозволяють отримати уточнене рішення. Хоча кінцевою метою оптимізації є відшукання найкращого або "Оптимального" рішення, зазвичай доводиться задовольнятися поліпшенням відомих рішень, а не доведенням їх до досконалості. Тому під оптимізацією розуміють скоріше прагнення до досконалості, яке, можливо, і не буде досягнуто.
Необхідність прийняття найкращих рішень так само стара, як саме людство. Споконвіку люди, приступаючи до здійснення своїх заходів, роздумували над їх можливими наслідками і приймали рішення, вибираючи тим чи іншим чином залежні від них параметри - способи організації заходів. Але до пори, до часу рішення могли прийматися без спеціального математичного аналізу, просто на основі досвіду і здорового глузду.
Візьмемо приклад: людина вийшла вранці з дому, щоб їхати на роботу. По ходу справи йому доводиться прийняти цілу низку рішень: чи брати з собою парасольку? В якому місці перейти вулицю? Яким видом транспорту скористатися? І так далі. Зрозуміло, всі ці рішення людина приймає без спеціальних розрахунків, просто опираючись на наявний у нього досвід і на здоровий глузд. Для обгрунтування таких рішень ніяка наука не потрібна, та навряд чи знадобиться й надалі.
Однак візьмемо інший приклад. Допусти, організовується робота міського транспорту. В нашому розпорядженні є якась кількість транспортних засобів.
Необхідно прийняти ряд рішень, наприклад: яка кількість і яких транспортних засобів направити по тому чи іншому маршруті? Як змінювати частоту проходження машин в залежно від часу доби? Де помістити зупинки? І так далі.
Ці рішення є набагато більш відповідальними, ніж рішення попереднього прикладу. В силу складності явища наслідки кожного з них не такі зрозумілі; для того, щоб уявити собі ці наслідки, потрібно провести розрахунки. А головне, від цих рішень значно більше залежить. У першому прикладі неправильний вибір рішення зачепить інтереси однієї людини, у другому - може відбитися на діловій життя цілого міста.
Найбільш складно йде справа з прийняттям рішень, коли мова йде про заходи, досвіду, у проведенні яких ще не існує і, отже, здоровому глузду не на що спертися, а інтуїція може обдурити. Нехай, наприклад, складається перспективний план розвитку озброєння на кілька років вперед. Зразки озброєння, про які може йти мова, ще не існують, ніякого досвіду їх застосування немає. При плануванні доводиться спиратися на велику кількість даних, що відносяться не стільки до минулого досвіду, скільки до предвидимом майбутньому. Вибране рішення повинно по можливості гарантувати нас від помилок, пов'язаних з неточним прогнозуванням, і бути достатньо ефективним для широкого кола умов. Для обгрунтування такого рішення приводиться в дію складна система математичних розрахунків.
Взагалі, чим складніше організовуване захід, чим більше вкладається в нього матеріальних засобів, чим ширше спектр його можливих наслідків, тим менше допустимі так звані "вольові" рішення, не спираються на науковий розрахунок, і тим більше значення отримує сукупність наукових методів, дозволяють заздалегідь оцінити наслідки кожного рішення, заздалегідь відкинути неприпустимі варіанти і рекомендувати ті, які представляються найбільш вдалими.
Методи спуску
Загальна схема
Всі методи спуску рішення задачі безумовної мінімізації розрізняються або вибором напрямку спуску, або способом руху вздовж напрямку спуску. Це дозволяє написати загальну схему методів спуска.
Вирішується завдання мінімізації функції j (x) на всьому просторі En. Методи спуску складаються в наступній процедурі побудови послідовності {xk}. В якості початкового наближення вибирається будь-яка точка x0ГЋEn. Послідовні наближення x1, x2, ... будуються за наступною схемою:
1) в точці xk вибирають напрям спуску - Sk;
2) знаходять (k +1)-е наближення за формулою xk +1 = xk-hkSk.
Напрям Sk вибирають таким чином, щоб забезпечити нерівність f (xk +1)
Число hk визначає відстань від точки xk до точки хk +1. Це число називається довжиною кроку або просто кроком. Основне завдання при виборі величини hk - це забезпечити виконання нерівності j (xk +1)
Величина кроку сильно впливає на ефективність методу. Більшою ефективністю володіє варіант методу, коли крок по кожній змінної визначається направляючими косинусами градієнта (в градієнтних методах).
xk +1 = xk-hk cos
де - cos =
У цьому випадки величина робочого кроку не залежить від величини модуля градієнта, і нею легше керувати зміною h. В районі оптимуму може виникати значне В«рисканняВ», тому використовують різні алгоритми корекції h.
Найбільше поширення одержали наступні алгоритми:
1. (Без корекції);
2. якщо; якщо
3. , Якщо;, якщо;, якщо,
де-кут між градієнтами на попередньому і поточному кроці;
і - задані порогові значення вибираються суб'єктивно
(наприклад,).
Далеко від оптимуму напрямок градієнта змінюється мало, тому крок можна збільшити (друге вираз), поблизу від оптимуму напрямок різко змінюється (кут між градієнтами R (x) великий), тому h скорочується (третє вираз).
Метод покоординатного спуску
Нехай потрібно знайти найменше значення цільової функції u = f (M) = f (x пЂ±, x пЂІ, . . . , Xn). Тут через М позначена точка n-мірного простору з координатами x пЂ±, x пЂІ, . . . , Xn: M = (x пЂ±, x пЂІ, . . . , Xn). Виберемо яку-небудь початкову точку М пЂ° = (x пЂ± пЂ°, x пЂІ пЂ°, . . . , Xn0) і розглянемо функцію f при фіксованих значеннях всіх змінних, крім першій: f (x пЂ±, x пЂІ пЂ°, x пЂі пЂ°, . . . , Xn0 ). Тоді вона перетвориться на функцію однієї змінної x пЂ± . Змінюючи цю змінну, будемо рухатися від початкової точки x пЂ± = x пЂ± пЂ° п‚ в бік зменшення функції, поки не дійдемо до її мінімуму при x пЂ± = x пЂ± пЂ±, після якого вона починає зростати. Точку з координатами (x пЂ± пЂ±, x пЂІ пЂ°, x пЂі пЂ°, . . . , Xn0) позначимо через М пЂ±, при цьому f (M0) пЂѕ пЂЅ f (M пЂ±).
Фіксуємо тепер змінні: x пЂ± = x пЂ± пЂ±, x пЂі = x пЂі пЂ°, . . . , Xn = xn0 і розглянемо функцію f як функцію однієї змінної x пЂІ: f (x пЂ± пЂ±, x пЂІ пЂІ, x пЂі пЂ° . . . , Xn0). Змінюючи x пЂІ, будемо знову рухатися від початкового значення x2 = x20 в бік зменшення функції, поки не дійдемо до мінімуму при x2 = x21 . Крапку з координатами {x пЂ± пЂ±, x пЂІ пЂ±, x пЂі пЂ° . . . xn0} позначимо через М пЂІ, при цьому f (M1) пЂѕ пЂЅ f (M пЂІ).
Проведемо таку ж мінімізацію цільової функції по змінним x пЂі, x пЂґ, . . . , Xn. Дійшовши до змінної xn, знову повернемося до x пЂ± і продовжимо процес. Ця процедура цілком виправдовує назву методу. З її допомогою ми побудуємо послідовність точок М пЂ° пЂ¬ М пЂ± пЂ¬ М пЂІ пЂ¬ пЂ . . . , Якій відповідає монотонна послідовність значень функції f (M0) пЂѕ пЂЅ пЂ f (M пЂ±) пЂѕ пЂЅ пЂ f (M пЂІ) пЂ пЂѕ пЂЅ пЂ пЂ Обриваючи її на деякому кроці k можна наближено прийняти значення функції f (Mk) за її найменше значення в розглянутій області.
Проведемо таку ж мініміза...
