Algorithmes d'optimisation non linéaire: descente de gradient, lm, bfgs, simplexe...

Soyez le premier à donner votre avis sur cette source.

Vue 21 779 fois - Téléchargée 2 468 fois

Description

Ce programme met en jeu plusieurs fonctions d'optimisation pour résoudre les problèmes de programmation non linéaire.
Le but est de trouver un minimum local dans la fonction à optimiser.

Différentes fonctions ont été implémentées. Toutes laissent le choix à l'utilisateur du nombre de paramètres à optimiser. Dans notre cas, nous nous situons en dimension 2 pour des problèmes de visualisation. On optimisera alors les coordonnées x et y de différentes fonctions:

Voici la déclaration mathématique de ce problème :

(x_Optimale,y_Optimale) = argmin f(x,y)

Puissance 2 : f(x,y) = x^2+y^2
Puissance 4 : f(x,y) = x^4+y^4
Rosenbrock : f(x,y) = (1-x^2)^2+100(y-x^2)^2
et d'autres fonctions...

Les fonctions d'optimisation utilisées sont les suivantes:
Descente de gradient, linéaire, suivant la méthode de Wolfe, BFGS, Levenberg-Marquadt (LM), Fletcher-Reeves avec relance périodique et Polack-Robiere

Ces fonctions utilisent toutes le gradient de la fonction f(x,y). Une dernière méthode a été implémenté pour la résolution de ce problème sans la connaissance du gradient de f: la méthode du simplexe (Nelder-Mead)

IHM : La navigation sur la carte a été facilité au maximum: (Manière Google Earth)

Click gauche/déplacé permet de se déplacer suivant x et y.
Mollette de la souris permet de zoomer/dé zoomer à l'endroit où se situe la souris.
Click droit, permet d'adapter l'échelle des couleurs à la fenêtre de visualisation.

Click gauche/déplacé sur le point initial permet de le déplacer et de lancer à nouveau la fonction d'optimisation sélectionnée.

Source / Exemple :


//********************************************************************************
//Vincent Morard 
//20 juin 2009
//http://ImAnalyse.free.fr
//Programme : Optimisation
//********************************************************************************

Conclusion :


L'exe est à renommer de Optimisation.ex en Optimisation.exe

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
229
Date d'inscription
dimanche 14 septembre 2003
Statut
Membre
Dernière intervention
20 août 2014

Merci à vous tous pour ces explications détaillées des cas pratiques ;-)
Messages postés
324
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
30 octobre 2020
2
=> SHENRON666 : pour continuer encore un peu sur les utilisations de toutes ces méthodes on peut citer en géométrie 3d l'ajustement automatique d'une surface au meilleur voisinage d'un nuage de points. Qu'il s'agisse soit d'une surface implicite, exemple une sphère définie par son centre et son rayon, soit d'une surface paramétrique, exemple une surface de Bézier définie par un tableau de points de contrôle, dans tous les cas la fonction à minimiser est la somme des distances, ou de leurs carrés, des points du nuage à la surface provisoire et les variables sont les valeurs qui définissent cette surface. On en déduit la surface optimum.
=> PISTOL_PETE : merci d'avoir mis côte à côte ces diverses méthodes ayant des caractéristiques différentes et qui peuvent convenir plus ou moins à certains types de problèmes ou à certains cas particuliers. ( je n'ai pas 10 parce que cela ne se compile pas sur mon vieux VC6 !! )
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
>PGL10 Effectivement au niveau de la stabilité la méthode Fletcher-Reeves avec relance périodique est très bonne.
Pour Shenron666, ces fonctions sont largement utilisé en chimie, en mécanique, en mathématique... en fait, presque toutes les disciplines.

Pour être concret, voici ma problématique; On sait que des particules d'un matériaux sont des parallélogrammes 3D. La problématique est de trouver la largeur, la longueur et l'épaisseur de ces particules: (L, l et e).
Ce sont donc mes trois paramètres que je vais optimiser par ces méthodes en minimisant une fonction "résidu" bien déterminé. Une fois la convergence atteinte, je connaitrais les paramètres optimaux (L*, l* et e*) de mes particules.
Messages postés
324
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
30 octobre 2020
2
Les méthodes de calcul dont on parle ici ont pour but de trouver le minimum d'une fonction à plusieurs variables en principe sans contraintes, c'est à dire sans limites du domaine à explorer, mais avec un nombre d'appel à la fonction et/ou son gradient le plus faible possible. Cela sert en économie pour optimiser un gain en fonction de paramètres, cela sert pour résoudre des équations non linéaires, ainsi que de nombreux autres problèmes.
Messages postés
324
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
30 octobre 2020
2
Bonjour Pistol_Pete
Je suis bien d'accord avec tes commentaires. L'ancienne méthode de Davidon Fletcher Powell, qui n'est pas là, est complètement surpassée par BFGS, on peut l'oublier. Mais si BFGS est le plus souvent la meilleure en rapidité,je crois que la méthode de Flechter et Reeves avec relance périodique peut dans certains cas être plus robuste. C'est justement pour cela que ton application est très utile pour faire divers essais et comparaisons. Donc encore bravo.
Afficher les 9 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.