J'essaie de résoudre certains problèmes d'optimisation non linéaire sans contrainte sur le GPU (CUDA).
La fonction objectif est une fonction non linéaire lisse, et son gradient est relativement bon marché à calculer analytiquement, donc je n'ai pas besoin de me soucier de l'approximation numérique.
Je veux résoudre ce problème avec principalement des opérations mathématiques fp32 (pour diverses raisons), alors quelle méthode d'optimisation non linéaire est plus robuste contre les erreurs d'arrondi tout en ayant de bonnes performances? (par exemple gradient conjugué / quasi newton / région de confiance), quelqu'un a-t-il essayé BFGS sur GPU avec de bons résultats?
BTW, le Hessian, si nécessaire, est relativement petit dans mon cas (<64x64 en général), mais je dois résoudre simultanément des milliers de ces problèmes d'optimisation à petite échelle.
la source
Réponses:
J'ai implémenté une grande variété de solveurs non linéaires sur le GPU, y compris LBFGS, la descente de gradient de Barzilai Borwein et le gradient conjugué non linéaire.
Pour cela, le gradient conjugué non linéaire de Dai & Yuan a été le plus efficace. En général, une autre version du gradient conjugué non linéaire peut être plus efficace (comme CG-DESCENT), mais peut également être plus difficile à mettre en œuvre.
LBFGS est en général un choix très solide, et à moins que vous ne soyez vraiment à court de mémoire, c'est probablement le meilleur endroit pour commencer.
Le gradient conjugué et le BFGS nécessitent cependant des recherches de ligne, c'est là que le fp32 devient un problème. Plutôt que d'utiliser les conditions Wolfe standard pour la recherche de ligne, je suggère d'utiliser la condition Wolfe approximative suggérée ici . Le papier est un peu impliqué, mais l'important est l'équation 4.1. Essentiellement, ils introduisent explicitement la précision avec laquelle vous pouvez calculer votre fonction.
Considérations pour le GPU:
Vous avez beaucoup de petits problèmes, ce qui est légèrement différent de mon cas d'utilisation d'un gros problème. Envisagez d'exécuter 1 problème par bloc GPU (ou warp, plutôt) si vous pouvez paralléliser les évaluations de fonction et de gradient pour utiliser tous les threads d'un bloc. De cette façon, ce n'est pas un problème si différents problèmes nécessitent un nombre différent d'itérations.
Si ce n'est pas une option, j'irais avec le solveur LBFGS. Si votre fonction se comporte bien, vous pouvez vous en sortir en utilisant simplement une taille de pas de 1 (en évitant la recherche de ligne) et en exécutant simplement tous les problèmes pour un nombre fixe d'itérations.
la source
Je vous suggère d'utiliser Levenberg Marquardt (une variante de région de confiance) car il est utilisé dans de nombreuses applications pratiques et a démontré de très bonnes performances vitesse / précision. De plus, pour le GPU, il existe certaines bibliothèques (par exemple cuLM https://github.com/zitmen/cuLM ), que vous pouvez essayer. S'ils ne font pas le travail, il y a des tonnes de ressources à mettre en œuvre. La mise en œuvre de LM n'est pas difficile du tout. Vous ne devez prendre soin de minimiser la communication GPU. Pour avoir une brève idée:
http://on-demand.gputechconf.com/gtc/2012/presentations/S0231-Levenberg-Marquardt-Using-Block-Sparse-Matrices-on-CUDA.pdf
la source
Peut-être qu'une procédure de recuit simulé peut mieux gérer les erreurs d'arrondi (et est facilement parallélisée).
Vous commencez avec une grille brute de la zone de recherche et un paramètre initial "température"
À chaque étape, vous calculez des points de solution possibles (on peut également accepter des points de non-solution, avec une probabilité inversement analogue à la température)
Ensuite, ne retenez que les solutions à cette étape et augmentez la température, ce qui fournit une grille à grains plus fins pour la prochaine itération
Faites ceci jusqu'à ce que la température <une limite / seuil de précision donné
la source