Drift artı ceza - Drift plus penalty

Matematiksel olasılık teorisinde, drift-plus-ceza yöntemi optimizasyonu için kullanılır kuyruk ağları ve diğeri stokastik sistemler.

Teknik, bir kuyruk ağını stabilize ederken aynı zamanda bir ağ ceza işlevinin zaman ortalamasını en aza indirmek içindir. Zaman ortalamalı güç, iş hacmi ve iş hacmi yardımcı programı gibi performans hedeflerini optimize etmek için kullanılabilir.^[1][2]En aza indirilmesi gereken özel bir durumda ve amaç, çok sekmeli bir ağda kararlı bir yönlendirme politikası tasarlamak olduğunda, yöntem şu şekilde azalır: geri basınç yönlendirme.^[3][4]Sürüklenme artı ceza yöntemi aynı zamanda bir sürenin ortalamasını en aza indirmek için de kullanılabilir. Stokastik süreç diğer stokastik süreçlerin bir toplamı üzerindeki ortalama zaman kısıtlamalarına tabidir.^[5]Bu, uygun bir dizi tanımlayarak yapılır. sanal kuyruklar. Ayrıca, zaman ortalamalı çözümler üretmek için de kullanılabilir. dışbükey optimizasyon sorunlar. ^[6][7]

Metodoloji

Sürüklenme artı ceza yöntemi, zaman aralıklarıyla ayrı zamanlarda çalışan kuyruk sistemleri için geçerlidir. t {0, 1, 2, ...} içinde. İlk olarak, negatif olmayan bir fonksiyon L(t) tüm kuyrukların zamanındaki durumunun skaler bir ölçüsü olarak tanımlanırt. İşlev L(t) tipik olarak tüm kuyruk boyutlarının karelerinin toplamı olarak tanımlanır tve denir Lyapunov işlevi. Lyapunov kayması tanımlanmış:

${ displaystyle Delta L (t) = L (t + 1) -L (t)}$

Her yuva t, mevcut kuyruk durumu gözlemlenir ve aşağıdakilerle ilgili bir sınırı iştahla en aza indirmek için kontrol eylemleri yapılır. drift-plus-ceza ifadesi:

${ displaystyle Delta L (t) + Vp (t),}$

nerede p(t) ceza fonksiyonudur ve V, negatif olmayan bir ağırlıktır. V parametresi, zaman ortalamasını sağlamak için seçilebilir. p(t), ortalama kuyruk boyutunda karşılık gelen bir değiş tokuşla, isteğe bağlı olarak optimuma yakındır. Sevmek geri basınç yönlendirme, bu yöntem tipik olarak işe girişler ve ağ hareketliliği için olasılık dağılımları hakkında bilgi gerektirmez.^[5]

Kökenler ve uygulamalar

Ne zaman ${ displaystyle V = 0,}$ yöntem, Lyapunov kaymasını açgözlülükle en aza indirmeye indirgenir. Bu, geri basınç yönlendirme ilk olarak Tassiulas ve Ephremides tarafından geliştirilen algoritma (aynı zamanda maksimum ağırlık algoritması).^[3][8] ${ displaystyle Vp (t)}$ Neely tarafından drift ifadesine terim eklendi^[9] ve Neely, Modiano, Li^[2] bir ağı stabilize ederken aynı zamanda bir verim yardımcı programı işlevini en üst düzeye çıkarmak için. Bunun için ceza ${ displaystyle p (t)}$ olarak tanımlandı ${ displaystyle -1}$ slotta kazanılan ödülün katı ${ displaystyle t.}$ Bu sürüklenme artı ceza tekniği daha sonra ortalama gücü en aza indirmek için kullanıldı^[1] ve diğer ceza ve ödül ölçütlerini optimize edin.^[4][5]

Teori, öncelikle kablosuz ağlar, geçici mobil ağlar ve diğer bilgisayar ağları dahil olmak üzere iletişim ağlarını optimize etmek için geliştirilmiştir. Bununla birlikte, matematiksel teknikler, yenilenebilir enerji tahsisi dahil olmak üzere diğer stokastik sistemler için optimizasyon ve kontrol için uygulanabilir. akıllı güç ızgaraları^[10][11][12] ve stok kontrolü ürün montaj sistemleri için.^[13]

Nasıl çalışır

Bu bölüm, diğer işlevlerin bir koleksiyonundaki zaman ortalama kısıtlamalarına tabi bir p (t) işlevinin zaman ortalamasını en aza indirmek için sürüklenme artı ceza yönteminin nasıl kullanılacağını gösterir. Aşağıdaki analiz, içindeki malzemeye dayanmaktadır.^[5]

Stokastik optimizasyon problemi

{0, 1, 2, ...} içindeki normalleştirilmiş zaman aralıkları t üzerinde gelişen ayrı bir zaman sistemini düşünün. P (t) 'yi, zaman ortalaması en aza indirilmesi gereken bir fonksiyon olarak tanımlayın. ceza fonksiyonu. Diyelim ki p (t) zaman ortalamasının en aza indirilmesi, K diğer fonksiyonların bir koleksiyonunda zaman-ortalama kısıtlamalarına tabi olarak yapılmalıdır:

• ${ displaystyle p (t) = { text {zaman ortalaması en aza indirilmesi gereken ceza işlevi}}}$

• ${ displaystyle y_ {1} (t), y_ {2} (t), ldots, y_ {K} (t) = { text {zaman ortalamaları pozitif olmayan diğer fonksiyonlar}}}$

Her t slotunda, ağ denetleyicisi yeni bir rastgele olay gözlemler. Daha sonra bu olayın bilgisine dayanarak bir kontrol eylemi yapar. P (t) ve y_i (t) değerleri, rastgele olayın ve t slotundaki kontrol eyleminin fonksiyonları olarak belirlenir:

• ${ displaystyle omega (t) = { text {yuvada rastgele olay}} t { text {(yuvalar üzerinde i.i.d olduğu varsayılır)}}}$

• ${ displaystyle alpha (t) = { text {yuvadaki kontrol eylemi}} t { text {(gözlemlendikten sonra seçilir}} omega (t) { text {)}}}$

• ${ displaystyle p (t) = P ( alpha (t), omega (t)) { text {(}} alpha (t) 'nin deterministik bir fonksiyonu, omega (t) { text {)} }}$

• ${ displaystyle y_ {i} (t) = Y_ {i} ( alpha (t), omega (t)) { text {}} forall i {1, ldots, K } { text {(belirleyici işlevler}} alpha (t), omega (t) { text {)}}}$

Küçük durum notasyonu p (t), y_i (t) ve büyük harf notasyonu P (), Y_i (), ceza değerlerini, bu değerleri rastgele olaya ve t slotu için kontrol eylemine göre belirleyen işlevden ayırmak için kullanılır. Rastgele olay ${ displaystyle omega (t)}$ bazı soyut olaylar dizisinde değer aldığı varsayılır ${ displaystyle Omega}$. Kontrol eylemi ${ displaystyle alpha (t)}$ bazı soyut setler içinde seçildiği varsayılmaktadır ${ displaystyle A}$ kontrol seçeneklerini içeren. Takımlar ${ displaystyle Omega}$ ve ${ displaystyle A}$ keyfi ve sonlu veya sonsuz olabilir. Örneğin, ${ displaystyle A}$ soyut elemanların sınırlı bir listesi, sayılamayacak kadar sonsuz (ve muhtemelen dışbükey olmayan) gerçek değerli vektörler koleksiyonu vb. olabilir. P (), Y_i () fonksiyonları da keyfidir ve süreklilik veya dışbükeylik varsayımları gerektirmez.

İletişim ağları bağlamında bir örnek olarak, rastgele olay ${ displaystyle omega (t)}$ her düğüm için dilim varış bilgisini ve her bağlantı için dilim kanal durum bilgisini içeren bir vektör olabilir. Kontrol eylemi ${ displaystyle alpha (t)}$ her düğüm için yönlendirme ve iletim kararlarını içeren bir vektör olabilir. P () ve Y_i () fonksiyonları, t slotu için kontrol eylemi ve kanal koşulu ile ilişkili güç harcamalarını veya iş hacmini temsil edebilir.

Açıklamanın basitliği için, P () ve Y_i () fonksiyonlarının sınırlı olduğunu varsayın. Ayrıca rastgele olay sürecini varsayalım ${ displaystyle omega (t)}$ dır-dir bağımsız ve aynı şekilde dağıtılmış (i.i.d.) t olasılıkla bilinmeyen bazı olasılık dağılımıyla yuvalar üzerinden. Amaç, aşağıdaki problemi çözmek için zaman içinde kontrol eylemleri yapmak için bir politika tasarlamaktır:

${ displaystyle { text {Küçült:}} lim _ {t rightarrow infty} { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [p ( tau)]}$

${ displaystyle { text {Konu:}} lim _ {t rightarrow infty} { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [y_ {i} ( tau)] leq 0 { text {}} forall i in {1, ldots, K }}$

Bu sorunun baştan sona olduğu varsayılmıştır. mümkün. Yani, tüm bunları karşılayabilecek bir algoritma olduğu varsayılır. K istenen kısıtlamalar.

Yukarıdaki problem, her kısıtlamayı ortaya çıkarır. standart biçim soyut bir süreç y_i (t) pozitif olmayan bir zaman ortalama beklentisi. Bu yaklaşımda genellik kaybı yoktur. Örneğin, bazı süreçlerin a (t) zaman ortalama beklentisinin belirli bir c sabitinden küçük veya ona eşit olmasını istediğini varsayalım. Sonra yeni bir ceza fonksiyonu y(t) = a(t) − c tanımlanabilir ve istenen kısıtlama, ortalama zaman beklentisine eşdeğerdir. y(t) pozitif olmamak. Aynı şekilde, iki işlem olduğunu varsayalım a(t) ve b(t) ve biri için zaman ortalama beklentisi a(t) şundan küçük veya ona eşit olmakb(t). Bu kısıtlama, yeni bir ceza fonksiyonu tanımlanarak standart biçimde yazılmıştır. y(t) = a(t) − b(t). Yukarıdaki problem arar küçültmek soyut ceza fonksiyonunun zaman ortalamasıp '(t) '. Bu kullanılabilir maksimize etmek bazılarının zaman ortalaması ödül işlevir(t) tanımlayarak p(t) = −r('t).

Sanal kuyruklar

Her kısıtlama için ben {1, ... içinde K}, tanımlayın sanal sıra yuvalar üzerinde dinamiklerle t {0, 1, 2, ...} içinde şu şekilde:

${ displaystyle ({ text {Denk.}} 1) { text {}} Q_ {i} (t + 1) = max [Q_ {i} (t) + y_ {i} (t), 0 ]}$

Başlat Q_ben(0) = 0 hepsi için ben {1, ... içinde K}. Bu güncelleme denklemi, bir gerçek Backlog Q_i (t) ve y_i (t) ile yeni gelenler ve yuvadaki yeni hizmet fırsatları arasındaki fark olan ayrık zaman kuyruğut. Sezgisel olarak, bu sanal kuyrukların dengelenmesi, kısıtlama fonksiyonlarının zaman ortalamalarının sıfırdan küçük veya sıfıra eşit olmasını sağlar, böylece istenen kısıtlamalar karşılanır. Bunu tam olarak görmek için, (Denklem 1) 'in şu anlama geldiğine dikkat edin:

${ displaystyle Q_ {i} (t + 1) geq Q_ {i} (t) + y_ {i} (t)}$

Bu nedenle:

${ displaystyle y_ {i} (t) leq Q_ {i} (t + 1) -Q_ {i} (t)}$

Yukarıdakileri ilk t yuvaları üzerinden toplamak ve iç içe geçen toplamlar yasasını kullanmak şu anlama gelir:

${ displaystyle toplamı _ { tau = 0} ^ {t-1} y_ {i} ( tau) leq Q_ {i} (t) -Q_ {i} (0) = Q_ {i} (t )}$

Bölme ölçütü t ve beklentileri almak şu anlama gelir:

${ displaystyle { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [y_ {i} ( tau)] leq { frac {E [Q_ {i } (t)]} {t}}}$

Bu nedenle, aşağıdaki {1, ..., içindeki tüm i'ler için geçerli olduğunda, sorunun istenen kısıtlamaları karşılanır. K}:

${ displaystyle lim _ {t rightarrow infty} { frac {E [Q_ {i} (t)]} {t}} = 0}$

Yukarıdaki limit denklemini karşılayan bir Q_i (t) kuyruğunun ortalama oran sabit.^[5]

Sürüklenme artı ceza ifadesi

Kuyrukları stabilize etmek için, yuvadaki toplam kuyruk biriktirme listesi olarak Lyapunov işlevi L (t) 'yi tanımlayınt:

${ displaystyle L (t) = { frac {1} {2}} toplamı _ {i = 1} ^ {K} Q_ {i} (t) ^ {2}}$

Sıra denkleminin (Denklem 1) karesinin alınması, {1, ..., K} 'deki her sıra i için aşağıdaki sınırla sonuçlanır:

${ displaystyle Q_ {i} (t + 1) ^ {2} leq (Q_ {i} (t) + y_ {i} (t)) ^ {2} = Q_ {i} (t) ^ {2 } + y_ {i} (t) ^ {2} + 2Q_ {i} (t) y_ {i} (t)}$

Bu nedenle,

${ displaystyle { frac {1} {2}} sum _ {i = 1} ^ {K} Q_ {i} (t + 1) ^ {2} leq { frac {1} {2}} toplam _ {i = 1} ^ {K} Q_ {i} (t) ^ {2} + { frac {1} {2}} toplam _ {i = 1} ^ {K} y_ {i} (t) ^ {2} + toplam _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t)}$

Bunu takip eder

${ displaystyle Delta L (t) = L (t + 1) -L (t) leq { frac {1} {2}} toplamı _ {i = 1} ^ {K} y_ {i} ( t) ^ {2} + toplam _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t)}$

Şimdi B'yi, yukarıdaki eşitsizliğin sağ tarafındaki ilk terimi üst sınırlayan pozitif bir sabit olarak tanımlayın. Böyle bir sabit vardır çünkü y_i (t) değerleri sınırlıdır. Sonra:

${ displaystyle Delta L (t) leq B + toplamı _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t)}$

Her iki tarafa Vp (t) eklemek, drift-plus-ceza ifadesinde aşağıdaki sınırla sonuçlanır:

${ displaystyle ({ text {Denk.}} 2) { text {}} Delta L (t) + Vp (t) leq B + Vp (t) + toplam _ {i = 1} ^ { K} S_ {i} (t) y_ {i} (t)}$

Sürüklenme artı ceza algoritması (aşağıda tanımlanmıştır), yukarıdaki eşitsizliğin sağ tarafını açgözlülükle en aza indiren her alanda kontrol eylemleri yapar. Sezgisel olarak, tek başına sürüklenmeyi en aza indiren bir eylemde bulunmak, kuyruk istikrarı açısından yararlı olabilir, ancak ortalama süre cezasını en aza indirmez. Tek başına cezayı en aza indiren bir eylemde bulunmak, kuyrukları sabitlemek zorunda değildir. Bu nedenle, ağırlıklı toplamı en aza indirmek için bir eylemde bulunmak, hem kuyruk kararlılığı hem de cezanın en aza indirilmesi hedeflerini içerir. V ağırlığı, bir performans değiş tokuşu ile sonuçlanan ceza minimizasyonuna az ya da çok vurgu yapacak şekilde ayarlanabilir.^[5]

Drift artı ceza algoritması

İzin Vermek ${ displaystyle A}$ olası tüm kontrol eylemlerinin soyut kümesi olun. Her t slotu, rastgele olayı ve mevcut kuyruk değerlerini gözlemleyin:

${ displaystyle { text {Gözlem:}} omega (t), Q_ {1} (t), ldots, Q_ {K} (t)}$

Alan t için bu gözlemler göz önüne alındığında, açgözlülükle bir kontrol eylemi seçin $A olarak { displaystyle alpha (t) }$ aşağıdaki ifadeyi en aza indirmek için (keyfi olarak bağları koparmak):

${ displaystyle VP ( alpha (t), omega (t)) + toplamı _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha (t), omega (t))}$

Sonra her bir i için sıraları {1, ..., K} 'de (Denklem 1)' e göre güncelleyin. T + 1 yuvası için bu prosedürü tekrarlayın.^[5]

Yuvada gözlemlenen rastgele olay ve kuyruk biriktirme listelerinin t yuva minimizasyonu için kontrol eylemini seçerken verilen sabitler gibi hareket edin. Böylece, her yuva, set üzerindeki kontrol eylemini en aza indirmek için deterministik bir arama içerir. Bir. Bu algoritmanın temel bir özelliği, rastgele olay sürecinin olasılık dağılımına ilişkin bilgi gerektirmemesidir.

Yaklaşık planlama

Yukarıdaki algoritma, soyut bir küme üzerinden minimum bir işlev bulmayı içerir. Bir. Genel durumlarda, asgari mevcut olmayabilir veya bulunması zor olabilir. Bu nedenle, algoritmanın aşağıdaki gibi yaklaşık bir şekilde uygulandığını varsaymak faydalıdır: C negatif olmayan bir sabit olarak ve tüm alanlar için tkontrol eylemi ${ displaystyle alpha (t)}$ sette seçilir Bir tatmin etmek:

${ displaystyle { başlar {hizalı} & VP ( alpha (t), omega (t)) + toplamı _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha (t), omega (t)) leq {} & C + inf _ { alpha içinde A} [VP ( alpha, omega (t)) + sum _ {i = 1} ^ { K} Q_ {i} (t) Y_ {i} ( alpha, omega (t))] end {hizalı}}}$

Böyle bir kontrol eylemi, C-katkı yaklaşımı.^[5] Dava C = 0, her yuvada istenen ifadenin tam olarak küçültülmesine karşılık gelirt.

Performans analizi

Bu bölüm, algoritmanın ortalama kuyruk boyutunda karşılık gelen bir O (V) değiş tokuşu ile optimalliğin O (1 / V) dahilinde bir zaman ortalama cezası ile sonuçlandığını göstermektedir.^[5]

Ortalama ceza analizi

Tanımla ${ displaystyle omega}$-yalnızca politika Kontrol eylemini seçmek için sabit ve rastgele bir politika olmak ${ displaystyle alpha (t)}$ gözlemlenene göre ${ displaystyle omega (t)}$ sadece. Yani bir ${ displaystyle omega}$-yalnızca politika, olası her rastgele olay için belirtir ${ displaystyle omega in Omega}$, bir kontrol eylemi seçmek için koşullu bir olasılık dağılımı $A olarak { displaystyle alpha (t) }$ verilen ${ displaystyle omega (t) = omega}$. Böyle bir politika, kararları mevcut kuyruk birikiminden bağımsız hale getirir. Varsayalım ki bir ${ displaystyle omega}$-yalnızca politika ${ displaystyle alpha ^ {*} (t)}$ aşağıdakileri karşılar:

${ displaystyle ({ text {Denklem}} 3) qquad E [P ( alpha ^ {*} (t), omega (t))] = p ^ {*} = { text {en uygun zaman sorun için ortalama ceza}}}$

${ displaystyle ({ text {Denk.}} 4) qquad E [Y_ {i} ( alpha ^ {*} (t), omega (t))] leqslant 0 qquad forall i in {1, ldots, K }}$

Yukarıdaki beklentiler rastgele değişkenle ilgilidir ${ displaystyle omega (t)}$ yuva için ${ displaystyle t,}$ ve rastgele kontrol eylemi ${ displaystyle alpha (t)}$ yuvada seçilmiş ${ displaystyle t}$ gözlemledikten sonra ${ displaystyle omega (t)}$. Böyle bir politika ${ displaystyle alpha ^ {*} (t)}$ İstenilen kontrol problemi uygulanabilir olduğunda ve olay yeri olduğunda var olduğu gösterilebilir. ${ displaystyle omega (t)}$ ve eylem alanı ${ displaystyle alpha (t)}$ sonludur veya hafif kapatma özellikleri sağlandığında.^[5]

İzin Vermek ${ displaystyle alpha (t)}$ Negatif olmayan bazı C sabitleri için, önceki bölümün sürüklenme artı ceza algoritmasının C toplamalı yaklaşımı tarafından alınan eylemi temsil eder. Terminolojiyi basitleştirmek için, bu eylemi drift-plus-ceza eylemi, Yerine C-katkılı yaklaşık sürüklenme artı ceza eylemi. İzin Vermek ${ displaystyle alpha ^ {*} (t)}$ temsil etmek ${ displaystyle omega}$-yalnızca karar:

${ displaystyle alpha (t) = { text {boşluk için kayma artı-ceza eylemi}} t}$

${ displaystyle alpha ^ {*} (t) = omega { text {-Yalnızca (Denklem 3) - (Denklem 4)}}} tatmin eden eylem$

Drift artı ceza eylemini varsayalım ${ displaystyle alpha (t)}$ her yuvada kullanılır. (Denklem 2) ile, bunun altındaki sürüklenme artı ceza ifadesi ${ displaystyle alpha (t)}$ eylem, her alan için aşağıdakileri karşılar ${ displaystyle t:}$

${ displaystyle { başlar {hizalı} Delta L (t) + Vp (t) & leqslant B + Vp (t) + toplamı _ {i = 1} ^ {K} Q_ {i} (t) y_ {i} (t) & = B + VP ( alpha (t), omega (t)) + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha (t), omega (t)) & leqslant B + C + VP ( alpha ^ {*} (t), omega (t)) + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t)) end {hizalı}}}$

son eşitsizliğin geldiği yer, çünkü eylem ${ displaystyle alpha (t)}$ bir katkı sabiti içinde gelir ${ displaystyle C}$ önceki ifadeyi kümedeki diğer tüm eylemlere göre küçültme ${ displaystyle A}$ dahil olmak üzere ${ displaystyle alpha ^ {*} (t).}$ Yukarıdaki eşitsizliğin beklentilerini almak şunları verir:

${ displaystyle { başlar {hizalı} E [ Delta (t) + Vp (t)] & leqslant B + C + VE [P ( alfa ^ {*} (t), omega (t))] + toplam _ {i = 1} ^ {K} E sol [Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t)) sağ] & = B + C + VE [P ( alpha ^ {*} (t), omega (t))] + toplam _ {i = 1} ^ {K} E [Q_ {i} (t)] E [Y_ {i} ( alpha ^ {*} (t), omega (t))] && alpha ^ {*} (t), omega (t) { text {bağımsızdır}} Q_ {i} (t) & leqslant B + C + Vp ^ {*} && { text {Denklem Kullanarak 3 ve Denk. 4}} end {hizalı}}}$

Dikkat edin ${ displaystyle alpha ^ {*} (t)}$ eylem hiçbir zaman gerçekten uygulanmadı. Varlığı, nihai eşitsizliğe ulaşmak için yalnızca karşılaştırma amacıyla kullanılmıştır. Yukarıdaki eşitsizliği ilki üzerinden toplamak ${ displaystyle t> 0}$ slotlar şunları verir:

${ displaystyle { başlar {hizalı} (B + C + Vp ^ {*}) t & geqslant toplamı _ { tau = 0} ^ {t-1} E [ Delta ( tau) + Vp ( tau)] & = E [L (t)] - E [L (0)] + V sum _ { tau = 0} ^ {t-1} E [p ( tau)] && Delta ( tau) = L ( tau +1) -L ( tau) & = E [L (t)] + V sum _ { tau = 0} ^ {t-1} E [p ( tau)] && { text {varsayım}} L (0) = 0 & geqslant V sum _ { tau = 0} ^ {t-1} E [p ( tau)] && L (t ) geqslant 0 end {hizalı}}}$

Yukarıdakileri bölerek ${ displaystyle Vt}$ tüm slotlar için geçerli olan aşağıdaki sonucu verir ${ displaystyle t> 0:}$

${ displaystyle { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [p ( tau)] leqslant p ^ {*} + { frac {B + ÖZGEÇMİŞ}}.}$

Böylece, zaman ortalamalı beklenen ceza keyfi olarak optimal değere yakın yapılabilir. ${ displaystyle p ^ {*}}$ seçerek ${ displaystyle V}$ uygun büyüklükte. Tüm sanal kuyrukların ortalama hızda kararlı olduğu ve böylece istenen tüm kısıtlamaların karşılandığı gösterilebilir.^[5] Parametre ${ displaystyle V}$ zaman ortalamalı kısıtlama fonksiyonlarının pozitif olmayan bir sayıya yakınsadığı hızı belirleyen kuyrukların boyutunu etkiler. Bir sonraki alt bölümde kuyrukların boyutuna ilişkin daha ayrıntılı bir analiz verilmektedir.

Ortalama sıra boyutu analizi

Şimdi var olduğunu varsayın ${ displaystyle omega}$-yalnızca politika ${ displaystyle alpha ^ {*} (t)}$(Eşitlik 3) - (Eşitlik 4) 'ü karşılayandan muhtemelen farklı, bazıları için aşağıdakileri karşılayan ${ displaystyle epsilon> 0}$:

${ displaystyle ({ text {Denklem}} 5) qquad E [Y_ {i} ( alpha ^ {*} (t), omega (t))] leq - epsilon qquad forall i {1, ldots, K }} içinde$

Önceki bölümdekine benzer bir argüman şunu gösterir:

${ displaystyle { başlar {hizalı} Delta (t) + Vp (t) & leqslant B + C + VP ( alpha ^ {*} (t), omega (t)) + toplamı _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t)) Delta (t) + Vp _ { min} & leqslant B + C + Vp _ { max} + sum _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} ( alpha ^ {*} (t), omega (t) ) && { text {varsayım}} p _ { min} leqslant P leqslant p _ { max} E [ Delta (t)] + Vp _ { min} & leqslant B + C + Vp _ { max} + sum _ {i = 1} ^ {K} E left [Q_ {i} (t)] E [Y_ {i} ( alpha ^ {*} (t), omega (t)) right] && { text {beklentiyi karşılamak}} E [ Delta (t)] + Vp _ { min} & leqslant B + C + Vp _ { max} + sum _ {i = 1} ^ {K} E [Q_ {i} (t)] (- epsilon) && { text {Kullanarak (Denklem 5)}} E [ Delta (t)] + epsilon sum _ {i = 1} ^ {K} E [Q_ {i} (t)] & leqslant B + C + V (p _ { max} -p _ { min}) end {hizalı}}}$

Önceki bölümdekine benzer bir iç içe geçme serisi argümanı, böylece tüm t> 0 için aşağıdakileri göstermek için kullanılabilir:^[5]

${ displaystyle { frac {1} {t}} toplamı _ { tau = 0} ^ {t-1} toplamı _ {i = 1} ^ {K} E [Q_ {i} ( tau) ] leqslant { frac {B + C + V (p _ { max} -p _ { min})} { epsilon}}}$

Bu, ortalama kuyruk boyutunun gerçekten O (V) olduğunu gösterir.

Olasılık 1 yakınsama

Yukarıdaki analiz, zaman ortalaması beklentilerini dikkate almaktadır. Sonsuz ufuk süresi ortalama kuyruk boyutu ve ceza için ilgili olasılık 1 performans sınırları, drift-plus-ceza yöntemi ile birlikte kullanılarak elde edilebilir. martingale teorisi.^[14]

Sınırlı kapasiteye sahip kuyruklara uygulama

Gösterildiği gibi, drift-plus-cezası, ortalama kuyruk boyutunu V parametresinin seçimine bağlı olan belirli bir eşiğin altında tutmaya izin verir, ancak genel olarak maksimum kuyruk doluluğu konusunda herhangi bir garanti sunmaz. Bununla birlikte, eylem seti belirli kısıtlamalara uyuyorsa, bir kuyruğun maksimum uzunluğunu zorlamak için V seçimine ek bir koşul eklemek ve böylece algoritmayı sınırlı kapasiteli kuyruklara da uygulamak mümkündür.^[15]

Kuyruk sistemlerinin tedavisi

Yukarıdaki analiz, herhangi bir açık kuyruğu olmayan stokastik bir sistemde zaman ortalamalarının kısıtlı optimizasyonunu dikkate alır. Her seferinde ortalama eşitsizlik kısıtlaması (Denklem 1) 'e göre sanal bir kuyruğa eşlendi. Bir kuyruk ağının optimize edilmesi durumunda, (Denklem 1) 'deki sanal kuyruk denklemleri gerçek kuyruk denklemleri ile değiştirilir.

Zaman ortalamalarının dışbükey fonksiyonları

Bununla ilgili bir sorun, aşağıdaki gibi kısıtlamalara tabi olan zaman ortalamalarının dışbükey bir fonksiyonunun en aza indirilmesidir:

${ displaystyle { text {Küçült}} quad f left ({ overline {y}} _ {1}, ldots, { overline {y}} _ {K} right) quad { text {konu}} quad g_ {i} left ({ overline {y}} _ {1}, ldots, { overline {y}} _ {K} right) leqslant 0 qquad forall i in {1, ldots, N }}$

nerede ${ displaystyle f}$ ve ${ displaystyle g_ {i}}$ vardır dışbükey fonksiyonlar ve zaman ortalamalarının tanımlandığı yer:

${ displaystyle { overline {y}} _ {i} = lim _ {t ila infty} { frac {1} {t}} sum _ { tau = 0} ^ {t-1} E [y_ {i} ( tau)]}$

Zaman ortalamalarının dışbükey işlevlerini optimize etmenin bu tür sorunları, işlevlerin zaman ortalamalarını optimize etme sorunlarına dönüştürülebilir. yardımcı değişkenler (Neely ders kitabının 5. Bölümüne bakın).^[2][5] Sonraki sorunlar daha sonra önceki alt bölümlerde açıklandığı gibi sürüklenme artı ceza yöntemi ile çözülebilir. Bir alternatif ilkel yöntem, drift-plus-ceza kararlarına benzer kararlar alır, ancak amaç fonksiyonunun kısmi türevleri ile tanımlanan bir ceza kullanır ${ displaystyle f.}$^[5][16][17] Primal-dual yaklaşım, aşağıdaki durumlarda yerel optimayı bulmak için de kullanılabilir. ${ displaystyle f}$ dışbükey değildir.^[5]

Ödünleşmeleri ve ilgili işleri geciktirme

Önceki bölümdeki matematiksel analiz, sürüklenme artı ceza yönteminin O (1 /V) optimallik, karşılık gelen Ö(V) ortalama kuyruk boyutunda değiş tokuş. Bu yöntem, Ö(1/V), Ö(V) tradeoff, Neely'de geliştirildi^[9] ve Neely, Modiano, Li^[2] kararlılığa tabi olan ağ yardımcı programını maksimize etme bağlamında.

Ağ hizmetini maksimize etmek için ilgili bir algoritma Eryılmaz ve Srikant tarafından geliştirilmiştir.^[18]Eryılmaz ve Srikant çalışması, drift-plus-ceza algoritmasına çok benzer bir algoritma ile sonuçlandı, ancak farklı bir analitik teknik kullandı. Bu teknik dayanıyordu Lagrange çarpanları. Lagrange çarpanı tekniğinin doğrudan kullanımı, daha kötü bir ödünleşime neden olur. Ö(1/V), Ö(V²). Bununla birlikte, Lagrange çarpan analizi, orijinali kurtarmak için daha sonra Huang ve Neely tarafından güçlendirildi. Ö(1/V), Ö(V), sıra boyutlarının, karşılık gelen deterministik optimizasyon probleminin Lagrange çarpanı etrafında sıkı bir şekilde kümelendiğini gösterirken, ödünleşmeler.^[19]Bu kümeleme sonucu, iyileştirmeyi etkinleştirmek için sürüklenme artı ceza algoritmasını değiştirmek için kullanılabilir. Ö(1/V), Ö(günlük²(V)) ödünleşimler. Değişiklikler her ikisini de kullanabilir yer tutucu biriktirme listesi^[19] veya Son Giren İlk Çıkar (LIFO) planlama.^[20][21]

Stokastik olmayan işlevler için uygulandığında, drift-plus-ceza yöntemi, ikili alt gradyan yöntemi nın-nin dışbükey optimizasyon teorisi çıktısının bir zaman ortalaması olması dışında ilk değişkenler, ilk değişkenlerin kendileri yerine.^[4][6] İlgili ilkel ikili teknik Stokastik bir kuyruk ağında faydayı maksimize etmek için, akışkan modeli analizi kullanılarak Stolyar tarafından geliştirilmiştir.^[16][17]Stolyar analizi, yardımcı program ve kuyruk boyutu arasındaki performans değiş tokuşu için analitik sonuçlar sağlamaz. Stokastik ağlar için primal-dual yöntemin daha sonraki bir analizi, benzer bir O (1 / V), O (V) yardımcı programı ve kuyruk boyutu değiş tokuşunu kanıtlar ve aynı zamanda, zaman ortalamalarının dışbükey olmayan fonksiyonlarını en aza indirmek için yerel optimallik sonuçlarını gösterir. ek yakınsama varsayımı.^[5] Bununla birlikte, bu analiz, zaman ortalamalarının sonsuz ufuk sınırlarına yakın bir şeye yakınsaması için ne kadar zaman gerektiğini belirtmez. Kuyruklar olmadan yardımcı program maksimizasyonu için ilgili primal-dual algoritmalar Agrawal ve Subramanian tarafından geliştirilmiştir.^[22]ve Kushner ve Whiting.^[23]

İ.i.d olmayan uzantılar. olay süreçleri

Sürüklenme artı ceza algoritmasının daha genel ergodik süreçler için benzer performans garantileri sağladığı bilinmektedir. ${ displaystyle omega (t)}$, böylece i.i.d. varsayım, analiz için çok önemli değildir. Algoritmanın olasılıklarda ergodik olmayan değişikliklere karşı sağlam olduğu gösterilebilir. ${ displaystyle omega (t)}$. Bazı senaryolarda, istenen analitik garantileri sağladığı gösterilebilir. evrensel çizelgeleme garantileri, keyfi için ${ displaystyle omega (t)}$ süreçler.^[5]

Değişken çerçeve uzunluğu sistemlerine uzatmalar

Sürüklenme artı ceza yöntemi, değişken boyutlu çerçeveler üzerinde çalışan sistemleri tedavi etmek için genişletilebilir.^[24][25] Bu durumda, çerçeveler indislerle etiketlenir r {0, 1, 2, ...} ve çerçeve süreleri {T[0], T[1], T[2], ...}, nerede T[r], her kare için negatif olmayan bir gerçek sayıdırr. İzin Vermek ${ displaystyle Delta [r]}$ ve ${ displaystyle p [r]}$ çerçeve arasında sürüklenmek r ve r + 1 ve çerçeve sırasında alınan toplam cezar, sırasıyla. Genişletilmiş algoritma, koşullu beklentilerin aşağıdaki oranındaki bir sınırı en aza indirmek için her çerçeve r üzerinde bir kontrol eylemi gerçekleştirir:

${ displaystyle { frac {E [ Delta [r] + Vp [r] orta Q [r]]} {E [T [r] orta Q [r]]}}}$

nerede Q[r], karenin başındaki kuyruk biriktirme listelerinin vektörüdürr. Tüm çerçevelerin aynı boyutta olduğu ve 1 yuva uzunluğuna normalleştirildiği özel durumda, T[r] = 1 hepsi için ryukarıdaki en aza indirme, standart drift-plus-ceza tekniğine indirgenir. Bu çerçeve tabanlı yöntem, kısıtlı optimizasyon için kullanılabilir. Markov karar sorunları (MDP'ler) ve deneyimlenen sistemleri içeren diğer sorunlar için yenilemeler.^[24][25]

Dışbükey programlamaya uygulama

İzin Vermek x = (x₁, ..., x_N) fasulye Ngerçek sayıların boyutlu vektörü ve hiper dikdörtgeni tanımlama Bir tarafından:

${ displaystyle A = {(x_ {1}, x_ {2}, ldots, x_ {N}) orta x _ { min, i} leq x_ {i} leq x _ { max, i} { text {}} forall i in {1, ldots, N } }}$

nerede x_{min, ben}, x_{max, ben} tatmin eden gerçek sayılar verilir ${ displaystyle x _ { min, i}$ hepsi içinben. İzin Vermek P(x) ve ${ displaystyle Y_ {i} (x)}$ {1, ... içindeki i için K} sürekli olun ve dışbükey fonksiyonlar of x her şeyin üzerinde vektör x içindeBir. Aşağıdakileri göz önünde bulundur dışbükey programlama sorun:

${ displaystyle ({ text {Denk.}} 6) { text {}} { text {Küçült:}} P (x)}$

${ displaystyle ({ text {Denk.}} 7) { text {}} { text {Subject to:}} Y_ {i} (x) leq 0 { text {}} forall i in A} içinde {1, ldots, K } { text {}}, { text {}} x = (x_ {1}, ldots, x_ {N})$

Bu, drift-plus-ceza yöntemiyle şu şekilde çözülebilir: Rastgele olay süreci içermeyen deterministik bir sistemin özel durumunu düşünün ${ displaystyle omega (t)}$. Kontrol eylemini tanımlayın ${ displaystyle alpha (t)}$ gibi:

${ displaystyle alpha (t) = x (t) = (x_ {1} (t), x_ {2} (t), ldots, x_ {N} (t))}$

ve eylem alanını şu şekilde tanımlayın: Nboyutlu hiper dikdörtgen Bir. Ceza ve kısıtlama işlevlerini şu şekilde tanımlayın:

• ${ displaystyle p (t) = P (x_ {1} (t), ldots, x_ {N} (t))}$

• ${ displaystyle y_ {i} (t) = Y_ {i} (x_ {1} (t), ldots, x_ {N} (t)) { text {}} forall i {1, ldots, K }}$

Aşağıdaki zaman ortalamalarını tanımlayın:

• ${ displaystyle { overline {x}} (t) = { frac {1} {t}} sum _ { tau = 0} ^ {t-1} (x_ {1} ( tau), ldots, x_ {N} ( tau))}$

• ${ displaystyle { overline {P}} (t) = { frac {1} {t}} toplamı _ { tau = 0} ^ {t-1} P (x_ {1} ( tau), ldots, x_ {N} ( tau))}$

• ${ displaystyle { overline {Y}} _ {i} (t) = { frac {1} {t}} sum _ { tau = 0} ^ {t-1} Y_ {i} (x_ { 1} ( tau), ldots, x_ {N} ( tau))}$

Şimdi aşağıdaki zaman ortalamalı optimizasyon problemini düşünün:

${ displaystyle ({ text {Denk.}} 8) { text {}} { text {Küçült:}} lim _ {t rightarrow infty} { overline {P}} (t)}$

${ displaystyle ({ text {Denk.}} 9) { text {}} { text {konu:}} lim _ {t rightarrow infty} { overline {Y}} _ {i} (t) leq 0 { text {}} forall i in {1, ldots, K }}$

Tarafından Jensen'in eşitsizliği aşağıdaki tüm slotlar t> 0 için geçerlidir:

${ displaystyle P ({ overline {x}} (t)) leq { overline {P}} (t) { text {}}, { text {}} Y_ {i} ({ overline { x}} (t)) leq { overline {Y}} _ {i} (t) { text {}} forall i in {1, ldots, K }}$

Buradan, zaman-ortalama problemine (Denklem 8) - (Denklem 9) optimal bir çözümün, tüm t slotları için x (t) = x * tipi çözümlerle elde edilebileceği gösterilebilir, burada x * konveks programı (Denklem 6) - (Denklem 7) çözen bir vektördür. Ayrıca, herhangi bir zaman ortalamalı vektör ${ displaystyle lim _ {t rightarrow infty} { overline {x}} (t)}$ zaman ortalamalı problemin bir çözümüne karşılık gelen (Denklem 8) - (Denklem 9) konveks programı (Eşitlik 6) - (Eşitlik 7) çözmelidir. Bu nedenle orijinal dışbükey program (Eşitlik 6) - (Eşitlik 7), ilgili zamana sürüklenme artı ceza algoritması uygulandığında alınan kararların zaman ortalamasını alarak (istenen herhangi bir doğruluk dahilinde) çözülebilir. ortalama problem (Eşitlik 8) - (Eşitlik 9). Problem için sürüklenme artı ceza algoritması (Denklem 8) - (Denklem 9) aşağıdakilere indirgenir:

Konveks programlama için drift-plus-ceza algoritması

Her yuva tvektör seç ${ displaystyle x (t) = (x_ {1} (t), ldots, x_ {N} (t)) A'da}$ ifadeyi en aza indirmek için:

${ displaystyle VP (x (t)) + toplamı _ {i = 1} ^ {K} Q_ {i} (t) Y_ {i} (x (t))}$

Ardından kuyrukları şuna göre güncelleyin:

${ displaystyle Q_ {i} (t + 1) = max [Q_ {i} (t) + Y_ {i} (x (t)), 0] { text {}} forall i { 1, ldots, K }}$

Ortalama zaman vektörü ${ displaystyle { overline {x}} (t)}$ dışbükey programa bir O (1 / V) yaklaşımına yakınsar.^[6]

Bu algoritma standarda benzer ikili alt gradyan algoritması optimizasyon teorisinin sabit bir 1 / V adım boyutu kullanarak.^[26] Bununla birlikte, temel bir fark, ikili alt gradyan algoritmasının tipik olarak aşağıdakiler için gerekli olan kısıtlayıcı katı dışbükeylik varsayımları altında analiz edilmesidir. ilk değişkenler x(t) yakınsamak için. Bu değişkenlerin optimal çözüme yakınsamadığı ve asla optimal çözüme yaklaşamadığı birçok önemli durum vardır (çoğu durumda bu böyledir) doğrusal programlar, Aşağıda gösterildiği gibi). Öte yandan, sürüklenme artı ceza algoritması katı dışbükeylik varsayımları gerektirmez. Sağlar zaman ortalamaları ilkellerin Ö(1/V) ile optimallik Ö(V) kuyruk boyutlarına ilişkin sınırlar (bunun bir Ö(V²) yakınsama süresine bağlı).^[6]

Doğrusal programlama için drift artı ceza algoritması

Özel durumunu düşünün doğrusal program. Özellikle varsayalım:

• ${ displaystyle P (x (t)) = toplamı _ {n = 1} ^ {N} c_ {n} x_ {n} (t)}$

• ${ displaystyle Y_ {i} (x (t)) = toplamı _ {n = 1} ^ {N} a_ {in} x_ {n} (t) -b_ {i} { text {}} forall i in {1, ldots, K }}$

gerçek değerli sabitler için (c₁, …, c_N), (a_içinde), (b₁, …, b_K). Daha sonra yukarıdaki algoritma aşağıdakine indirgenir: Her yuva t ve her değişken için n {1,… içinde N}, Seç x_n(t) içinde [x_min,n, x_max,n] ifadeyi küçültmek için:

${ displaystyle sol [Vc_ {n} + toplamı _ {i = 1} ^ {K} Q_ {i} (t) a_ {in} sağ] x_ {n} (t)}$

Ardından sıraları güncelleyin Q_ben(t) eskisi gibi. Bu, her bir değişkeni seçmek anlamına gelir x_ben(t) göre basit bang-bang kontrol politikası:

${ displaystyle { text {Seç}} x_ {i} (t) = x _ { min, i} { text {if}} Vc_ {n} + sum _ {i = 1} ^ {K} Q_ {i} (t) a_ {in} geq 0}$

${ displaystyle { text {Seç}} x_ {i} (t) = x _ { max, i} { text {if}} Vc_ {n} + sum _ {i = 1} ^ {K} Q_ {i} (t) a_ {içinde} <0}$

İlk değişkenlerden beri x_ben(t) her zaman ikisidir x_min,ben veya x_max,ben, eğer optimal çözüm hiper dikdörtgenin köşe noktası değilse, asla optimal çözüme yakınsamazlar. Bir. Ancak zaman ortalamaları bu patlama-patlama kararlarından Ö(1/V) optimal çözümün yaklaşıklığı. Örneğin, varsayalım ki x_{min, 1} = 0, x_{maks, 1} = 1 ve doğrusal programa yönelik tüm optimal çözümlerin x₁ = 3/4. İlk değişken için patlama-patlama kararının kabaca 3 / 4'ü x₁(t) = 1 ve kalan süre x₁(t) = 0.^[7]

İlgili Bağlantılar

• Geri basınç yönlendirme
• Lyapunov optimizasyonu
• Dışbükey optimizasyon
• Doğrusal programlama

Referanslar

Birincil kaynaklar

• M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.