Problem liniowej komplementarności

W matematycznej teorii optymalizacji problem komplementarności liniowej (LCP) pojawia się często w mechanice obliczeniowej i obejmuje dobrze znane programowanie kwadratowe jako przypadek szczególny. Zaproponowali go Cottle i Dantzig w 1968 roku.

Sformułowanie

Mając rzeczywistą macierz M i wektor q , problem liniowej komplementarności LCP( q , M ) szuka wektorów z i w , które spełniają następujące ograniczenia:

• ${\ Displaystyle w, z \ geqslant 0,}$ (czyli każdy składnik tych dwóch wektorów jest nieujemny)
• ${\ Displaystyle z ^ {T} w = 0}$ lub równoważnie ${\ Displaystyle \ suma \ nolimits _ {i} w_ {i} z_ {i} = 0.}$ Jest to $implikuje$ , $.$ , że dla wszystkich $i$ najwyżej jeden z być dodatni
• ${\ Displaystyle w = Mz + q}$

Wystarczającym warunkiem istnienia i jednoznaczności rozwiązania tego problemu jest, aby M było symetrycznie dodatnio określone . Jeśli M jest takie, że LCP( q , M ) ma rozwiązanie dla każdego q , to ​​M jest Q-macierzą . Jeśli M jest takie, że LCP( q , M ) ma unikalne rozwiązanie dla każdego q , to M jest macierzą P . Obie te charakterystyki są wystarczające i konieczne.

Wektor w jest zmienną typu „slack” i dlatego jest generalnie odrzucany po znalezieniu z . W związku z tym problem można również sformułować w następujący sposób:

• ${\ Displaystyle Mz + q \ geqslant 0}$
• ${\ displaystyle z \ geqslant 0}$
• ${\ Displaystyle z ^ {\ operatorname {T}} (Mz + q) = 0}$ (warunek komplementarności)

Minimalizacja wypukła kwadratowa: warunki minimalne

Znalezienie rozwiązania problemu liniowej komplementarności wiąże się z minimalizacją funkcji kwadratowej

${\ Displaystyle f (z) = z ^ {T} (Mz + q)}$

podlega ograniczeniom

${\ Displaystyle {Mz} + q \ geqslant 0}$

${\ Displaystyle z \ geqslant 0}$

Te ograniczenia zapewniają, że f jest zawsze nieujemne. Minimum f wynosi 0 w z wtedy i tylko wtedy, gdy z rozwiązuje problem liniowej komplementarności.

Jeśli M jest dodatnio określone , dowolny algorytm rozwiązywania (ściśle) wypukłych QP może rozwiązać LCP. Specjalnie zaprojektowane algorytmy obracania wymiany bazowej, takie jak algorytm Lemkego i wariant algorytmu simplex Dantziga, są używane od dziesięcioleci. Oprócz wielomianowej złożoności czasowej, metody punktów wewnętrznych są również skuteczne w praktyce.

Również problem programowania kwadratowego określony jako minimalizacja $} Qx}$${\ Displaystyle f (x) = c ^ {T} x + {\ tfrac {1} {2}} x ^ {$$jak$ z zastrzeżeniem ${\ Displaystyle Ax \ geqslant b}$ również z Q symetrycznym

jest tym samym, co rozwiązanie LCP z

${\ Displaystyle q = {\ rozpocząć {bmatrix} c \\ -b \ koniec {bmatrix}} \ qquad M = {\ rozpocząć {bmatrix} Pytania i odpowiedzi^{T}\\A&0\end{bmacierz}}}$

Dzieje się tak, ponieważ warunki Karusha – Kuhna – Tuckera problemu QP można zapisać jako:

${\ Displaystyle {\ rozpocząć {przypadki} v = Qx-A ^ {T }{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end {sprawy}}}$

z v mnożnikami Lagrange'a na ograniczeniach nieujemnych, λ mnożnikami na ograniczeniach nierówności i s zmiennymi luźnymi dla ograniczeń nierówności. Czwarty warunek wynika z komplementarności każdej grupy zmiennych ( x , s ) z jej zbiorem wektorów KKT (optymalne mnożniki Lagrange'a) wynoszącym ( v , λ ) . W tym wypadku,

${\ Displaystyle Z = {\ rozpocząć {bmatrix} x \\\ lambda \ koniec {bmatrix}}, \ qquad w = {\ rozpocząć {bmatrix} v \\ s \end{bmacierz}}}$

Jeśli ograniczenie nieujemności na x zostanie złagodzone, wymiarowość problemu LCP można sprowadzić do liczby nierówności, o ile Q nie jest osobliwa (co jest gwarantowane, jeśli jest dodatnio określone ). Mnożniki v nie są już obecne, a pierwsze warunki KKT można przepisać jako:

${\ Displaystyle Qx = A ^ {T} {\ lambda} -c}$

Lub:

${\ Displaystyle x = Q ^ {- 1} (A ^ {T} {\ lambda} -c)}$

wstępnie mnożąc obie strony przez A i odejmując b otrzymujemy:

${\ Displaystyle Ax-b = AQ ^ {- 1} (A ^ {T} {\ lambda} -c) -b \,}$

Lewa strona, ze względu na drugi warunek KKT, to s . Podstawianie i zmiana kolejności:

${\ Displaystyle s = (AQ ^ {- 1} A ^ {T}) {\ lambda} + (-AQ ^ { -1}cb)\,}$

Dzwonię teraz

${\ Displaystyle {\ rozpocząć {wyrównane} M &: = (AQ ^ {- 1} A ^ {T}) \ \q&:=(-AQ^{-1}cb)\end{wyrównane}}}$

mamy LCP, ze względu na relację komplementarności między zmiennymi luźnymi s a ich mnożnikami Lagrange'a λ . Gdy go rozwiążemy, możemy otrzymać wartość x z λ przez pierwszy warunek KKT.

Wreszcie, możliwe jest również obsłużenie dodatkowych ograniczeń równości:

$\ Displaystyle A_ {równ.} x = b_ {równ.}}$

Wprowadza to wektor mnożników Lagrange'a μ , o tym samym wymiarze co ${\ displaystyle b_ {eq}}$ .

Łatwo jest sprawdzić, czy M i Q dla systemu LCP są teraz wyrażone jako: ${\ Displaystyle s = M {\ lambda} + Q}$

${\ Displaystyle {\ rozpocząć {wyrównane} M &: = {\ rozpocząć {bmatrix} A & 0 \ koniec {bmatrix}}} {\ rozpocząć {bmatrix} Q&A_ {równ.} ^ {T} \\ - A_ {równ.} i 0 \ koniec { bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin {bmatrix}Q&A_{równ.}^{T}\\-A_{równ.}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{równ.}\koniec{bmatrix}}- b\end{wyrównane}}}$

Z λ możemy teraz odzyskać wartości zarówno x , jak i mnożnika równości Lagrange'a μ :

${\ Displaystyle {\ rozpocząć {bmatrix} x \\\ mu \ koniec {bmatrix}} = {\begin{bmatrix}Pytania i odpowiedzi_{równ.}^{T}\\-A_{równ.}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\ -b_{równ.}\end{bmacierz}}}$

W rzeczywistości większość solwerów QP pracuje na formule LCP, w tym na metodzie punktu wewnętrznego , przestawianiu zasady/komplementarności i metodach zbioru aktywnego . Problemy LCP można również rozwiązać algorytmem krzyżowym , i odwrotnie, w przypadku problemów z liniową komplementarnością algorytm krzyżowy kończy się skończenie tylko wtedy, gdy macierz jest wystarczającą macierzą. Wystarczająca macierz jest uogólnieniem zarówno macierzy dodatnio określonej, jak i macierzy P , której główne drugorzędne każdy jest pozytywny. Takie LCP można rozwiązać, gdy zostaną sformułowane abstrakcyjnie przy użyciu zorientowanych matroidów .

Zobacz też

• Teoria komplementarności
• Silnik fizyki Silniki fizyki typu impuls/ograniczenie w grach wykorzystują to podejście.
• Dynamika kontaktu Dynamika kontaktu z podejściem niegładkim.
• Gry Bimatrix można zredukować do LCP.

Notatki

•    Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; biały, Neil ; Ziegler, Gunter (1999). „10 Programowanie liniowe”. Zorientowane Matroidy . Wydawnictwo Uniwersytetu Cambridge. s. 417–479. doi : 10.1017/CBO9780511586507 . ISBN 978-0-521-77750-6 . MR 1744046 .
• Cottle, RW; Gdańsk, GB (1968). „Komplementarna teoria przestawna programowania matematycznego” . Algebra liniowa i jej zastosowania . 1 : 103–125. doi : 10.1016/0024-3795(68)90052-9 .
•    Cottle, Richard W.; Pang, Jong-Shi; Kamień, Richard E. (1992). Problem liniowej komplementarności . Informatyka i obliczenia naukowe. Boston, MA: Academic Press, Inc. s. XXIV + 762 s. ISBN 978-0-12-192350-1 . MR 1150683 .
•   Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (marzec – kwiecień 1989). „Wystarczające macierze i problem liniowej komplementarności” . Algebra liniowa i jej zastosowania . 114-115: 231-249. doi : 10.1016/0024-3795(89)90463-1 . MR 0986877 .
•   Csizmadia, Zsolt; Illés, Tibor (2006). „Nowe algorytmy typu krzyżowego dla problemów z liniową komplementarnością z wystarczającą liczbą macierzy” (PDF) . Metody optymalizacji i oprogramowanie . 21 (2): 247–266. doi : 10.1080/10556780500095009 . S2CID 24418835 .
•    Fukuda, Komei ; Namiki, Makoto (marzec 1994). „O ekstremalnych zachowaniach metody najmniejszego indeksu Murty'ego”. Programowanie matematyczne . 64 (1): 365–370. doi : 10.1007/BF01582581 . MR 1286455 . S2CID 21476636 .
•     Fukuda, Komei; Terlaky, Tamás (1997). Thomasa M. Lieblinga; Dominique de Werra (red.). „Metody krzyżowe: świeże spojrzenie na algorytmy przestawne”. Programowanie matematyczne, seria B. Referaty z 16. Międzynarodowego Sympozjum Programowania Matematycznego, które odbyło się w Lozannie, 1997. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . doi : 10.1007/BF02614325 . MR 1464775 . S2CID 2794181 . Preprint postscriptowy .
• den Hertog, D.; Roos, C.; Terlaky, T. (1 lipca 1993). „Problem liniowej komplementarności, wystarczające macierze i metoda krzyżowa” (PDF) . Algebra liniowa i jej zastosowania . 187 : 1–14. doi : 10.1016/0024-3795(93)90124-7 .
• Murty, Katta G. (styczeń 1972). „O liczbie rozwiązań problemu komplementarności i obejmujących właściwości stożków komplementarnych” (PDF) . Algebra liniowa i jej zastosowania . 5 (1): 65–108. doi : 10.1016/0024-3795(72)90019-5 . hdl : 2027.42/34188 .
•    Murty, KG (1988). Komplementarność liniowa, programowanie liniowe i nieliniowe . Seria Sigma w matematyce stosowanej. Tom. 3. Berlin: Heldermann Verlag. ISBN 978-3-88538-403-8 . MR 0949214 . Zaktualizowana i bezpłatna wersja PDF na stronie Katta G. Murty . Zarchiwizowane od oryginału w dniu 2010-04-01.
•   Taylor, Joshua Adam (2015). Optymalizacja wypukła systemów elektroenergetycznych . Wydawnictwo Uniwersytetu Cambridge. ISBN 9781107076877 .
•      Terlaky, Tamás; Zhang, Shu Zhong (1993). „Zasady obrotu dla programowania liniowego: ankieta dotycząca ostatnich osiągnięć teoretycznych”. Roczniki badań operacyjnych . Degeneracja w problemach optymalizacyjnych. 46-47 (1): 203-233. CiteSeerX 10.1.1.36.7658 . doi : 10.1007/BF02096264 . ISSN 0254-5330 . MR 1260019 . S2CID 6058077 .
•   Todd, Michael J. (1985). „Programowanie liniowe i kwadratowe w zorientowanych matroidach” . Dziennik teorii kombinatorycznej . Seria B. 39 (2): 105–133. doi : 10.1016/0095-8956(85)90042-5 . MR 0811116 .

Dalsza lektura

• R. Chandrasekaran. „Gry Bimatrix” (PDF) . s. 5–7 . Źródło 18 grudnia 2015 r .

Linki zewnętrzne

• LCPSolve — Prosta procedura w GAUSS do rozwiązania problemu liniowej komplementarności
• Siconos / Numerics implementacja open source GPL w C algorytmu Lemkego i inne metody rozwiązywania LCP i MLCP