Міністерству освіти і науки Російської Федерації
Федеральне державне автономне освітня установа
вищої професійної освіти
«Волгоградський державний університет»
(ВолДУ)
Інститут математики та інформаційних технологій
Лабораторна робота №3
по курсу «Чисельні методи оптимізації»
Методи багатовимірної безумовної мінімізації. Порівняння правої РП та центральної РП на прикладі мінімізації функції декількох аргументів методом сполучених градієнтів
Виконали:
Студенти 3-го курсу
групи ПМ - 101
Самородов Е. А.
Гусинін О. С.
Болотін А. В.
Прийняв:
Яновський Т.А.
Волгоград 2013
Завдання:
Порівняти праву і центральну разностную похідну на прикладі мінімізації функції декількох аргументів методом сполучених градієнтів. Як функції взята функція Пауелла.
Метод:
Метод сполучених градієнтів (метод Флетчера-Ривса)
В основі методу лежить побудова напрямків пошуку мінімуму, є лінійними комбінаціями градієнта попередніх напрямків пошуку. При цьому вагові коефіцієнти вибираються так, щоб зробити напрямки сполученими щодо матриці Гессе. Для підвищення швидкості збіжності методу, в разі не квадратичної використовується рестарт: через кожні n циклів напрямок пошуку замінюється на Поряд з початковою точкою і вектором позитивних збільшень координат, алгоритм методу вимагає апріорного завдання параметра точності пошуку? gt; 0.
Алгоритм:
Функція:
Результати роботи програми:
Був проведений ряд розрахунків з метою визначення відмінностей центральної РП і правої РП. Для цієї мети в якості змінних параметрів були взяті eps1 і h. Де eps1 - максимальна величина норми градієнта при якій триває розрахунок, h - крок який використовується в РП для знаходження похідної функції.
В якості методу одновимірної мінімізації узятий метод золотого перетину.
При мінімізації відрізка використаний постійний крок 0.01. Для мети роботи він не важливий, як і точність з якою буде знайдений alfa методом золотого перетину.
Приклад роботи програми:
Використовуємо для розрахунку Центральну РП.
Тут під МСГ розуміється кількість ітерацій пройдених методом сполучених градієнтів, під ОМ - кількість ітерацій при знаходженні відрізка мінімізації, під ЗС - кількість ітерації в методі золотого перетину.
Тепер використовуємо Праву РП.
На перший погляд видно, що різниця між ЦРП і ПРП тільки в кількості ітерацій. За допомогою ЦРП необхідний результат знайдений трохи швидше. Тепер змінимо eps1 і h. Візьмемо eps1=0.1, h=0.001. З центральної РП:
З правого РП:
Очевидно, що використання ЦРП, при більш грубому кроці h і низької точності eps1, сприяє якнайшвидшому і більше найточнішому знаходженню мінімуму функції на відміну від ПРП.
Висновки
Експериментально для даної задачі вдалося встановити найбільш ефективна кількість ітерацій n, після яких потрібно виробляти рестарт. При використанні n=6 досягається необхідна точність знаходження мінімуму при найменшій кількості ітерацій.
Нижче наведена таблиця кількостей ітерації при різних n і h, і однаковою точністю (,), при центральній РП і правої РП (ЦРП/ПРП).
багатовимірний мінімізація похідна функція
nh 449/49 * 48/55 * 48/17248/51531/71 * 31/49 * 31/3431/26624/37 * 24/31 * 24/2824/26737/71 * 35/42 * 35/4035/49840/49 * 43/64 * 43/5943/55930/46 * 30/36 * 30/4830/371042/31 * 42/50 * 42/4542/421136/34 * 36/34 * 36/3736/411238/49 * 39/48 * 39/3939/371337/53 * 38/52 * 38/4338/401437/43 * 37/57 * 37/4337/511541/46 * 42/75 * 42/4842/431635/49 * 35/66 * 35/3735/351741/52 * 40/51 * 40/5540/411841/37 * 44/90 * 42/4543/44
Як видно з таблиці правая РП більш чутлива до зміни кроку h ніж центральна. З цього випливає, що ЦРП має меньшею похибка знаходження похідної, ніж ПРЦ.
До того ж, при великих значення h застосування ПРП, в даному прикладі, прищепило до дуже малій зміні аргументів, тобто до зациклення.
У таблиці (*) позначено то кількість ітерацій, де застосування ПРП призвело до зациклення, що не д...
