Загальний підхід до методу спуску

МІНІСТЕРСТВО ОСВІТИ І  НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

 

Черкаський національний університет імені Богдана Хмельницького

ННІ фізики математики та КІС

 

Кафедра прикладної математики

 

 

 

Реферат на тему

Загальний підхід до методу спуску

 

 

Виконала студентка спец. 6.040301–«Прикладна математика»:

 

Івкова Руслана Олегівна

___________________________

«____»________________2012р.

 

Науковий керівник

д.т.н., професор

Головня Борис Петрович

___________________________

«____»________________2012р.

 

Завідувач кафедри

прикладної математики

д.т.н., професор

Головня Борис Петрович

___________________________

«____»________________2012р.

 

 

 

 

 

Черкаси 2012

Метод оптимізації як розділ математики є досить давно. Оптимізація - такий вибір, тобто. те що постійно доводиться проводити дозвілля у  повсякденні. Тоді терміном "оптимізація" у літературі позначають процес чи послідовність операцій, дозволяють отримати уточнену рішення. Хоча кінцевою метою оптимізації є пошук  найкращого чи "оптимального" рішення, звичайно припадає задовольнятися поліпшенням  відомих рішень, а чи не доведенням їх до досконалості. Тому під оптимізацією розуміють скоріш прагнення до досконалості, яке, можливо, не залишиться досягнуто.

Потреба вжити найкращих  рішень як і стара, як саме людство.Испокон віці люди, розпочинаючи здійсненню своїх заходів, роздумували за їхньою можливими випливають, та приймали рішення, обираючи що тим чи в інший спосіб залежать від них параметри - способи організації заходів. Але тимчасово, до часу рішення могли прийматися без спеціального математичного аналізу, просто з урахуванням досвіду і здоровим глуздом.

Візьмемо приклад: людина вийшла уранці з дому, щоб їхати  працювати. У процесі мусить прийняти низку рішень: чи приймати з собою  парасольку? У якій місці перейти  вулицю? Яким виглядом транспорту скористатися? І далі. Зрозуміло, всі ці рішення  людина приймає без спеціальних  розрахунків, просто спираючись на наявний  в нього досвід минулого і на здоровий глузд. Для обґрунтування таких рішень ніяка наука абсолютно не потрібна, так навряд чи знадобиться й надалі.

Метод градієнтного спуску.

Градієнтний спуск - метод знаходження локального мінімуму ( максимуму) функції за допомогою руху уздовж градієнта. Для мінімізації функції в напрямку градієнта використовуються методи одновимірної оптимізації, наприклад, метод золотого перерізу. Також можна шукати не найкращу точку в напрямку градієнта, а яку-небудь краще поточної.

Збіжність методу градієнтного спуску залежить від ставлення максимального і мінімального власних чисел матриці Гессе в околиці мінімуму (максимуму). Чим більше це відношення, тим гірше збіжність методу.

1. Опис

2.                                           

Ілюстрація послідовних наближень до точки екстремуму в напрямі найшвидшого спуску (червоне) в разі дробового кроку. Синім позначені лінії рівня. Нехай цільова функція має вигляд:

.

І завдання оптимізації задана наступним чином:

Основна ідея методу полягає в тому, щоб йти в напрямку найшвидшого спуску, а цей напрямок задається анти градієнтом :

де  λ ^[j] вибирається

• постійною, в цьому випадку метод може розходитися;
• дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
• порад задля спуском:

1.1. Алгоритм 

1. Задають початкове наближення і точність розрахунку
2. Розраховують , Де
3. Перевіряють умова зупинки:
• Якщо або (Вибирають одну з умов), то j = j + 1 і перехід до кроку 2.
• Інакше і зупинка.

1.2. Приклад 

Застосуємо градієнтний метод до функції . Тоді послідовні наближення будуть виглядати так:

 

1.3. Удосконалення

Метод градієнтного спуску виявляється дуже повільним при русі вздовж яру (див. яружний функції). Прикладом такої функції є функції Розенброка. Більш ефективним вважається метод спряжених градієнтів.

Метод покоординатного спуску.

Однією з найпростіших способів визначення напрями спуску є вибір якSk однієї з координатних векторів ±e1, ±e2, …, ± en, унаслідок чого уxk з кожної ітерації змінюється один із компонент.

Існують численні варіантипокоординатного спуску. Але за будь-якого з цих методів вибирають як ->Sk те з двох напрямів, +>ej, ->ej, якому відповідав би нерівність

[j ’(>xk),Sk] > 0.

Що стосується, якщо =0, вважаютьxk+1=xk і переходять до наступній ітерації.

Наведемо перший цикл методу, що з n ітерацій. У довільній точціx0 вибираютьS0=± e, яких і визначає величину b 0 способом подвоєння те щоб було j (>x1)=j (>x0-b0S0)<j (>x0). Потім вибираютьS1=±e2 і, вважаючи b =b 0, подвоєнням обчислюють b 1 тощо. У цьому з кожної ітерації прагнуть визначення величини кроку методом подвоєння здійснювати з найменшою числом обчислень значень функції j (x). Цикл закінчується приk=n-1, після чого починають наступний цикл, вважаючиSn=±e1 тощо.

Укладання

Практика породжує дедалі нові завдання оптимізації, причому  їх складність зростає. Потрібні нові математичні моделі та художні засоби, які враховують наявність багатьох критеріїв, проводять глобальний пошук  оптимуму. Інакше кажучи, життя змушує розвивати математичний апарат оптимізації.

Реальні прикладні завдання дискретної оптимізації дуже складні. Сучасні методи оптимізації які  завжди виходить із рішенням реальних завдань без допомоги людини. Ні, такої теорії, яка врахувала б  будь-які особливості функцій, що описують постановку завдання. Варто  віддати перевагу таких методів, якими простіше управляти у процесі  виконання завдання.