Méthode des moindres carrés : algo maths

Voir le sujet précédent Voir le sujet suivant Aller en bas

Méthode des moindres carrés : algo maths

Message par farhat le Ven 6 Fév - 13:53

Bonjour à tous,



Je dois trouver une approximation du vecteur X colonne à 60 éléments qui satisfasse au mieux (dans le sens des moindres carrés) :

(Obsi) = (aij)*(xj) i allant de 0 à 47,j allant de 0 à 60

Où les Obsi et aij sont connus.

Ce problème correspond à une régression linéaire avec les Xi comme paramètres d’un modèle où Obs serait la variable à expliquer et les aij des réalisations de variables explicatives. Sauf que la contrainte de positivité des paramètres vient tout gâcher.

Mes idées :

1- Faire une minimisation de la fonction des moindres carrés des écarts entre Obs et SOMME (aijXi)… : cf. http://fr.wikipedia.org/wiki/M%C3%A9thode_des_moindres_carr%C3%A9s

J’ai fait un algorithme qui suit les étapes de la méthode des moindres carrés.

Avec un exemple avec 6 variables (au lieu de 60)

Ça marche plus tôt bien mais pas avec 60 variables.

2- J’ai décidé d’utiliser des librairies java très pointues.

Exemple :

http://www.ee.ucl.ac.uk/~mflanaga/java/Regression.html

idem ça marche bien avec 6 variables mais avec 60 variables problème du nombre itération.

3- J’ai utilisé un Modeling Language GNU MathProg.

c'est une minimisation linéaire (alors que ici c'est une fonction quadratique)

donc des résultats par très bon)

Tous m’ont données des résultats mais pas loin de ce que donne une feuille Excel (en utilisant un solveur). Et avec des erreur de convergence.

Quelqu'un aurait un code java ou un algo ou n'importe quel document qui pourrait me permettre de résoudre en algo ou java :

un problème d’optimisation avec contraintes d’égalité

min f(x) avec x appartient à Rn

sous les contraintes

h(x) = 0 et x>=0

f non-lineaire,h lineaire.

et/ou une explication mathématique de ce problème m'aiderai à faire un algo.

Merci d'avance.

farhat
Entier Naturel
Entier Naturel

Féminin
Nombre de messages : 2
Localisation : paris
Réputation : 0
Points : 3209
Date d'inscription : 06/02/2009

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Méthode des moindres carrés : algo maths

Message par Napoléon le Ven 6 Fév - 15:18

Bienvenue dans le forum.
Il s'agit bien d'un problème d'optimisation continue, non linéaire et à contraintes linéaires avec la particularité d'un nombre de variables assez élevé (60).

Il y a plusieurs travaux de recherche qui ont abordé cette classe de problèmes. En général, on ne peut pas trouver la solution optimale. On se contente de la solution approximative donnée par la plupart des algorithmes.

... à suivre.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Méthode des moindres carrés : algo maths

Message par farhat le Ven 6 Fév - 17:09

Merci,
tu as bien saisi le problème.
Vous préconisez quoi d'utiliser des logiciels de calcul comme Matlab ou autre?
Là j'essaye de faire un programme en Scilab avec la méthode optim/dyoptim et j'avoue je viens de me lancer dans ce type de logiciel...
si quelqu'un à un exemple simple en Scilab sur l'optimisation.
Merci.

farhat
Entier Naturel
Entier Naturel

Féminin
Nombre de messages : 2
Localisation : paris
Réputation : 0
Points : 3209
Date d'inscription : 06/02/2009

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Méthode des moindres carrés : algo maths

Message par Napoléon le Sam 7 Fév - 0:16

Je t'invite à lire ce document à prpos des Multiplicateurs de Lagrange:
http://fr.wikipedia.org/wiki/Multiplicateur_de_Lagrange

Il s'agit d'une méthode conçue pour optimiser des fonctions continues à des contraintes d'égalité.

Qu'est-ce que tu en penses ?


_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Méthode des moindres carrés : algo maths

Message par Alkhawarizmi le Lun 11 Mai - 12:42

farhat a écrit:Bonjour à tous,



Je dois trouver une approximation du vecteur X colonne à 60 éléments qui satisfasse au mieux (dans le sens des moindres carrés) :

(Obsi) = (aij)*(xj) i allant de 0 à 47,j allant de 0 à 60

Où les Obsi et aij sont connus.

Ce problème correspond à une régression linéaire avec les Xi comme paramètres d’un modèle où Obs serait la variable à expliquer et les aij des réalisations de variables explicatives. Sauf que la contrainte de positivité des paramètres vient tout gâcher.

Mes idées :

1- Faire une minimisation de la fonction des moindres carrés des écarts entre Obs et SOMME (aijXi)… : cf. http://fr.wikipedia.org/wiki/M%C3%A9thode_des_moindres_carr%C3%A9s

J’ai fait un algorithme qui suit les étapes de la méthode des moindres carrés.

Avec un exemple avec 6 variables (au lieu de 60)

Ça marche plus tôt bien mais pas avec 60 variables.

2- J’ai décidé d’utiliser des librairies java très pointues.

Exemple :

http://www.ee.ucl.ac.uk/~mflanaga/java/Regression.html

idem ça marche bien avec 6 variables mais avec 60 variables problème du nombre itération.

3- J’ai utilisé un Modeling Language GNU MathProg.

c'est une minimisation linéaire (alors que ici c'est une fonction quadratique)

donc des résultats par très bon)

Tous m’ont données des résultats mais pas loin de ce que donne une feuille Excel (en utilisant un solveur). Et avec des erreur de convergence.

Quelqu'un aurait un code java ou un algo ou n'importe quel document qui pourrait me permettre de résoudre en algo ou java :

un problème d’optimisation avec contraintes d’égalité

min f(x) avec x appartient à Rn

sous les contraintes

h(x) = 0 et x>=0

f non-lineaire,h lineaire.

et/ou une explication mathématique de ce problème m'aiderai à faire un algo.

Merci d'avance.

As tu deja essaye de reecrite tom probeleme en tant que "geometric-program" ( Si les aij sont positifs --- Sinon en tant que mixed linear-geometric program).


La fonction a minimiser doit etre lineaire avec coefficients positifs --- donc tu introduis des ti qui sont (Xi- ci)^2 et puis tu rajoute les containtes que (Xi - ci)^2 <= ti.
Pou la programmation geometique tu reecris ca bien sur en Xi^2 + ci^2 <= ti + 2ciXi (si ci >=0) ou Xi^2 -2ciXi + ci^2 <= ti (si ci < 0).

hope it helps.
Al.

Alkhawarizmi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 13
Localisation : sewf
Réputation : 9
Points : 3143
Date d'inscription : 06/05/2009

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Méthode des moindres carrés : algo maths

Message par Napoléon le Mar 12 Mai - 1:05

Il faudrait expliquer ou donner le principe des termes cités :

- "geometric-program"
- "linear geometric-program"

Des liens wikipédia feront l'affaire.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Méthode des moindres carrés : algo maths

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut


 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum