Méthode Quasi-newton

Méthode Quasi-NewtonIl s'agit d'une méthode d'optimisation basée sur la méthode de Newton, qui est principalement utilisée pour résoudre les problèmes de valeurs nulles, maximales et minimales d'équations non linéaires ou de fonctions continues.

 

Lorsque la matrice jacobienne dans la méthode de Newton ou  Toile de jute Lorsque la matrice est difficile voire impossible à calculer, la méthode quasi-Newton entre en jeu. C'est l'une des méthodes les plus efficaces pour résoudre les problèmes d'optimisation non linéaire. La méthode quasi-Newton a été proposée pour la première fois par les États-Unis. Argonne Physicien au Laboratoire national WCDavidon À 20 siècle 50 L'ère proposée.

L'idée de la méthode quasi-Newton

La méthode de Newton résout Toile de jute Lors du calcul de la matrice, la matrice inverse doit d'abord être calculée, ce qui entraînera une diminution de l'efficacité, mais la méthode quasi-Newton utilise une matrice définie positive pour approximer Toile de jute La matrice inverse de la matrice est obtenue, réduisant ainsi la complexité de l'algorithme et améliorant l'efficacité.

Algorithmes quasi-Newton courants

• Algorithme DFP (Davidon-Fletcher-Powell)

Dans l'algorithme DFP, nous choisissons comme approximation de , en supposant qu'à chaque itération la matrice est composée de plus deux termes supplémentaires, à savoir

dans,
etest la matrice indéterminée. mais

FaireEn satisfaisant la condition quasi-Newtonienne, nous pouvonsetsatisfaire

Souhaitable

La matrice peut être obtenueFormule itérative

Il peut être prouvé que si la matrice initialeest définie positive, alors chaque matrice dans le processus itératifIls sont tous positifs.

• Algorithme BFGS (Broyden-Fletcher-Goldfard-Shano)

DFP est unApproximation de l'inverse de la matrice hessienne, tandis que dans l'algorithme BFGS,Approximation de la matrice hessienne, la condition quasi-Newtonienne correspondante

Supposons qu'à chaque itération la matriceEstAvec deux termes supplémentaires, à savoir

dans,etest la matrice indéterminée. mais

FaireEn satisfaisant la condition quasi-Newtonienne, nous pouvonsetsatisfaire

Souhaitable

La matrice peut être obtenueFormule itérative

Il peut être prouvé que si la matrice initialeest définie positive, alors chaque matrice dans le processus itératifIls sont tous positifs.

• algorithme de type Broyden (algorithme de Broyden)

Nous pouvons obtenir la matrice de l'algorithme BFGSLa formule itérative de l'algorithme BFGS estFormule d'itération de .

souviens-toi

En appliquant deux fois la formule de Sherman-Morrison, nous obtenons

Il s'agit de l'algorithme BFGS.Formule d'itération de .

La formule de Sherman-Morrison : Supposonsest une matrice réversible d'ordre n,est un vecteur à n dimensions, etest également une matrice réversible, alors :

Soit la formule itérative obtenue par l'algorithme DFPEnregistré comme, selon la formule itérative de l'algorithme BFGSCe que vous obtenezNoté comme, puisque et satisfont tous deux à la condition quasi-Newton, la combinaison linéaire des deux

Elle satisfait également la condition quasi-Newtonienne et est définie positive. dans,. Ce type d'algorithme est appelé algorithme de type Broyden.

Mots apparentés : méthode de Newton, optimisation