Doğrusal tamamlayıcılık
Gelen matematik ve daha özel olarak işlemler araştırma ve optimizasyonu , bir doğrusal tamamlayıcılık sorun matris verileri ile tanımlanır ve bir vektör ve bir vektörün bulunmasında meydana gelmektedir bileşenleri ve bu şekilde pozitif ve şekildedir ve ortogonal olan Öklid skaler çarpımı :
M∈Rdeğil×değil{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}
q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}
x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
y: =Mx+q{\ displaystyle y: = Mx + q}
x{\ displaystyle x}
y{\ displaystyle y}
Rdeğil{\ displaystyle \ mathbb {R} ^ {n}}
x⩾0,Mx+q⩾0vex⊤(Mx+q)=0,{\ displaystyle x \ geqslant 0, \ qquad Mx + q \ geqslant 0 \ qquad {\ mbox {et}} \ qquad x ^ {\! \ top} (Mx + q) = 0,}
nerede transpoze vektörü belirtir . Bu sorun, özel bir varyasyonel eşitsizlik durumu olarak görülebilir .
x⊤{\ displaystyle x ^ {\ top}}
x{\ displaystyle x}
Bu problemler genellikle NP açısından zordur ve bu nedenle problemin boyutu büyüdüğünde çözülmesi zordur . Bir kombinasyon sorun sıfır ve orada çözeltinin bileşenleri belirlemek için gerekli olan olmasından kaynaklanır , bu elde etmek için olasılık.
değil{\ displaystyle n}
2değil{\ displaystyle 2 ^ {n}}
Tamamlayıcılık problemleri ilk olarak optimizasyon problemlerinin optimallik koşullarında, Karush, Kuhn ve Tucker'ın koşullarında kendini gösterdi . Bir bakıma rekabet içinde olan çeşitli denklem sistemleri tarafından tanımlanan problemleri modellemeyi mümkün kılarlar; olanı ortak bir dizine karşılık gelen, belirli bir yerde ve zamanda aktiftir ve eşik eğer: ya ulaşamamış eşikleri bağlıdır ulaşılamaması, yani o , denklem devreye girer. Tamamlayıcılıkla modellenen problem örnekleri çoktur; temas problemleri, çok fazlı akışlarda fazların ortaya çıkması ve kaybolması problemleri, çökelme-çözünme problemleri kimyası, meteoroloji vb .
x{\ displaystyle x}y{\ displaystyle y}xben=0{\ displaystyle x_ {i} = 0}
xben>0{\ displaystyle x_ {i}> 0}
(Mx+q)ben=0{\ displaystyle (Mx + q) _ {i} = 0}
Sorun
Bazı notlar
Bir vektör için gösterim , vektörün tüm bileşenlerinin pozitif veya sıfır olduğu anlamına gelir .
v∈Rdeğil{\ displaystyle v \ in \ mathbb {R} ^ {n}}
v⩾0{\ displaystyle v \ geqslant 0}
vben{\ displaystyle v_ {i}}
Biz ifade pozitif orthant arasında .
R+değil: ={x∈Rdeğil:x⩾0}{\ displaystyle \ mathbb {R} _ {+} ^ {n}: = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0 \}}
Rdeğil{\ displaystyle \ mathbb {R} ^ {n}}
İki parça ve bir vektör uzayı için, küme olan Minkowski toplamını belirtin .
AT{\ displaystyle A}
B{\ displaystyle B}
AT+B{\ displaystyle A + B}
AT+B: ={x+y:x∈AT, y∈B}{\ displaystyle A + B: = \ {x + y: x \ A’da, ~ y \ B’de \}}
Tanımlar
Kare bir gerçek matris göz önüne alındığında , zorunlu olarak simetrik olmayan , ve bir vektör , bir doğrusal tamamlayıcılık sorun bir vektörün bulunmasında meydana gelmektedir şekilde
M∈Rdeğil×değil{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
x⩾0,Mx+q⩾0vex⊤(Mx+q)=0.{\ displaystyle x \ geqslant 0, \ qquad Mx + q \ geqslant 0 \ qquad {\ mbox {et}} \ qquad x ^ {\! \ top} (Mx + q) = 0.}
Yukarıdaki sembol , vektörün soluna transpozisyonunu belirtmek için kullanılır. Bu nedenle, gerekli ortogonalliği ve soran miktarları için Hadamard ürün bu iki vektörün sıfır:
⊤{\ displaystyle {} ^ {\ top}}
x{\ displaystyle x}Mx+q{\ displaystyle Mx + q}
x⋅(Mx+q)=0{\ displaystyle x \ cdot (Mx + q) = 0}
Bu problem genellikle kısaca şu şekilde yazılır:
CL(M,q):0⩽x⊥(Mx+q)⩾0.{\ displaystyle {\ mbox {CL}} (M, q): \ qquad 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.}
Doğrulayan ve sorunu ve seti
için kabul edilebilir olduğu söylenen bir noktax{\ displaystyle x}x⩾0{\ displaystyle x \ geqslant 0}
Mx+q⩾0{\ displaystyle Mx + q \ geqslant 0}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Adm(M,q): ={x∈Rdeğil:x⩾0, Mx+q⩾0}{\ displaystyle {\ mbox {Adm}} (M, q): = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0, ~ Mx + q \ geqslant 0 \}}
bu sorunun kabul edilebilir kümesi olarak adlandırılır . Sorun olduğu söylenir mümkün olsa . Bunu kolayca gösteririz
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}Adm(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}
R+değil-M(R+değil)={q∈Rdeğil:Adm(M,q)≠∅}{\ displaystyle \ mathbb {R} _ {+} ^ {n} -M (\ mathbb {R} _ {+} ^ {n}) = \ {q \ in \ mathbb {R} ^ {n}: { \ mbox {Adm}} (M, q) \ neq \ varnothing \}}
.
Fark ederiz
Zemin(M,q){\ displaystyle {\ mbox {Sol}} (M, q)}
çözümler grubu doğrusal tamamlayıcılık problem ; Bir olan birlik dışbükey polyhedra.
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Diğer sorunlara bağlantılar
İkinci dereceden bir optimizasyon probleminin optimallik koşulları
İkinci dereceden bir optimizasyon probleminin optimallik koşulları, doğrusal bir tamamlayıcılık problemi olarak ifade edilebilir . Aslında, genel ikinci dereceden optimizasyon problemini düşünün
{infx∈Rdeğilg⊤x+12x⊤HxATx⩾bx⩾0,{\ displaystyle \ sol \ {{\ begin {array} {l} \ textstyle \ inf _ {x \ in \ mathbb {R} ^ {n}} \, g ^ {\ top} x + {\ frac {1 } {2}} \, x ^ {\ top} Hx \\ Ax \ geqslant b \\ x \ geqslant 0, \ end {dizi}} \ sağ.}
burada , a, simetrik bir matris (ille pozitif yarı tanımlı), ve . Onun birinci dereceden eniyileme koşulları çarpanları için yazılır ve :
g∈Rdeğil{\ displaystyle g \ in \ mathbb {R} ^ {n}}
H∈Rdeğil×değil{\ displaystyle H \ in \ mathbb {R} ^ {n \ times n}}
AT∈Rm×değil{\ displaystyle A \ in \ mathbb {R} ^ {m \ times n}}
b∈Rm{\ displaystyle b \ in \ mathbb {R} ^ {m}}
y∈Rm{\ displaystyle y \ in \ mathbb {R} ^ {m}}
z∈Rdeğil{\ displaystyle z \ in \ mathbb {R} ^ {n}}
{g+Hx-AT⊤y-z=00⩽y⊥(ATx-b)⩾00⩽z⊥x⩾0.{\ displaystyle \ sol \ {{\ başlar {dizi} {l} g + Hx-A ^ {\ top} yz = 0 \\ 0 \ leqslant y \ perp (Ax-b) \ geqslant 0 \\ 0 \ leqslant z \ perp x \ geqslant 0. \ end {dizi}} \ sağ.}
Çarpanı ortadan kaldırarak, birleştirilmiş iki doğrusal tamamlayıcılık probleminden oluşan bir sistem elde ederiz.
z{\ displaystyle z}
{0⩽y⊥(ATx-b)⩾00⩽(g+Hx-AT⊤y)⊥x⩾0.{\ displaystyle \ sol \ {{\ başlar {dizi} {l} 0 \ leqslant y \ perp (Ax-b) \ geqslant 0 \\ 0 \ leqslant (g + Hx-A ^ {\ top} y) \ perp x \ geqslant 0. \ end {dizi}} \ sağ.}
Bu, benzersiz bir doğrusal tamamlayıcılık problemi olarak ifade edilebilir:
0⩽(xy)⊥(H-AT⊤AT0)(xy)+(g-b)⩾0.{\ displaystyle 0 \ leqslant {\ begin {pmatrix} x \\ y \ end {pmatrix}} \ perp {\ begin {pmatrix} H & -A ^ {\ top} \\ A & 0 \ end {pmatrix}} {\ begin {pmatrix} x \\ y \ end {pmatrix}} + {\ begin {pmatrix} g \\ - b \ end {pmatrix}} \ geqslant 0.}
Ayrıca, zaman simetrik yarı tanımlı pozitif olan sorun, ikinci dereceden optimizasyon problemine eşdeğerdirM∈Rdeğil×değil{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}
{infx∈Rdeğilq⊤x+12x⊤Mxx⩾0.{\ displaystyle \ sol \ {{\ begin {array} {l} \ textstyle \ inf _ {x \ in \ mathbb {R} ^ {n}} \, q ^ {\ top} x + {\ frac {1 } {2}} \, x ^ {\ top} Mx \\ x \ geqslant 0. \ end {dizi}} \ sağ.}
Gerçekten de, belirtilen koşullar altında, ikinci dereceden optimizasyon problemi onun eşdeğerdir birinci dereceden eniyilik koşulları : varolduğundan şekilde
(x,z)∈Rdeğil×Rdeğil{\ displaystyle (x, z) \ in \ mathbb {R} ^ {n} \ times \ mathbb {R} ^ {n}}
{q+Mx-z=00⩽x⊥z⩾0.{\ displaystyle \ left \ {{\ begin {array} {l} q + Mx-z = 0 \\ 0 \ leqslant x \ perp z \ geqslant 0. \ end {dizi}} \ sağ.}
Çarpanı eledikten sonra elde ederiz .
z{\ displaystyle z}CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}
İkinci dereceden bir optimizasyon problemi olarak ifade
Düşünün kuadratik optimizasyon sorunu ile aşağıdaki:
x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
(PQ){minx⊤(Mx+q)x⩾0Mx+q⩾0.{\ displaystyle {\ mbox {(PQ)}} \ qquad \ sol \ {{\ başlar {dizi} {l} \ min \; x ^ {\! \ top} (Mx + q) \\ x \ geqslant 0 \\ Mx + q \ geqslant 0. \ end {dizi}} \ sağ.}
Doğrusal tamamlayıcılık problemi kabul edilebilir ise, yani ikinci dereceden problemin kabul edilebilir kümesi boş değil. Bu durumda, bu ikinci dereceden problemin bir çözümü vardır (çünkü maliyeti kabul edilebilir sete göre daha düşük sınırlıdır - orada pozitiftir, bkz. Frank ve Wolfe, 1956) ve dolayısıyla sabit noktalar . Fark ederiz
CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}Adm(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}(PQ){\ displaystyle ({\ mbox {PQ}})}
Sta(M,q){\ displaystyle {\ mbox {Sta}} (M, q)}
kümesi sabit noktaları kuadratik optimizasyon sorununun . Elimizde ve önceki gerekçeye göre,
(PQ){\ displaystyle ({\ mbox {PQ}})}Zemin(M,q)⊂Sta(M,q)⊂Adm(M,q){\ displaystyle {\ mbox {Sol}} (M, q) \ subset {\ mbox {Sta}} (M, q) \ subset {\ mbox {Adm}} (M, q)}
Adm(M,q)≠∅⟹Sta(M,q)≠∅.{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing \ qquad \ Longrightarrow \ qquad {\ mbox {Sta}} (M, q) \ neq \ varnothing.}
Elbette var
x∈Zemin(M,q)⟺x{\ displaystyle x \ in \ operatorname {Sol} (M, q) \ quad \ Longleftrightarrow \ quad x}
sıfır optimum maliyetle (PQ) çözümüdür.
Bununla birlikte, (PQ) genel olarak dışbükey olmayan bir problemdir, bu nedenle (PQ) 'dan geçme çözünürlüğü kolay değildir.
CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}
Varyasyonel eşitsizliğin özel durumu
Problemi varyasyon eşitsizlik ile skalar ürün vasıtası ile tanımlanır ile , bir bütün boş olmayan bir fonksiyonu . Bu bir noktayı bulmakta oluşur şekildedir
Rdeğil{\ displaystyle \ mathbb {R} ^ {n}}⟨⋅,⋅⟩{\ displaystyle \ langle \ cdot, \ cdot \ rangle}
Rdeğil{\ displaystyle \ mathbb {R} ^ {n}}K⊂Rdeğil{\ displaystyle K \ altkümesi \ mathbb {R} ^ {n}}
F:K→Rdeğil{\ displaystyle F: K \ - \ mathbb {R} ^ {n}}
x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
{x∈K⟨F(x),y-x⟩⩾0,∀y∈K.{\ displaystyle \ left \ {{\ begin {array} {l} x \ in K \\\ langle F (x), yx \ rangle \ geqslant 0, \ quad \ forall y \ in K \ end {array} } \ sağ.}
İç çarpım Öklid sklalar çarpımı ise, pozitif orthant ise ve eğer , yukarıdaki varyasyonel eşitsizlik problemi doğrusal tamamlayıcılık probleminden başka bir şey değildir .
⟨sen,v⟩: =sen⊤v{\ displaystyle \ langle u, v \ rangle: = u ^ {\ top} v}
K{\ displaystyle K}
R+değil{\ displaystyle \ mathbb {R} _ {+} ^ {n}}
F:x∈R+değil↦(Mx+q)∈Rdeğil{\ displaystyle F: x \ in \ mathbb {R} _ {+} ^ {n} \ mapsto (Mx + q) \ in \ mathbb {R} ^ {n}}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Denklemleri kullanarak reformülasyonlar
Doğrusal tamamlayıcılık sorununu denklemler aracılığıyla ifade edebiliriz , genel olarak pürüzsüz değil, yani türevlenemez. Bu formülasyona müdahale eden ve sıfır aranan fonksiyonlara C fonksiyonları (tamamlayıcılık için C) denir . Bu formülasyon, çözünürlük algoritmaları tarafından kullanılır.
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Bunun bir C işlevi olduğunu söylüyoruz, eğer
f:R2→R{\ displaystyle f: \ mathbb {R} ^ {2} \ - \ mathbb {R}}
f(-de,b)=0⟺-deb=0,-de⩾0,b⩾0.{\ displaystyle f (a, b) = 0 \ qquad \ Longleftrightarrow \ qquad ab = 0, \ quad a \ geqslant 0, \ quad b \ geqslant 0.}
Böylece bir C fonksiyonu, problemi doğrusal olmayan denklemler sistemi
ile değiştirmeyi mümkün kılar.CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
F(x)=0,{\ displaystyle F (x) = 0,}
bileşeni nerede tanımlanır
F:Rdeğil→Rdeğil{\ displaystyle F: \ mathbb {R} ^ {n} \ - \ mathbb {R} ^ {n}}
ben{\ displaystyle i}
Fben(x)=f(Fben(x),Gben(x)).{\ displaystyle F_ {i} (x) = f (F_ {i} (x), G_ {i} (x)).}
Türevlenebilir C-fonksiyonlarına sahip olmaya hiç ilgi yoktur , çünkü o zaman dejenere bir çözümde tersine çevrilemez (ve bu nedenle Newton'un algoritması çalışmaz). Görünüşe göre pürüzsüz olmayan C fonksiyonları daha verimli algoritmalara yol açıyor.
f{\ displaystyle f}
F′(x){\ displaystyle F '(x)}
x{\ displaystyle x}
Aşağıda, C-fonksiyonlarına ve özelliklerine ilişkin bazı örnekler verilmiştir.
C fonksiyonu min
En basit C işlevi, minimum işlevdir :
fmin(-de,b)=min(-de,b).{\ displaystyle f _ {\ min} (a, b) = \ min (a, b).}
Kostreva (1976) ve Mangasarian (1977) tarafından ilk kez önerilmiş gibi görünüyor. Bunun gerçekten bir C fonksiyonu olduğunu kolayca gösterebiliriz. O zamandan beri
min(x,Mx+q)=0⟺x∈Zemin(M,q),{\ displaystyle \ min (x, Mx + q) = 0 \ qquad \ Longleftrightarrow \ qquad x \ {\ mbox {Sol}} (M, q),}
burada min işlevi, bileşene göre bileşeni etkiler: herhangi bir dizin için .
min(sen,v)ben=min(senben,vben){\ displaystyle \ min (u, v) _ {i} = \ min (u_ {i}, v_ {i})}
ben{\ displaystyle i}
Fischer-Burmeister C işlevi
Fischer-Burmeister fonksiyonu ile tanımlanır:
fFB(-de,b)=-de2+b2-(-de+b).{\ displaystyle f _ {\ rm {\ scriptscriptstyle FB}} (a, b) = {\ sqrt {a ^ {2} + b ^ {2}}} - (a + b).}
Bir C-fonksiyonu olduğunu, dışbükey olduğunu, dışında her yerde türevlenebilir olduğunu ve karesinin sürekli türevlenebilir olduğunu kolayca gösterebiliriz .
(0,0){\ displaystyle (0,0)}
Uygun matrisler galerisi
Doğrusal tamamlayıcılık problemlerinin özellikleri elbette matrisinkilere bağlıdır . Bu özellikler çok çeşitlidir ve tek bir matrise bağlı değildir. Bu nedenle durum, özellikleri büyük ölçüde sistemi tanımlayan matrisin tersine çevrilebilirliğine bağlı olan bir doğrusal denklem sisteminin çözümünde karşılaşılandan çok daha karmaşık ve çok farklıdır . Bazı dikkate değer matris sınıflarını ve bunlarla ilişkili doğrusal tamamlayıcılık probleminin özelliklerini aşağıda listeledik . Bu matris sınıfları genellikle (ancak her zaman değil) üyelerinin tanınmasına izin veren cebirsel karakterizasyonlara sahiptir.
M{\ displaystyle M}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
- Aşağıdaki monotonluk özelliğiyle -matrisler , problem için çözümün varlığını ve benzersizliğini sağlayanlardır :M{\ displaystyle \ mathbf {M}}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
x¯1∈Zemin(M,q1),x¯2∈Zemin(M,q2),q1⩽q2⟹x¯1⩾x¯2.{\ displaystyle {\ bar {x}} ^ {1} \ in \ operatorname {Sol} (M, q ^ {1}), \ quad {\ bar {x}} ^ {2} \ in \ operatorname {Sol } (M, q ^ {2}), \ quad q ^ {1} \ leqslant q ^ {2} \ quad \ Longrightarrow \ quad {\ bar {x}} ^ {1} \ geqslant {\ bar {x} } ^ {2}.}
- Dejenere olmayan matrisler ne olursa olsun kendisi için olanlar vardır olası çözüm, lokal olarak benzersizdir.q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
- Sütununda yeterli matrisler çözümler kümesi dışbükeyliğini sağlamak olanlardır , ne olursa olsun .Zemin(M,q){\ displaystyle \ operatöradı {Sol} (M, q)}
q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}
- Yeterli çevrimiçi matrisler ne olursa olsun bu sağlamak olanlardır , çözeltiler grubu ilişkili ikinci dereceden bir sorun (PQ) sabit noktaları kümesi ile aynıdır.q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}Zemin(M,q){\ displaystyle \ operatöradı {Sol} (M, q)}
- -Matrisleri varlığını ve sorunun çözümü benzersizliğini sağlamak verenlerdir , ne olursa olsun .P{\ displaystyle \ mathbf {P}}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}
- -Matrisleri sorunun çözümünün varlığını sağlamak verenlerdir , her neyse .Q{\ displaystyle \ mathbf {Q}}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}
- -Matrisleri sorun sağlamak olanlardır bu mümkün olduğunda, bir çözüm vardır.Q0{\ displaystyle \ mathbf {Q_ {0}}}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
- -Matrisleri sağlamak olanlardır tek çözüm .R0{\ displaystyle \ mathbf {R_ {0}}}
x=0{\ displaystyle x = 0}
CL(M,0){\ displaystyle {\ mbox {CL}} (M, 0)}
- -Matrisleri o kabul set sağlamak verenlerdir , ne olursa olsun .S{\ displaystyle \ mathbf {S}}
Adm(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}
- -Matrisleri (sipariş için minimum varlığını sağlamak olanlardır ait ait) bir çözüm olduğunu, her şeyin için, ayarlanan kabuledilebilir yapma .Z{\ displaystyle \ mathbf {Z}}
⩽{\ displaystyle \ leqslant}
Rdeğil{\ displaystyle \ mathbb {R} ^ {n}}Adm(M,q){\ displaystyle {\ mbox {Adm}} (M, q)}
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}q{\ displaystyle q}
Adm(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}
Çözümün varlığı
Doğrusal bir tamamlayıcılık sorununun bir çözümü olduğunu göstermek için (en az) iki strateji belirleriz. İlki, ilgili ikinci dereceden problem (PQ) ve optimallik koşullarından geçer. İkincisi, Brouwer'in sabit nokta teoremine dayanmaktadır . Bugün (2013) bu soruyu özellikle ele aldığımızı düşünmüyoruz, çünkü vektör ne olursa olsun bir çözümün varlığını sağlayan Q-matris sınıflarını cebirsel olarak nasıl tanımlayacağımızı bilmiyoruz .
q{\ displaystyle q}
Optimizasyon yaklaşımı
Bu yaklaşımda, ikinci dereceden problemin (PQ) optimal bir sıfır değerine sahip olduğunu göstermeye çalışıyoruz . Bu ikinci dereceden problemin bir çözümü olduğu için (Frank ve Wolfe, 1956), bu, doğrusal tamamlayıcılık probleminin bir çözümüdür .
CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}
Örneğin, doğrusal tamamlayıcılık sorun durumda bir çözüm olduğunu göstermek için bir edilir -Matris biz bilgileri eniyilik koşulları arasında (PQ) bir çözelti içinde : kısıtlamaları gibi kalifiye , uygun çarpanları orada var ve bu şekilde
M{\ displaystyle M}P{\ displaystyle \ mathbf {P}}x{\ displaystyle x}s{\ displaystyle s}
z{\ displaystyle z}
{(-de)(M+M⊤)x+q-s-M⊤z=0(b)0⩽x⊥s⩾0(vs)0⩽(Mx+q)⊥z⩾0.{\ displaystyle \ sol \ {{\ başlar {dizi} {ll} (a) & (M + M ^ {\ top}) x + qsM ^ {\ top} z = 0 \\ (b) & 0 \ leqslant x \ perp s \ geqslant 0 \\ (c) & 0 \ leqslant (Mx + q) \ perp z \ geqslant 0. \ end {dizi}} \ sağ.}
(C) 'den çıkarmak için bunun bir çözümü olduğunu göstermek yeterlidir . Bazı akıllıca cebirsel manipülasyonlara, biz elde edebilirsiniz olduğu sonucunu getirir sayesinde -matricity arasında o çıkarılır, .
z=x{\ displaystyle z = x}
x{\ displaystyle x}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}(x-z)⋅M⊤(x-z)⩽0{\ displaystyle (xz) \ cdot M ^ {\ top} (xz) \ leqslant 0}
z=x{\ displaystyle z = x}P{\ displaystyle \ mathbf {P}}M⊤{\ displaystyle M ^ {\ top}}
M{\ displaystyle M}
Sabit nokta yaklaşımı
Bu yaklaşımda, aşağıdakilerle tanımlanan artırılmış bir doğrusal tamamlayıcılık problemini tanıtarak başlıyoruz .
CL(M~,q~){\ displaystyle {\ mbox {CL}} ({\ tilde {M}}, {\ tilde {q}})}
M~=(Mp-p⊤0)∈R(değil+1)×(değil+1)veq~=(qr)∈Rdeğil+1,{\ displaystyle {\ tilde {M}} = {\ begin {pmatrix} M & p \\ - p ^ {\ top} & 0 \ end {pmatrix}} \ in \ mathbb {R} ^ {(n + 1 ) \ times (n + 1)} \ qquad {\ mbox {et}} \ qquad {\ tilde {q}} = {\ begin {pmatrix} q \\ r \ end {pmatrix}} \ in \ mathbb {R } ^ {n + 1},}
nerede ve . Bu sorun, iki birleştirilmiş lineer tamamlayıcılık sorunları, bir bir sistem olarak yazılır , diğer :
p∈Rdeğil{\ displaystyle p \ in \ mathbb {R} ^ {n}}
r∈R{\ displaystyle r \ in \ mathbb {R}}
x∈Rdeğil{\ displaystyle x \ in \ mathbb {R} ^ {n}}α∈R{\ displaystyle \ alpha \ in \ mathbb {R}}
{(-de)0⩽x⊥(Mx+q+αp)⩾0(b)0⩽α⊥(r-p⊤x)⩾0.{\ displaystyle \ sol \ {{\ başlar {dizi} {ll} (a) & 0 \ leqslant x \ perp (Mx + q + \ alpha p) \ geqslant 0 \\ (b) & 0 \ leqslant \ alpha \ perp (rp ^ {\ top} x) \ geqslant 0. \ end {dizi}} \ sağ.}
Biz gösteren başarılı olursa görüyoruz bir çözümü vardır ile , çözümünü olacaktır (tarafından yukarıdaki sorunun ). Çoğu zaman, bu koşullar yalnızca sınırı geçtikten sonra elde edilir.
CL(M~,q~){\ displaystyle {\ mbox {CL}} ({\ tilde {M}}, {\ tilde {q}})}(x,α){\ displaystyle (x, \ alpha)}
α=0{\ displaystyle \ alpha = 0}
x{\ displaystyle x}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}(-de){\ displaystyle (a)}
Artırılmış sorunun çözümünün varlığı
Bu nedenle ilk adım seçim yapmaktır ve böylece artan sorunun bir çözümü vardır. İşte iki sonuç var, ilki simetrik olduğunu varsayıyor , ikincisi değil.
p∈Rdeğil{\ displaystyle p \ in \ mathbb {R} ^ {n}}r∈R{\ displaystyle r \ in \ mathbb {R}}CL(M~,q~){\ displaystyle {\ mbox {CL}} ({\ tilde {M}}, {\ tilde {q}})}M{\ displaystyle M}
PCL çözeltisinin varlığı ile artan
simetrik M{\ displaystyle M} - ise , simetrik ve eğer ve yukarıdaki gibidir, ile ve bu şekilde aşağıda sınırlanan , daha sonra bir çözelti.
M{\ displaystyle M}M~{\ displaystyle {\ tilde {M}}}
q~{\ displaystyle {\ tilde {q}}}
p∈Rdeğil{\ displaystyle p \ in \ mathbb {R} ^ {n}}r∈R{\ displaystyle r \ in \ mathbb {R}}x↦12x⊤Mx+q⊤x{\ displaystyle x \ mapsto {\ frac {1} {2}} x ^ {\ top} Mx + q ^ {\ top} x}
{x∈Rdeğil:x⩾0{\ displaystyle \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0}
p⊤x⩽r}≠∅{\ displaystyle p ^ {\ top} x \ leqslant r \} \ neq \ varnothing}
CL(M~,q~){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}})}
Kanıt, belirtilen koşullar altında, ikinci dereceden optimizasyon probleminin
{infx12x⊤Mx+q⊤xx≥0,p⊤x≤r,{\ displaystyle \ sol \ {{\ başlar {dizi} {l} \ textstyle \ inf _ {x} \, {\ frac {1} {2}} x ^ {\ top} Mx + q ^ {\ top} x \\ x \ geq 0, \\ p ^ {\ top} x \ leq r, \ end {dizi}} \ sağ.}
bir çözümü vardır (Frank ve Wolfe, 1956). Bu , birinci derecenin optimallik koşullarını doğrular, bu koşullar ve yukarısı dışında hiçbir şey yoktur .
(-de){\ displaystyle (a)}(b){\ displaystyle (b)}
Ne zaman simetrik değil, biz ifade bir şekilde varyasyon eşitsizlik sorunu olan
M{\ displaystyle M}CL(M~,q~){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}})} IV(F,K){\ displaystyle \ operatöradı {IV} (F, K)}
F:Rdeğil→Rdeğil:x↦Mx+qveK: ={x∈Rdeğil:x⩾0, p⊤x⩽r}.{\ displaystyle F: \ mathbb {R} ^ {n} \ to \ mathbb {R} ^ {n}: x \ mapsto Mx + q \ qquad {\ mbox {ve}} \ qquad K: = \ {x \ \ mathbb {R} ^ {n}: x \ geqslant 0, ~ p ^ {\ top} x \ leqslant r \}.}
Tabii ki dışbükey ve kapalı. Boş olmayan ve sınırlı hale getirmek için (bir IV'ün çözüm varoluş teoremini uygulamak için ), almak doğaldır ve . Daha sonra aşağıdaki sonucu elde ederiz.
K{\ displaystyle K}p>0{\ displaystyle p> 0}
r⩾0{\ displaystyle r \ geqslant 0}
Artar PCL çözeltisinin varlığı - If ve , yukarıda olarak verilmiştir ve ardından bir çözümü vardır.
M~{\ displaystyle {\ tilde {M}}}q~{\ displaystyle {\ tilde {q}}}p>0{\ displaystyle p> 0}r⩾0{\ displaystyle r \ geqslant 0}CL(M~,q~){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}})}
Orijinal sorunun çözümünün varlığı
İkinci adım, bir çözümden başlayarak bir çözüm bulmaya izin veren koşulları vermekten ibarettir . Aşağıdaki sonuç, içindeki ve üzerindeki çarpanın sıfır olması için yeterli koşulları verir .
CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}CL(M~,q~){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}})}α{\ displaystyle \ alpha}
(-de){\ displaystyle (a)}(b){\ displaystyle (b)}
PCL çözümünün varlığının CS - Let ve . Bir vektör varsa ve ikinci dereceden fonksiyon gibi bir skaler pozitif ise , o zaman bir çözüm.
M∈Rdeğil×değil{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}p>0{\ displaystyle p> 0}r>0{\ displaystyle r> 0}
x↦x⊤(Mx+q){\ displaystyle x \ mapsto x ^ {\ top} (Mx + q)}
{x∈Rdeğil:x≥0{\ displaystyle \ {x \ in \ mathbb {R} ^ {n}: x \ geq 0}
p⊤x=r}{\ displaystyle p ^ {\ top} x = r \}}
CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}
Sorunun çözümü varlığının gerekli ve yeterli koşullar altında aşağıda verilmiştir, bunu garanti edemez içinde ve üzerinde, fakat çözeltiler varsayılmaktadır bir sonucu artmıştır sorunlar , bu yapıştığı sıfır şekildedir .
CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}α=0{\ displaystyle \ alpha = 0}(-de){\ displaystyle (a)}(b){\ displaystyle (b)}(xk,αk){\ displaystyle (x_ {k}, \ alpha _ {k})}
CL(M~,q~k){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}} _ {k})}
k∈DEĞİL{\ displaystyle k \ in \ mathbb {N}}
{αk}{\ displaystyle \ {\ alpha _ {k} \}}
PCL çözüm varlığı MSS - Let , ve . Aşağıdaki özellikler eşdeğerdir.
M∈Rdeğil×değil{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rdeğil{\ displaystyle q \ in \ mathbb {R} ^ {n}}p>0{\ displaystyle p> 0}
- Sorunun bir çözümü var.CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}
- Herhangi bir sınırsız sırası için , problemler ile{rk}⊂R+{\ displaystyle \ {r_ {k} \} \ alt küme \ mathbb {R} _ {+}}
CL(M~,q~k){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}} _ {k})}
M~: =(Mp-p⊤0)∈R(değil+1)×(değil+1)veq~k: =(qrk)∈R(değil+1),{\ displaystyle {\ tilde {M}}: = {\ begin {pmatrix} M & p \\ - p ^ {\ top} & 0 \ end {pmatrix}} \ in \ mathbb {R} ^ {(n + 1) \ times (n + 1)} \ qquad {\ mbox {et}} \ qquad {\ tilde {q}} _ {k}: = {\ begin {pmatrix} q \\ r_ {k} \ end { pmatrix}} \ in \ mathbb {R} ^ {(n + 1)},}
sıfırın birikim noktası olduğu gibi çözümlere sahip .(xk,αk){\ displaystyle (x_ {k}, \ alpha _ {k})}{αk}{\ displaystyle \ {\ alpha _ {k} \}}
- Sınırsız bir dizi vardır sorunlar, öyle ki , birlikte nokta 2 olarak verilen çözümleri ile .{rk}⊂R+{\ displaystyle \ {r_ {k} \} \ alt küme \ mathbb {R} _ {+}}CL(M~,q~k){\ displaystyle \ operatorname {CL} ({\ tilde {M}}, {\ tilde {q}} _ {k})}(M~,q~k){\ displaystyle ({\ tilde {M}}, {\ tilde {q}} _ {k})}
(xk,αk){\ displaystyle (x_ {k}, \ alpha _ {k})}αk→0{\ displaystyle \ alpha _ {k} \ ile 0}
Bunu göstermek için bu sonucu kullanabiliriz
- katı ko-pozitif matrisler olan S-matrisler ,
- Bir sorun ile copositive ve ( pozitif ikili ) bir çözümü var.CL(M,q){\ displaystyle \ operatöradı {CL} (M, q)}M{\ displaystyle M} q∈{x∈R+değil:x⊤Mx=0, Mx⩾0}+{\ displaystyle q \ in \ {x \ in \ mathbb {R} _ {+} ^ {n}: x ^ {\ top} Mx = 0, ~ Mx \ geqslant 0 \} ^ {+}}
Çözünürlük yöntemleri
Tahmin edilebileceği gibi, doğrusal bir tamamlayıcılık problemini çözmek için ideal bir algoritma yoktur, ancak özellikleri itibariyle belirli problem sınıflarına az çok uygun olan bir dizi algoritma vardır.
Döndürme yöntemleri
Döndürme yöntemlerinin üstel bir en kötü durum karmaşıklığı vardır. Bu türden algoritmik yaklaşımların bir açıklaması için bkz. Murty (1988), Cottle ve Pang (2009).
-
Lemke algoritması (giriş)
-
Taramalı algoritma (içinde)
- Ana pivot algoritması
İç nokta yöntemleri
Düzgün olmayan yöntemler
Düzgün olmayan ham yöntemler
Burada izlenen strateji, doğrusal tamamlayıcılık problemini bir C fonksiyonu aracılığıyla ifade etmekten ve sonuçta ortaya çıkan pürüzsüz olmayan sistemi Newton'unkilerle ilgili yinelemelerle çözmekten ibarettir .
Düzenli, pürüzsüz olmayan yöntemler
Doğrusal tamamlayıcılık problemini çözülmesi gereken pürüzsüz olmayan bir denklem olarak ifade ediyoruz ( Düzgün olmayan yöntemler bölümüne bakın ) ve onu düzenli hale getiriyoruz. Bu düzenleme, yinelemeler sırasında azaltılan bir parametreye bağlıdır. Örneğin Chen ve Mangasarian'ın (1995) katkısına bakınız.
Bu yaklaşım, iç nokta yaklaşımı ile ilgilidir . Analizleri, karmaşıklığın sonucu olmaksızın (iç noktaların algoritmalarının aksine) hızlı küresel ve yerel yakınsama sonuçlarına yol açar.
Diğer yöntemler
Karmaşıklık
Ekler
Notlar
-
(tr) MJM Janssen (1983). Doğrusal bir tamamlayıcılık probleminin çözüm kümesinin yapısı üzerine. Defterler Merkezi Études Rech. Oper. , 25, 41–48.
-
(en) M. Frank, P. Wolfe (1956). İkinci dereceden programlama için bir algoritma. Naval Research Logistics Quarterly , 3, 95–110.
-
Facchinei ve Pang (2003), önerme 9.1.1.
-
(içinde) Bay Kostreva (1976). Tamamlayıcılık Problemleri için Doğrudan Algoritmalar . Doktora tezi, Rensselaer Polytechnic Institute, Troy, New York.
-
(içinde) O. Mangasarian (1977). Simetrik doğrusal tamamlayıcılık problemlerinin iteratif yöntemlerle çözümü. Optimizasyon Teorisi ve Uygulamaları Dergisi , 22, 465–485.
-
(in) A. Fischer (1992). Özel bir Newton tipi optimizasyon yöntemi. Optimizasyon , 24, 269–284.
-
(in) A. Fischer (1995). Pozitif yarı kesin doğrusal tamamlayıcılık problemleri için Newton tipi bir yöntem. Optimizasyon Teorisi ve Uygulamaları Dergisi , 86, 585–608.
-
(inç) H. Samelson, RM Thrall, Wesler O. (1958). Öklid n- uzayı için bir bölme teoremi . Amerikan Matematik Derneği Bildirileri , 9, 805–807.
-
(içinde) C. Chen, OL Mangasarian (1995). Dışbükey eşitsizlikler ve doğrusal tamamlayıcı problemler için yumuşatma yöntemleri. Matematiksel Programlama , 71, 1–112. doi
Genel işler
- (en) RW Cottle, J.-S. Pang ve RE Stone, The Linear Complementarity Problem , Philadelphia, PA, SIAM, diğerleri. "Uygulamalı Matematikte Klasikler" ( n o 60),2009
-
(en) F. Facchinei ve J.-S. Pang, Sonlu Boyutlu Varyasyonel Eşitsizlikler ve Tamamlayıcılık Problemleri (2 cilt), New York, Springer-Verlag, cilt. "Yöneylem Araştırmasında Springer Serisi", 2003
-
(en) KG Cinayet, Doğrusal Tamamlayıcılık, Doğrusal ve Doğrusal Olmayan Programlama , Berlin, Heldermann Verlag, der . "Uygulamalı Matematikte Sigma Serileri" ( n o 3),1988( ISBN 978-3-88538-403-8 ), yazarın web sitesinden indirilebilir
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">