Перегляд вихідного коду сторінки Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно

'''Алгоритм Бройдена - Флетчера - Гольдфарба - Шанно''' ({{lang-en|Broyden–Fletcher–Goldfarb–Shanno (BFGS)}}) - [[Метод ітерації|ітеративний метод]] числової оптимізації, призначений для знаходження локального максимуму / мінімуму [[Лінійна функція|нелінійної функції]] без обмежень (є спірними слова "без обмежень", див. '''примітка''').

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

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

== Детальна інформація ==
Матриця Гессіана (або Зворотній гессіан) - <math>V \approx H^{-1}</math> - це матриця розміру n × n (де n - довжина вектора градієнта '''g''').

Значення <math>V</math> обчислюються на кожному кроці алгоритму наступним чином.

<math>V_0 = 1</math>

<math>V_{k+1} = V_k - \frac{V_k \centerdot s \centerdot s^T \centerdot V_k}{s^T \centerdot V_k \centerdot s} + \frac{r \centerdot r^T}{s^T \centerdot s}</math>       ('''1''')

де 

<math>r = \vartriangle g_k = g_k - g_{k-1}</math> - це зміна градієнту,

<math>s = \vartriangle W_k = W_k - W_{k-1}</math> - зміна ваг

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

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

== Алгоритм методу ==
Алгоритм складається з наступної послідовності кроків :
# Ініціалізуємо вагові коефіцієнти (випадковими малими значеннями) і встановимо початкове значення наближення зворотнього гессіана. 
# Обчислимо значення градієнту g. 
# Виконаємо корекцію значень вагових коефіцієнтів (<math>\vartriangle W = g \centerdot\tau</math>; <math>W_{k+1} = W_k - \vartriangle W</math>;  де - <math>\tau</math> параметр швидкості навчання)
# Зберігаємо старе значення градієнту (<math>g_{old} = g </math>) та обчислюємо нове значення (<math>g = g(W)</math>) і зміну градієнту (<math>\vartriangle g = g - g_{old}</math>).
# Обчислимо значення зворотнього гессіана <math>V(\vartriangle g, \vartriangle W)</math> за '''формулою 1'''.
# Обчислимо зміну вагових коефіцієнтів (<math>\vartriangle W = V \centerdot g</math>) і виконаємо корекцію параметрів (<math>W = W - \vartriangle W</math>)
# Обчислимо похибку (<math>E(W)</math>)
# Якщо отримане значення похибки менше, ніж задана точність (<math>E(W) < \varepsilon</math>), то алгоритм зупиняється.
# Якщо точність не досягнута, то повторюємо алгоритм з 4 кроку.

== Програмна реалізація ==
Реалізація мовою '''С''' у рамках проекту GNU Scientific Library ([https://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms-with-Derivatives.html детальніше] {{Webarchive|url=https://web.archive.org/web/20171208072544/http://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms-with-Derivatives.html |date=8 грудня 2017 }}).

Високоточна версія алгоритму мовою '''С++'''  - [http://www.loshchilov.com/pbfgs.html посилання] {{Webarchive|url=https://web.archive.org/web/20170823031924/http://loshchilov.com/pbfgs.html |date=23 серпня 2017 }}. 

Реалізація алгоритму BFGS та схожих алгоритмів (L-BFGS, L-BFGS-B, CG, метод Ньютона) мовою '''С++''' - [https://github.com/PatWie/CppNumericalSolvers посилання] {{Webarchive|url=https://web.archive.org/web/20170711112241/https://github.com/PatWie/CppNumericalSolvers |date=11 липня 2017 }}.

Алгоритм реалізований у бібліотеці SciPy ([https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_bfgs.html#scipy.optimize.fmin_bfgs детальніше] {{Webarchive|url=https://web.archive.org/web/20201029015410/https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_bfgs.html#scipy.optimize.fmin_bfgs |date=29 жовтня 2020 }}) мовою '''Python'''. 

Реалізація мовою '''R''' - [https://stat.ethz.ch/R-manual/R-devel/library/stats/html/optim.html посилання] {{Webarchive|url=https://web.archive.org/web/20200504143056/https://stat.ethz.ch/R-manual/R-devel/library/stats/html/optim.html |date=4 травня 2020 }}.

Функція з пакету {{нп|Optimization_Toolbox|Optimization toolbox|en|Optimization_Toolbox}} мовою '''Matlab''' - [http://www.mathworks.com/help/optim/ug/fminunc.html;jsessionid=566e468d8f16c34b3deee167539f посилання].

== Посилання ==
{{Методи оптимізації}}
{{без джерел|дата=листопад 2017}}

[[Категорія:Алгоритми оптимізації]]