Optimisation sous contrainte

par **Jake45** » 25 Juil 2007, 13:48

Bonjour,

J'ai besoin d'aide pour résoudre le problème suivant :

je cherche à trouver le meilleur

(matrice de réels

) tel que :

(ou encore

)

les matrices

(

) et

(

) sont connues.

De plus, et c'est la la difficulté, je voudrais que toutes les valeurs de

soient comprises entre 0 et 1.

ce que je pensai faire, c'est -comme je peut traiter chercher les lignes de

séparemment- chercher les meilleurs

tels que

(ou encore

)

Par suite, regarder la meilleure solution entre

et

puis recommencer ce procédé itérativement entre le meilleur des

précédent et le milieu entre les deux

, i.e, une recherche locale par dichotomie. Le problème c'est que j'aimerais pas trop avoir un vecteur solution uniforme avec les même valeurs car je ne pourrai rien en tirer.

Je dois conserver l'approche numérique plutôt qu'analytique car ce problème doit etre implementé dans un langage de programmation (R pour les connaisseurs)

Merci d'avance pour vos suggestions!

par **Jake45** » 26 Juil 2007, 10:35

personne ne peut m'aider? :((

je sais qu'il éxiste plusieurs techniques tels que :

- simplex
- point intérieurs
- descente du gradient
- méthodes de tir

mais j'ai un peu de mal a les assimiler et j'en aurais encore plus à les mettre en oeuvre. Si quelqu'un connait bien une de ces méthodes je le remercie d'avance de bien vouloir m'aiguiller.

Un jour je serai expert je l'espère !

par **Alpha** » 26 Juil 2007, 10:39

Jake45 a écrit:Un jour je serai expert je l'espère !

Tu l'expères :ptdr:

J'expère que quelqu'un saura te répondre.

par **Jake45** » 26 Juil 2007, 10:49

au moins cette jolie phrase aura suscité une vive réaction!

pas de suggestion pour résoudre cette optimisation de moindres carrés bornés/contraints ?

par **Alpha** » 26 Juil 2007, 10:51

Qu'entends-tu par "le meilleur X" ?

par **Jake45** » 26 Juil 2007, 10:55

je cherche le meilleur X tel que ||B - AX||² est minimal

par **Alpha** » 26 Juil 2007, 10:58

Et c'est quoi, M?

par **Jake45** » 26 Juil 2007, 11:01

oula! j'ai pas assez dormi!

OK j'ai confondu mes notations

je veux trouver le meilleur X tel que ||B-AX||² est minimal.

désolé ^^

par **Alpha** » 26 Juil 2007, 11:03

Ok, ce que je te propose c'est de rajouter cette précision dans ton message d'origine, et ensuite je supprimerai les 2 derniers messages. Comme ça ça sera plus clair pour ceux qui vont tomber sur cette discussion. Précise aussi ce que tu entends par "les meilleurs xi", j'imagine que c'est ceux pour lesquels X est le meilleur.

Personnellement, j'ai pas d'idée pour répondre à ton problème, mais si tu éclaircis ces quelques points, tu auras plus de chances pour que quelqu'un te réponde.

par **Jake45** » 26 Juil 2007, 11:13

ok tu pe supprimer

par **totor** » 26 Juil 2007, 11:35

Jake45 a écrit:Bonjour,

J'ai besoin d'aide pour résoudre le problème suivant :

je cherche à trouver le meilleur (matrice de réels ) tel que :

(ou encore )

les matrices () et () sont connues.

De plus, et c'est la la difficulté, je voudrais que toutes les valeurs de soient comprises entre 0 et 1.

ce que je pensai faire, c'est -comme je peut traiter chercher les lignes de séparemment- chercher les meilleurs tels que

(ou encore )

Par suite, regarder la meilleure solution entre et puis recommencer ce procédé itérativement entre le meilleur des précédent et le milieu entre les deux , i.e, une recherche locale par dichotomie. Le problème c'est que j'aimerais pas trop avoir un vecteur solution uniforme avec les même valeurs car je ne pourrai rien en tirer.

Je dois conserver l'approche numérique plutôt qu'analytique car ce problème doit etre implementé dans un langage de programmation (R pour les connaisseurs)

Merci d'avance pour vos suggestions!

salut, est ce que n > m ou bien ?

par **Jake45** » 26 Juil 2007, 11:38

ca dépend il n'ya pas d'obligation, je peux rencontrer les cas > et < et =

Dans mon application de test, n>>m mais j'en ai une aussi ou m>>n

par **totor** » 26 Juil 2007, 11:40

Jake45 a écrit:ca dépend il n'ya pas d'obligation, je peux rencontrer les cas > et >m mais j'en ai une aussi ou m>>n

dans ce cas je pense que tu voudrai faire ca ?
http://www.netlib.org/lapack/lug/node27.html

tiens, ici c'est bien expliqué :
http://icl.cs.utk.edu/lapack-forum/viewtopic.php?p=497&

je pense qu'il faut calculer le pseudo inverse

par **Jake45** » 26 Juil 2007, 12:21

totor a écrit:dans ce cas je pense que tu voudrai faire ca ?
http://www.netlib.org/lapack/lug/node27.html

c'est la version non contraint, c'est facile à faire

totor a écrit:tiens, ici c'est bien expliqué :
http://icl.cs.utk.edu/lapack-forum/viewtopic.php?p=497&

je connais ce package LAPACK mais il n'aborde pas les contraintes de bornes pour la solution du probleme de minimisation de moindres carrés linéaires

totor a écrit:je pense qu'il faut calculer le pseudo inverse

effectivement il y'a un calcul de pseudo inverse, mais ca c'est facile

ba si tu veux j'ai aucuns problèmes pour résoudre AX=B si il n'y a aucunes contraintes sur X. En effet même si A n'est pas carrée. On peut quand même résoudre le système en effectuant une décomposition QR de A mais ce qui me bloques surtout c'est le coté contraint sur X chaque valeur de X doit être entre 0 et 1. Donc résoudre un linear least square problem n'est pas suffisant.

Je me dis de plus en plus que je trouverai pas une méthode raisonnable pour trouver le minimum global de ||B-AX||² mais que je dois me concentrer sur des heuristiques astucieuses pour trouver un "bon minimum local". Je pense que je vais me diriger vers une descente de gradient en attendant mais je sais pas ce que ca va donner...

En fait ce que je cherche c'est un minimum mais dans un domaine restreint entre la matrice nulle (0) et la matrice (1) sachant qu'il n'ya aucune monotonie a priori et qu'aucune de ces borne n'est a priori un maximum ou un minimum

Optimisation sous contrainte

Optimisation sous contrainte

Qui est en ligne