Komplementaritás

A matematikában a komplementaritási probléma az egyenletek és egyenlőtlenségek rendszere, amely egy ortogonalitási relációt tartalmaz, amely fontos kombinatorikust indukál ebben a rendszerben, vagyis sokféle módon érheti el ezt az ortogonalitást egyenletekkel. A komplementaritás az a tudományág, amely elemzi ezeket a problémákat, és megoldási algoritmusokat javasol.

A komplementaritási problémák gyakran a variációs egyenlőtlenségek speciális eseteinek tekinthetők . Először a korlátozott optimalizálási problémák, Karush, Kuhn és Tucker körülményei között mutatták be .

Példák a kiegészítő jellegű kérdésekre

Lineáris komplementaritás

A lineáris komplementaritási probléma abban áll, hogy olyan vektort találunk , amely x∈Rnem{\ displaystyle x \ in \ mathbb {R} ^ {n}}

x⩾0,Mx+q⩾0és⟨x,Mx+q⟩=0,{\ displaystyle x \ geqslant 0, \ qquad Mx + q \ geqslant 0 \ qquad {\ mbox {et}} \ qquad \ langle x, Mx + q \ rangle = 0,}

ahol , és a jelöli a euklideszi dot terméket . Az egyenlőtlenségeket komponensenként kell érteni. Ezt a problémát gyakran tömören az alábbiak szerint írják: M∈Rnem×nem{\ displaystyle M \ in \ mathbb {R} ^ {n \ szor n}}q∈Rnem{\ displaystyle q \ in \ mathbb {R} ^ {n}}⟨⋅,⋅⟩{\ displaystyle \ langle \ cdot, \ cdot \ rangle}

0⩽x⊥(Mx+q)⩾0.{\ displaystyle 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.}

Az ortogonalitási viszony többféleképpen valósulhat meg : mindennek , akár , akár . Ez a lehetőségek nagy száma megnehezíti a probléma megoldását. Általában NP kemény (in) . ⟨x,Mx+q⟩=0{\ displaystyle \ langle x, Mx + q \ rangle = 0}2nem{\ displaystyle 2 ^ {n}}én∈[[1,nem]]{\ displaystyle i \ itt: [\! [1, n] \!]}xén=0{\ displaystyle x_ {i} = 0}(Mx+q)én=0{\ displaystyle (Mx + q) _ {i} = 0} 

Nemlineáris komplementaritás

Egy általánosabb és nemlineárisabb komplementaritási probléma abban áll, hogy a halmazban olyan vektort találunk , amely x{\ displaystyle x}E{\ displaystyle \ mathbb {E}}

K∋F(x)⊥G(x)∈K+,{\ displaystyle K \ ni F (x) \ perp G (x) \ in K ^ {+},}

ahol ( egy Hilbert-tér ) , egy kúp zárt, nem üres konvex , a kettős kúp pozitív, és az ortogonalitást a skaláris szorzat értelmében vesszük . Ez az írás azt jelenti, hogy keresünk , hogy , és úgy, hogy és merőleges. F:E→H{\ displaystyle F: \ mathbb {E} \ to \ mathbb {H}}H{\ displaystyle \ mathbb {H}}G:E→H{\ displaystyle G: \ mathbb {E} \ to \ mathbb {H}}K{\ displaystyle K}H{\ displaystyle \ mathbb {H}}K+{\ displaystyle K ^ {+}}K{\ displaystyle K}H{\ displaystyle \ mathbb {H}}x∈E{\ displaystyle x \ in \ mathbb {E}}F(x)∈K{\ displaystyle F (x) \ K-ban}G(x)∈K+{\ displaystyle G (x) \ in K ^ {+}}F(x){\ displaystyle F (x)}G(x){\ displaystyle G (x)}

Függelékek

Kapcsolódó cikkek

• Lineáris komplementaritás
• Variációs egyenlőtlenség

Bibliográfia

• (en) SC Billups, KG Murty (2000). Komplementaritási problémák. Journal of Computational and Applied Mathematics , 124, 303–318.
• (en) F. Facchinei, J.-S. Pang (2003). Véges-dimenziós variációs egyenlőtlenségek és komplementaritási problémák (2 kötet). Springer sorozat az operációkutatásban. Springer-Verlag, New York.

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