Відкрити головне меню

Алгоритм Бройдена - Флетчера - Гольдфарба - Шанно (англ. Broyden–Fletcher–Goldfarb–Shanno (BFGS)) - ітеративний метод числової оптимізації, призначений для знаходження локального максимуму / мінімуму нелінійної функції без обмежень.

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

Зміст

Детальна інформаціяРедагувати

Матриця Гессіана (або Зворотній гессіан) -   - це матриця розміру n × n (де n - довжина вектора градієнта g).

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

 

  (1)

де

  - це зміна градієнту,

  - зміна ваг

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

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

Алгоритм методуРедагувати

Алгоритм складається з наступної послідовності кроків :

  1. Ініціалізуємо вагові коефіцієнти (випадковими малими значеннями) і встановимо початкове значення наближення зворотнього гессіана.
  2. Обчислимо значення градієнту g.
  3. Виконаємо коррекцію значень вагових коефіцієнтів ( ;  ; де -   параметр швидкості навчання)
  4. Зберігаємо старе значення градієнту ( ) та обчислюємо нове значення ( ) і зміну градієнту ( ).
  5. Обчислимо значення зворотнього гессіана   за формулою 1.
  6. Обчислимо зміну вагових коефіцієнтів ( ) і виконаємо коррекцію параметрів ( )
  7. Обчислимо похибку ( )
  8. Якщо отримане значення похибки менше, ніж задана точність ( ), то алгоритм зупиняється.
  9. Якщо точність не досягнута, то повторюємо алгоритм з 4 кроку.

Програмна реалізаціяРедагувати

Реалізація мовою С у рамках проекту GNU Scientific Library (детальніше).

Високоточна версія алгоритму мовою С++ - посилання.

Реалізація алгоритму BFGS та схожих алгоритмів (L-BFGS, L-BFGS-B, CG, метод Ньютона) мовою С++ - посилання.

Алгоритм реалізований у бібліотеці SciPy (детальніше) мовою Python.

Реалізація мовою R - посилання.

Функція з пакету Optimization toolbox[en] мовою Matlab - посилання.

ПосиланняРедагувати