Discussion :

[Triton972]

Bonsoir,

Tout d'abord, désolé si la question est triviale ou déjà traitée, j'ai cherché sur le forum mais je n'ai pas vraiment trouvé la réponse à mon problème.

Je cherche à résoudre une équation : Ax=B avec A matrice (m,n) (m et n quelconques) et x le vecteur inconnu.

En fonction de m et n, mon système peut être sous-dimensionné ou sur-dimensionné. Les contraintes sont :
- Toutes les (meilleures) solutions doivent être positives ou nulles (Tous les éléments de x doivent être >=0)
- La somme des éléments de x doit être égal à 1.

Je démarre avec OCTAVE et j'aurai souhaité connaitre des pistes ou les fonctions à utiliser pour programmer au mieux la recherche de ces solutions.

Je vous remercie d'avance.
Cordialement,

[FR119492]

Salut!
Je note 3 points importants dans la formulation de ton problème; je commence par le plus simple:

La somme des éléments de x doit être égal à 1

Il te suffit d'ajouter à la matrice A une ligne ne comportement que des 1 et au vecteur B un terme qui vaut aussi 1.

Ax=B avec A matrice (m,n) (m et n quelconques)

Si m<n, il y a en général (mais pas toujours) une infinité de solutions. Si m>n, il n'y a en général pas de solution exacte. Dans un cas comme dans l'autre, je te conseille de voir du côté de la décomposition selon les valeurs singulières (SVD).

Tous les éléments de x doivent être >=0

Alors, ça, c'est plus compliqué. A mon avis, tu devrais satisfaire tout d'abord les deux premières conditions, puis appliquer une méthode itérative qu'il te reste à imaginer.

Jean-Marc Blanc

[Zavonen]

Les contraintes sur les (x_i) signifient simplement que le vecteur x parcourt l'enveloppe convexe des points (1,0,..,0),(0,1,..,0), ...(0,..,0,1).
Tu peux voir ce que cela donne en dimension deux (un segment) ou trois (un triangle).
Maintenant si tu cherches une pseudo-solution à epsilon près tu commences à calculer
||A|| = sup_i,j |a_i,j|
puis tu remarques que si F(X)=AX-B F est lipschitzienne de constante ||A|| de sorte que
||X1-X2|| < epsilon/||A||=eta entraîne ||F(X1)-F(X2)||<epsilon.
Il te suffit ensuit de faire une maillage suffisamment fin de l'enveloppe convexe
G_n=(h_1, h_2, .... ,h_n) avec tous les h_i positifs et leur somme valant 1 de telle sorte que la distance d'un G_i au G_j le plus proche est inférieure à eta.
De la sorte tu es sûr que le minimum de F sur l'ensemble FINI des G_i diffère de moins de epsilon du minimum absolu de F sur l'enveloppe convexe.

[Triton972]

Bonjour,

Je vous remercie pour vos réponses. Mais je débute avec OCTAVE et de plus, je ne pratique pas ce "type" de réflexion fréquemment. J'ai donc un peu de difficulté à exploiter vos pistes
Pourriez-vous m'orienter vers des pistes un peu plus "opérationnelles" ?
Merci d'avance.
Cordialement,