| dbpprop:abstract
|
- In optimization, quasi-Newton methods (also known as variable metric methods) are well-known algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on Newton's method to find the stationary point of a function, where the gradient is 0. Newton's method assumes that the function can be locally approximated as a quadratic in the region around the optimum, and use the first and second derivatives (gradient and Hessian) to find the stationary point. In Quasi-Newton methods the Hessian matrix of second derivatives of the function to be minimized does not need to be computed. The Hessian is updated by analyzing successive gradient vectors instead. Quasi-Newton methods are a generalization of the secant method to find the root of the first derivative for multidimensional problems. In multi-dimensions the secant equation is under-determined, and quasi-Newton methods differ in how they constrain the solution, typically by adding a simple low-rank update to the current estimate of the Hessian. The first quasi-Newton algorithm was proposed by W.C. Davidon, a physicist working at Argonne National Laboratory. He developed the first quasi-Newton algorithm in 1959: the DFP updating formula, which was later popularized by Fletcher and Powell in 1963, but is rarely used today. The most common quasi-Newton algorithms are currently the SR1 formula (for symmetric rank one) and the widespread BFGS method, that was suggested independently by Broyden, Fletcher, Goldfarb, and Shanno, in 1970. The Broyden's class is a linear combination of the DFP and BFGS methods. The SR1 formula does not guarantee the update matrix to maintain positive-definiteness and can be used for indefinite problems. The Broyden's method does not require the update matrix to be symmetric and it is used to find the root of a general system of equations (rather than the gradient) by updating the Jacobian (rather than the Hessian).
- Quasi-Newton-Verfahren sind eine Klasse von numerischen Verfahren zur Lösung nichtlinearer Minimierungsprobleme. Die Verfahren basieren auf dem Newton-Verfahren, berechnen die Inverse der Hesse-Matrix jedoch nicht direkt, sondern nähern sie lediglich an, um den Rechnenaufwand pro Iteration zu verkleinern. Der erste Algorithmus wurde von W. C Davidon, einem Physiker am Argonne National Laboratory Mitte der 1950er Jahre entwickelt. Die bekanntesten Algorithmen sind Broyden-Fletcher-Goldfarb-Shanno (BFGS) und Davidon-Fletcher-Powell (DFP).
- L'idée des méthodes Quasi-Newton est de remplacer <math>Df(x_k)^{-1}</math> par une matrice <math>B_k</math> plus facile à calculer, et à laquelle on peut imposer certaines propriétés. En l'occurence, il est naturel d'exiger qu'elle soit définie positive. Le fait qu'elle soit une approximation de l'inverse du jacobien se traduit par la relation de Quasi-Newton, <math>x_{k+1}-x_k = B_k\cdot(f-f)</math>, ce qui est manifestement la généralisation du coefficient utilisé dans la méthode de la sécante. Les itérations des méthodes de Quasi-Newton sont alors de la forme suivante: :<math>x_{k+1} = x_{k} - \rho _k\, B_k\cdot f(x_k) ~. </math> Dans cette formule, <math>\rho_k</math> est un coefficient choisi pour optimiser la convergence, et <math>B_k</math> est mise à jour à chaque itération selon une formule particulière. Selon les méthodes de Quasi-Newton, la formule de mise à jour varie. Souvent on applique la méthode à la recherche d'un minimum d'une fonction g(x) que l'on traduit en la recherche de <math>f(x):=\nabla g(x)=0</math>. Dans ce cas il est naturel d'imposer à la matrice Bk qu'elle soit symétrique, car elle correspond alors à la matrice hessienne de g.
- W zagadnieniach optymalizacji, Metody quasi-Newtonowskie (nazywane również metodami zmiennej metryki) są dobrze znanymi algorytmami znajdowania ekstremów lokalnych funkcji. Metody quasi-Newtownowskie bazują na metodzie Newtona znajdowania punktów stacjonarnych funkcji. Metoda Newtona zakłada, że funkcja może być lokalnie aproksymowana funkcją kwadratową w otoczeniu optimum, oraz używają pierwszych i drugich pochodnych (gradient i Hesjan) w celu znalezienia punktów stacjonarnych. W metodzie Quasi-Newtona hesjan(macierz drugich pochodnych) minimalizowanej funkcji nie musi być obliczana. Hesjan jest przybliżany przez analizowanie kolejnych wektorów gradientu. Metody Quasi-Newtona są uogólnieniem metody siecznych znajdowania pierwiastków pierwszej pochodnej na problem wielowymiarowy. W przypadku wielowymiarowym równanie siecznej jest wyznaczane w trakcie działania algorytmu. Metody quasi-Newtonowskie różnią się między sobą sposobem ograniczeń rozwiązania, zazwyczaj przez dodawanie nieznacznej poprawki do przybliżanego w każdym kroku hesjanu. Pierwszy algorytm quasi-Newtonowski został zaproponowany przez W.C. Davidon, fizyka z Argonne National Laboratory.
- Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.
|
| rdfs:comment
|
- In optimization, quasi-Newton methods (also known as variable metric methods) are well-known algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on Newton's method to find the stationary point of a function, where the gradient is 0. Newton's method assumes that the function can be locally approximated as a quadratic in the region around the optimum, and use the first and second derivatives (gradient and Hessian) to find the stationary point.
- Quasi-Newton-Verfahren sind eine Klasse von numerischen Verfahren zur Lösung nichtlinearer Minimierungsprobleme. Die Verfahren basieren auf dem Newton-Verfahren, berechnen die Inverse der Hesse-Matrix jedoch nicht direkt, sondern nähern sie lediglich an, um den Rechnenaufwand pro Iteration zu verkleinern. Der erste Algorithmus wurde von W. C Davidon, einem Physiker am Argonne National Laboratory Mitte der 1950er Jahre entwickelt.
- L'idée des méthodes Quasi-Newton est de remplacer <math>Df(x_k)^{-1}</math> par une matrice <math>B_k</math> plus facile à calculer, et à laquelle on peut imposer certaines propriétés. En l'occurence, il est naturel d'exiger qu'elle soit définie positive.
- W zagadnieniach optymalizacji, Metody quasi-Newtonowskie (nazywane również metodami zmiennej metryki) są dobrze znanymi algorytmami znajdowania ekstremów lokalnych funkcji. Metody quasi-Newtownowskie bazują na metodzie Newtona znajdowania punktów stacjonarnych funkcji. Metoda Newtona zakłada, że funkcja może być lokalnie aproksymowana funkcją kwadratową w otoczeniu optimum, oraz używają pierwszych i drugich pochodnych (gradient i Hesjan) w celu znalezienia punktów stacjonarnych.
- Квазиньютоновские методы — методы оптимизации, основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, чем принципиально отличаются от ньютоновских методов.
|
![[RDF Data]](/statics/sw-cube.png)
