Broyden–Fletcher–Goldfarb–Shanno algorithm (original) (raw)

About DBpedia

在数值优化中， Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法是一种求解无约束非线性优化问题的迭代算法。 和相关的Davidon–Fletcher–Powell算法类似，BFGS算法通过利用曲率信息对梯度进行预处理来确定下降方向。曲率信息则是通过维护一个使用广义的割线法逐步近似的关于损失函数的Hessian矩陣来获得。

Property Value
dbo:abstract Das Broyden–Fletcher–Goldfarb–Shanno (BFGS) Verfahren ist ein numerisches Verfahren zur Lösung von nichtlinearen Optimierungsproblemen. Das Verfahren wurde von den Mathematikern Broyden, Fletcher, Goldfarb und Shanno im Jahre 1970 unabhängig voneinander entwickelt und in vier wissenschaftlichen Artikeln publiziert. Es gehört zu der Gruppe der Quasi-Newton-Verfahren. Als solches vermeidet es die direkte Berechnung der Hesse-Matrix, indem es die Hesse-Matrix iterativ approximiert. Bei quadratischen Funktionen benötigen sowohl das Newton-Verfahren als auch Quasi-Newton-Verfahren ca. N² Funktionsaufrufe (wenn man die Ableitungen über Differenzenquotienten approximiert); dies gilt auch für das Verfahren der konjugierten Gradienten. Allerdings hat sich insbesondere das BFGS-Verfahren in der Praxis besonders bewährt (z. B. ist es relativ tolerant gegenüber Fehlern bei der Schrittweitensteuerung). (de) In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems. Like the related Davidon–Fletcher–Powell method, BFGS determines the descent direction by preconditioning the gradient with curvature information. It does so by gradually improving an approximation to the Hessian matrix of the loss function, obtained only from gradient evaluations (or approximate gradient evaluations) via a generalized secant method. Since the updates of the BFGS curvature matrix do not require matrix inversion, its computational complexity is only , compared to in Newton's method. Also in common use is L-BFGS, which is a limited-memory version of BFGS that is particularly suited to problems with very large numbers of variables (e.g., >1000). The BFGS-B variant handles simple box constraints. The algorithm is named after Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno. (en) En mathématiques, la méthode de Broyden-Fletcher-Goldfarb-Shanno (BFGS) est une méthode permettant de résoudre un problème d'optimisation non linéaire sans contraintes. La méthode BFGS est une solution souvent utilisée lorsque l'on veut un algorithme à directions de descente. L'idée principale de cette méthode est d'éviter de construire explicitement la matrice hessienne et de construire à la place une approximation de l'inverse de la dérivée seconde de la fonction à minimiser, en analysant les différents gradients successifs. Cette approximation des dérivées de la fonction conduit à une méthode quasi-Newton (une variante de la méthode de Newton) de manière à trouver le minimum dans l'espace des paramètres. La matrice hessienne n'a pas besoin d'être recalculée à chaque itération de l'algorithme. Cependant, la méthode suppose que la fonction peut être approchée localement par un développement limité quadratique autour de l'optimum. (fr) 数理最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャンノ法 (英: Broyden–Fletcher–Goldfarb–Shanno algorithm)、略してBFGS法は、非制限非線形最適化問題に対する反復的解法の一つである。 BFGS法は山登り法の一種である、準ニュートン法に属しており、（2回微分可能であることが望ましい）関数の停留点を探索する。この種の問題の最適性の十分条件は勾配が零となることである。ニュートン法とBFGS法は、の近傍で関数が二次までテイラー展開可能でない場合、収束が保証されない。しかし、BFGS法は関数が滑らかでない場合でもよい性能を発揮することが示されている。 準ニュートン法では、二次微分のヘッセ行列は必ずしも直接計算しなければならないわけではなく、勾配を計算（あるいは近似計算）した結果を用いて近似することもできる。準ニュートン法は、一次微分の根を探索する割線法を多次元問題へ一般化したものである。多次元問題では、正割方程式は一意解を与えないため、準ニュートン法はどのように解を拘束するかによってことなる。BFGS法はこの種の手法の中で最も普及しているものの一つである。その他にも、BFGS法を限られたメモリで実行できるようにし、非常に多くの変数を扱えるように変更されたL-BFGS法も広く使われている。単純な矩形拘束を扱うBFGS-B法と呼ばれる変種も存在する。 このアルゴリズムの名前は、、、、に因む。 (ja) Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm) — итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений. BFGS — один из наиболее широко применяемых квазиньютоновских методов. В квазиньютоновских методах не вычисляется напрямую гессиан функции. Вместо этого гессиан оценивается приближенно, исходя из сделанных до этого шагов. Также существуют модификация данного метода с ограниченным использованием памяти, который предназначен для решения нелинейных задач с большим количеством неизвестных, а также модификация с ограниченным использованием памяти в многомерном кубе. Данный метод находит минимум любой дважды непрерывно дифференцируемой выпуклой функции. Несмотря на эти теоретические ограничения, как показывает опыт, BFGS хорошо справляется и с невыпуклыми функциями. (ru) Алгоритм Бройдена - Флетчера - Гольдфарба - Шанно (англ. Broyden–Fletcher–Goldfarb–Shanno (BFGS)) - ітеративний метод числової оптимізації, призначений для знаходження локального максимуму / мінімуму нелінійної функції без обмежень (є спірними слова "без обмежень", див. примітка). Даний метод є одним з найрозповсюдженіших серед класу квазіньютонівських методів. У квазіньютонівських методах гессіан функції не обчислюється безпосередньо, а визначається приблизно, на основі дій зроблених до цього з матрицею Гессіана за допомогою градієнтної оцінки. Вектор градієнта функції помилки вираховується за допомогою звичайної процедури зворотнього розповсюдження помилки. Примітка: Метод Бройдена - Флетчера - Гольдфарба - Шанно не дає повного сходження та його рішення пошуку погрішності не вираховує до кінця погрішність в реальності часу, як наслідок в метод необхідно додавати нові складові для визначення збільшеності погрішності в часі, так як сама постановка задачі не має повноти визначення в алгоритмі (сама задача поставлена локально). Метод не вирішує визначення погрішності, необхідно метод розширити новими змінними для рішення розвитку сходження методу. Тобто: Погрішність повинна стати не врахуванням помилки для визначення поточного результату, погрішність методу повинна стати функцією зміни результату в залежності від зміни часу. (uk) 在数值优化中， Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法是一种求解无约束非线性优化问题的迭代算法。 和相关的Davidon–Fletcher–Powell算法类似，BFGS算法通过利用曲率信息对梯度进行预处理来确定下降方向。曲率信息则是通过维护一个使用广义的割线法逐步近似的关于损失函数的Hessian矩陣来获得。 (zh)
dbo:wikiPageExternalLink https://julianlsolvers.github.io/Optim.jl/stable/ https://archive.org/details/practicalmethods0000flet
dbo:wikiPageID 1926409 (xsd:integer)
dbo:wikiPageLength 16975 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1124576811 (xsd:integer)
dbo:wikiPageWikiLink dbr:BHHH_algorithm dbr:SciPy dbr:Nonlinear_optimization dbr:Julia_(programming_language) dbr:Pattern_search_(optimization) dbr:Charles_George_Broyden dbr:David_Shanno dbr:Davidon–Fletcher–Powell_formula dbr:Descent_direction dbr:Donald_Goldfarb dbr:Levenberg–Marquardt_algorithm dbr:John_Wiley_&_Sons dbr:Positive_definiteness dbr:Confidence_interval dbr:Mathematica dbr:Matrix_inverse dbr:Matrix_inversion dbr:Maximum_likelihood_estimation dbr:Nelder–Mead_method dbr:Wolfe_conditions dbr:Optimization_(mathematics) dbr:GNU_Octave dbr:GNU_Scientific_Library dbr:Gradient dbr:Gradient_descent dbr:Credible_interval dbr:Strongly_convex_function dbr:Computational_complexity_of_mathematical_operations dbc:Optimization_algorithms_and_methods dbr:Line_search dbr:Sherman–Morrison_formula dbr:ALGLIB dbr:Numerical_analysis dbr:Iterative_method dbr:Artelys_Knitro dbr:Hessian_matrix dbr:Newton's_method_in_optimization dbr:Optimization_Toolbox dbr:R_(programming_language) dbr:Secant_method dbr:Loss_function dbr:Roger_Fletcher_(mathematician) dbr:Trust_region dbr:Symmetric_rank-one dbr:L-BFGS dbr:Quasi-Newton_methods dbr:Preconditioned_gradient_descent
dbp:wikiPageUsesTemplate dbt:Citation dbt:Citation_needed dbt:Div_col dbt:Div_col_end dbt:More_citations_needed dbt:Redirect dbt:Reflist dbt:Short_description dbt:Optimization_algorithms
dcterms:subject dbc:Optimization_algorithms_and_methods
gold:hypernym dbr:Method
rdf:type dbo:Software yago:WikicatOptimizationAlgorithmsAndMethods yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:comment 在数值优化中， Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法是一种求解无约束非线性优化问题的迭代算法。 和相关的Davidon–Fletcher–Powell算法类似，BFGS算法通过利用曲率信息对梯度进行预处理来确定下降方向。曲率信息则是通过维护一个使用广义的割线法逐步近似的关于损失函数的Hessian矩陣来获得。 (zh) Das Broyden–Fletcher–Goldfarb–Shanno (BFGS) Verfahren ist ein numerisches Verfahren zur Lösung von nichtlinearen Optimierungsproblemen. Das Verfahren wurde von den Mathematikern Broyden, Fletcher, Goldfarb und Shanno im Jahre 1970 unabhängig voneinander entwickelt und in vier wissenschaftlichen Artikeln publiziert. (de) In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems. Like the related Davidon–Fletcher–Powell method, BFGS determines the descent direction by preconditioning the gradient with curvature information. It does so by gradually improving an approximation to the Hessian matrix of the loss function, obtained only from gradient evaluations (or approximate gradient evaluations) via a generalized secant method. (en) En mathématiques, la méthode de Broyden-Fletcher-Goldfarb-Shanno (BFGS) est une méthode permettant de résoudre un problème d'optimisation non linéaire sans contraintes. La méthode BFGS est une solution souvent utilisée lorsque l'on veut un algorithme à directions de descente. La matrice hessienne n'a pas besoin d'être recalculée à chaque itération de l'algorithme. Cependant, la méthode suppose que la fonction peut être approchée localement par un développement limité quadratique autour de l'optimum. (fr) 数理最適化において、ブロイデン・フレッチャー・ゴールドファーブ・シャンノ法 (英: Broyden–Fletcher–Goldfarb–Shanno algorithm)、略してBFGS法は、非制限非線形最適化問題に対する反復的解法の一つである。 BFGS法は山登り法の一種である、準ニュートン法に属しており、（2回微分可能であることが望ましい）関数の停留点を探索する。この種の問題の最適性の十分条件は勾配が零となることである。ニュートン法とBFGS法は、の近傍で関数が二次までテイラー展開可能でない場合、収束が保証されない。しかし、BFGS法は関数が滑らかでない場合でもよい性能を発揮することが示されている。 このアルゴリズムの名前は、、、、に因む。 (ja) Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm) — итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений. Данный метод находит минимум любой дважды непрерывно дифференцируемой выпуклой функции. Несмотря на эти теоретические ограничения, как показывает опыт, BFGS хорошо справляется и с невыпуклыми функциями. (ru) Алгоритм Бройдена - Флетчера - Гольдфарба - Шанно (англ. Broyden–Fletcher–Goldfarb–Shanno (BFGS)) - ітеративний метод числової оптимізації, призначений для знаходження локального максимуму / мінімуму нелінійної функції без обмежень (є спірними слова "без обмежень", див. примітка). (uk)
rdfs:label BFGS-Verfahren (de) Broyden–Fletcher–Goldfarb–Shanno algorithm (en) Méthode de Broyden-Fletcher-Goldfarb-Shanno (fr) BFGS法 (ja) Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (ru) BFGS算法 (zh) Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (uk)
owl:sameAs freebase:Broyden–Fletcher–Goldfarb–Shanno algorithm wikidata:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-de:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-fa:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-fr:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-ja:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-ru:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-uk:Broyden–Fletcher–Goldfarb–Shanno algorithm dbpedia-zh:Broyden–Fletcher–Goldfarb–Shanno algorithm https://global.dbpedia.org/id/2fepT
prov:wasDerivedFrom wikipedia-en:Broyden–Fletcher–Goldfarb–Shanno_algorithm?oldid=1124576811&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Broyden–Fletcher–Goldfarb–Shanno_algorithm
is dbo:wikiPageDisambiguates of dbr:Goldfarb
is dbo:wikiPageRedirects of dbr:BFGS dbr:BFGS_method dbr:Broyden-Fletcher-Goldfarb-Shanno_algorithm dbr:Broydon-Fletcher-Goldfarb-Shanno
is dbo:wikiPageWikiLink of dbr:Bayesian_optimization dbr:David_Shanno dbr:Davidon–Fletcher–Powell_formula dbr:Donald_Goldfarb dbr:Limited-memory_BFGS dbr:List_of_numerical_analysis_topics dbr:Maximum_likelihood_estimation dbr:Gradient_descent dbr:Berndt–Hall–Hall–Hausman_algorithm dbr:Stan_(software) dbr:Mathematics_of_artificial_neural_networks dbr:Broyden's_method dbr:K-transform dbr:Centroidal_Voronoi_tessellation dbr:Goldfarb dbr:Nonlinear_conjugate_gradient_method dbr:Hessian_matrix dbr:Portable,_Extensible_Toolkit_for_Scientific_Computation dbr:BFGS dbr:BFGS_method dbr:Broyden-Fletcher-Goldfarb-Shanno_algorithm dbr:Broydon-Fletcher-Goldfarb-Shanno
is foaf:primaryTopic of wikipedia-en:Broyden–Fletcher–Goldfarb–Shanno_algorithm