BFGS vs méthode du gradient conjugué

Quelles considérations dois-je prendre lors du choix entre BFGS et gradient conjugué pour l'optimisation? La fonction que j'essaie d'adapter à ces variables sont des fonctions exponentielles; cependant, la fonction objective réelle implique l'intégration, entre autres choses, et est très coûteuse si cela aide du tout.

JM a raison sur le stockage. BFGS nécessite une toile de jute approximative, mais vous pouvez l'initialiser avec la matrice d'identité, puis calculer les mises à jour de rang deux de la toile de jute approximative au fur et à mesure, tant que vous disposez d'informations sur le gradient, de préférence analytiquement plutôt que par des différences finies. BFGS est une méthode quasi-Newton, et convergera en moins d'étapes que CG, et a un peu moins tendance à se "bloquer" et à nécessiter de légers ajustements algorithmiques afin d'obtenir une descente significative pour chaque itération.

En revanche, CG nécessite des produits matriciels-vectoriels, qui peuvent vous être utiles si vous pouvez calculer des dérivées directionnelles (encore une fois, analytiquement ou en utilisant des différences finies). Un calcul de différence finie d'une dérivée directionnelle sera beaucoup moins cher qu'un calcul de différence finie d'une Hesse, donc si vous choisissez de construire votre algorithme en utilisant des différences finies, calculez simplement la dérivée directionnelle directement. Cette observation, cependant, ne s'applique pas vraiment à BFGS, qui calculera les Hessiens approximatifs en utilisant les produits internes des informations de gradient.

En termes de taux de convergence, si est le nombre de variables de décision dans votre problème, alors itérations CG sont approximativement égales à une étape de la méthode de Newton. BFGS est une méthode quasi-Newton, mais le même type d'observation devrait être valable; vous êtes susceptible d'obtenir une convergence en moins d'itérations avec BFGS à moins qu'il y ait quelques directions CG dans lesquelles il y a beaucoup de descente, puis après quelques itérations CG, vous la redémarrez. Les méthodes de type CG sont moins chères si les produits à matrice vectorielle sont bon marché et que votre problème est si important que le stockage de la Hesse est difficile, voire impossible. BFGS implique quelques produits vectoriels supplémentaires pour mettre à jour sa Hesse approximative, donc chaque itération BFGS sera plus chère, mais vous en aurez besoin moins pour atteindre un minimum local.$n$$n$

Je comparerais les deux algorithmes sur un petit problème de test pour votre application si vous savez que le stockage ne sera pas un problème. Sans connaître les spécificités particulières de votre problème, je suppose que BFGS sera plus rapide, mais vous devriez vraiment tester les deux algorithmes pour avoir une meilleure idée de ce qui fonctionnera mieux.

Enfin, un mot sur la différenciation automatique: ayant une certaine expérience avec une installation de différenciation automatique (AD) en interne pour Fortran ( DAEPACK ), je peux vous dire que les outils AD sont souvent capricieux. Ils ne sont pas nécessairement en mesure de différencier le code qu'ils génèrent eux-mêmes. Il existe deux types d'outils AD:

• outils AD source à source
• surcharge des outils AD de l'opérateur

Les outils source à source sont essentiellement des compilateurs modifiés qui prennent le code source que vous avez écrit, l'analysent et génèrent automatiquement un nouveau code source qui calcule le gradient des fonctions dans votre code source. Les outils AD surchargés par les opérateurs vous obligent à utiliser les opérateurs AD surchargés dans votre code source afin que les dérivés puissent être calculés, ce qui nécessiterait un effort supplémentaire de votre part pour calculer les dérivés analytiques avec AD.

Le coût associé de BFGS peut être davantage aligné sur CG si vous utilisez les variantes de mémoire limitées plutôt que le BFGS à stockage complet. Cela calcule efficacement la mise à jour BFGS pour les dernières mises à jour par une série de mises à jour de premier rang sans avoir besoin de stocker plus que les dernières solutions et gradients.$m$$m$

D'après mon expérience, BFGS avec beaucoup de mises à jour stocke des informations trop loin de la solution actuelle pour être vraiment utile dans l'approximation du jacobien non décalé, et vous pouvez réellement perdre la convergence si vous stockez trop. Il existe des variantes "sans mémoire" de BFGS qui ressemblent beaucoup à des gradients conjugués non linéaires (voir la mise à jour finale décrite pour l'un d'entre eux) pour ces seules raisons. Par conséquent, si vous êtes prêt à faire du L-BFGS plutôt que du BFGS, les problèmes de mémoire disparaissent et les méthodes sont liées . Des preuves anecdotiques indiquent que le redémarrage est un problème délicat, car il est parfois inutile et parfois très nécessaire.

Votre choix entre les deux dépend également fortement des problèmes qui vous intéressent. Si vous avez les ressources, vous pouvez essayer les deux pour vos problèmes et décider lequel fonctionne le mieux. Par exemple, personnellement, je ne fais pas d'optimisation avec ces algorithmes, mais je me soucie plutôt de la solution des systèmes d'équations non linéaires. Pour ceux-ci, j'ai constaté que NCG fonctionne mieux et est plus facile à effectuer un préconditionnement non linéaire. BFGS est plus robuste.

Franchement, ma méthode préférée pour ce genre de choses est N-GMRES . Cela est particulièrement vrai si votre évaluation gradient est très cher, comme dans mon expérience , il vous donne le plus pour votre argent en résolvant un petit problème de minimisation sur les derniers itère pour construire une nouvelle solution plus faible résiduelle.$m$

En faible dimension, une méthode BFGS bien implémentée est généralement à la fois plus rapide et plus robuste que CG, surtout si la fonction n'est pas très éloignée d'un quadratique.

Ni BFGS ni CG n'ont besoin d'hypothèses sur la convexité; seule l'approximation initiale de Hesse (pour BFGS) resp. le préconditionneur (pour CG) doit être défini positif. Mais ceux-ci peuvent toujours être choisis pour être la matrice d'identité, dans de petites dimensions sans trop de mal. Voir également /scicomp//a/3213/1117

En l'absence d'un gradient programmé, c'est un grand gaspillage d'effort d'utiliser des gradients numériques, surtout lorsque les valeurs de fonction sont coûteuses. Il faut plutôt utiliser un algorithme sans dérivé. Voir http://archimedes.cheme.cmu.edu/?q=dfocomp pour une enquête récente.