Метод Ньютона в оптимізації

В диференціальному численні метод Ньютона — це ітераційний метод пошуку коренів диференційовної функції , які є розв'язками рівняння . В оптимізації метод Ньютона застосовується до похідної подвійно диференційовної функції для пошуку коренів похідної (розв'язки ), також відомих як стаціонарні точки Ці розв'язки можуть бути мінімумами, максимумами або сідловими точками.[1]

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

Метод Ньютона

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

Маючи двічі диференційовну функцію , ми прагнемо вирішити оптимізаційну задачу

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

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

мінімум досягається для

Збираючи все разом, метод Ньютона виконує ітерацію

Геометрична інтерпретація

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

Вищі виміри

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

Часто метод Ньютона змінюють, щоб включити маленький розмір кроку замість :

Це часто роблять, щоб гарантувати, що умови Вольфе задовольняються на кожному кроці методу.

Збіжність

Припустімо, що двічі неперервно диференційовна на відкритому проміжку і існує таке, що За умови, що метод Ньютона визначено як

і припущення, що коли Можна стверджувати, що при достатньо великому

при

Тобто, збігається до квадратично.

Доведення

Нехай тобто Згідно з теоремою Тейлора, поклавши і для певного у проміжку від до маємо

Завдяки тому, що і маємо

Через те, що похідна неперервна з можна сказати, що якщо достатньо близько до Отже ми можемо поділити на

скориставшись означенням методу Ньютона маємо

Отже,

Завдяки неперервності, збігається до і, з того, що гніздиться між і випливає, що збігається до і тому збігається до отже, для достатньо великих

якщо

Примітки

  1. Relative Extrema. Lamar University. Процитовано 28 серпня 2019.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.