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



+ Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 15 sur 25

Optimisation avec BFGS

  1. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Optimisation avec BFGS

    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(x1-1)- e(-x2+1)+(x1-x2)2

    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 x1 et x2. Le problème est que ce ne sont pas les bonnes !

    Voici les résultats des valeurs x1 et x2 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

    -----

     


    • Publicité



  2. SULREN

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

    Re : Optimisation avec BFGS

    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é.
     

  3. SULREN

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

    Re : Optimisation avec BFGS

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

  4. SULREN

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

    Re : Optimisation avec BFGS

    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 (x2+1)
     

  5. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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-x2+1 - 2x1 + 2x2.

    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
     


    • Publicité



  6. SULREN

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

    Re : Optimisation avec BFGS

    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).
    Dernière modification par SULREN ; 15/08/2017 à 22h19.
     

  7. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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
     

  8. SULREN

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

    Re : Optimisation avec BFGS

    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
     

  9. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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(x1-1)+ e(-x2+1)+(x1-x2)2

    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 x1 et x2 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 (X1 = 0,796 et X2 = 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 ?
     

  10. JPL

    Date d'inscription
    septembre 2003
    Messages
    67 815

    Re : Optimisation avec BFGS

    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.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac
     

  11. SULREN

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

    Re : Optimisation avec BFGS

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

  12. SULREN

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

    Re : Optimisation avec BFGS

    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.
     

  13. LLS

    Date d'inscription
    août 2017
    Messages
    9

    Re : Optimisation avec BFGS

    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 x1 et x2 les valeurs qui permettent de résoudre l'équation:

    e(x1-1) + e(-x2+1) + (x1-x2)2 = 0

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

  14. SULREN

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

    Re : Optimisation avec BFGS

    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.
    Dernière modification par SULREN ; 17/08/2017 à 00h59.
     

  15. SULREN

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

    Re : Optimisation avec BFGS

    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é ?
     


    • 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