Optimisation sous contrainte

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Jake45

Bonjour,

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

je cherche à trouver le meilleur $X$ (matrice de réels $n \times k$) tel que :

$AX=B$

(ou encore min_X ||B-AX||^2 )

les matrices $A$ ($n \times m$) et $B$ ($k \times m$) sont connues.

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

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

$Ax_i=b_i$
(ou encore min_x_i ||b_i-Ax_i||^2 )

Par suite, regarder la meilleure solution entre $x_i=(0,0,...,0)$ et $x_i=(1,1,...,1)$ puis recommencer ce procédé itérativement entre le meilleur des $x_i$ précédent et le milieu entre les deux $x_i$, 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!


Posted by: Jake45

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 !


Posted by: Alpha

Citation:
Posté par Jake45
Un jour je serai expert je l'espère !


Tu l'expères

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


Posted by: Jake45

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 ?


Posted by: totor

Citation:
Posté par Jake45
Bonjour,

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

je cherche à trouver le meilleur $X$ (matrice de réels $n \times k$) tel que :

$AX=B$

(ou encore min_X ||B-AX||^2 )

les matrices $A$ ($n \times m$) et $B$ ($k \times m$) sont connues.

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

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

$Ax_i=b_i$
(ou encore min_x_i ||b_i-Ax_i||^2 )

Par suite, regarder la meilleure solution entre $x_i=(0,0,...,0)$ et $x_i=(1,1,...,1)$ puis recommencer ce procédé itérativement entre le meilleur des $x_i$ précédent et le milieu entre les deux $x_i$, 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 ?


Posted by: Jake45

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


Posted by: totor

Citation:
Posté par Jake45
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


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


Posted by: Jake45

Citation:
Posté par totor
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
Citation:
Posté par totor

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
Citation:
Posté par totor
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










-