Lineært komplementaritetsproblem - Linear complementarity problem

I matematisk optimeringsteori opstår det lineære komplementaritetsproblem (LCP) ofte i beregningsmekanik og omfatter den velkendte kvadratiske programmering som et specielt tilfælde. Det blev foreslået af Cottle og Dantzig i 1968.

Formulering

Givet en reel matrix M og vektor q , søger det lineære komplementaritetsproblem LCP ( q , M ) vektorer z og w, som opfylder følgende begrænsninger:

• ${\ displaystyle w, z \ geqslant 0,}$ (det vil sige, at hver komponent i disse to vektorer ikke er negativ)
• ${\ displaystyle z ^ {T} w = 0}$eller tilsvarende Dette er komplementaritetsbetingelsen , da det indebærer, at for alle højst en af og kan være positiv.${\ displaystyle \ sum \ nolimits _ {i} w_ {i} z_ {i} = 0.}$${\ displaystyle i}$${\ displaystyle w_ {i}}$${\ displaystyle z_ {i}}$
• ${\ displaystyle w = Mz + q}$

En tilstrækkelig betingelse for eksistens og unikhed ved en løsning på dette problem er, at M er symmetrisk positiv-bestemt . Hvis M er sådan, at LCP ( q , M ) har en løsning for hver q , er M en Q-matrix . Hvis M er sådan, at LCP ( q , M ) har en unik løsning til hver q , er M en P-matrix . Begge disse karakteriseringer er tilstrækkelige og nødvendige.

Vektoren w er en slap variabel , og derfor kasseres den generelt, efter at z er fundet. Som sådan kan problemet også formuleres som:

• ${\ displaystyle Mz + q \ geqslant 0}$
• ${\ displaystyle z \ geqslant 0}$
• ${\ displaystyle z ^ {\ mathrm {T}} (Mz + q) = 0}$ (komplementaritetsbetingelsen)

Konveks kvadratisk minimering: Minimumsbetingelser

At finde en løsning på det lineære komplementaritetsproblem er forbundet med at minimere den kvadratiske funktion

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

underlagt begrænsningerne

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

${\ displaystyle z \ geqslant 0}$

Disse begrænsninger sikrer, at f altid er ikke-negativ. Minimumet af f er 0 ved z, hvis og kun hvis z løser det lineære komplementaritetsproblem.

Hvis M er positiv bestemt , kan enhver algoritme til løsning af (strengt) konvekse QP'er løse LCP. Specielt designet basisudvekslings drejealgoritmer, såsom Lemkes algoritme og en variant af simpleksalgoritmen i Dantzig, er blevet brugt i årtier. Udover at have polynomisk tidskompleksitet er indvendige punktmetoder også effektive i praksis.

Også et kvadratisk programmeringsproblem angivet som minimer med forbehold for såvel som med Q- symmetrisk ${\ displaystyle f (x) = c ^ {T} x + {\ tfrac {1} {2}} x ^ {T} Qx}$${\ displaystyle Axe \ geqslant b}$${\ displaystyle x \ geqslant 0}$

er det samme som at løse LCP med

${\ displaystyle q = {\ begin {bmatrix} c \\ - b \ end {bmatrix}}, \ qquad M = {\ begin {bmatrix} Q & -A ^ {T} \\ A & 0 \ end {bmatrix}}}$

Dette skyldes, at Karush – Kuhn – Tucker- betingelserne for QP-problemet kan skrives som:

${\ displaystyle {\ begin {cases} v = Qx-A ^ {T} {\ lambda} + c \\ s = Ax-b \\ x, {\ lambda}, v, s \ geqslant 0 \\ x ^ {T} v + {\ lambda} ^ {T} s = 0 \ end {cases}}}$

med v Lagrange-multiplikatorerne på ikke-negativitetsbegrænsningerne, λ multiplikatorerne på ulighedsbegrænsningerne, og s de slakke variabler for ulighedsbegrænsningerne. Den fjerde betingelse stammer fra komplementariteten af ​​hver gruppe af variabler ( x , s ), hvor dens sæt KKT-vektorer (optimale Lagrange-multiplikatorer) er ( v , λ ) . I det tilfælde,

${\ displaystyle z = {\ begin {bmatrix} x \\\ lambda \ end {bmatrix}}, \ qquad w = {\ begin {bmatrix} v \\ s \ end {bmatrix}}}$

Hvis ikke-negativitetsbegrænsningen på x er afslappet, kan dimensionaliteten af ​​LCP-problemet reduceres til antallet af uligheder, så længe Q ikke er ental (hvilket er garanteret, hvis det er positivt bestemt ). Multiplikatorerne v er ikke længere til stede, og de første KKT-betingelser kan omskrives som:

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

eller:

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

ved at pre-multiplicere de to sider med A og trække b får vi:

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

Venstre side på grund af den anden KKT-tilstand er s . Udskiftning og ombestilling:

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

Ringer nu

${\ displaystyle {\ begin {align} M &: = (AQ ^ {- 1} A ^ {T}) \\ q &: = (- AQ ^ {- 1} cb) \ end {aligned}}}$

Vi har en LCP på grund af forholdet mellem komplementaritet mellem de slakke variabler s og deres Lagrange-multiplikatorer λ . Når vi først har løst det, opnår vi muligvis værdien af x fra λ gennem den første KKT-tilstand.

Endelig er det også muligt at håndtere yderligere ligestillingsbegrænsninger:

${\ displaystyle A_ {eq} x = b_ {eq}}$

Dette introducerer en vektor af Lagrange-multiplikatorer μ med samme dimension som . ${\ displaystyle b_ {eq}}$

Det er let at kontrollere, at M og Q for LCP-systemet nu udtrykkes som: ${\ displaystyle s = M {\ lambda} + Q}$

${\ displaystyle {\ begin {align} M &: = {\ begin {bmatrix} A & 0 \ end {bmatrix}} {\ begin {bmatrix} Q & A_ {eq} ^ {T} \\ - A_ {eq} & 0 \ end { bmatrix}} ^ {- 1} {\ begin {bmatrix} A ^ {T} \\ 0 \ end {bmatrix}} \\ q &: = - {\ begin {bmatrix} A & 0 \ end {bmatrix}} {\ begin {bmatrix} Q & A_ {eq} ^ {T} \\ - A_ {eq} & 0 \ end {bmatrix}} ^ {- 1} {\ begin {bmatrix} c \\ b_ {eq} \ end {bmatrix}} - b \ end {justeret}}}$

Fra λ kan vi nu gendanne værdierne for både x og Lagrange-multiplikatoren for lighed μ :

${\ displaystyle {\ begin {bmatrix} x \\\ mu \ end {bmatrix}} = {\ begin {bmatrix} Q & A_ {eq} ^ {T} \\ - A_ {eq} & 0 \ end {bmatrix}} ^ {-1} {\ begin {bmatrix} A ^ {T} \ lambda -c \\ - b_ {eq} \ end {bmatrix}}}$

Faktisk arbejder de fleste QP-løsere på LCP-formuleringen, herunder den indre punktmetode , hoved- / komplementaritetsdrejning og aktive sætmetoder. LCP-problemer kan også løses ved krydskrydsalgoritmen , omvendt for krypteringsalgoritme til lineære komplementaritetsproblemer slutter kun finit, hvis matrixen er en tilstrækkelig matrix. En tilstrækkelig matrix er en generalisering både af en positiv-bestemt matrix og af en P-matrix , hvis vigtigste mindreårige hver især er positive. Sådanne LCP'er kan løses, når de formuleres abstrakt ved hjælp af orienteret-matroid- teori.

Se også

• Komplementaritetsteori
• Fysikmotor Impuls- / begrænsningstype fysikmotorer til spil bruger denne tilgang.
• Kontaktdynamik Kontaktdynamik med den ikke-glatte tilgang.
• Bimatrix-spil kan reduceres til en LCP.

Bemærkninger

Referencer

• Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; Hvid, Neil ; Ziegler, Günter (1999). "10 Lineær programmering". Orienterede matroider . Cambridge University Press. s. 417–479. doi : 10.1017 / CBO9780511586507 . ISBN 978-0-521-77750-6. MR  1744046 .
• Cottle, RW; Dantzig, GB (1968). "Supplerende drejningsteori om matematisk programmering". Lineær algebra og dets applikationer . 1 : 103–125.
• Cottle, Richard W .; Pang, Jong-Shi; Stone, Richard E. (1992). Det lineære komplementaritetsproblem . Datalogi og videnskabelig databehandling. Boston, MA: Academic Press, Inc. s. Xxiv + 762 s. ISBN 978-0-12-192350-1. MR  1150683 .
• Cottle, RW ; Pang, J.-S .; Venkateswaran, V. (marts-april 1989). "Tilstrækkelige matricer og det lineære komplementaritetsproblem" . Lineær algebra og dens applikationer . 114–115: 231–249. doi : 10.1016 / 0024-3795 (89) 90463-1 . MR  0986877 .
• Csizmadia, Zsolt; Illés, Tibor (2006). "Nye kryds-tværs-algoritmer til lineære komplementaritetsproblemer med tilstrækkelige matricer" (PDF) . Optimeringsmetoder og software . 21 (2): 247-266. doi : 10.1080 / 10556780500095009 . S2CID  24418835 .
• Fukuda, Komei ; Namiki, Makoto (marts 1994). "Om ekstrem opførsel af Murty's mindste indeksmetode". Matematisk programmering . 64 (1): 365–370. doi : 10.1007 / BF01582581 . MR  1286455 . S2CID  21476636 .
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (red.). "Kryds-tværs-metoder: En ny opfattelse af pivotalgoritmer". Matematisk programmering, Serie B . Papirer fra det 16. internationale symposium om matematisk programmering afholdt i Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373 . doi : 10.1007 / BF02614325 . MR  1464775 . S2CID  2794181 . Fortrykt efterskrift .
• den Hertog, D .; Roos, C .; Terlaky, T. (1. juli 1993). "Det lineære komplementaritetsproblem, tilstrækkelige matricer og kryds og tværs-metoden" (PDF) . Lineær algebra og dens applikationer . 187 : 1–14. doi : 10.1016 / 0024-3795 (93) 90124-7 .
• Murty, Katta G. (januar 1972). "Om antallet af løsninger på komplementaritetsproblemet og spændende egenskaber for komplementære kegler" (PDF) . Lineær algebra og dens applikationer . 5 (1): 65–108. doi : 10.1016 / 0024-3795 (72) 90019-5 . HDL : 2027,42 / 34.188 .
• Murty, KG (1988). Lineær komplementaritet, lineær og ikke-lineær programmering . Sigma-serien i anvendt matematik. 3 . Berlin: Heldermann Verlag. ISBN 978-3-88538-403-8. MR  0949214 . Opdateret og gratis PDF-version på Katta G. Murty's websted . Arkiveret fra originalen 2010-04-01.
• Taylor, Joshua Adam (2015). Konveks optimering af elsystemer . Cambridge University Press. ISBN 9781107076877.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivotregler for lineær programmering: En undersøgelse af nyere teoretisk udvikling". Annaler for operationsforskning . Degenerering i optimeringsproblemer. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . doi : 10.1007 / BF02096264 . ISSN  0254-5330 . MR  1260019 . S2CID  6.058.077 .
• Todd, Michael J. (1985). "Lineær og kvadratisk programmering i orienterede matroider" . Journal of Combinatorial Theory . Serie B. 39 (2): 105–133. doi : 10.1016 / 0095-8956 (85) 90042-5 . MR  0811116 .

Yderligere læsning

• R. Chandrasekaran. "Bimatrix-spil" (PDF) . s. 5–7 . Hentet 18. december 2015 .

eksterne links

• LCPSolve - En enkel procedure i GAUSS til løsning af et lineært komplementaritetsproblem
• Siconos / Numerics open source GPL implementering i C af Lemkes algoritme og andre metoder til løsning af LCP'er og MLCP'er