Q0-Matrix

In der Mathematik ist ein -Matrix ist eine echte quadratische Matrix bestimmte Eigenschaften Bereitstellen lineare Komplementarität Probleme . Dies sind diejenigen, die sicherstellen, dass eine Lösung existiert, sobald das Problem durchführbar ist. ${\ mathbf {Q_ {0}}}$

Definitionen

Einige Notationen

Für einen Vektor bedeutet die Notation , dass alle Komponenten des Vektors positiv sind. $v \ in \ mathbb {R} ^ {n}$ $v \ geqslant 0$ $v_ {i}$

Wir bezeichnen die positive Orthante von . $\ mathbb {R} _ {+} ^ {n}: = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0 \}$ $\ mathbb {R} ^ {n}$

Wenn es sich um eine Ordnungsmatrix handelt , bezeichnen wir das Bild von by ; es ist ein polyedrischer Kegel (daher ein geschlossener). $BEIM$ $nicht$ ${\ displaystyle A (\ mathbb {R} _ {+} ^ {n}): = \ {Ax: x \ geqslant 0 \}}$ $\ mathbb {R} _ {+} ^ {n}$ $BEIM$

Komplementaritätsproblem

Bei einer quadratischen reellen Matrix und ein Vektor , ein lineares Komplementarität Problem besteht darin , einen Vektor zu finden , dass eine solche , und die , die in abgekürzter Weise geschrieben werden , wie folgt: $M \ in \ mathbb {R} ^ {{n \ times n}}$ $q \ in \ mathbb {R} ^ {n}$ $x \ in \ mathbb {R} ^ {n}$ $x \ geqslant 0$ $Mx + q \ geqslant 0$ $x ^ {\! \ top} (Mx + q) = 0$

$\ mbox {CL} (M, q): \ qquad 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.$

Ein Punkt, der überprüft und als für das Problem und die Menge zulässig gilt $x$ $x \ geqslant 0$ $Mx + q \ geqslant 0$ ${\ mbox {CL}} (M, q)$

${\ mbox {Adm}} (M, q): = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0, ~ Mx + q \ geqslant 0 \}$

wird die zulässige Menge dieses Problems genannt. Das Problem wird gesagt, dass machbar allerdings . ${\ mbox {CL}} (M, q)$ ${\ mbox {Adm}} (M, q) \ neq \ varnothing$

Q0-Matrix

Zum Beispiel stellen wir die beiden folgenden Kegel vor $M \ in \ mathbb {R} ^ {{n \ times n}}$ $\ mathbb {R} ^ {n}$

${\ displaystyle {\ begin {array} {rcl} Q_ {R} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {ist machbar}} \}, \\ Q_ {S} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {hat eine Lösung}} \}. \ end {array}}}$

Offensichtlich ohne notwendigerweise Gleichheit zu haben (dies motiviert die Einführung des Begriffs -matrix). Der Kegel ist polyedrisch konvex, weil er als Summe zweier polyedrischer konvexer Kegel geschrieben ist: ${\ displaystyle Q_ {S} (M) \ Teilmenge Q_ {R} (M)}$ ${\ mathbf {Q_ {0}}}$ ${\ displaystyle Q_ {R} (M)}$

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

Im Gegenteil, ist nicht unbedingt konvex. In Wirklichkeit zeigen wir , dass eine Vereinigung von polyedrischen konvexen Kegel (disjoint unabhängig , wenn und nur wenn ist in Spalte ausreichend ): ${\ displaystyle Q_ {S} (M)}$ ${\ displaystyle Q_ {S} (M)}$ $q$ $M.$

{\ displaystyle Q_ {S} (M) = \ displaystyle \ bigcup _ {I \ subset \ {1, \ ldots, n \}} \, K_ {I} (\ mathbb {R} _ {+} ^ {n })}

Wo ist die Matrix, deren Spalten gegeben sind durch ${\ displaystyle K_ {I}}$

${\ displaystyle (K_ {I}) ^ {I} = - M ^ {I} \ qquad {\ mbox {et}} \ qquad (K_ {I}) ^ {I ^ {c}} = I ^ {I. ^ {c}}.}$

Wir sehen, dass die zwei Kegel, deren Summe die Summe ist, in enthalten sind ; Sie werden durch Einnahme von und erhalten . Diese Beobachtungen führen zu der folgenden Definition. ${\ displaystyle Q_ {R} (M)}$ ${\ displaystyle Q_ {S} (M)}$ ${\ displaystyle I = \ varnothing}$ ${\ displaystyle I = \ {1, \ ldots, n \}}$

Q0-Matrix - Wir sagen , dass eine Matrix eine ist -Matrix , wenn sie erfüllt eine der folgenden äquivalenten Bedingungen: $M \ in \ mathbb {R} ^ {{n \ times n}}$ ${\ mathbf {Q_ {0}}}$

Das Problem hat eine Lösung, wenn es machbar ist. $\ operatorname {CL} (M, q)$
${\ displaystyle Q_ {S} (M) = Q_ {R} (M)}$ ,
${\ displaystyle Q_ {S} (M)}$ ist konvex.

Wir bezeichnen die Menge der Matrizen. ${\ mathbf {Q_ {0}}}$ ${\ mathbf {Q_ {0}}}$

Anhänge

Anmerkungen

Nach Cottle, Pang und Venkateswaran (1989) wurden Zapfen von Samelson, Thrall und Wesler (1958) eingeführt und von Murty (1972) im Zusammenhang mit linearen Komplementaritätsproblemen untersucht. ${\ displaystyle K_ {I} (\ mathbb {R} _ {++} ^ {n})}$
(in) H. Samelson, RM Thrall, Wesler O. (1958). Ein Partitionssatz für den euklidischen n-Raum. Proceedings of the American Mathematical Society , 9, 805–807.
(en) KG Murty (1972). Über die Anzahl der Lösungen für das Komplementaritätsproblem und die übergreifenden Eigenschaften von Komplementaritätskegeln. Lineare Algebra und ihre Anwendungen , 5, 65–108.
(in) RW Cottle, JS Pang, V. Venkateswaran (1989). Ausreichende Matrizen und das Problem der linearen Komplementarität. Lineare Algebra und ihre Anwendungen , 114, 231–249. doi

Zum Thema passende Artikel

Literaturverzeichnis

(en) RW Cottle, J.-S. Pang, RE Stone (2009). Das lineare Komplementaritätsproblem . Klassiker der Angewandten Mathematik 60. SIAM, Philadelphia, PA, USA.