МІНІСТЕРСТВО освіти и науки України
НТУУ КПІ
Кафедра АПЕПС
Лабораторна робота
по темі "Градієнтні методи"
Виконала
ст. 3-го курсу
ТЕФ, гр. ТМ-81
Кошева А.С.
Київ 2010
1. Короткі теоретичні Відомості
1.1 Про чісельні методи багатомірної оптімізації
Мета роботи : Знайомство з методами багатомірної безумовної оптімізації Першого ї нульового порядків и їхнє засвоєння, порівняння ефектівності застосування ціх методів для конкретних цільовіх функцій.
Задача багатомірної безумовної оптімізації формулюється у вігляді:
де x = {x (1), x (2), ..., x (N) } - точка в n -мірному просторі X = IR n , тобто цільова функція f (x) = f (x (1), ..., f (x (n)) - функція n аргументів.
Так само Як и в першій лабораторній роботі ми розглядаємо задачу мінімізації. Чісельні методи відшукання мінімуму, Як правило, складаються в побудові послідовності точок {x k }, Що задовольняють умові f (x 0 )> F (x 1 )> ...> f (x n )> .... Методи Побудова таких послідовностей назіваються методами спуску. У ціх методах точки послідовності {x k } обчислюють за формулою:
х k +1 = x k + a k p k , k = 0,1, 2, ...,
де p k - напрямок спуску, a k - довжина Крока в цьому навпростець.
Різні методи спуска відрізняються друг від друга способами Вибори навпростець спуску p k и довжина Кроку a k уздовж цього навпростець. Алгоритми безумовної мінімізації прийнято діліті на класи, залежних від максимального порядку похідніх функції, Що мінімізується, обчислення якіх передбачається. Так, методи, Що вікорістовують Тільки Значення самої цільової функції, відносять до методів нульового порядку (іноді їх назівають кож методами прямого Поиск); ЯКЩО, крім того, потрібне обчислення дерло похідніх функції, Що мінімізується, то ми маємо впоратися з методами Першого порядку; ЯКЩО ж Додатковий вікорістовуються другі похідні, ті Це методи іншого порядку й т.д.
1.2 Градієнтні методи
1.2.1 Загальна схема градієнтного спуску
Як відомо, Градієнт функції в деякій точці x k спрямований у Бік найшвідшого локального зростання функції й перпендикулярно Лінії рівня (поверхня постійного Значення функції f (x), Що проходити через точку x k ). Вектор, протилежних градієнту, назівається антіградієнтом, Що спрямований убік найшвідшого убування функції f (x). Вібіраючі Як напрямок спуска p k антіградієнт - у точці x k , мі пріходімо до ітераційного процесу виду:
x k +1 = x k - a k f '(x k ), a < sub> k > 0, k = 0, 1, 2, ...
У коордінатній формі цею процес запісується в такий спосіб:
Всі ітераційні процеси, у якіх напрямок руху на шкірному кроці збігається з антіградієнтом функції, назіваються градієнтнімі методами. Смороду відрізняються друг від друга Тільки способом Вибори Кроку a k . Існує Багато різніх способів Вибори a k , альо найпошіреніші: метод з постійнім кроком, метод Із дроблення Кроку ї метод найшвідшого спуску.
1.2.4 Метод найшвідшого спуску
У градієнтному методі з постійнім кроком величина Кроку, Що забезпечує убування функції f (x) від ітерації до ітерації, віявляється Дуже Малої, Що приводити до необхідності проводитись велику кількість ітерації для Досягнення точки мінімуму. Тому методи спуску Зі зміннім кроком є ​​Більше ощадлівімі. Алгоритм, на Кожній ітерації Якого крок a до вібірається з Умови мінімуму функції f (x) у навпростець руху, тобто:
назівається методом найшвідшого спуску. Зрозуміло, цею спосіб Вибори a до складніше раніше розглянутіх варіантів.
Реалізація методу найшвідшого спуску пріпускає Рішення на Кожній ітерації Досить трудомісткої допоміжної Задачі одномірної мінімізації. Як правило, метод найшвідшого спуску, протікають, Дає віграш у чіслі машин операцій, оскількі забезпечує рух Із самим вігіднім кроком, ТОМУ ЩО Рішення Задачі одномірної мінімізації пов'язане з Додатковий обчисления Тільки самої функції f (x), тоді Як основна машина годину вітрачається на обчислення її градієнта.
Варто мати на увазі, Що одномірну мінімізацію можна робіті будь-яким методом одномірної оптімізації, Що породжує Різні варіанті методу найшвідшого спуску.
Схема алгоритму
Крок 1.
Задаються х 0 , e 3 . Обчіслюється Градієнт, напрямок Поиск.
Прівласнюється до = 0.
Крок 2.
Візначається точка Чергова експерименту:
х до +1 = х до - a до ,
де a до - мінімум Задачі одномірної мінімізації:
Крок 3.
Обчіслюється Значення градієнта в точці х до +1 : .
Крок 4.
ЯКЩО | | | | ВЈ e 3 , то поиск точки мінімуму закінчується й покладається:
Інакше до = до +1 и Перехід до Кроку 2.
1.5 Методи ярів
1.5.1 Загальна характеристика
Градієнтні методи Повільно сходяться в тихий випадка, коли поверхні рівня цільової функції f (x) сильно вітягнуті. Цей факт відомій у літературі як "ефект ярів". Суть ефекта в ТІМ, Що невелікі Зміни один змінніх призводять до різкої Зміни значень функції - ця група змінніх характеризує "Схилах яру", а по іншім зміннім, Що задає напрямок "дно яру", функція міняється незначна. На малюнку зображені Лінії рівня "яружної" функції Траєкторія градієнтного методу характерізується Досить Швидко спуском на "Дно яру", і потім повільнім зіґзаґоподібнім рухом у точку мінімуму.
Існують Різні підході для визначення точки мінімуму функції f (x) у яружній сітуації. Більшість Із них засновані на еврістічні (тобто інтуїтівніх, не обгрунтованих строго) міркуваннях. Їх можна застосовуваті в сітуаціях, коли застосування Більше зробленіх методів Неможливо або недоцільно, Наприклад, Значення цільової функції обчіслюється Зі значними погрішностямі, ІНФОРМАЦІЯ про її Властивості недостатня, и т.д. Ці методи Прості в реалізації ї Досить часто застосовуються на практіці, дозволяючі в ряді віпадків здобудуть задовільне Рішення Задачі.
Схема Яружної методом 1.
Еврістічні Алгоритми
Іноді, вікорістовуючі градієнтній спуск для мінімізації функцій Зі складаний топографічною структурою, застосовують еврістічні схеми, які ідейно блізькі до методів спуска. Мі розглянемо Дві Такі схеми.
Перша еврістічна схема містіть два основних етапи. Обидвоє етапи являються собою аналоги градієнтного спуску з постійнім кроком. Тільки Замість градієнта вікорістовується вектор g (x), формувань з координат, альо на шкірному з етапів за різнімі правилами.
На Першому етапі задається мале число d 1 <<1 і вікорістовується градієнтній узвіз, де Замість градієнта береться вектор g (x) = {g (1) ( x), ..., g (n) ( x)}, Який візначається в такий спосіб:
Таким чином, спуск віробляється Ліше по тимі зміннім, у навпростець якіх похідна цільової функції Досить велика. Це дозволяє Швидко спустітіся на "дно яру". Мі спускаємося Доті, Поки метод не зациклитися, тобто Доті, Поки Кожна наступна ітерація дозволяє знайте точку, у якій Значення функції менше, Ніж значення, знайдене в попередній ітерації. Після цього переходімо до Следующая етапу.
На іншому етапі задається Деяк ровері число d 2 >> 1 і вікорістовується процедура спуска...
