İkinci dereceden optimizasyon
Olarak matematiksel optimizasyon , bir ikinci dereceden optimizasyon sorunu bir ilgili ikinci dereceden bir fonksiyon minimize (ya da en üst düzeye çıkarmak) olan bir optimizasyon sorunu olan dışbükey çokgen . Kısıtlamalar bu nedenle ile tanımlanabilir doğrusal fonksiyonları (bir söylemek gerekir afin ). İkinci dereceden optimizasyon , sorunları inceleyen disiplindir. Lineer optimizasyon kuadratik optimizasyon özel bir durum olarak görülebilir.
Bu problem genel durumda NP-zordur . Dışbükey bir amaç fonksiyonunun en aza indirilmesi durumunda , sorun polinomdur ve dışbükey ikinci dereceden optimizasyondan bahsediyoruz ; daha iyi bilinen özelliklere sahip zaten çok zengin bir disiplin.
Kriter ve kısıtlamalar ikinci dereceden optimizasyon problemi olduğunda, herhangi bir ikinci dereceden optimizasyondan (en) bahsediyoruz . Bu problem sınıfı, tüm polinom optimizasyonunu içerir ve bu nedenle, ikinci dereceden optimizasyondan çok daha geneldir.
Sorunun formülasyonu
İkinci dereceden bir optimizasyon problemi, dışbükey bir çokyüzlü üzerinde mutlaka dışbükey olmayan ikinci dereceden bir işlevi en aza indirmeyi içerir .
q:Rdeğil→R{\ displaystyle q: \ mathbb {R} ^ {n} \ - \ mathbb {R}}
En aza indirilecek kriter
Q fonksiyonu , par.
x=(x1,...,xdeğil)∈Rdeğil{\ displaystyle x = (x_ {1}, \ ldots, x_ {n}) \ in \ mathbb {R} ^ {n}}![x = (x_ {1}, \ ldots, x_ {n}) \ in \ mathbb {R} ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98f2a731cf0f9d3ae04cdc9d693faab33ad3a80e)
q(x)=gTx+12xTHx=∑ben=1değilgbenxben+12∑ben=1değil∑j=1değilHbenjxbenxj.{\ displaystyle q (x) = g ^ {\ mathsf {T}} x + {\ frac {1} {2}} \, x ^ {\ mathsf {T}} Hx = \ sum _ {i = 1} ^ {n} g_ {i} x_ {i} + {\ frac {1} {2}} \, \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {n} H_ {ij} x_ {i} x_ {j}.}
Q ( x ) ' in ilk ifadesinde, matris formundaki ifade bir vektördür ve simetrik bir gerçek matristir (bunun genellikle simetrik olduğu varsayılır , çünkü q , H'nin olası antisimetrik kısmını görmez ). Terimi sabit tutarak hiçbir anlamı yoktur q o minimizasyonu sorununun çözümü etkilemez çünkü.
g∈Rdeğil{\ displaystyle g \ in \ mathbb {R} ^ {n}}
H∈Rdeğil×değil{\ displaystyle H \ in \ mathbb {R} ^ {n \ times n}}![\ Mathbb'de H \ {R} ^ {n \ kere n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/907fdad816c0c7231ec44d81e5b79fd33502f329)
Bu tür bir ikinci derecede fonksiyonudur olduğu geri çağırma q olduğu
Kısıtlamalar
Ayrıca aranan x vektörünün dışbükey bir polihedrona ait olmasını da empoze ediyoruz , bu da x'in sonlu sayıda afin kısıtlamayı karşılaması gerektiği anlamına gelir . Bunlar, aşağıdaki gibi çeşitli biçimlerde olabilir:
lB⩽x⩽senB(bağlı kısıtlamalar)lben⩽ATbenx⩽senben(afin eşitsizlik kısıtlamaları)ATEx=bE(afin eşitlik kısıtlamaları),{\ displaystyle {\ begin {dizi} {ll} l_ {B} \ leqslant x \ leqslant u_ {B} & {\ mbox {(bağlı kısıtlamalar)}} \\ l_ {I} \ leqslant A_ {I} x \ leqslant u_ {I} & {\ mbox {(afin eşitsizlik kısıtlamaları)}} \\ A_ {E} x = b_ {E} & {\ mbox {(afin eşitlik kısıtlamaları),}} \ end {dizi}}}
kaydettiğimiz ifadeler
-
l B ve u B vektörleri bu nedenle sonsuz değerler alabilir ve l B < u B'yi doğrulayabilir ,R¯değil{\ displaystyle {\ bar {\ mathbb {R}}} ^ {n}}
![{\ bar {\ mathbb {R}}} ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbb53410b7fd663d97d618ed7fc4201089c814b8)
-
ATben∈Rmben×değil{\ displaystyle A_ {I} \ in \ mathbb {R} ^ {m_ {I} \ times n}}
m I × n türünde bir gerçek matris ( A I x , A I matrisinin x vektörüyle çarpımını gösterir ),
-
l I ve l I vektörleri bu nedenle sonsuz değerler alabilir ve l I < u I doğrulayarak ,R¯mben{\ displaystyle {\ bar {\ mathbb {R}}} ^ {m_ {I}}}
![{\ bar {\ mathbb {R}}} ^ {m_ {I}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12c1883ac6d119a794337a0ef6d3f9c349f2dc6f)
-
ATE∈RmE×değil{\ displaystyle A_ {E} \ in \ mathbb {R} ^ {m_ {E} \ kere n}}
m E × n türünde gerçek bir matris ,
-
bE∈RmE{\ displaystyle b_ {E} \ in \ mathbb {R} ^ {m_ {E}}}
gerçek bir vektör.
Kompakt gösterimi kullanmak ilginç olacak
[lB,senB]: ={x∈Rdeğil:lB⩽x⩽senB}{\ displaystyle [l_ {B}, u_ {B}]: = \ {x \ in \ mathbb {R} ^ {n}: l_ {B} \ leqslant x \ leqslant u_ {B} \}}
ve [ l I , u I ] için benzer bir tanım . Biz tarafından ifade x Q , yani kısıtlamaları, yukarıda herkes tarafından kabul edilen belirli bir dizi
XQ: ={x∈Rdeğil:x∈[lB,senB], ATbenx∈[lben,senben], ATEx=bE}.{\ displaystyle X_ {Q}: = \ {x \ in \ mathbb {R} ^ {n}: x \ in [l_ {B}, u_ {B}], ~ A_ {I} x \ in [l_ { I}, u_ {I}], ~ A_ {E} x = b_ {E} \}.}
Kompakt formülasyon
Kompakt bir şekilde, ikinci dereceden optimizasyon problemini aşağıdaki gibi yazabiliriz
(PQ)infx∈XQq(x).{\ displaystyle (P_ {Q}) \ quad \ inf _ {x \, X_ {Q}} \, q (x).}
Bu sorun olduğunu söylemek dışbükey kriter ise q olan dışbükey , ancak ve ancak, eğer durum, lH yarı tanımlı pozitiftir.
Problem analizi
Çözümün varlığı
Temel sonuç, Frank ve Wolfe'den (1956) kaynaklanmaktadır. Doğrusal optimizasyonda bilinenle aynı tiptedir . bunu hatırlayalım
- bir optimizasyon probleminin, kabul edilebilir seti boş değilse uygulanabilir olduğu söylenir (bu, optimum değerinin + ∞'a eşit olmadığı anlamına gelir ),
- Olası bir optimizasyon probleminin, optimal değeri –∞'a eşit değilse sınırlandırılmış olduğu söylenir (kriterin –∞'a doğru yöneldiği bir dizi kabul edilebilir nokta bulunamaz ).
Çözümün varlığı - İkinci dereceden bir optimizasyon problemi için (mutlaka dışbükey değil), aşağıdaki özellikler eşdeğerdir:
- sorunun bir çözümü var,
- sorun uygulanabilir ve sınırlıdır,
- problemin optimal değeri sonludur.
Çözümün tekliği eğer kesinlikle meydana gelecektir q ise kesinlikle dışbükey , ama onsuz oluşabilir. Bu, örneğin kriteri doğrusal olan (dolayısıyla tam olarak dışbükey olmayan) tek değişkenli inf { x : x ≥ 0} problemi için geçerlidir .
Doğuş
Burada, teorik çıkarları olan ve dijital olan bir yönün varlığı açısından uygulanabilir bir dışbükey ikinci dereceden problemin (yani kabul edilebilir küme boş olmayan) sınırlı (veya sınırsız) karakterinin bir karakterizasyonu yer almaktadır. Bu unutulmamalıdır X ∞ asimptotik koni seti arasında X .
Dışbükey ikinci dereceden bir problemin doğuşu - Kabul edilebilir çok yüzlü kümesi X ile gösterilen uygulanabilir bir dışbükey ikinci dereceden optimizasyon problemi için aşağıdaki özellikler eşdeğerdir:
- sorun sınırsızdır,
- Orada bir yönde mevcut d şekilde , ve .g⊤d<0{\ displaystyle g ^ {\ top} d <0}
Hd=0{\ displaystyle Hd = 0}
d∈X∞{\ displaystyle d \ içinde X ^ {\ infty}}![X ^ {\ infty} içinde d \](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff3eda6203544d7819b2dde89faf5dadaca41455)
Asimptotik koni kabul kümesinin x Q, yukarıda tanımlandığı gibidir (boş değil kabul) yazılır
XQ∞={d∈Rdeğil:d∈[lB,senB]∞, ATbend∈[lben,senben]∞, ATEd=0}.{\ displaystyle X_ {Q} ^ {\ infty} = \ {d \ in \ mathbb {R} ^ {n}: d \ in [l_ {B}, u_ {B}] ^ {\ infty}, ~ A_ {I} d \ in [l_ {I}, u_ {I}] ^ {\ infty}, ~ A_ {E} d = 0 \}.}
İfadesi [ l , u ] ∞ verilir asimptotik koni üzerinde sayfasında .
Çözünürlük yöntemleri
Yalnızca eşitlik kısıtlamaları varsa, sorun doğrusal bir sistemi çözmeye gelir. Eşitsizlik kısıtlamalarının varlığında, sorun genel olarak NP-zordur ve aşağıdaki yaklaşımlarla çözülebilir:
Ekler
Not
-
Makalenin ekine (i) bakın.
-
Örneğin, Chiche ve Gilbert (2014) tarafından yazılan makaledeki Lemma 2.2'ye bakınız.
-
Bu konuda birçok katkı. Delbos ve Gilbert (2005) tarafından yazılan makale, sorunun bir çözümü olduğunda küresel doğrusal yakınsamasını analiz etmektedir; Chiche ve Gilbert (2014) 'inki, problem uygulanabilir olmadığında davranışı analiz eder.
İlgili Makaleler
Dış bağlantı
- Yöneylem Araştırma Modelleri ve Yöntemleri (Paul A. Jensen ve Jonathan F. Bard) [1]
Kaynakça
-
(tr) A. Chiche, J. Ch. Gilbert (2016). Artırılmış Lagrangian algoritması, uygulanabilir olmayan bir dışbükey ikinci dereceden optimizasyon problemiyle nasıl başa çıkabilir? Dışbükey Analiz Dergisi , 23: 2, 425-459.
-
(en) F. Delbos, J. Ch. Gilbert (2005). Dışbükey ikinci dereceden optimizasyon problemlerini çözmek için artırılmış bir Lagrangian algoritmasının küresel doğrusal yakınsaması. Dışbükey Analiz Dergisi , 12, 45-69. [2]
-
(tr) M. Frank, P. Wolfe (1956). İkinci dereceden programlama için bir algoritma. Naval Research Logistics Quarterly , 3, 95–110.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">