Problém lineární komplementarity - Linear complementarity problem

V matematice teorie optimalizace, problém lineární komplementarity (LCP) vzniká často v výpočetní mechanika a zahrnuje dobře známé kvadratické programování jako zvláštní případ. Navrhl to Cottle a Dantzig v roce 1968.^[1][2][3]

Formulace

Vzhledem ke skutečné matici M a vektor q, problém lineární komplementarity LCP (q, M) hledá vektory z a w které splňují následující omezení:

• ${ displaystyle w, z geqslant 0,}$ (to znamená, že každá složka těchto dvou vektorů je nezáporná)
• ${ displaystyle z ^ {T} w = 0}$ nebo ekvivalentně ${ displaystyle sum nolimits _ {i} w_ {i} z_ {i} = 0.}$ To je doplňkovost podmínka, protože to znamená pro všechny ${ displaystyle i}$, maximálně jeden z ${ displaystyle w_ {i}}$ a ${ displaystyle z_ {i}}$ může být pozitivní.
• ${ displaystyle w = Mz + q}$

Postačující podmínkou pro existenci a jedinečnost řešení tohoto problému je to M být symetrický pozitivní-definitivní. Li M je takový LCP (q, M) mít řešení pro každého q, pak M je Q-matice. Li M je takový LCP (q, M) mít pro každého jedinečné řešení q, pak M je P-matice. Obě tyto charakterizace jsou dostatečné a nezbytné.^[4]

Vektor w je volná proměnná,^[5] a tak se po něm obvykle zahodí z je nalezeno. Problém lze tedy formulovat jako:

• ${ displaystyle Mz + q geqslant 0}$
• ${ displaystyle z geqslant 0}$
• ${ displaystyle z ^ { mathrm {T}} (Mz + q) = 0}$ (podmínka doplňkovosti)

Konvexní kvadratická minimalizace: Minimální podmínky

Hledání řešení problému lineární komplementarity je spojeno s minimalizací kvadratické funkce

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

s výhradou omezení

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

${ displaystyle z geqslant 0}$

Tato omezení to zajišťují F je vždy nezáporné. Minimum F je 0 v z kdyby a jen kdyby z řeší problém lineární komplementarity.

Li M je pozitivní určitý, jakýkoli algoritmus pro řešení (striktně) konvexního QP může vyřešit LCP. Speciálně navržené otočné algoritmy základnové výměny, jako např Lemkeho algoritmus a varianta simplexní Dantzigův algoritmus byly používány po celá desetiletí. Kromě toho, že mají polynomiální časovou složitost, jsou v praxi účinné také metody vnitřních bodů.

Také problém s kvadratickým programováním byl uveden jako minimalizovaný ${ displaystyle f (x) = c ^ {T} x + { tfrac {1} {2}} x ^ {T} Qx}$ podléhá ${ displaystyle Axe geqslant b}$ stejně jako ${ displaystyle x geqslant 0}$ s Q symetrický

je stejné jako řešení LCP s

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

Je to proto, že Karush – Kuhn – Tucker podmínky problému QP lze zapsat jako:

${ 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 {případů}}}$

s proti Lagrangeovy multiplikátory na omezeních negativity, λ multiplikátory omezení nerovnosti a s uvolněné proměnné pro omezení nerovnosti. Čtvrtá podmínka pochází z komplementarity každé skupiny proměnných (X, s) se sadou vektorů KKT (optimálních Lagrangeových multiplikátorů) (proti, λ). V tom případě,

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

Pokud je omezení negativity na X je uvolněná, lze rozměrnost problému LCP snížit na počet nerovností, pokud Q není singulární (což je zaručeno, pokud je pozitivní určitý ). Multiplikátory proti již nejsou k dispozici a první podmínky KKT lze přepsat jako:

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

nebo:

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

předběžné vynásobení obou stran A a odečítání b získáváme:

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

Levá strana, kvůli druhé podmínce KKT, je s. Náhrada a změna pořadí:

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

Volám hned

${ displaystyle { begin {zarovnáno} M &: = (AQ ^ {- 1} A ^ {T}) q &: = (- AQ ^ {- 1} c-b) end {zarovnáno}}}$

máme LCP kvůli vztahu komplementarity mezi uvolněnými proměnnými s a jejich Lagrangeovy multiplikátory λ. Jakmile to vyřešíme, můžeme získat hodnotu X z λ přes první podmínku KKT.

Nakonec je také možné zpracovat další omezení rovnosti:

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

Tím se zavádí vektor Lagrangeových multiplikátorů μ, se stejnou dimenzí jako ${ displaystyle b_ {eq}}$.

Je snadné ověřit, že M a Q pro systém LCP ${ displaystyle s = M { lambda} + Q}$ jsou nyní vyjádřeny jako:

${ displaystyle { begin {aligned} 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 {zarovnáno}}}$

Z λ nyní můžeme obnovit hodnoty obou X a Lagrangeův multiplikátor rovností μ:

${ 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}}}$

Ve skutečnosti většina řešitelů QP pracuje na formulaci LCP, včetně metoda vnitřních bodů otočení jistiny / doplňkovosti a aktivní sada metody.^[1][2] Problémy s LCP lze vyřešit také pomocí křížový algoritmus,^[6][7][8][9] naopak, u problémů lineární komplementarity se algoritmus křížového přechodu definitivně ukončí, pouze pokud je matice dostatečnou maticí.^[8][9] A dostatečná matice je zobecnění a pozitivně definitivní matice a P-matice, jehož hlavní nezletilí jsou pozitivní.^[8][9][10]Takové LCP lze vyřešit, když jsou formulovány abstraktně pomocí orientovaný matroid teorie.^[11][12][13]

Viz také

• Teorie komplementarity
• Fyzikální engine Tento přístup používají fyzikální enginy typu impulz / omezení.
• Dynamika kontaktů Kontaktní dynamika s nehladkým přístupem.
• Hry Bimatrix lze snížit na LCP.

Poznámky

Reference

• Cottle, Richard W .; Pang, Jong-Shi; Kámen, Richard E. (1992). Problém lineární komplementarity. Počítačová věda a vědecké výpočty. Boston, MA: Academic Press, Inc. s. Xxiv + 762 s. ISBN  978-0-12-192350-1. PAN  1150683.CS1 maint: ref = harv (odkaz)
• Cottle, R. W.; Pang, J.-S .; Venkateswaran, V. (březen – duben 1989). "Dostatečné matice a problém lineární komplementarity". Lineární algebra a její aplikace. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. PAN  0986877.CS1 maint: ref = harv (odkaz)
• Csizmadia, Zsolt; Illés, Tibor (2006). „Nové křížové algoritmy pro problémy lineární komplementarity s dostatečnými maticemi“ (PDF). Optimalizační metody a software. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID  24418835.
• Fukuda, Komei; Namiki, Makoto (březen 1994). "O extremálním chování Murtyho metody nejmenšího indexu". Matematické programování. 64 (1): 365–370. doi:10.1007 / BF01582581. PAN  1286455. S2CID  21476636.CS1 maint: ref = harv (odkaz)
• den Hertog, D .; Roos, C .; Terlaky, T. (1. července 1993). „Problém lineární komplementarity, dostatek matic a křížová metoda“ (PDF). Lineární algebra a její aplikace. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.CS1 maint: ref = harv (odkaz)
• Murty, K. G. (1988). Lineární komplementarita, lineární a nelineární programování. Série Sigma v aplikované matematice. 3. Berlín: Heldermann Verlag. str. xlviii + 629 str. ISBN  978-3-88538-403-8. PAN  0949214. Aktualizovaná a bezplatná verze PDF na webových stránkách Katty G. Murtyové. Archivovány od originál dne 01.04.2010.CS1 maint: ref = harv (odkaz)
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Křížové metody: nový pohled na pivotní algoritmy". Matematické programování, řada B.. Příspěvky ze 16. mezinárodního symposia o matematickém programování, které se konalo v Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373. doi:10.1007 / BF02614325. PAN  1464775. S2CID  2794181. Postprintový předtisk.CS1 maint: ref = harv (odkaz)
• Todd, Michael J. (1985). "Lineární a kvadratické programování v orientovaných matroidech". Journal of Combinatorial Theory. Řada B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. PAN  0811116.CS1 maint: ref = harv (odkaz)
• R. Chandrasekaran. „Hry Bimatrix“ (PDF). str. 5–7. Citováno 18. prosince 2015.

Další čtení

• R. W. Cottle a G. B. Dantzig. Doplňková pivotní teorie matematického programování. Lineární algebra a její aplikace, 1:103-125, 1968.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot pravidla pro lineární programování: Průzkum o nedávném teoretickém vývoji". Annals of Operations Research. Degenerace v optimalizačních problémech. 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658. doi:10.1007 / BF02096264. ISSN  0254-5330. PAN  1260019. S2CID  6058077.CS1 maint: ref = harv (odkaz)

externí odkazy

• LCPSolve - Jednoduchý postup v GAUSS k řešení problému lineární komplementarity
• Siconos / Numerická implementace GPL s otevřeným zdrojovým kódem v C Lemkeho algoritmu a dalších metod řešení LCP a MLCP