Optimisation avec BFGS

[invite78803cef]

Bonsoir à tous,

Je me lance dans l'apprentissage de la méthode BFGS (Broyden-Fletcher-Goldfarb-Shanno), qui est une méthode d'optimisation.

Voici l'algorithme que j'utilise:

BFGS.png

Je souhaite utiliser le BFGS afin de trouver le vecteur de solutions x^* de la fonction suivante:

f(x)= e^(x₁-1)- e^(-x₂+1)+(x₁-x₂)²

Voici le détail de mon calcul des deux premières itérations:

BFGS-Calcul_2.pdf

Au fil des itérations, il apparaît bien que le résultat converge vers deux valeurs x₁ et x₂. Le problème est que ce ne sont pas les bonnes !

Voici les résultats des valeurs x₁ et x₂ des 10 premières itérations:

ITERATION 1 X1 0 X2 0
ITERATION 2 X1 -0,092 X2 0,68
ITERATION 3 X1 1,014 X2 1,264
ITERATION 4 X1 0,75 X2 1,164
ITERATION 5 X1 0,782 X2 1,176
ITERATION 6 X1 0,79 X2 1,19
ITERATION 7 X1 0,785 X2 1,195
ITERATION 8 X1 0,794 X2 1,203
ITERATION 9 X1 0,796 X2 1,204
ITERATION 10 X1 0,796 X2 1,204

Je cherche donc à quel endroit j'aurais pu faire une erreur. Peut-être dans la recherche linéaire ?
J'ai l'impression de tourner en rond et de ne pas avancer en cherchant cette erreur. Je me dis qu'un œil neuf pourrait m'être utile !

Je remercie d'avance ceux qui prendront le temps de se pencher sur mon problème.

Bonne soirée

Léo
-----

[SULREN]

Bonjour,

Au fil des itérations, il apparaît bien que le résultat converge vers deux valeurs x1 et x2. Le problème est que ce ne sont pas les bonnes !

Sauf erreur bien sûr (et j'en fais beaucoup), je trouve 3 solutions, dont {0,0}. Les deux autres ne sont peut-être que des solutions approchées, à 10^-7
Si elles sont exactes, il faudrait que votre algo converge successivement vers 3 solutions.

Mais cela ne répond pas à la question que vous avez posée. Désolé.

[SULREN]

EDIT je viens de voir que j'ai écrit (-x2 -1) dans la 2eme exponentielle au lieu de (-x2+1), donc tout faux. Sorry.

[SULREN]

Bonjour,
Au tout début du document BFGS-calcul_2.pdf, dans le calcul de Δf(x), vérifiez si le terme en début de la 2eme ligne est correct.
Je parle du: -2 Exp (x₂+1)

[A voir en vidéo sur Futura]

[invite78803cef]

Bonsoir Sulren,

Tout d'abord merci beaucoup pour votre aide.

Vous avez raison, j'ai oublié de mettre un - en recopiant la formule de la deuxième ligne. Il s'agit bien de -e^-x₂+1 - 2x₁ + 2x₂.

Il s'agit d'une coquille, et la suite des calculs est bien réalisée avec la bonne formule. Ce qui signifie que mon problème vient d'ailleurs malheureusement.

Voici le fichier rectifié pour que tout soit clair:

BFGS_Calcul.pdf

Bonne soirée

Léo

[SULREN]

Re,
Ce qui me semblait faux c'est non seulement le signe - qui manquait devant le x2 et qui n'a aucune conséquence à la première itération car x2=0.
C'est aussi le signe - devant l'exponentielle elle-même. Il me semble qu'il faudrait un + et là cela change tout dès la première itération. Le do devient faux.
Dans la dérivation le -x2 donne un -1 à mettre devant l'exponentielle, qui se combine avec le - déjà existant devant elle pour donner un +.
(mais je peux me tromper, je ne suis pas un grand matheux).

[invite78803cef]

Vous avez tout à fait raison, c'est bien un + et non un -. C'est une erreur, je suis allé un peu trop vite.
Je vais recommencer mon investigation avec cette nouvelle version.
Merci

[SULREN]

Re,
Sachant que votre intérêt est principalement l’apprentissage de l’application de la méthode, et pas ses résultats numériques, je ne suis pas sûr que ce qui suit vous intéressera.

Je trouve 3 solutions :
- La (1,1) qui est évidente
- La (-1,062819957733 , 0,306199014187) qui n’est peut-être qu’une solution approchée, à -3*10^-8
- La (-0,210846006870 , 0,769563972950) qui n’est peut-être aussi qu’une solution approchée, à -7*10^-8

[invite78803cef]

Bonsoir,

Alors je me suis finalement rendu compte que c'est en recopiant ma fonction que j'ai fait une erreur...
C'est un + et non un - devant la deuxième exponentielle:

f(x)= e^(x₁-1)+ e^(-x₂+1)+(x₁-x₂)²

D'où l'erreur sur le gradient (c'est finalement bien un -).

La suite des calculs est bonne. Ce n'était que des erreurs de copie au début du document. Désolé Sulren pour le temps passé.
Voici le fichier à jour (cette fois c'est la bonne !):

BFGS_Calcul.pdf

J'ai également compris les résultats que j'obtenais au fil des itérations.
Il s'agit des valeurs des variables x₁ et x₂ qui annulent le gradient. Ce qui paraît plutôt logique finalement.

Par exemple si je calcule le gradient avec les valeurs de l'itération 10 (X₁ = 0,796 et X₂ = 1,204) j'obtiens un résultat très proche de 0 (et on se rapproche de 0 à chaque itération).

Mon algorithme semble finalement bien fonctionner.

Ce qu'il me reste à faire maintenant est de trouver un moyen de résoudre mon équation à partir de là.
Quelqu'un aurait-il une idée ?

[JPL]

Je laisse le pdf mais on peut faire la même chose avec l’outil Tex de l’éditeur en mode avancé : http://forums.futura-sciences.com/fo...e-demploi.html.

[SULREN]

Bonsoir,

@ LLS :
Vous avez écrit :

Désolé Sulren pour le temps passé.

Aucun problème. Je n’interviens sur le forum que par pur plaisir, sans aucun souci de rentabilité, mais avec quand même le souci d’aider le plus efficacement possible.

Vous avez écrit dans le post d’ouverture :

Au fil des itérations, il apparaît bien que le résultat converge vers deux valeurs x1 et x2. Le problème est que ce ne sont pas les bonnes !

Et ces valeurs étaient :
X1 0,796 X2 1,204

Ce n’est que mon avis, celui d'un petit matheux, mais je pense que ces valeurs sont les bonnes.
Ma méthode « bidouille » aboutit aussi à ces valeurs.
Elles conduisent au minimum de F(x).

[SULREN]

Re,

Plus précisément je trouve (je pourrais encore affiner) :
X1 : 0,796111524105
X2 : 1,203888535500

Minimum de f(x) : 1,7973886728

sous réserve d'avoir bien compris ce que vous cherchez.

[invite78803cef]

Re,

Merci pour votre dévouement !

Oui je suis d'accord, ce sont bien les valeurs qui annulent le gradient de la fonction.
Je pensais que ces valeurs étaient fausses au départ car je m'attendais à ce que l'algorithme retourne comme x₁ et x₂ les valeurs qui permettent de résoudre l'équation:

e^(x₁-1) + e^(-x₂+1) + (x₁-x₂)² = 0

Car mon objectif est bien d'utiliser le BFGS pour trouver les x₁ et x₂ qui résolvent l'équation.
Voyez-vous comment procéder ?

[SULREN]

Re,

J'ai cherché aussi les racines de la fonction dans sa nouvelle formulation, mais je n'en trouve pas non plus.
f(x) ne descend pas en dessous de 1,7973 C'est ce que j'ai voulu dire en parlant de minimum de f(x).
Il n'existerait pas de x1 et de x2 qui fassent que f(x) = 0

Je trouvais des racines, et je les ai indiquées, pour la fonction formulée au tout début, et qui comportait le signe - devant la deuxième exponentielle.

[SULREN]

Bonjour,

Ceci étant LLS, si votre objectif était de maîtriser l’application de la méthode BFGS, vous l’avez atteint, puisqu’elle est une manière de trouver le minimum d’une fonction dans l'espace des paramètres et qu’elle vous a conduit au minimum de f(x).

Le mot « optimisation » dans le titre de la discussion suggérait d’ailleurs qu’on se posait un problème de recherche d’extremum et pas de recherche de 0 (de racines).

Mais c’est en contradiction avec :

Car mon objectif est bien d'utiliser le BFGS pour trouver les x1 et x2 qui résolvent l'équation.

L’algorithme de Newton ne serait-il pas plus approprié ?

[invite78803cef]

Bonjour,

Pour vous permettre d'y voir plus clair, je vais tenter de vous expliquer pourquoi j'ai besoin d'utiliser cet algorithme. C'est sûrement ce que j'aurais du faire depuis le début, plutôt que de partir sur l'exemple "abstrait' d'une fonction.

Je souhaite utiliser l'algorithme BFGS pour résoudre des problèmes basés sur des contraintes géométriques.
Ces contraintes géométriques peuvent être traduites sous forme d'équations.
Par exemple si je souhaite que le point P2 soit aligné avec le point P1 en y, j'aurais l'équation:
P₁y - P₂y = 0
Si je souhaite que mon point P2 se trouve à une distance D de mon point P1, j'aurais une équation de cercle:
(P₂x - P₁x)² + (P₂y - P₁y)² - D² = 0
Et ainsi de suite...

L'ensemble de mes contraintes sont donc modélisées sous la forme d'un système d'équations.
Le but étant de trouver les inconnues qui permettent de résoudre ce système, et donc de respecter l'ensemble des contraintes géométriques.

Je n'ai pas choisi la méthode BFGS par hasard, j'ai trouvé plusieurs documents concernant la résolution de problèmes basés sur des contraintes géométriques et tous utilisent cette méthode.
Une des raisons principales étant sa capacité à fournir un résultat même si le nombre d'équations diffère du nombre d'inconnues (ce qui est une des limites de la méthode de Newton, il me semble).

Il semble que mon algorithme fonctionne puisqu'il converge bien vers le minimum de la fonction comme nous avons pu le voir.
Néanmoins il me reste à comprendre comment l'appliquer à mon problème.

Ce que j'ai fait intuitivement est de considérer comme fonction de départ la somme des équations géométriques à résoudre.
Dans ce cas, l'algorithme me retourne les valeurs qui permettent d'annuler le gradient (comme pour la fonction de mon exemple). Ce qui est logique.

J'en suis donc à chercher comment transformer mon système d'équations géométriques de manière à ce que la méthode BFGS puisse me retourner la solution de ce système.
Je reste convaincu que cela est possible !

[SULREN]

Bonjour,
Merci pour cette explication détaillée du problème qui se pose à vous……et merci aussi d’avoir fait découvrir la méthode BFGS à ceux qui (comme moi) ne la connaissaient pas.

Il s’agit semble t'il d’une méthode de descente vers un minimum local et pas d’une méthode de convergence vers les 0, mais si vous l’avez vue appliquée à des cas similaires aux vôtres, c’est qu’on doit parvenir à l’adapter.
A moins que ces cas étaient des problèmes d’optimisation (ex : dimensionnelle, de matière,….), ce qui ramène à une recherche d’extremum et pas de 0.
Votre algorithme fonctionne bien dans ces cas là, comme vous l’avez montré.

Je ne suis hélas pas en mesure de vous aider à l’utiliser pour la résolution de F(x) =0.
Mais les « pointures » de ce forum le feront probablement.

Par contre, j’ai eu comme vous à résoudre des systèmes d’équations non linéaires un peu tordues, pour mes hobbies.
Dans l’urgence, je n’ai même pas tenté de réviser les méthodes mathématiques perdues au fond de mes souvenirs d’étudiant,…..et y serais-je même parvenu ?
J’ai donc mis au point un code numérique brutal, mais efficace et qui digère tout. En tous cas il ne m’a encore jamais lâché.
Si vous avez des systèmes à résoudre n’hésitez pas à les soumettre, pour comparer et conforter les résultats.
@+ j’espère.

PS :

Ce que j'ai fait intuitivement est de considérer comme fonction de départ la somme des équations géométriques à résoudre.
Dans ce cas, l'algorithme me retourne les valeurs qui permettent d'annuler le gradient.

L’annulation du gradient de la somme des équations signifie t-elle qu’on est parvenu à une solution (racine) du système constitué par ces équations ?
De plus il peut exister plusieurs racines.

[invite78803cef]

Bonsoir,

Mon problème est résolu !

La méthode à adopter est de considérer comme fonction à traiter la somme des carrés des fonctions du système.

Par exemple si je veux résoudre le système d'équations suivant (qui correspond à trois contraintes de longueur de trois lignes pour définir un triangle):

f₁(X)=(x₁−100)²+(100−100)²−200²=0
f₂(X)=(x₂−x₁)²+(x₃−100)²−300²=0
f₃(X)=(x₂−100)²+(x₃−100)²−250²=0

J'utilise la fonction F suivante comme donnée d'entrée du BFGS:

F(X) = f₁(X)² + f₂(X)² + f₃(X)²

La suite se déroule de la même manière que l'exemple de mon post de départ avec les exponentielles.

En prenant comme point de départ X₀ = (200,200,200) par exemple, la solution X* obtenue converge vers les valeurs (300.000 , 131.250 , 148.039) qui sont bien les solutions que je souhaite obtenir.
Quand il y a plusieurs solutions possibles (c'est le cas pour ce système), le choix du point de départ X₀ sera crucial puisqu'il déterminera vers quelles solutions l'algorithme convergera.

J'ai contacté quelqu'un qui a travaillé avec la méthode BFGS pour résoudre des problèmes géométriques similaires aux miens, et il m'a conseillé également la méthode du GRG (Generalized Reducer Gradient) qui est une méthode d'optimisation elle aussi. C'est cette méthode qui est par exemple utilisée dans le solveur d'équations d'Excel, solveur qui a l'air assez puissant. Il pourrait être intéressant de comparer les performances de cette méthode avec celle du BFGS pour la résolution de problèmes basés sur des contraintes géométriques.

Sulren, merci pour votre aide et votre patience.
Votre méthode "brutale" (j'aime bien le terme !) fonctionnerait-elle pour ce type de système d'équations ?
Et pour des systèmes dont le nombre d'équations diffère du nombre d'inconnues (problèmes géométriques sous-contraints ou sur-contraints) ?

Bonne soirée.

Léo

[SULREN]

Bonjour,
En tous cas bravo pour votre persévérance ! Vous ne lâchez pas le problème.

En première analyse j’ai un doute sur la méthode, mais c’est peut-être simplement dû à mes insuffisances en maths. Donc à approfondir.

La minimisation par BFGS de la somme des carrés des fonctions devrait en effet conduire à un jeu des valeurs des inconnues qui annule simultanément toutes ces fonctions, donc à une solution du système qu’elles constituent……mais dans la mesure où ce système a une solution.
Sinon on arriverait juste à un minimum de cette somme.

Je n’ai pas essayé de résoudre le système d’équations que nous avez posé, car le terme (100-100)^2 dans la première équation me trouble.
Après clarification de ce point j’essaierai ma méthode sur ce système et répondrai à la dernière question de votre message.
@+

[invite78803cef]

Bonjour,

Voici d'où provient ce système d'équations:

Considérons un triangle défini par trois points P1, P2, et P3 et possédant 3 contraintes de longueurs: P1P2 = 200 ; P2P3 = 300; P3P1 = 250.
J'ai trois équations de cercle qui correspondent à ces trois contraintes de longueurs:

f1(X) = (P2x - P1x)² + (P2y - P1y)² - 200² = 0
f2(X) = (P3x - P2x)² + (P3y - P2y)² - 300² = 0
f3(X) = (P3x - P1x)² + (P3y - P1y)² - 250² = 0

J'impose à mon premier point P1 les coordonnées (100,100) et à mon point P2 une contrainte d'horizontalité avec P1 (P1y = P2y = 100).

En utilisant la notation X1, X2, ... , Xn on obtient:

f1(X) = (x1 - 100)² + (100 - 100)² - 200² = 0
f2(X) = (x2 - x1)² + (x3 - 100)² - 300² = 0
f3(X) = (x2 - 100)² + (x3 - 100)² - 250² = 0

[SULREN]

Re,
Avant d'analyser votre raisonnement pour y trouver d'éventuelles failles, disons que si on considère le plan contenant votre triangle, et qu'on le dote d'un système de coordonnées rectangulaires {x,y}, et qu'on prenne en compte les contraintes que vous avez fixées et les positions imposées à P1 et P2, les trois points de ce triangle ont pour coordonnées:

P1 (x=100; y=100)
P2 (x=300; y=100)
P3 (x=131,25; y=348,039185)

Dans le cas présent l'application de Pythagore suffisait. Dans un cas plus général il faudra autre chose.

[invite78803cef]

Re,

Il s'agit bien des coordonnées que j'obtiens avec le BFGS.
J'ai marqué dans mon précédent post (300.000 , 131.250 , 148.039) comme coordonnées mais il s'agit bien de (300.000 , 131.250 , 348.039).
La possibilité de résoudre ce système par par Pythagore n'est pas le sujet, l'objectif étant de résoudre des systèmes plus complexes et de taille plus importantes, avec d'autres types de contraintes (contraintes angulaires par exemple).

La question n'est pas de remettre en cause le BFGS puisqu'il semble bien fonctionner (je vais le tester sur des cas plus complexes), mais plutôt de comparer ses performances à d'autres méthodes.

Voici un document intéressant concernant l'utilisation du BFGS pour la résolution de contraintes géométriques et qui m'a permis de venir à bout de mon problème, si cela vous intéresse (pages 2 et 3): http://scholar.google.fr/scholar_url...OYQgAMIKCgAMAA

[SULREN]

Re,
Tel qu’il est posé :
- Espace à 2 dimensions
- Coordonnées de P1 imposées
- Direction de P2 imposée
- Distances entre points imposées,
le problème a bien deux solutions :

P1 (x=100; y=100)
P2 (x=300; y=100)
P3 (x=131,25; y= 348,039185)
Et :
P1 (x=100; y=100)
P2 (x=300; y=100)
P3 (x=131,25; y= -148,039185)

Dans l’espace à 3 dimensions P3 serait sur un cercle bien sûr…..de quoi « puzzler » quelque peu l’algorithme.

Ma méthode a trouvé les deux solutions mais j’ai dû faire 4 passes pour converger à 0,02 près sur les coordonnées. De plus ce n'est pas une méthode mathématique et la comparaison mérite plus de se faire entre BFGS et autre chose.

En tous cas BFGS donne satisfaction.....avec peut-être ce petit doute de tomber sur un minimum local?

Merci pour votre indication concernant GRG que je vais essayer de comprendre.

[SULREN]

Précision: "direction orientée de P2 imposée"

car sinon on trouve aussi bien sûr les solutions symétriques par rapport à la parallèle à Y en P1

[SULREN]

Bonsoir,

LLS a dit :

Votre méthode "brutale" (j'aime bien le terme !) fonctionnerait-elle pour ce type de système d'équations ?
Et pour des systèmes dont le nombre d'équations diffère du nombre d'inconnues (problèmes géométriques sous-contraints ou sur-contraints) ?

A travers les qualificatifs peu flatteurs que je lui ai attribué, vous avec vu qu’il s’agissait d’une méthode dite communément « force brute », et donc qui n’a rien de mathématique. Sur un forum comme celui-ci elle ne mérite pas mieux et elle n’a peut-être même pas droit de cité. D’ici à ce que j’en sois aussi banni, il n’y a qu’un pas……
Mais en réalité j’ai de l’affection pour « cette bidouille », car elle m’a souvent bien aidé, y compris dans d’autres problèmes que la résolution d’équations. De plus, avec un peu d’astuce dans l’analyse et d’optimisation dans le codage on peut la rendre moins « bourrine » et plus rapide en exécution.

Elle résout très bien le type d’équations que vous avez posées, sans rater de solutions et en s’accommodant du problème de l’écart entre le nombre des équations et celui des inconnues (elle ne comporte pas de jacobienne à inverser )

Cependant, dans le cas d’un système sous-contraint, la multiplicité des solutions due au nombre élevé de degrés de liberté peut faire qu’on s’égare. Par exemple, si on étend votre problème à l’espace à 3 dimensions, sans ajouter de contraintes à celles que vous aviez énoncées, le point P3 peut se trouver sur deux cercles.
En ne voyant que les équations du système, sans connaître du tout le problème source, on peut ne pas réaliser qu’on a un, ou deux, lieux de solutions et se perdre.

CONCERNANT LES EQUATIONS DONT IL EST QUESTION CI-DESSUS :
Après les avoir rentrées dans mon programme je n’ai eu :
- qu’à définir la plage à balayer par chacune des 3 inconnues
- rentrer le pas de progression voulu pour chacune des inconnues
- rentrer le seuil de mon test de détection de « proximité de solution ».
- et à lancer le programme.

Avec x1, x2 et x3 allant chacune de -500 à +500
Avec un pas de progression de 1 pour x1, x2 et x3 (donc 1000 pas par variable)

Le programme a effectué 1 milliards d’itérations, en 4 minutes 50 secondes de calcul et il m’a sorti un tableau comportant 1091 « proximités de solutions ».
Puis il a enclenché automatiquement un re-balayage à « plage » et à « pas fin », préprogrammés une fois pour toutes, autour de chacun de ces 1091 cas.
L’exécution dure 3 ou 4 secondes, pour sortir un tableau concentré de 60 solutions les plus précises.

J’ai constaté qu’elles tournaient toutes autour des mêmes valeurs, dont les 4 plus précises sont :

Copier-coller de lignes du fichier texte généré automatiquement par le programme :

143 ; 299.555541992188 ; 131.555557250977 ; -148.444442749023 ; 449.333343505859 ; 20
149 ; 299.555541992188 ; 131.555557250977 ; 348.555541992188 ; 457.061737060547 ; 20
396 ; -99.444442749023 ; 68.555557250977 ; -148.444442749023 ; 486.666656494141 ; 20
402 ; -99.444442749023 ; 68.555557250977 ; 348.555541992188 ; 494.395050048828 ; 20

En partant de la gauche :
1er nombre : numéro d’ordre dans le tableau
2eme nombre : valeur de x1
3eme nombre : valeur de x2
4eme nombre : valeur de x3
5eme nombre : indice de précision de la solution
6eme nombre : statut de la ligne (information à mon usage)

On a bien, de façon certes imprécise, les 4 solutions de notre système à résoudre. Il faut maintenant les explorer finement en une ou deux passes, dans le micro-espace qui les entoure, selon un pas et une plage que je devrai définir cette fois-ci (car ce n'est pas pré-programmé), en vue d’amener l’indice de précision à 10^-5 environ au lieu de 449,33 ou 494,39.

Désolé pour la longueur du message.