Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 16 à 25 sur 25

Optimisation avec BFGS

  1. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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:
    P1y - P2y = 0
    Si je souhaite que mon point P2 se trouve à une distance D de mon point P1, j'aurais une équation de cercle:
    (P2x - P1x)2 + (P2y - P1y)2 - D2 = 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 !

    -----

     


    • Publicité



  2. SULREN

    Date d'inscription
    août 2014
    Localisation
    Proche Toulouse au Nord Ouest
    Âge
    71
    Messages
    281

    Re : Optimisation avec BFGS

    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.
     

  3. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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):

    f1(X)=(x1−100)2+(100−100)2−2002=0
    f2(X)=(x2−x1)2+(x3−100)2−3002=0
    f3(X)=(x2−100)2+(x3−100)2−2502=0

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

    F(X) = f1(X)2 + f2(X)2 + f3(X)2

    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 X0 = (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 X0 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
     

  4. SULREN

    Date d'inscription
    août 2014
    Localisation
    Proche Toulouse au Nord Ouest
    Âge
    71
    Messages
    281

    Re : Optimisation avec BFGS

    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.
    @+
     

  5. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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
     


    • Publicité



  6. SULREN

    Date d'inscription
    août 2014
    Localisation
    Proche Toulouse au Nord Ouest
    Âge
    71
    Messages
    281

    Re : Optimisation avec BFGS

    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.
    Dernière modification par SULREN ; 27/08/2017 à 11h42.
     

  7. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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
     

  8. SULREN

    Date d'inscription
    août 2014
    Localisation
    Proche Toulouse au Nord Ouest
    Âge
    71
    Messages
    281

    Re : Optimisation avec BFGS

    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.
     

  9. SULREN

    Date d'inscription
    août 2014
    Localisation
    Proche Toulouse au Nord Ouest
    Âge
    71
    Messages
    281

    Re : Optimisation avec BFGS

    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
    Dernière modification par SULREN ; 27/08/2017 à 14h35.
     

  10. SULREN

    Date d'inscription
    août 2014
    Localisation
    Proche Toulouse au Nord Ouest
    Âge
    71
    Messages
    281

    Re : Optimisation avec BFGS

    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.
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. optimisation. ( avec dérivé)
    Par akapouchon dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 18/01/2013, 10h34
  2. aide BFGS scilab
    Par jejetfc dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 28/05/2012, 13h32
  3. Optimisation avec contraintes
    Par ichigo01 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 29/04/2012, 22h34
  4. Algorithme BFGS et Gradient conjugué
    Par bbdoll dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 11/02/2011, 18h46
  5. methode BFGS pour MLP?
    Par ixi dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 02/03/2005, 20h12