Complementaritate

În matematică , o problemă de complementaritate este un sistem de ecuații și inegalități, care conține o relație de ortogonalitate care induce o combinație importantă în acest sistem, adică un număr mare de moduri de a realiza această ortogonalitate prin ecuații. Complementaritatea este disciplina care analizează aceste probleme și propune algoritmi de soluționare.

Problemele de complementaritate pot fi adesea văzute ca cazuri speciale de inegalități variaționale . Au fost prezentate pentru prima dată în condițiile de optimitate ale problemelor de optimizare constrânse, în condițiile Karush, Kuhn și Tucker .

Exemple de probleme de complementaritate

Complementaritatea liniară

Problema complementarității liniare constă în găsirea unui vector astfel încât X∈Rnu{\ displaystyle x \ in \ mathbb {R} ^ {n}}

X⩾0,MX+q⩾0și⟨X,MX+q⟩=0,{\ displaystyle x \ geqslant 0, \ qquad Mx + q \ geqslant 0 \ qquad {\ mbox {et}} \ qquad \ langle x, Mx + q \ rangle = 0,}

în cazul în care , și reprezintă euclidian produsul scalar . Inegalitățile trebuie înțelese componentă cu componentă. Această problemă este adesea scrisă concis, după cum urmează: M∈Rnu×nu{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rnu{\ 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.}

Relația ortogonalitate poate fi realizat în diferite moduri: pentru tot , fie , fie . Acest număr mare de posibilități face dificilă rezolvarea problemei. De obicei este NP greu (în) . ⟨X,MX+q⟩=0{\ displaystyle \ langle x, Mx + q \ rangle = 0}2nu{\ displaystyle 2 ^ {n}}eu∈[[1,nu]]{\ displaystyle i \ in [\! [1, n] \!]}Xeu=0{\ displaystyle x_ {i} = 0}(MX+q)eu=0{\ displaystyle (Mx + q) _ {i} = 0} 

Complementaritate neliniară

O problemă de complementaritate mai generală și neliniară constă în găsirea unui vector într-un set astfel încât X{\ displaystyle x}E{\ displaystyle \ mathbb {E}}

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

unde ( este un spațiu Hilbert ) , este un con închis convex non-gol , este conul dual pozitiv și ortogonalitatea este luată în sensul produsului scalar . Această scriere înseamnă că căutăm astfel încât , și astfel încât și să fie ortogonali. 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) \ în K}G(X)∈K+{\ displaystyle G (x) \ în K ^ {+}}F(X){\ displaystyle F (x)}G(X){\ displaystyle G (x)}

Anexe

Articole similare

• Complementaritatea liniară
• Inegalitatea variațională

Bibliografie

• (ro) SC Billups, KG Murty (2000). Probleme de complementaritate. Journal of Computational and Applied Mathematics , 124, 303-318.
• (ro) F. Facchinei, J.-S. Pang (2003). Inegalități variaționale finite-dimensională și probleme de complementaritate (2 volume). Seria Springer în cercetarea operațională. 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;">