Doplňkovost

V matematice je problémem komplementarity systém rovnic a nerovností, který obsahuje vztah ortogonality, který v tomto systému indukuje důležitý kombinatorický systém, to znamená velké množství způsobů, jak dosáhnout této ortogonality pomocí rovnic. Komplementarita je disciplína, která analyzuje tyto problémy a navrhuje algoritmy řešení.

Problémy s komplementaritou lze často považovat za zvláštní případy variačních nerovností . Poprvé byly představeny za podmínek optimality omezených optimalizačních problémů, podmínek Karush, Kuhn a Tucker .

Příklady otázek doplňkovosti

Lineární komplementarita

Komplementarita lineární problém spočívá v nalezení vektoru tak, že $x \ in \ mathbb {R} ^ {n}$

${\ displaystyle x \ geqslant 0, \ qquad Mx + q \ geqslant 0 \ qquad {\ mbox {et}} \ qquad \ langle x, Mx + q \ rangle = 0,}$

kde , a označuje Euclidean skalární součin . Nerovnosti je třeba chápat po jednotlivých složkách. Tento problém je často stručně napsán takto: $M \ in \ mathbb {R} ^ {{n \ krát n}}$ $q \ in \ mathbb {R} ^ {n}$ ${\ displaystyle \ langle \ cdot, \ cdot \ rangle}$

${\ displaystyle 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.}$

Vztah ortogonality lze realizovat různými způsoby: buď pro všechno , nebo . Právě toto velké množství možností činí problém obtížně řešitelným. Obvykle je to NP tvrdé (v) . ${\ displaystyle \ langle x, Mx + q \ rangle = 0}$ $2 ^ {n}$ $i \ in [\! [1, n] \!]$ $x_ {i} = 0$ $(Mx + q) _ {i} = 0$

Nelineární komplementarita

Obecnější a nelineární problém komplementarity spočívá v hledání vektoru v sadě takových, že $X$ $\ mathbb {E}$

${\ displaystyle K \ ni F (x) \ perp G (x) \ v K ^ {+},}$

kde ( je Hilbertův prostor ) , je kužel uzavřený neprázdný konvexní , je kladný dvojitý kužel a ortogonalita je brána ve smyslu skalárního součinu . Psaní tohoto článku znamená, že jsme hledali tak, že , a taková, že a jsou kolmé. ${\ displaystyle F: \ mathbb {E} \ do \ mathbb {H}}$ $\ mathbb {H}$ ${\ displaystyle G: \ mathbb {E} \ do \ mathbb {H}}$ $K.$ $\ mathbb {H}$ $K ^ {+}$ $K.$ $\ mathbb {H}$ $x \ in \ mathbb {E}$ ${\ displaystyle F (x) \ v K}$ ${\ displaystyle G (x) \ v K ^ {+}}$ $F (x)$ $G (x)$

Dodatky

Související články

Bibliografie

(en) SC Billups, KG Murty (2000). Problémy s komplementaritou. Journal of Computational and Applied Mathematics , 124, 303–318.
(en) F. Facchinei, J.-S. Pang (2003). Konečně dimenzionální variační nerovnosti a problémy s komplementaritou (2 svazky). Springer Series v operačním výzkumu. Springer-Verlag, New York.