Q0-matrice

În matematică , o -matrice este o matrice pătrată reală care oferă proprietăți particulare problemelor de complementaritate liniară . Acestea sunt cele care asigură existența unei soluții de îndată ce problema este fezabilă. Î0{\ displaystyle \ mathbf {Q_ {0}}}

Definiții

Unele notații

Pentru un vector , notația înseamnă că toate componentele vectorului sunt pozitive. v∈Rnu{\ displaystyle v \ in \ mathbb {R} ^ {n}}v⩾0{\ displaystyle v \ geqslant 0}veu{\ displaystyle v_ {i}}

Notăm orthant pozitiv al . R+nu: ={X∈Rnu:X⩾0}{\ displaystyle \ mathbb {R} _ {+} ^ {n}: = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0 \}}Rnu{\ displaystyle \ mathbb {R} ^ {n}}

Dacă este o matrice de ordine , denotăm imaginea lui by  ; este un con poliedric (deci unul închis). LA{\ displaystyle A}nu{\ displaystyle n}LA(R+nu): ={LAX:X⩾0}{\ displaystyle A (\ mathbb {R} _ {+} ^ {n}): = \ {Ax: x \ geqslant 0 \}}R+nu{\ displaystyle \ mathbb {R} _ {+} ^ {n}}LA{\ displaystyle A}

Problemă de complementaritate

Având în vedere o matrice pătrată reală și un vector , o problemă de complementaritate liniară constă în găsirea unui vector astfel încât , și , care este scris în formă scurtă după cum urmează: M∈Rnu×nu{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rnu{\ displaystyle q \ in \ mathbb {R} ^ {n}}X∈Rnu{\ displaystyle x \ in \ mathbb {R} ^ {n}}X⩾0{\ displaystyle x \ geqslant 0}MX+q⩾0{\ displaystyle Mx + q \ geqslant 0}X⊤(MX+q)=0{\ displaystyle x ^ {\! \ top} (Mx + q) = 0}

CL(M,q):0⩽X⊥(MX+q)⩾0.{\ displaystyle {\ mbox {CL}} (M, q): \ qquad 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.}

Un punct care verifică și se spune că este admisibil pentru problemă și set X{\ displaystyle x}X⩾0{\ displaystyle x \ geqslant 0}MX+q⩾0{\ displaystyle Mx + q \ geqslant 0}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}

Adm(M,q): ={X∈Rnu:X⩾0, MX+q⩾0}{\ displaystyle {\ mbox {Adm}} (M, q): = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0, ~ Mx + q \ geqslant 0 \}}

se numește setul admisibil al acestei probleme. Se spune că problema este totuși fezabilă . CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}Adm(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}

Q0-matrice

Pentru că, introducem cele două conuri ale următoarelor M∈Rnu×nu{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}Rnu{\ displaystyle \ mathbb {R} ^ {n}}

ÎR(M): ={q∈Rnu:CL⁡(M,q) este realizabil},ÎS(M): ={q∈Rnu:CL⁡(M,q) are o soluție}.{\ displaystyle {\ begin {array} {rcl} Q_ {R} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {este fezabil}} \}, \\ Q_ {S} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {are o soluție}} \}. \ end {array}}}

Evident , fără a avea neapărat egalitate (acesta este motivul introducerii noțiunii de -matrice). Conul este convex poliedrică , deoarece este scris ca suma a două poliedre convexe conuri: ÎS(M)⊂ÎR(M){\ displaystyle Q_ {S} (M) \ subset Q_ {R} (M)}Î0{\ displaystyle \ mathbf {Q_ {0}}} ÎR(M){\ displaystyle Q_ {R} (M)}

ÎR(M)=R+nu-M(R+nu){\ displaystyle Q_ {R} (M) = R _ {+} ^ {n} -M (R _ {+} ^ {n})}.

Dimpotrivă, nu este neapărat convex. În realitate, arătăm că este o uniune de conuri poliedrice convexe (disjunct indiferent dacă și numai dacă este suficient în coloană ): ÎS(M){\ displaystyle Q_ {S} (M)}ÎS(M){\ displaystyle Q_ {S} (M)}q{\ displaystyle q}M{\ displaystyle M}

ÎS(M)=⋃Eu⊂{1,...,nu}KEu(R+nu){\ displaystyle Q_ {S} (M) = \ displaystyle \ bigcup _ {I \ subset \ {1, \ ldots, n \}} \, K_ {I} (\ mathbb {R} _ {+} ^ {n })},

unde este matricea ale cărei coloane sunt date de KEu{\ displaystyle K_ {I}}

(KEu)Eu=-MEuși(KEu)Euvs.=EuEuvs..{\ displaystyle (K_ {I}) ^ {I} = - M ^ {I} \ qquad {\ mbox {et}} \ qquad (K_ {I}) ^ {I ^ {c}} = I ^ {I ^ {c}}.}

Vedem că cele două conuri ale cărora este suma sunt conținute în  ; se obțin prin luarea și . Aceste observații conduc la următoarea definiție. ÎR(M){\ displaystyle Q_ {R} (M)}ÎS(M){\ displaystyle Q_ {S} (M)}Eu=∅{\ displaystyle I = \ varnothing}Eu={1,...,nu}{\ displaystyle I = \ {1, \ ldots, n \}}

Q0-matrice  -  Noi spunem că o matrice este o -matrix în cazul în care se constată că una dintre următoarele condiții echivalente: M∈Rnu×nu{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}Î0{\ displaystyle \ mathbf {Q_ {0}}}

1. problema are o soluție dacă este fezabilă,CL⁡(M,q){\ displaystyle \ operatorname {CL} (M, q)}
2. ÎS(M)=ÎR(M){\ displaystyle Q_ {S} (M) = Q_ {R} (M)},
3. ÎS(M){\ displaystyle Q_ {S} (M)} este convex.

Notăm setul de -matrici. Î0{\ displaystyle \ mathbf {Q_ {0}}}Î0{\ displaystyle \ mathbf {Q_ {0}}}

Anexe

Note

1. Conform lui Cottle, Pang și Venkateswaran (1989), conurile au fost introduse de Samelson, Thrall și Wesler (1958) și au fost studiate în contextul problemelor de complementaritate liniară de Murty (1972).KEu(R++nu){\ displaystyle K_ {I} (\ mathbb {R} _ {++} ^ {n})}
2. (în) H. Samelson, RM Thrall, Wesler O. (1958). O teoremă de partiție pentru spațiul n euclidian. Proceedings of the American Mathematical Society , 9, 805–807.
3. (ro) KG Murty (1972). Cu privire la numărul de soluții la problema complementarității și proprietățile de acoperire ale conurilor de complementaritate. Algebra liniară și aplicațiile sale , 5, 65–108.
4. (în) RW Cottle, JS Pang, V. Venkateswaran (1989). Matrici suficiente și problema complementarității liniare. Algebra liniară și aplicațiile sale , 114, 231–249. doi

Articole similare

• Complementaritatea liniară
• P-matrice

Bibliografie

• (ro) RW Cottle, J.-S. Pang, RE Stone (2009). Problema complementarității liniare . Clasici în matematică aplicată 60. SIAM, Philadelphia, PA, SUA.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">