Q0-matice

V matematiky , je -matrix je skutečný čtvercová matice poskytuje konkrétní vlastnosti lineárních komplementaritu problémů . To jsou ty, které zajišťují existenci řešení, jakmile je problém proveditelný. Q0{\ displaystyle \ mathbf {Q_ {0}}}

Definice

Některé notace

Pro vektor znamená notace, že všechny složky vektoru jsou kladné. proti∈Rne{\ displaystyle v \ in \ mathbb {R} ^ {n}}proti⩾0{\ displaystyle v \ geqslant 0}protii{\ displaystyle v_ {i}}

Označíme na pozitivní orthant o . R+ne: ={X∈Rne:X⩾0}{\ displaystyle \ mathbb {R} _ {+} ^ {n}: = \ {x \ v \ mathbb {R} ^ {n}: x \ geqslant 0 \}}Rne{\ displaystyle \ mathbb {R} ^ {n}}

Pokud je matice objednávky , označujeme obraz o  ; je to polyedrický kužel (tedy uzavřený). NA{\ displaystyle A}ne{\ displaystyle n}NA(R+ne): ={NAX:X⩾0}{\ displaystyle A (\ mathbb {R} _ {+} ^ {n}): = \ {Axe: x \ geqslant 0 \}}R+ne{\ displaystyle \ mathbb {R} _ {+} ^ {n}}NA{\ displaystyle A}

Problém komplementarity

Vzhledem k tomu, čtvercovou skutečnou matici a vektor , je lineární komplementarita problém spočívá v nalezení vektoru tak, že , a , který je zapsán ve zkrácené způsobem takto: M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}q∈Rne{\ displaystyle q \ in \ mathbb {R} ^ {n}}X∈Rne{\ 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.}

Bod ověřující a říká se, že je přípustný pro problém a soubor 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)}

Admirál(M,q): ={X∈Rne:X⩾0, MX+q⩾0}{\ displaystyle {\ mbox {Adm}} (M, q): = \ {x \ v \ mathbb {R} ^ {n}: x \ geqslant 0, ~ Mx + q \ geqslant 0 \}}

se nazývá přípustná množina tohoto problému. Problém je prý možné, ačkoli . CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}Admirál(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}

Q0-matice

Pro představujeme dva kužely z následujících možností M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}Rne{\ displaystyle \ mathbb {R} ^ {n}}

QR(M): ={q∈Rne:CL⁡(M,q) je dosažitelný},QS(M): ={q∈Rne:CL⁡(M,q) má řešení}.{\ displaystyle {\ begin {array} {rcl} Q_ {R} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {je proveditelné}} \}, \\ Q_ {S} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {má řešení}} \}. \ end {pole}}}

Je zřejmé , že to nemusí nutně mít rovnost (právě to motivuje k zavedení pojmu -matice). Kužel je mnohostěnný konvexní, protože to je psáno jako součet dvou mnohostěnný konvexní kužely: QS(M)⊂QR(M){\ displaystyle Q_ {S} (M) \ podmnožina Q_ {R} (M)}Q0{\ displaystyle \ mathbf {Q_ {0}}} QR(M){\ displaystyle Q_ {R} (M)}

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

Naopak nemusí být nutně konvexní. Ve skutečnosti ukážeme, že jde o spojení polyedrických konvexních kuželů (disjunktní bez ohledu na to, zda a pouze pokud je ve sloupci dostačující ): QS(M){\ displaystyle Q_ {S} (M)}QS(M){\ displaystyle Q_ {S} (M)}q{\ displaystyle q}M{\ displaystyle M}

QS(M)=⋃Já⊂{1,...,ne}K.Já(R+ne){\ displaystyle Q_ {S} (M) = \ displaystyle \ bigcup _ {I \ podmnožina \ {1, \ ldots, n \}} \, K_ {I} (\ mathbb {R} _ {+} ^ {n })},

kde je matice, jejíž sloupce jsou dány K.Já{\ displaystyle K_ {I}}

(K.Já)Já=-MJáa(K.Já)Jávs.=JáJávs..{\ displaystyle (K_ {I}) ^ {I} = - M ^ {I} \ qquad {\ mbox {et}} \ qquad (K_ {I}) ^ {I ^ {c}} = I ^ {I ^ {c}}.}

Vidíme, že dva kužele, jejichž součet je obsažen v  ; získávají se užíváním a . Tato pozorování vedou k následující definici. QR(M){\ displaystyle Q_ {R} (M)}QS(M){\ displaystyle Q_ {S} (M)}Já=∅{\ displaystyle I = \ varnothing}Já={1,...,ne}{\ displaystyle I = \ {1, \ ldots, n \}}

Q0-matice  -  Říkáme, že matice je -matice, pokud splňuje jednu z následujících ekvivalentních podmínek: M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}Q0{\ displaystyle \ mathbf {Q_ {0}}}

1. problém má řešení, pokud je to proveditelné,CL⁡(M,q){\ displaystyle \ operatorname {CL} (M, q)}
2. QS(M)=QR(M){\ displaystyle Q_ {S} (M) = Q_ {R} (M)},
3. QS(M){\ displaystyle Q_ {S} (M)} je konvexní.

Označíme množinu -matic. Q0{\ displaystyle \ mathbf {Q_ {0}}}Q0{\ displaystyle \ mathbf {Q_ {0}}}

Dodatky

Poznámky

1. Podle Cottle, Pang a Venkateswaran (1989), šišky představili Samelson, Thrall a Wesler (1958) a Murty (1972) je studoval v kontextu problémů lineární komplementarity.K.Já(R++ne){\ displaystyle K_ {I} (\ mathbb {R} _ {++} ^ {n})}
2. (in) H. Samelson, RM Thrall, Wesler O. (1958). Věta o rozdělení pro euklidovský n-prostor. Proceedings of the American Mathematical Society , 9, 805–807.
3. (en) KG Murty (1972). O počtu řešení problému komplementarity a vlastnostech komplementárních kuželů. Lineární algebra a její aplikace , 5, 65–108.
4. (in) RW Cottle, JS Pang, V. Venkateswaran (1989). Dostatečné matice a problém lineární komplementarity. Lineární algebra a její aplikace , 114, 231–249. doi

Související články

• Lineární komplementarita
• P-matice

Bibliografie

• (en) RW Cottle, J.-S. Pang, RE Stone (2009). Problém lineární komplementarity . Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.

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