J'ai besoin de trouver le minimum d'une fonction. En lisant les documents sur http://docs.scipy.org/doc/scipy/reference/optimize.html je vois qu'il existe plusieurs algorithmes qui font la même chose, c'est-à-dire trouver le minimum. Comment savoir lequel choisir?
une partie de l'algorithme répertorié
- Minimisez une fonction en utilisant l'algorithme du simplex de descente.
- Réduisez une fonction à l'aide de l'algorithme BFGS.
- Minimisez une fonction avec un algorithme de gradient conjugué non linéaire.
- Minimisez la fonction f à l'aide de la méthode Newton-CG.
- Minimisez une fonction en utilisant la méthode de Powell modifiée.
Ma fonction est linéaire. la dimensionnalité est d'environ 232750 (c'est le nombre de dégradés différents que je dois calculer à chaque fois), il faut environ 2 minutes pour calculer le gradient et le coût une fois, donc pas bon marché. Je ne pense pas avoir de contraintes. elle est déterministe et continue.
optimization
siamii
la source
la source
Réponses:
D'après ce que vous avez dit: je suppose que vous devez optimiser pour 50 variables; Je suppose également que vous vous trouvez dans une situation où il est très coûteux de trouver des dérivés analytiques (sans parler de retirer des données numériques) et que votre optimisation est sans contrainte.
Permettez-moi de souligner, vous êtes un peu malchanceux car entre 25-30 et 100 variables, c'est un peu une zone crépusculaire quand il s'agit de choisir entre des routines d'optimisation à grande ou à petite échelle. Cela dit, rien n'est perdu.
Étant donné que même un dérivé de premier ordre coûte cher pour retirer ce type, il tue l'idée de la méthode de Newton. Vous pourriez avoir de la chance avec Quasi-Newton (BFGS), mais si votre Hessian est légèrement diagonal, vous aimeriez commencer. CG est généralement un peu plus lent que BFGS, ce qui n'améliorera probablement pas beaucoup les choses; utilisez-le si la mémoire est également un problème (ou optez simplement pour L-BFGS dans ce cas). De plus, étant donné la lenteur à évaluer votre fonction, un simple algorithme de recherche de descente / ligne le plus raide serait tortueusement lent; il en va de même pour le recuit simulé et d'autres variantes de recherche aléatoire (je suppose que vous n'avez pas accès à la console HMC et à tout ce jazz).
Ainsi, lorsque vous avez besoin du meilleur rapport qualité / prix pour une évaluation de fonction unique: optez pour la méthode de Powell et testez également COBYLA; bien qu'il s'agisse d'un algorithme d'optimisation contraint, car il rapprochera linéairement en interne le gradient de votre fonction pour accélérer les choses, il pourra profiter de la linéarité de votre fonction. Aussi certainement essayer NLopt pour Python . Ils ont beaucoup d'optimiseurs sans gradient; essayez UOBYQA; c'est aussi l'idée originale de Powell (Optimisation sans contrainte par approximations quadratiques).
Très brièvement: les algorithmes N-CG dépendent du calcul du Hessian, et votre Hessian semble très cher à calculer. NLCG et BFGS ne l'exigent pas, bien qu'ils pourraient essayer de le calculer une fois dans leur première étape.
J'ai délibérément omis l'algorithme simplex car c'est une bête totalement différente; rien à voir avec les dégradés en tant que tels. Essayez-le mais je ne peux pas vraiment le commenter; cela dépend vraiment de la nature de votre problème.
Pour une première bonne référence sur l'optimisation numérique, le livre de CTKelly, Iterative Methods for Optimization , vous mènera assez loin, très bien.
la source
Vous devriez peut-être vous procurer un livre d'introduction sur l'optimisation numérique. Vous devrez prendre en compte votre fonction pour décider de l'algorithme.
Parmi les algorithmes que vous mentionnez, les différences importantes sont de savoir si le jacobien ou le hessois est nécessaire ou uniquement la fonction elle-même.
Étant donné qu'il s'agit d'un site de questions-réponses statistiques et traite donc de variables aléatoires: assurez-vous que votre fonction est déterministe peut être évaluée d'une manière qui donne des résultats continus sur l'espace de recherche.
la source