Complementarità

In matematica , un problema di complementarità è un sistema di equazioni e disequazioni, contenente una relazione di ortogonalità che induce un importante combinatorio in questo sistema, vale a dire un gran numero di modi per ottenere questa ortogonalità mediante equazioni. La complementarità è la disciplina che analizza questi problemi e propone algoritmi di risoluzione.

I problemi di complementarità possono spesso essere visti come casi speciali di disuguaglianze variazionali . Sono stati presentati per la prima volta nelle condizioni di ottimalità dei problemi di ottimizzazione vincolata, le condizioni di Karush, Kuhn e Tucker .

Esempi di problemi di complementarità

Complementarità lineare

Il problema della complementarità lineare consiste nel trovare un vettore tale che X∈Rnon{\ displaystyle x \ in \ mathbb {R} ^ {n}}

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

dove , e denota il prodotto punto euclideo. Le disuguaglianze devono essere comprese componente per componente. Questo problema è spesso scritto in modo conciso come segue: M∈Rnon×non{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rnon{\ 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.}

La relazione di ortogonalità può essere realizzata in diversi modi: per tutto , o o . È questo gran numero di possibilità che rende il problema difficile da risolvere. Di solito è NP difficile (in) . ⟨X,MX+q⟩=0{\ displaystyle \ langle x, Mx + q \ rangle = 0}2non{\ displaystyle 2 ^ {n}}io∈[[1,non]]{\ displaystyle i \ in [\! [1, n] \!]}Xio=0{\ displaystyle x_ {i} = 0}(MX+q)io=0{\ displaystyle (Mx + q) _ {i} = 0} 

Complementarità non lineare

Un problema di complementarità più generale e non lineare consiste nel trovare un vettore in un insieme tale che X{\ displaystyle x}E{\ displaystyle \ mathbb {E}}

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

dove ( è uno spazio di Hilbert ) , è un cono chiuso non vuoto convesso , è il doppio cono positivo e l'ortogonalità è presa nel senso del prodotto scalare . Questo significa di scrittura che stiamo cercando in modo tale che , e tale che e sono 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) \ in K}G(X)∈K+{\ displaystyle G (x) \ in K ^ {+}}F(X){\ displaystyle F (x)}G(X){\ displaystyle G (x)}

Appendici

Articoli Correlati

• Complementarità lineare
• Disuguaglianza variazionale

Bibliografia

• (en) SC Billups, KG Murty (2000). Problemi di complementarità. Journal of Computational and Applied Mathematics , 124, 303–318.
• (en) F. Facchinei, J.-S. Pang (2003). Disuguaglianze variazionali finite e problemi di complementarità (2 volumi). Serie Springer nella ricerca operativa. 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;">