Квазі-ньютонів метод

Квазі-Ньютонівські методи — це методи, що використовуються для пошуку нулів або локальних максимумів та мінімумів функцій, як альтернатива методу Ньютона. Їх можливо використовувати, якщо якобіан або гессіан недоступні або обчислення на кожній ітерації займає забагато ресурсів. «Повний» метод Ньютона вимагає наявності якобіана для пошуку нулів або гессіана для знаходження екстремумів. Деякі ітераційні методи, що зводяться до методу Ньютона, такі як SLSQP, можуть вважатися квазі-Ньютонівськими.

Пошук нулів: знаходження коренів

Метод Ньютона для визначення нулів функції $g$ кількох змінних визначається як $x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})$, де $[J_{g}(x_{n})]^{-1}$ — лівий обернений якобіан матриці $J_{g}(x_{n})$ для $g$ у точці $x_{n}$.

Загалом, будь-який метод, який замість точного якобіану $J_{g}(x_{n})$ використовує наближене значення, є квазі-Ньютонівським методом. Простим прикладом є метод хорд, в якому на всіх ітераціях $J_{g}(x_{n})$ замінюється на $J_{g}(x_{0})$. Наведені нижче методи оптимізації вказують на важливий підклас квазі-Ньютонівських методів, які засновані на методі хорд.

Використання методів, які розроблено для пошуку екстремумів з метою визначення нулів, не завжди є конструктивною стратегією, оскільки більшість таких методів вимагають, щоб матриця була симетричною. У контексті пошуку екстремумів це має місце, проте це малоймовірно у випадку визначення нулів. Методи Бройдена — «добрий» і «поганий» — це два методи, які часто використовуються для пошуку екстремумів і також можуть бути застосовані для визначення нулів. Інші методи, які можуть бути використані, — це метод оновлення стовпця, метод оберненого оновлення стовпця, квазі-Ньютонівський метод найменших квадратів і квазі-Ньютонівський метод обернених найменших квадратів.

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

Пошук екстремуму: оптимізація

Пошук мінімуму або максимуму скалярної функції представляє собою визначення нулів градієнта цієї функції. Таким чином, квазі-Ньютонівські методи можна легко використовувати для пошуку екстремумів функції. Іншими словами, якщо $g$ — це градієнт $f$, то визначення нулів векторної функції $g$ еквівалентне пошуку екстремумів скалярної функції $f$; якобіан $g$ тепер стає гессіаном $f$. Основна відмінність полягає в тому, що матриця Гессе є симетричною, на відміну від якобіана при визначенні нулів. Більшість використовуваних в оптимізації квазі-Ньютонівських методів користуються цією властивістю.

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

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

Перший квазі-Ньютонівський алгоритм був запропонований Вільямом К. Давідоном, фізиком, який працював в Аргоннській національній лабораторії. Він розробив перший квазі-Ньютонівський алгоритм у 1959 році: формулу оновлення DFP, яка пізніше стала популярною завдяки Флетчеру і Пауеллу в 1963 році, але сьогодні рідко використовується. Серед найпоширеніших квазі-Ньютонівських алгоритмів в наш час варто відзначити формулу SR1 («симетричний ранг-один»), метод BHHH, широко поширений метод BFGS (запропонований незалежно Бройденом, Флетчером, Голдфарбом і Шанно в 1970 році) та його розширення з обмеженим використанням пам'яті L-BFGS. Клас Бройдена представляє собою лінійною комбінацією методів DFP і BFGS.

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

Однією з головних переваг квазі-Ньютонівські методів над методом Ньютона є те, що немає необхідності знаходити обернену матрицю Гессе (або, у випадку квазі-Ньютонівських методів, її наближення) $B$ . Метод Ньютона та його похідні, такі як методи внутрішньої точки, вимагають оберненої матриці Гессе, що, зазвичай реалізується шляхом розв'язання системи лінійних рівнянь, і є витратним процесом. На відміну від цього, квазі-Ньютонівські методи зазвичай генерують безпосередню оцінку матриці $B^{-1}$.

Як і в методі Ньютона, використовується апроксимація другого порядку для пошуку мінімуму функції $f(x)$. Ряд Тейлора $f(x)$ в околі ітеративної точки виглядає наступним чином:

$f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{\mathrm {T} }\,\Delta x+{\frac {1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,$

де ($\nabla f$) — градієнт, а $B$ наближення матриці Гессе. Градієнт цієї апроксимації (відносно $\Delta x$) виглядає наступним чином:

$\nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\,\Delta x,$

і встановлення цього градієнту рівним нулю (що є метою оптимізації) дає крок Ньютона:

$\Delta x=-B^{-1}\nabla f(x_{k}).$

Наближення матриці Гессе $B$ обирається так, щоб задовольнити умовний вираз:

$\nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,$

який називається рівнянням хорд (ряд Тейлора градієнта). У багатовимірному випадку матриця $B$ недостатньо визначена. В одновимірному випадку розв'язання для $B$ та застосування кроку Ньютона з оновленою величиною еквівалентне методу хорд. Квазі-Ньютонові методи відрізняються своїм вибором розв'язку рівняння хорди (у одновимірному випадку всі варіанти еквівалентні). Більшість методів (але є винятки, такі як метод Бройдена) шукають симетричний розв'язок ($B^{T}=B$); крім того, варіанти, що перелічено нижче, можуть бути обгрунтовані пошуком оновлення $B_{k+1}$ яке якомога ближче до $B_{k}$ за якоюсь нормою; тобто, $B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}$, де $V$ — це деяка додатньо-визначена матриця, яка визначає норму. Приблизне початкове значення $B_{0}=\beta I$ часто є достатнім для швидкої збіжності, хоча немає загальної стратегії вибору $\beta$. Зверніть увагу, що $B_{0}$ повинна бути додатньо-визначеною. Невідомий $x_{k}$ оновлюється застосуванням кроку Ньютона, розрахованого за допомогою поточної приблизної матриці Гессе $B_{k}$:

• $\Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})$, де $\alpha$, обрано так, щоб задовольняти умовам Вольфе;
• $x_{k+1}=x_{k}+\Delta x_{k}$;
• Градієнт, обчислений у новій точці $\nabla f(x_{k+1})$, та

$y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$

використовується для оновлення наближення матриці Гессе $B_{k+1}$, або безпосередньо її оберненої матриці $H_{k+1}=B_{k+1}^{-1}$ за допомогою формули Шермана-Морісона.

• Ключовою властивістю оновлень BFGS і DFP є те, що якщо $B_{k}$ є додатньо-визначеною, і $\alpha _{k}$ обрано так, щоб задовольняти умовам Вольфе $B_{k+1}$ також є додатньо-визначеною.

Найпопулярніші формули оновлення:

Метод	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
BFGS	$B_{k}+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }B_{k}\,\Delta x_{k}}}$	$\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}$
Бройден	$B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{\mathrm {T} }\,\Delta x_{k}}}\,\Delta x_{k}^{\mathrm {T} }$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{\mathrm {T} }H_{k}}{\Delta x_{k}^{\mathrm {T} }H_{k}\,y_{k}}}$
Сімейство Бройдена	$(1-\varphi _{k})B_{k+1}^{\text{BFGS}}+\varphi _{k}B_{k+1}^{\text{DFP}},\quad \varphi \in [0,1]$
DFP	$\left(I-{\frac {y_{k}\,\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}$	$H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }\,y_{k}}}-{\frac {H_{k}y_{k}y_{k}^{\mathrm {T} }H_{k}}{y_{k}^{\mathrm {T} }H_{k}y_{k}}}$
SR1	$B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }}{(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }\,\Delta x_{k}}}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}$

Інші методи включають метод Пірсона, метод Маккорміка, симетричний метод Бройдена Пауелла (PSB) та метод Грінштадта.

Зв'язок з оберненою матрицею

Коли функція $f$ є опуклою квадратичною функцією з додатно-визначеною матрицею Гессе $B$, можна очікувати, що матриці $H_{k}$ створені квазі-Ньютоновським методом, будуть збігатися до оберненої матриці Гессе $H=B^{-1}$. Це дійсно так для класу квазі-Ньютоновських методів, які ґрунтуються на оновленнях з мінімальними змінами.

Відомі реалізації

Реалізації квазі-Ньютоновських методів доступні в багатьох мовах програмування.

Серед реалізації з відкритим кодом найбільше відомі такі:

• GNU Octave використовую модифікацію BFGS у своїй функції fsolve з додаванням областей довіри.
• GNU Scientific Library реалізує алгоритм Бройдена-Флетчера-Голдфарба-Шанно (BFGS).
• ALGLIB реалізує (L)BFGS мовами програмування C++ та C#
• у R загальнозначущий оптимізатор, реалізований в функції optim, використовує метод BFGS з параметром method="BFGS".
• Scipy.optimize містить функцію fmin_bfgs. У бібліотеці SciPy для мови програмування Python, функція scipy.optimize.minimize включає, серед інших методів, реалізацію BFGS.

Серед реалізацій з власницьким кодом найбільш відомі такі:

• Mathematica включає рішення з використанням квазі-Ньютонівських методів.
• Бібліотека NAG містить кілька процедур для мінімізації або максимізації функції, які використовують квазі-Ньютонівські алгоритми.
• У MATLAB Optimization Toolbox, функція fminunc використовує (поміж інших методів) квазі-Ньютонівський метод BFGS. Багато з обмежених методів також використовують BFGS та його варіант L-BFGS.

Див. також

• Методи BFGS
  • L-BFGS
  • OWL-QN
• Метод Бройдена
• Формула оновлення DFP
• Метод Ньютона
• Метод Ньютона в оптимізації
• SR1 формула

Додаткові матеріали

• Bonnans, J. F.; Gilbert, J. Ch.; Lemaréchal, C.; Sagastizábal, C. A. (2006). Numerical Optimization : Theoretical and Numerical Aspects (вид. Second). Springer. ISBN 3-540-35445-X.
• Fletcher, Roger (1987), Practical methods of optimization (вид. 2nd), New York: John Wiley & Sons, ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999). Quasi-Newton Methods. Numerical Optimization. New York: Springer. с. 192—221. ISBN 0-387-98793-2.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). Section 10.9. Quasi-Newton or Variable Metric Methods in Multidimensions. Numerical Recipes: The Art of Scientific Computing (вид. 3rd). Cambridge University Press. ISBN 978-0-521-88068-8.
• Scales, L. E. (1985). Introduction to Non-Linear Optimization. New York: MacMillan. с. 84—106. ISBN 0-333-32552-4.