Dostatečná matice
V matematice pojmy dostatečné ve sloupci , dostatečné v řadě a dostatečné kvalifikují skutečné čtvercové matice poskytující konkrétní vlastnosti problémům lineární komplementarity . Stručně řečeno, říká se
maticeM∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}
-
dostatečné ve sloupci, pokud to naznačuje ,X⋅(MX)⩽0{\ displaystyle x \ cdot (Mx) \ leqslant 0}X⋅(MX)=0{\ displaystyle x \ cdot (Mx) = 0}
-
dostačující, pokud to naznačuje ,X⋅(M⊤X)⩽0{\ displaystyle x \ cdot (M ^ {\ top} x) \ leqslant 0}X⋅(M⊤X)=0{\ displaystyle x \ cdot (M ^ {\ top} x) = 0}
-
dostatečné, pokud je dostatečné ve sloupci i dostatečné v řádku.
V těchto definicích, označuje produkt Hadamardova z vektorů a , což je vektor, jehož složkou je , a označuje transponovaných matice z . Mělo by být chápáno „z toho vyplývá “ takto: „jakýkoli bod ověřující také ověřuje “.
u⋅proti{\ displaystyle u \ cdot v}u{\ displaystyle u}proti{\ displaystyle v}i{\ displaystyle i}uiprotii{\ displaystyle u_ {i} v_ {i}}M⊤{\ displaystyle M ^ {\ top}}M{\ displaystyle M}X⋅(MX)⩽0{\ displaystyle x \ cdot (Mx) \ leqslant 0}X⋅(MX)=0{\ displaystyle x \ cdot (Mx) = 0}X{\ displaystyle x}X⋅(MX)⩽0{\ displaystyle x \ cdot (Mx) \ leqslant 0}X⋅(MX)=0{\ displaystyle x \ cdot (Mx) = 0}
Dostatečné sloupcové matice jsou také ty, které zajišťují konvexnost souboru řešení problému lineární komplementarity . Dostatečné online matice jsou také ty, které zajišťují, že soubor řešení takového problému je identický se souborem stacionárních bodů jeho přidruženého kvadratického problému.
Tyto pojmy zavedly Cottle, Pang a Venkateswaran (1989). Původní anglická terminologie je sloupec dostačující , řádek dostačující a dostačující . Kvalifikátory sloupců a řádků jsou stěží intuitivní. Ve skutečnosti byl název dostačující ve sloupci zvolen částečně pro vtip a parodování výrazu adekvátního ve sloupci , což je pojem zavedený Ingletonem (1966), což znamená, že
∀X∈Rne:X⋅(MX)⩽0⟹MX=0.{\ displaystyle \ forall \, x \ in \ mathbb {R} ^ {n}: \ qquad x \ cdot (Mx) \ leqslant 0 \ quad \ Longrightarrow \ quad Mx = 0.}
Vzhledem k tomu, představa činí tím, že pro každou neprázdné, tehdy a jen tehdy, pokud jsou sloupy z lineárně závislá, kvalifikátor ve sloupci je snadněji odůvodněna v druhém případě.
Já⊂{1,...,ne}{\ displaystyle I \ podmnožina \ {1, \ ldots, n \}}detMJá,Já=0{\ displaystyle \ det \, M_ {I, I} = 0} M∙Já{\ displaystyle M _ {\ odrážka I}}M{\ displaystyle M}
Problém komplementarity
Právě problémy komplementarity motivovaly k zavedení pojmů dostatečná matice. Proto si zde připomínáme některé pojmy související s těmito problémy.
Definice
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}}
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 . Všimli jsme si
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}Admirál(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}
Přízemní(M,q){\ displaystyle {\ mbox {Sol}} (M, q)}
množina řešení lineární komplementarity problému .
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Přidružený kvadratický problém
Vezměme si optimalizační problém kvadratické podle následujícího důvodu:
X∈Rne{\ displaystyle x \ in \ mathbb {R} ^ {n}}
(PQ){minX⊤(MX+q)X⩾0MX+q⩾0.{\ displaystyle {\ mbox {(PQ)}} \ qquad \ left \ {{\ begin {pole} {l} \ min \; x ^ {\! \ top} (Mx + q) \\ x \ geqslant 0 \\ Mx + q \ geqslant 0. \ end {pole}} \ vpravo.}
Vzhledem k tomu, že cena tohoto problému je omezena níže přes přípustnou množinu (je tam pozitivní), má tento problém vždy řešení (Frank a Wolfe, 1956). To pak odvodíme
X∈Přízemní(M,q)⟺X{\ displaystyle x \ in \ operatorname {Sol} (M, q) \ quad \ Longleftrightarrow \ quad x} je řešení (PQ) s nulovými optimálními náklady.
Kvadratický problém (PQ) však může obecně mít lokální minima nebo stacionární body, které nejsou řešením . Připomíná se, že bod je stacionární pro problém (PQ), pokud existují multiplikátory a takové, že jsou ověřeny následující podmínky Karush, Kuhn a Tucker :
CL(M,q){\ displaystyle \ operatorname {CL} (M, q)}X∈Rne{\ displaystyle x \ in \ mathbb {R} ^ {n}}s∈Rne{\ displaystyle s \ in \ mathbb {R} ^ {n}}z∈Rne{\ displaystyle z \ in \ mathbb {R} ^ {n}}
(KKT){(na)(M+M⊤)X+q-s-M⊤z=0(b)0⩽X⊥s⩾0(vs.)0⩽(MX+q)⊥z⩾0.{\ displaystyle {\ mbox {(KKT)}} \ qquad \ left \ {{\ begin {pole} {cl} (a) & (M + M ^ {\ top}) x + qsM ^ {\ top} z = 0 \\ (b) & 0 \ leqslant x \ perp s \ geqslant 0 \\ (c) & 0 \ leqslant (Mx + q) \ perp z \ geqslant 0. \ end {array}} \ right.}
Všimli jsme si
Sta(M,q){\ displaystyle {\ mbox {Sta}} (M, q)}
množina stacionárních bodů kvadratické úlohy (PQ).
Dostatečná matice ve sloupci
Definice
Dostatečná matrice ve sloupci - Říkáme, že skutečný čtvercová matice je ve sloupci dostačující , jestliže pro všechny taková, že máme ; které lze shrnout takto:
M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}X∈Rne{\ displaystyle x \ in \ mathbb {R} ^ {n}}X⋅(MX)⩽0{\ displaystyle x \ cdot (Mx) \ leqslant 0}X⋅(MX)=0{\ displaystyle x \ cdot (Mx) = 0}
X⋅(MX)⩽0⟹X⋅(MX)=0.{\ Displaystyle x \ cdot (Mx) \ leqslant 0 \ qquad \ Longrightarrow \ qquad x \ cdot (Mx) = 0.}
Poznamenáváme sadu dostatečných matic ve sloupci.
SVS{\ displaystyle \ mathbf {SC}}
Role v otázkách doplňkovosti
Obecně lze říci, že množina řešení na komplementaritu problém lineárního je unie z konvexní mnohostěnů . Dostatečné sloupcové matice jsou ty, pro které je sadou těchto řešení jediný konvexní mnohostěn.
Přízemní(M,q){\ displaystyle \ operatorname {Sol} (M, q)}
SVS{\ displaystyle \ mathbf {SC}}-matice a konvexita Přízemní(M,q){\ displaystyle \ operatorname {Sol} (M, q)} - U matice jsou ekvivalentní následující vlastnosti:
M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}
-
M∈SVS{\ displaystyle M \ in \ mathbf {SC}},
-
∀q∈Rne, Přízemní(M,q){\ displaystyle \ forall \, q \ in \ mathbb {R} ^ {n}, ~ \ operatorname {Sol} (M, q)} je konvexní.
Propojení s jinými třídami matic
Označíme množinu -matic . Pokud je taková, že pro každý index , . Tato vlastnost není kompatibilní s -matricity. Máme tedy následující zařazení.
P0{\ displaystyle \ mathbf {P_ {0}}}P0{\ displaystyle \ mathbf {P_ {0}}}M∉P0{\ displaystyle M \ notin \ mathbf {P_ {0}}}X≠0{\ displaystyle x \ neq 0}i{\ displaystyle i}Xi≠0{\ displaystyle x_ {i} \ neq 0} ⇒{\ displaystyle \ Rightarrow} Xi(MX)i<0{\ displaystyle x_ {i} (Mx) _ {i} <0}SVS{\ displaystyle \ mathbf {SC}}
SVS⊂P0{\ displaystyle \ mathbf {SC} \ podmnožina \ mathbf {P_ {0}}}.
Dostatečná matice v řadě
Definice
Dostatečná matice v řádku - Říkáme, že skutečná čtvercová matice je dostatečná v řadě, pokud je její transpozice dostatečná ve sloupci; které lze shrnout takto:
M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}
X⋅(M⊤X)⩽0⟹X⋅(M⊤X)=0.{\ displaystyle x \ cdot (M ^ {\ top} x) \ leqslant 0 \ qquad \ Longrightarrow \ qquad x \ cdot (M ^ {\ top} x) = 0.}
Poznamenáváme sadu dostatečných matic online.
SL{\ displaystyle \ mathbf {SL}}
Role v otázkách doplňkovosti
Pokud jde o řešení úlohy lineární komplementarity , jedná se také o řešení kvadratické úlohy (PQ). Vzhledem k tomu, že omezení jsou kvalifikována , podmínky Karush, Kuhn a Ticker (KKT) jsou ověřeny pro multiplikátory a . Takže máme
X∈Rne{\ displaystyle x \ in \ mathbb {R} ^ {n}}CL(M,q){\ displaystyle \ operatorname {CL} (M, q)}s∈Rne{\ displaystyle s \ in \ mathbb {R} ^ {n}}z∈Rne{\ displaystyle z \ in \ mathbb {R} ^ {n}}
Přízemní(M,q)⊂Sta(M,q).{\ displaystyle \ operatorname {Sol} (M, q) \ podmnožina \ operatorname {Sta} (M, q).}
Následující výsledek ukazuje, že v tomto vztahu máme rovnost bez ohledu na to , zda a pouze v případě, že je matice dostatečná v řadě.
q∈Rne{\ displaystyle q \ in \ mathbb {R} ^ {n}}M{\ displaystyle M}
SL{\ displaystyle \ mathbf {SL}}-matice a rovnost Přízemní(M,q)=Sta(M,q){\ displaystyle \ operatorname {Sol} (M, q) = {\ mbox {Sta}} (M, q)} - U matice jsou ekvivalentní následující vlastnosti:
M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}
-
M∈SL{\ displaystyle M \ in \ mathbf {SL}},
-
∀q∈Rne, Přízemní(M,q)=Sta(M,q){\ displaystyle \ forall \, q \ in \ mathbb {R} ^ {n}, ~ \ operatorname {Sol} (M, q) = {\ mbox {Sta}} (M, q)}.
Spojení s jinými třídami matic
Pokud označíme množinu P-matic , množinu P0-matic množinu Q0-matic a množinu kladných polo-definovaných matic (ne nutně symetrických), mámeP{\ displaystyle \ mathbf {P}}P0{\ displaystyle \ mathbf {P_ {0}}}
Q0{\ displaystyle \ mathbf {Q_ {0}}}SDP{\ displaystyle \ mathbf {SDP}}
(SDP∪P)⊂SL⊂(P0∩Q0){\ displaystyle (\ mathbf {SDP} \ cup \ mathbf {P}) \ podmnožina \ mathbf {SL} \ podmnožina (\ mathbf {P} _ {0} \ cap \ mathbf {Q} _ {0})}.
Inkluze vyplývají z definic SL-matic, P-matic a P0-matic . Potom pozorujeme, že pokud je takový , pak má kvadratický problém (PQ) řešení, které je stacionárním bodem tohoto problému; nyní, pokud je dostatečné v řadě, je tento stacionární bod řešením ; proto . A konečně, zařazení je způsobeno Dornem (1961).
P⊂SL⊂P0{\ displaystyle \ mathbf {P} \ podmnožina \ mathbf {SL} \ podmnožina \ mathbf {P_ {0}}}q{\ displaystyle q}Admirál(M,q)≠∅{\ displaystyle \ operatorname {Adm} (M, q) \ neq \ varnothing}M{\ displaystyle M}CL(M,q){\ displaystyle \ operatorname {CL} (M, q)}SL⊂Q0{\ displaystyle \ mathbf {SL} \ podmnožina \ mathbf {Q} _ {0}}SDP⊂SL{\ displaystyle \ mathbf {SDP} \ podmnožina \ mathbf {SL}}
Dostatečné online matice jsou tedy přesně ty, které umožňují demonstrovat existenci řešení procházejícího podmínkami optimality (KKT) kvadratického problému (PQ). Skutečnost, že to není všechno, naznačuje, že musí existovat další analytické přístupy umožňující ukázat existenci řešení ; se ko-pozitivním a matrice vnesené Lemke (1965), jsou známým příkladem třídy matic, které nejsou v souladu dostatečné.
CL(M,q){\ displaystyle \ operatorname {CL} (M, q)}SL{\ displaystyle \ mathbf {SL}}Q0{\ displaystyle \ mathbf {Q_ {0}}}CL(M,q){\ displaystyle \ operatorname {CL} (M, q)}
Dostatečná matice
Definice
Dostatečná Matrix - skutečná čtvercová matice se říká, že je postačující , pokud je to i dostačující ve sloupci a dostatečné v řadě.
M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}
Role v otázkách doplňkovosti
Dostatečná matice a komplementarita - u matice jsou ekvivalentní následující vlastnosti:
M∈Rne×ne{\ displaystyle M \ in \ mathbb {R} ^ {n \ krát n}}
-
M{\ displaystyle M} je dostačující,
-
∀q∈Rne, Přízemní(M,q)=Sta(M,q){\ displaystyle \ forall \, q \ in \ mathbb {R} ^ {n}, ~ \ operatorname {Sol} (M, q) = {\ mbox {Sta}} (M, q)} a tato sada je konvexní.
Spojení s jinými třídami matic
Pokud označíme množinu kladných polo-definovaných matic (nemusí být nutně symetrických), množinu P-matic a množinu -matic , máme následující inkluzi a rovnost.
SDP{\ displaystyle \ mathbf {SDP}}P{\ displaystyle \ mathbf {P}}P∗{\ displaystyle \ mathbf {P _ {*}}}P∗{\ displaystyle P _ {*}}
(SDP∪P)⊂SU=P∗{\ displaystyle (\ mathbf {SDP} \ cup \ mathbf {P}) \ podmnožina \ mathbf {SU} = \ mathbf {P _ {*}}}.
Dodatky
Poznámky
-
(en) RW Cottle, J.-S. Pang, V. Venkateswaran (1989). Dostatečné matice a problém lineární komplementarity. Lineární algebra a její aplikace , 114, 231–249. doi
-
(v) RW Cottle (2005). Lineární komplementarita od roku 1978. In Variační analýza a aplikace , nekonvexní optimalizace a její aplikace 79, strany 239–257. Springer, New York.
-
(cs) AW Ingleton (1966). Problém lineárních nerovností. Proc. London Math. Soc. , 2, 519–536.
-
(en) M. Frank, P. Wolfe (1956). Algoritmus pro kvadratické programování. Naval Research Logistics Quarterly , 3, 95–110.
-
(en) MJM Janssen (1983). O struktuře souboru řešení problému lineární komplementarity. Centrum notebooků Études Rech. Oper. , 25, 41–48.
-
Dornova věta 1 (1961).
-
(v) CE Lemke (1965). Bimatrixovy rovnovážné body a matematické programování. Management Science , 11, 681–689. doi
-
(en) RW Cottle, GB Dantzig (1968). Teorie komplementarity pivot matematického programování. Lineární algebra a její aplikace , 1, 103–125. doi
-
Zahrnutí prokázali Kojima, Megiddo, Noma a Yoshise (1991). Zahrnutí prokázali Guu a Cottle (1995). Zahrnutí prokázal Väliaho (1996).(SDP∪P)⊂P∗⊂SVS{\ displaystyle (\ mathbf {SDP} \ cup \ mathbf {P}) \ podmnožina \ mathbf {P _ {*}} \ podmnožina \ mathbf {SC}}P∗⊂SL{\ displaystyle \ mathbf {P _ {*}} \ podmnožina \ mathbf {SL}}SU⊂P∗{\ displaystyle \ mathbf {SU} \ podmnožina \ mathbf {P _ {*}}}
Související článek
Reference
-
(en) WS Dorn , „ Self-dual quadratic programs “ , Journal of the Society for Industrial and Applied Mathematics , sv. 9,1961, str. 51–54 ( DOI 10.1137 / 0109006 ).
-
(en) S.-M. Guu a RW Cottle , „ We subclass ofP0{\ displaystyle \ mathbf {P_ {0}}} “ , Linear Algebra and its Applications , vol. 223/224,1995, str. 325–335.
-
(en) M. Kojima , N. Megiddo , T. Noma a A. Yoshise , Unified Approach to Interior Point Algorithms for Linear Complementarity Problémy , Berlín, Springer-Verlag, kol. "Lecture Notes in Computer Science" ( n o 538)1991.
-
(en) H. Väliaho , „ matice jsou dostačující “P∗{\ displaystyle \ mathbf {P _ {*}}} , Linear Algebra and its Applications , sv. 239,1996, str. 103–108.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">