Doğrusal tamamlayıcılık sorunu - Linear complementarity problem

Matematiksel olarak optimizasyon teorisi, doğrusal tamamlayıcılık sorunu (LCP) sık sık ortaya çıkar hesaplama mekaniği ve iyi bilinenleri kapsar ikinci dereceden programlama özel bir durum olarak. Cottle tarafından önerilmiş ve Dantzig 1968'de.^[1]^[2]^[3]

Formülasyon

Gerçek bir matris verildiğinde M ve vektör qdoğrusal tamamlayıcılık problemi LCP (q, M) vektörler arar z ve w aşağıdaki kısıtlamaları karşılayan:

${ displaystyle w, z geqslant 0,}$ (yani, bu iki vektörün her bir bileşeni negatif değildir)
${ displaystyle z ^ {T} w = 0}$ Veya eşdeğer olarak ${ displaystyle nolimits _ {i} w_ {i} z_ {i} = 0.}$ Bu tamamlayıcılık koşul, çünkü bunu ima ettiği için, herkes için ${ displaystyle i}$ , en fazla biri ${ displaystyle w_ {i}}$ ve ${ displaystyle z_ {i}}$ olumlu olabilir.
${ displaystyle w = Mz + q}$

Bu soruna bir çözümün varlığı ve benzersizliği için yeterli bir koşul, M olmak simetrik pozitif tanımlı. Eğer M şekildedir $LCP (q, M)$ her biri için bir çözüme sahip olmak q, sonra M bir Q matrisi. Eğer M şekildedir $LCP (q, M)$ her biri için benzersiz bir çözüme sahip q, sonra M bir P-matrisi. Bu karakterizasyonların her ikisi de yeterli ve gereklidir.^[4]

Vektör w bir gevşek değişken,^[5] ve bu nedenle genellikle sonra atılır z bulunan. Bu nedenle, sorun şu şekilde de formüle edilebilir:

${ displaystyle Mz + q geqslant 0}$
${ displaystyle z geqslant 0}$
${ displaystyle z ^ { mathrm {T}} (Mz + q) = 0}$ (tamamlayıcılık koşulu)

Konveks ikinci dereceden minimizasyon: Minimum koşullar

Doğrusal tamamlayıcılık problemine bir çözüm bulmak, ikinci dereceden fonksiyonun en aza indirilmesi ile ilişkilidir.

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

kısıtlamalara tabi

{ displaystyle {Mz} + q geqslant 0}

{ displaystyle z geqslant 0}

Bu kısıtlamalar şunları sağlar: f her zaman negatif değildir. Minimum f 0'da z ancak ve ancak z doğrusal tamamlayıcılık problemini çözer.

Eğer M dır-dir pozitif tanımlı, (kesinlikle) dışbükey çözme algoritması QP'ler LCP'yi çözebilir. Özel olarak tasarlanmış temel değişim pivot algoritmaları, örneğin Lemke algoritması ve bir varyantı Dantzig'in simpleks algoritması onlarca yıldır kullanılmaktadır. Polinom zaman karmaşıklığına sahip olmanın yanı sıra, iç-nokta yöntemleri de pratikte etkilidir.

Ayrıca, ikinci dereceden programlama problemi minimize olarak ${ displaystyle f (x) = c ^ {T} x + { tfrac {1} {2}} x ^ {T} Qx}$ tabi ${ displaystyle Ax geqslant b}$ Hem de ${ displaystyle x geqslant 0}$ ile Q simetrik

LCP'yi çözmekle aynı şey

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

Bunun nedeni Karush – Kuhn – Tucker QP probleminin koşulları şu şekilde yazılabilir:

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

ile v Negatif olmayan sınırlamalara ilişkin Lagrange çarpanları, λ eşitsizlik kısıtlamalarının çarpanları ve s eşitsizlik kısıtlamaları için gevşek değişkenler. Dördüncü koşul, her değişken grubunun tamamlayıcılığından türemiştir. $(x, s)$ KKT vektörleri kümesi (optimal Lagrange çarpanları) $(v, λ)$ . Bu durumda,

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

Negatif olmayan kısıtlama x gevşediği sürece, BYT sorununun boyutluluğu eşitsizliklerin sayısına indirgenebilir. Q tekil değildir (eğer öyleyse garantilidir pozitif tanımlı ). Çarpanlar v artık mevcut değildir ve ilk KKT koşulları şu şekilde yeniden yazılabilir:

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

veya:

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

iki tarafı önceden çarparak Bir ve çıkarma b elde ederiz:

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

İkinci KKT durumundan dolayı sol taraf, s. Değiştirme ve yeniden sıralama:

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

Şimdi aranıyor

{ displaystyle { başlar {hizalı} M &: = (AQ ^ {- 1} A ^ {T}) q &: = (- AQ ^ {- 1} c-b) end {hizalı}}}

gevşek değişkenler arasındaki tamamlayıcılık ilişkisi nedeniyle bir LCP'ye sahibiz s ve Lagrange çarpanları λ. Çözdüğümüzde, değerini elde edebiliriz x itibaren λ ilk KKT koşulu ile.

Son olarak, ek eşitlik kısıtlamalarının üstesinden gelmek de mümkündür:

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

Bu, Lagrange çarpanlarının bir vektörünü sunar μile aynı boyutta ${ displaystyle b_ {eq}}$ .

Doğrulamak kolaydır. M ve Q LCP sistemi için ${ displaystyle s = M { lambda} + Q}$ şimdi şu şekilde ifade edilmektedir:

{ 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} S & A_ {eq} ^ {T} - A_ {eq} & 0 end {bmatrix}} ^ {- 1} { begin {bmatrix} c b_ {eq} end {bmatrix}} - b end {hizalı}}}

Nereden λ şimdi her ikisinin de değerlerini kurtarabiliriz x ve Lagrange çarpanı eşitlik μ:

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

Aslında, çoğu QP çözücüsü, LCP formülasyonu üzerinde çalışır. iç nokta yöntemi, ana / tamamlayıcılık ekseninde dönme ve aktif küme yöntemler.^[1]^[2] LCP sorunları şu yöntemlerle de çözülebilir: çaprazlama algoritması,^[6]^[7]^[8]^[9] tersine, doğrusal tamamlayıcılık problemleri için, çaprazlama algoritması sadece matrisin yeterli bir matris olması durumunda sonlu olarak sonlanır.^[8]^[9] Bir yeterli matris hem bir genellemedir pozitif tanımlı matris ve bir P-matrisi, kimin asıl küçükler her biri olumlu.^[8]^[9]^[10]Bu tür LCP'ler soyut olarak formüle edildiklerinde çözülebilir. yönelimli matroid teori.^[11]^[12]^[13]

Ayrıca bakınız

Tamamlayıcılık teorisi
Fizik motoru Oyunlar için dürtü / kısıtlama tipi fizik motorları bu yaklaşımı kullanır.
İletişim dinamikleri Pürüzsüz olmayan yaklaşımla temas dinamikleri.
Bimatrix oyunları bir LCP'ye indirgenebilir.

Notlar

^ ^a ^b Murty (1988)
^ ^a ^b Cottle, Pang ve Stone (1992)
^ R. W. Cottle ve G. B. Dantzig. Matematiksel programlamanın tamamlayıcı pivot teorisi. Doğrusal Cebir ve Uygulamaları, 1:103-125, 1968.
^ Murty, Katta G. (Ocak 1972). "Tamamlayıcılık sorununa çözüm sayısı ve tamamlayıcı konilerin kapsayıcı özellikleri hakkında" (PDF). Doğrusal Cebir ve Uygulamaları. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5. hdl:2027.42/34188.
^ Taylor, Joshua Adam (2015), Güç Sistemlerinin Konveks Optimizasyonu, Cambridge University Press, s. 172, ISBN 9781107076877.
^ Fukuda ve Namiki (1994)
^ Fukuda ve Terlaky (1997)
^ ^a ^b ^c den Hertog, D .; Roos, C .; Terlaky, T. (1 Temmuz 1993). "Doğrusal tamamlayıcılık sorunu, yeterli matrisler ve çaprazlama yöntemi" (PDF). Doğrusal Cebir ve Uygulamaları. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.CS1 Maint: birden çok isim: yazarlar listesi (bağlantı)
^ ^a ^b ^c Csizmadia, Zsolt; Illés, Tibor (2006). "Yeterli matrisler ile doğrusal tamamlayıcılık problemleri için yeni çapraz tip algoritmalar" (PDF). Optimizasyon Yöntemleri ve Yazılımları. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID 24418835.
^ Cottle, R.W.; Pang, J.-S .; Venkateswaran, V. (Mart – Nisan 1989). "Yeterli matrisler ve doğrusal tamamlayıcılık problemi". Doğrusal Cebir ve Uygulamaları. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. BAY 0986877.CS1 bakimi: ref = harv (bağlantı)
^ Todd (1985)
^ Terlaky ve Zhang (1993): Terlaky, Tamás; Zhang, Shu Zhong (1993). "Doğrusal programlama için pivot kuralları: Son teorik gelişmeler üzerine bir anket". Yöneylem Araştırması Yıllıkları. Optimizasyon problemlerinde dejenerelik. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007 / BF02096264. ISSN 0254-5330. BAY 1260019. S2CID 6058077.CS1 bakimi: ref = harv (bağlantı)
^ Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; Beyaz, Neil; Ziegler, Günter (1999). "10 Doğrusal programlama". Odaklı Matroidler. Cambridge University Press. sayfa 417–479. doi:10.1017 / CBO9780511586507. ISBN 978-0-521-77750-6. BAY 1744046.CS1 Maint: birden çok isim: yazarlar listesi (bağlantı)

Referanslar

Cottle, Richard W .; Pang, Jong-Shi; Taş Richard E. (1992). Doğrusal tamamlayıcılık sorunu. Bilgisayar Bilimi ve Bilimsel Hesaplama. Boston, MA: Academic Press, Inc. s. Xxiv + 762 s. ISBN 978-0-12-192350-1. BAY 1150683.CS1 bakimi: ref = harv (bağlantı)
Cottle, R.W.; Pang, J.-S .; Venkateswaran, V. (Mart – Nisan 1989). "Yeterli matrisler ve doğrusal tamamlayıcılık problemi". Doğrusal Cebir ve Uygulamaları. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. BAY 0986877.CS1 bakimi: ref = harv (bağlantı)
Csizmadia, Zsolt; Illés, Tibor (2006). "Yeterli matrisler ile doğrusal tamamlayıcılık problemleri için yeni çapraz tip algoritmalar" (PDF). Optimizasyon Yöntemleri ve Yazılımları. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID 24418835.
Fukuda, Komei; Namiki, Makoto (Mart 1994). "Murty'nin en az indeks yönteminin aşırı davranışları üzerine". Matematiksel Programlama. 64 (1): 365–370. doi:10.1007 / BF01582581. BAY 1286455. S2CID 21476636.CS1 bakimi: ref = harv (bağlantı)
den Hertog, D .; Roos, C .; Terlaky, T. (1 Temmuz 1993). "Doğrusal tamamlayıcılık sorunu, yeterli matrisler ve çaprazlama yöntemi" (PDF). Doğrusal Cebir ve Uygulamaları. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.CS1 bakimi: ref = harv (bağlantı)
Murty, K. G. (1988). Doğrusal tamamlayıcılık, doğrusal ve doğrusal olmayan programlama. Uygulamalı Matematikte Sigma Serileri. 3. Berlin: Heldermann Verlag. s. xlviii + 629 s. ISBN 978-3-88538-403-8. BAY 0949214. Katta G. Murty'nin web sitesinde güncellenmiş ve ücretsiz PDF sürümü. Arşivlenen orijinal 2010-04-01 tarihinde.CS1 bakimi: ref = harv (bağlantı)
Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (editörler). "Criss-cross yöntemleri: Pivot algoritmalarına yeni bir bakış". Matematiksel Programlama, B Serisi. 1997'de Lozan'da düzenlenen 16. Uluslararası Matematiksel Programlama Sempozyumu'ndan makaleler. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007 / BF02614325. BAY 1464775. S2CID 2794181. Postscript ön baskısı.CS1 bakimi: ref = harv (bağlantı)
Todd, Michael J. (1985). "Yönlendirilmiş matroidlerde doğrusal ve ikinci dereceden programlama". Kombinatoryal Teori Dergisi. B Serisi 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. BAY 0811116.CS1 bakimi: ref = harv (bağlantı)
R. Chandrasekaran. "Bimatrix oyunları" (PDF). s. 5–7. Alındı 18 Aralık 2015.

daha fazla okuma

R. W. Cottle ve G. B. Dantzig. Matematiksel programlamanın tamamlayıcı pivot teorisi. Doğrusal Cebir ve Uygulamaları, 1:103-125, 1968.
Terlaky, Tamás; Zhang, Shu Zhong (1993). "Doğrusal programlama için pivot kuralları: Son teorik gelişmeler üzerine bir anket". Yöneylem Araştırması Yıllıkları. Optimizasyon problemlerinde dejenerelik. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007 / BF02096264. ISSN 0254-5330. BAY 1260019. S2CID 6058077.CS1 bakimi: ref = harv (bağlantı)

Dış bağlantılar

LCPSolve - GAUSS'ta doğrusal bir tamamlayıcılık problemini çözmek için basit bir prosedür
Siconos / Lemke'nin C algoritmasında Numerics açık kaynaklı GPL uygulaması ve LCP'leri ve MLCP'leri çözmek için diğer yöntemler

[Murty88-1] Murty (1988)

[CPS92-2] Cottle, Pang ve Stone (1992)

[3] R. W. Cottle ve G. B. Dantzig. Matematiksel programlamanın tamamlayıcı pivot teorisi. Doğrusal Cebir ve Uygulamaları, 1:103-125, 1968.

[4] Murty, Katta G. (Ocak 1972). "Tamamlayıcılık sorununa çözüm sayısı ve tamamlayıcı konilerin kapsayıcı özellikleri hakkında" (PDF). Doğrusal Cebir ve Uygulamaları. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5. hdl:2027.42/34188.

[5] Taylor, Joshua Adam (2015), Güç Sistemlerinin Konveks Optimizasyonu, Cambridge University Press, s. 172, ISBN 9781107076877.

[6] Fukuda ve Namiki (1994)

[7] Fukuda ve Terlaky (1997)

[HRT-8] Hertog, D .; Roos, C .; Terlaky, T. (1 Temmuz 1993). "Doğrusal tamamlayıcılık sorunu, yeterli matrisler ve çaprazlama yöntemi" (PDF). Doğrusal Cebir ve Uygulamaları. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.CS1 Maint: birden çok isim: yazarlar listesi (bağlantı)

[CIsufficient-9] Csizmadia, Zsolt; Illés, Tibor (2006). "Yeterli matrisler ile doğrusal tamamlayıcılık problemleri için yeni çapraz tip algoritmalar" (PDF). Optimizasyon Yöntemleri ve Yazılımları. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID 24418835.

[10] Cottle, R.W.; Pang, J.-S .; Venkateswaran, V. (Mart – Nisan 1989). "Yeterli matrisler ve doğrusal tamamlayıcılık problemi". Doğrusal Cebir ve Uygulamaları. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. BAY 0986877.CS1 bakimi: ref = harv (bağlantı)

[Todd-11] Todd (1985)

[12] Terlaky ve Zhang (1993): Terlaky, Tamás; Zhang, Shu Zhong (1993). "Doğrusal programlama için pivot kuralları: Son teorik gelişmeler üzerine bir anket". Yöneylem Araştırması Yıllıkları. Optimizasyon problemlerinde dejenerelik. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007 / BF02096264. ISSN 0254-5330. BAY 1260019. S2CID 6058077.CS1 bakimi: ref = harv (bağlantı)

[13] Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; Beyaz, Neil; Ziegler, Günter (1999). "10 Doğrusal programlama". Odaklı Matroidler. Cambridge University Press. sayfa 417–479. doi:10.1017 / CBO9780511586507. ISBN 978-0-521-77750-6. BAY 1744046.CS1 Maint: birden çok isim: yazarlar listesi (bağlantı)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Tamamlayıcılık problemleri ve algoritmaları
Tamamlayıcılık Sorunları	Doğrusal programlama (LP) Karesel programlama (QP) Doğrusal tamamlayıcılık sorunu (LCP) Karışık doğrusal (MLCP) Karışık (MCP) Doğrusal Olmayan (NCP)
Temel -değişim algoritmaları	Basit (Dantzig ) Revize edilmiş simpleks Criss-cross Lemke