P-matice

V matematice , je -matrix nebo matice je reálná čtvercová matice , jejíž hlavní nezletilí jsou striktně pozitivní . Někteří autoři kvalifikují tyto matice jako zcela přísně pozitivní . ${\ mathbf {P}}$ ${\ mathbf {P}}$

Tyto -matrices zabývá studiem problémů lineární komplementarity . ${\ mathbf {P}}$

Příbuzný pojem je -matrix . ${\ mathbf {P_ {0}}}$

Zápisy

Všimli jsme si

${\ displaystyle [\! [1, n] \!]: = \ {1, \ ldots, n \}}$ množina prvních celých čísel, $ne$
$u \ cdot v$ produkt Hadamardova ze dvou vektorů a , který je definován pro každou index , $u$ $proti$ ${\ displaystyle (u \ cdot v) _ {i} = u_ {i} v_ {i},}$ $i$
${\ displaystyle M_ {IJ}}$ dílčí matice tvořená jejími prvky s indexy řádků a indexy sloupců . $M$ $Já$ $J$

Definice

Pojem -matice lze definovat různými způsoby, samozřejmě ekvivalentními. ${\ mathbf {P}}$

${\ mathbf {P}}$ -matrix - Říkáme, že skutečná čtvercová matice je -matrix, pokud platí jedna z následujících ekvivalentních vlastností: ${\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}$ ${\ mathbf {P}}$

Všechny hlavní nezletilí ze striktně pozitivní: pro všechny non-prázdné, $M$ $I \ podmnožina \ {1, \ ldots, n \}$ ${\ displaystyle \ det M_ {II}> 0,}$
jakýkoli vyhovující vektor je nula, $x \ in \ mathbb {R} ^ {n}$ ${\ displaystyle x \ cdot (Mx) \ leqslant 0}$
jakéhokoli neprázdné, že skutečné vlastní čísla ze jsou naprosto pozitivní. $I \ podmnožina \ {1, \ ldots, n \}$ ${\ displaystyle M_ {II}}$

Označíme množinu -matric libovolné objednávky. Říkáme -matricity vlastnost matice, ke které patří ${\ mathbf {P}}$ ${\ mathbf {P}}$ ${\ mathbf {P}}$ ${\ displaystyle \ mathbf {P}.}$

Název těchto matic navrhli Fiedler a Pták (1966). Rovnocennost mezi definicemi 1 a 2 je dána Fiedlerem a Ptákem (1962).

Okamžité vlastnosti

Z definice 1 to odvodíme

${\ displaystyle M \ in \ mathbf {P}}$ pokud, a pouze pokud , ${\ displaystyle M ^ {\ top \!} \ in \ mathbf {P}}$
if je symetrický, pak if, a pouze v případě, že je pozitivní určitý , $M$ ${\ displaystyle M \ in \ mathbf {P}}$ $M$
${\ displaystyle \ mathbf {P} \ cap \ mathbb {R} ^ {n \ krát n}}$ je otevřen od . ${\ displaystyle \ mathbb {R} ^ {n \ krát n}}$

Z definice 2 to odvodíme

pokud je kladně definitivní , pak ${\ displaystyle M + M ^ {\! \ nahoru \!}}$ ${\ displaystyle M \ in \ mathbf {P}.}$

Další vlastnosti

Lineární komplementarita

Problém lineární komplementarity spočívá v nalezení vektoru takového, že a V této definici je transponování a nerovnosti je třeba chápat po jednotlivých komponentách. Tento problém je někdy kompaktně zaznamenán následovně ${\ displaystyle x \ geqslant 0,}$ $Mx + q \ geqslant 0$ ${\ displaystyle x ^ {\! \ nahoru \!} (Mx + q) = 0.}$ ${\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n},}$ ${\ displaystyle q \ in \ mathbb {R} ^ {n},}$ ${\ displaystyle x ^ {\! \ nahoru \!}}$ $X$

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

Existence a jedinečnost řešení

Důležitost matic v problémech lineární komplementarity vychází z následujícího výsledku existence a jedinečnosti. ${\ mathbf {P}}$

${\ mathbf {P}}$ -matice a problém lineární komplementarity - U matice jsou ekvivalentní následující vlastnosti: ${\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}$

${\ displaystyle M \ in \ mathbf {P}}$ ,
pro každý vektor má problém lineární komplementarity jedno a pouze jedno řešení. $q \ in \ mathbb {R} ^ {n}$ ${\ displaystyle {\ mbox {CL}} (M, q)}$

Proto pokud existuje vektor takový, že nastane jedna z následujících dvou výlučných situací: ${\ displaystyle M \ notin \ mathbf {P}}$ $q \ in \ mathbb {R} ^ {n}$

buď nemá řešení, ${\ mbox {CL}} (M, q)$
nebo má více než jedno řešení. ${\ mbox {CL}} (M, q)$

Nelze však potvrdit, že pro matici , i symetrickou a nedegenerovanou , existuje vektor takový , že nastává první ze dvou výše uvedených situací. Tak ${\ displaystyle M \ notin \ mathbf {P}}$ $q$

${\ displaystyle M = {\ begin {pmatrix} 1 & 2 \\ 2 & 1 \ end {pmatrix}}}$

není matice, ale problém má řešení cokoli ${\ mathbf {P}}$ ${\ displaystyle {\ mbox {CL}} (M, q)}$ ${\ displaystyle q.}$

Algoritmická charakterizace

Lineární komplementarita nabízí další charakterizaci -matric, pokud jde o vlastnost algoritmu pro řešení těchto problémů, Newton- minův algoritmus . To je dobře definované, když se matice je není degenerovaná . Pro takovou matici a daný vektor lze spojit se sadou indexů , označeným uzlem, což je jedinečné řešení lineárního systému ${\ mathbf {P}}$ $M$ $q$ ${\ displaystyle I \ podmnožina [\! [1, n] \!]}$ ${\ displaystyle x ^ {(I)}}$ $X$

${\ displaystyle x_ {I ^ {c}} = 0 \ qquad {\ mbox {a}} \ qquad (Mx + q) _ {I} = 0.}$

Zaznamenali jsme doplněk v . Stručně řečeno, Newton-minův algoritmus je polohladký Newtonův algoritmus pro řešení lineární rovnice po částech ${\ displaystyle I ^ {c}: = [\! [1, n] \!] \ setminus I}$ $Já$ $[\! [1, n] \!]$

${\ displaystyle \ min (x, Mx + q) = 0,}$

což je ekvivalent problému . Ve verzi, na které záleží na výsledku níže, určuje Newton-minův algoritmus nejprve v aktuálním bodě množinu indexů ${\ mbox {CL}} (M, q)$ $x \ in \ mathbb {R} ^ {n}$

${\ displaystyle I = \ {i \ v [\! [1, n] \!]: x_ {i}> (Mx + q) _ {i} \}}$

a poté vypočítá další iteraci . Máme následující charakterizaci (Věta 4.2 v []). ${\ displaystyle x ^ {+} = x ^ {(I)}}$

${\ mathbf {P}}$ -matice a algoritmus Newton-min - pro nedegenerovanou matici jsou ekvivalentní následující vlastnosti: ${\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}$

${\ displaystyle M \ in \ mathbf {P}}$ ,
Bez ohledu na to , že výše popsaný Newton-minův algoritmus při použití necykluje mezi dvěma uzly . $q$ ${\ mbox {CL}} (M, q)$

Polynomiální časové rozlišení?

Neznáme algoritmus umožňující vyřešit problém v polynomiálním čase , ale někteří navrhli argumenty ve prospěch této možnosti. ${\ mbox {CL}} (M, q)$ ${\ displaystyle M \ in \ mathbf {P}}$

Zkontrolujte P-matici

Ověření, že matice zadaná v je -matice, je problémem s úplnou spoluprací . ${\ displaystyle \ mathbb {Q} ^ {n \ krát n}}$ ${\ mathbf {P}}$

Zřejmým způsobem, jak zkontrolovat P- matricitu dané matice, je výpočet jejích hlavních nezletilých ( test hlavních nezletilých ), což vyžaduje operace. Rump (2003) ukázal, že bez ohledu na to, co je neprázdné, můžeme najít matici takovou a pro jakoukoli neprázdnost a odlišnou od , takže hlavní test menšího nezanedbává žádnou menší. $M$ $2 ^ {n} -1$ ${\ displaystyle O (n ^ {3} \, 2 ^ {n})}$ ${\ displaystyle I \ podmnožina [\! [1, n] \!]}$ $M \ in \ mathbb {R} ^ {{n \ krát n}}$ ${\ displaystyle \ det M_ {II} <0}$ ${\ displaystyle \ det M_ {JJ}> 0}$ ${\ displaystyle J \ podmnožina [\! [1, n] \!]}$ $Já$

Tsatsomeros a Li (2000) navrhli test založený na Schurově doplňku , který snižuje počet operací na . Test stále vyžaduje tento exponenciální počet operací, pokud je maticí P- matice, ale může vyžadovat mnohem méně, pokud , protože k prokázání tohoto nečlenství stačí pouze jedna záporná vedlejší. ${\ displaystyle 7 \, 2 ^ {n}}$ ${\ displaystyle M \ notin \ mathbf {P}}$

Rump (2003) navrhl první test, který k ověření P- matricity nutně nevyžaduje exponenciální počet operací .

Příklady

Cauchy matice je čtvercová matice, jehož skutečný prvek je dán ${\ displaystyle C \ in \ mathbb {R} ^ {n \ krát n}}$ $(i, j)$ ${\ displaystyle \ displaystyle C_ {ij} = {\ frac {1} {a_ {i} + b_ {j}}},}$ kde . Cauchyova matice je -matice, pokud a pokud sekvence a jsou přísně rostoucí. Zejména Hilbertova matice je -matice (je to Cauchyova matice se vším ). ${\ displaystyle a_ {i} + b_ {j} \ neq 0}$ ${\ mathbf {P}}$ ${\ displaystyle a_ {1} + b_ {1}> 0}$ ${\ displaystyle \ {a_ {i} \}}$ ${\ displaystyle \ {b_ {j} \}}$ ${\ mathbf {P}}$ ${\ displaystyle a_ {i} = b_ {i} = i-1/2}$ $i \ in [\! [1, n] \!]$
Zvažte cirkulující matici definovanouM∈Rne×ne,{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n},} ${\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n},}$ ne⩾2,{\ displaystyle n \ geqslant 2,} ${\ displaystyle n \ geqslant 2,}$ M=(1αα ⋱ ⋱ 1α1){\ displaystyle M = {\ begin {pmatrix} 1 &&& \ alpha \\\ alpha & ~~~ \ ddots ~~~ && \\ & ~~~ \ ddots ~~~ & 1 & \\ && \ alpha & 1 \ end {pmatrix}}} ${\ displaystyle M = {\ begin {pmatrix} 1 &&& \ alpha \\\ alpha & ~~~ \ ddots ~~~ && \\ & ~~~ \ ddots ~~~ & 1 & \\ && \ alpha & 1 \ end {pmatrix}}}$ nebo přesněji tím, zda , pokud a pokud ne. TakMij=1{\ displaystyle M_ {ij} = 1} ${\ displaystyle M_ {ij} = 1}$ i=j{\ displaystyle i = j} $i = j$ Mij=α{\ displaystyle M_ {ij} = \ alfa} ${\ displaystyle M_ {ij} = \ alfa}$ i=(jmodne)+1{\ displaystyle i = (j \ mod n) +1} ${\ displaystyle i = (j \ mod n) +1}$ Mij=0{\ displaystyle M_ {ij} = 0} ${\ displaystyle M_ {ij} = 0}$
- Pokud je sudé, pak pokud, a pouze tehdy , $ne$ ${\ displaystyle M \ in \ mathbf {P}}$ ${\ displaystyle | \ alpha | <1}$
- pokud je liché, pak právě a jen pokud . $ne$ ${\ displaystyle M \ in \ mathbf {P}}$ ${\ displaystyle \ alpha> -1}$
Zvažte cirkulující matici definovanou ${\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n},}$ ${\ displaystyle n \ geqslant 3,}$ ${\ displaystyle M = {\ begin {pmatrix} 1 &&& \ beta ~~~ & \ alpha \\\ alpha & ~~~ \ ddots ~~~ &&& \ beta \\\ beta & ~~~ \ ddots ~~~ & 1 ~~~ & \\ & ~~~ \ ddots ~~~ & \ alpha ~~~ & 1 ~~~ \\ && \ beta ~~~ & \ alpha ~~~ & 1 \ end {pmatrix}} }$ nebo přesněji ${\ displaystyle M_ {ij} = \ left \ {{\ begin {array} {ll} 1 & {\ mbox {si}} ~ i = j \\\ alpha & {\ mbox {si}} ~ i = ( j \ mod n) +1 \\\ beta & {\ mbox {si}} ~ i = ((j + 1) \ mod n) +1 \\ 0 & {\ mbox {jinak}}. \ end {pole }} \ vpravo.}$ Takže jestli nebo jestli . ${\ displaystyle M \ in \ mathbf {P}}$ ${\ displaystyle | \ alfa | -1 <\ beta <| \ alfa | / 4}$ ${\ displaystyle \ alpha ^ {2} +8 (\ beta - {\ textstyle {\ frac {1} {2}}}) ^ {2} <2}$

Dodatky

Poznámky

Definice 1.12, strana 20, Berman and Shaked-Monderer (2003).
(in) Mr. Fiedler, Pták V. (1966). Některá zevšeobecnění pozitivní jednoznačnosti a monotónnosti. Numerische Mathematik , 9, 163–172.
(in) Mr. Fiedler, Pták V. (1962). Na maticích s nepozitivními mimo diagonální prvky a hlavními nezletilými. Czechoslovak Mathematics Journal , 12, 382–400.
(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.
(in) I. Ben Gharbia, J.Ch. Gilbert (2012). Algoritmická charakterizace -matricity. SIAM Journal on Matrix Analysis and Applications (připravovaný). Výzkumná zpráva INRIA RR-8004 . ${\ mathbf {P}}$
(in) W. Morris (2002). Randomizované otočné algoritmy pro problémy lineární komplementarity P-matice. Mathematical Programming , 92A, 285–296. doi
(en) N. Megiddo (1988). Poznámka ke složitosti PCP matice LCP a výpočtu rovnováhy. Technická zpráva RJ 6439 (62557). IBM Research, Almaden Research Center, 650 Harry Road, San Jose, CA, USA.
(in) D. Solow R. Stone, CA Tovey (1987). Řešení LCP na P-matricích pravděpodobně není NP-těžké. Nepublikovaná poznámka.
(in) GE Coxson (1994). Problém s P-maticí je dokončen společně. Mathematical Programming , 64, 173–178. doi
Rumpova věta 2.2 (2003).
MJ Tsatsomeros, L. Li (2000). Opakovaný test pro P-matice. ILO , 40, 410–414.
Příklad 1.7, strana 20, Berman and Shaked-Monderer (2003).
(en) I. Ben Gharbia, J.Ch. Gilbert (2012). Nekonvergence prostého Newton-minova algoritmu pro problémy lineární komplementarity s P-maticí. Mathematical Programming , 134, 349-364. doi Zentralblatt MATH odkaz

Související články

Bibliografie

(en) A. Berman, N. Shaked-Monderer (2003). Zcela pozitivní matice . World Scientific, River Edge, NJ, USA.
(en) RW Cottle, J.-S. Pang, RE Stone (2009). Problém lineární komplementarity . Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.
(en) RA Horn, Ch. R. Jonhson (1991). Témata maticové analýzy . Cambridge University Press, New York, NY, USA.
(en) SM Rump (2003). My P-matice. Lineární algebra a její aplikace , 363, 237–250.