Résolution système linéaire avec contraintes

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,

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

Citation:

---

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.

Citation:

---

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

Citation:

---

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

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.

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,