Optymalizacja Lapunowa

Ten artykuł opisuje optymalizację Lapunowa dla układów dynamicznych . Podaje przykład zastosowania do optymalnego sterowania w sieciach kolejkowych .

Wstęp

Optymalizacja Lapunowa odnosi się do wykorzystania funkcji Lapunowa do optymalnego sterowania systemem dynamicznym. Funkcje Lapunowa są szeroko stosowane w teorii sterowania w celu zapewnienia różnych form stabilności systemu. Stan systemu w określonym czasie jest często opisywany za pomocą wektora wielowymiarowego. Funkcja Lapunowa jest nieujemną skalarną miarą tego wielowymiarowego stanu. Zazwyczaj funkcja jest zdefiniowana tak, aby rosła, gdy system zbliża się do niepożądanych stanów. Stabilność systemu osiąga się poprzez podjęcie działań kontrolnych, które powodują, że funkcja Lapunowa dryfuje w kierunku ujemnym w kierunku zera.

Dryf Lapunowa ma kluczowe znaczenie dla badania optymalnej kontroli w sieciach kolejkowych. Typowym celem jest ustabilizowanie wszystkich kolejek sieciowych przy jednoczesnej optymalizacji niektórych celów dotyczących wydajności, takich jak minimalizacja średniego zużycia energii lub maksymalizacja średniej przepustowości. Minimalizowanie dryftu kwadratowej funkcji Lapunowa prowadzi do routingu przeciwciśnienia dla stabilności sieci, zwanego również algorytmem maksymalnej wagi . Dodanie ważonego terminu kary do dryfu Lapunowa i zminimalizowanie sumy prowadzi do algorytmu dryfu plus kary dla stabilności wspólnej sieci i minimalizacji kar. Procedurę dryf plus kara można również wykorzystać do obliczania rozwiązań programów wypukłych i programów liniowych .

Dryf Lapunowa dla sieci kolejkowych

Rozważmy sieć kolejkową, która ewoluuje w czasie dyskretnym ze znormalizowanymi szczelinami czasowymi ${\ displaystyle t \ in \ {0,1,2, \ ldots \}.}$$Załóżmy, że w sieci$ są i zdefiniuj wektor zaległości w kolejce w czasie przez ${\ displaystyle t}$ :

${\ Displaystyle Q (t) = (Q_ {1} (t), \ ldots, Q_ {N} (t)}}$

Kwadratowe funkcje Lapunowa

Dla każdego gniazda określ: ${\ displaystyle t}$

${\ Displaystyle L (t) = {\ Frac {1} {2}} \ suma _ {i = 1} ^ {N} Q_ { i}(t)^{2}}$

Ta funkcja jest skalarną miarą całkowitego zaległości w kolejce w sieci. Nazywa się to kwadratową funkcją Lapunowa w stanie kolejki. Zdefiniuj dryf Lapunowa jako zmianę tej funkcji z jednego gniazda do drugiego:

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

Ograniczenie dryfu Lapunowa

Załóżmy, że zaległości w kolejce zmieniają się w czasie zgodnie z następującym równaniem:

${\ Displaystyle Q_ {i} (t + 1) = \ max \ lewo \ {Q_ { i}(t)+a_{i}(t)-b_{i}(t),0\prawo\}}$

gdzie ${\ Displaystyle a_ {i} (t)}$ i ${\ Displaystyle b_ {i} (t)}$ to odpowiednio przyloty i możliwości serwisowe w kolejce za $) {\ Displaystyle a_ {i} (t)}$ na gnieździe ${\ displaystyle t.}$ To równanie może być użyte do obliczenia granicy dryfu Lapunowa dla dowolnej szczeliny t:

${\ Displaystyle Q_ {i} (t + 1) ^ {2} = \ lewo (\ max \ lewo \ {Q_ {i} (t) + a_ {i} (t) -b_ {i} (t) ,0\right\}\right)^{2}\leqslant \left(Q_{i}(t)+a_{i}(t)-b_{i}(t)\right)^{2}}$

Przekształcenie tej nierówności, zsumowanie wszystkich $\ displaystyle i,}$ podzielenie przez 2 prowadzi do: ja ,

${\ Displaystyle \ Delta L (t) \ leqslant B(t)+\suma _{i=1}^{N}Q_{i}(t)(a_{i}(t)-b_{i}(t))\qquad (Równanie1)}$

Gdzie:

${\ Displaystyle B (t) = {\ Frac {1} {2}} \ suma _ {i = 1}^{N}\left(a_{i}(t)-b_{i}(t)\right)^{2}}$

$Załóżmy , że drugie momenty przyjazdów i obsługi w każdej$$displaystyle$ są ograniczone, tak że istnieje skończona stała , że ​​dla wszystkich i wszystkich możliwych wektorów kolejki $>$ the following property holds:

${\ Displaystyle \ mathbb {E} [B (t) | Q (t)] \ leqslant B}$

Przyjęcie warunkowych oczekiwań (Równanie 1) prowadzi do następującej granicy warunkowego oczekiwanego dryfu Lapunowa :

${\ Displaystyle \ mathbb {E} [\ Delta L (t) | Q (t)] \ leqslant B + \ suma _ {i = 1} ^ {N} Q_ {i} (t) \ mathbb {E} [a_ {i}(t)-b_{i}(t)|Q(t)]\qquad (Równanie 2)}$

Podstawowe twierdzenie o dryfie Lapunowa

W wielu przypadkach sieć można kontrolować tak, aby różnica między przyjazdami a obsługą w każdej kolejce spełniała następującą właściwość dla pewnej liczby rzeczywistej: ${\ displaystyle \ varepsilon > 0}$ :

${\ Displaystyle \ mathbb {E} [a_ {i} (t) -b_ {i} (t) | Q (t)] \ leqslant - \ varepsilon}$

$to$ powyższe odnosi się do tego samego epsilon $wszystkich$$wszystkich$ i wektorów ( 2) sprowadza się do warunku dryfu użytego w następującym twierdzeniu Lapunowa o dryfie. Poniższe twierdzenie można postrzegać jako wariację na temat twierdzenia Fostera dla łańcuchów Markowa . Jednak nie wymaga struktury łańcucha Markowa.

Twierdzenie (dryf Lapunowa). Załóżmy, że istnieją stałe takie, że dla wszystkich $Q(t)$$Displaystyle$ możliwych wektorów warunkowy $\ geqslant 0 \ varepsilon$ the conditional Lyapunov drift satisfies:

${\ Displaystyle \ mathbb {E} [\ Delta L (t) | Q (t)] \ leqslant B- \ varepsilon \ suma _ {i = 1} ^ {N} Q_ {i} (t).} Wtedy$

dla wszystkie gniazda ${\ displaystyle t> 0}$ średni czasowy rozmiar kolejki w sieci spełnia:

${\ Displaystyle {\ Frac {1} {t}} \ suma _ {\ tau = 0} ^ {t-1} \ suma _ {i = 1} ^ {N} \ mathbb {E} [Q_ {i} (\ tau)] \ leqslant {\ frac {B} {\ varepsilon}} + {\ frac {\ mathbb {E} [L (0)]} {\ varepsilon t}}.}$

Dowód. Biorąc oczekiwania po obu stronach nierówności dryfu i stosując prawo iterowanych oczekiwań, otrzymujemy:

${\ Displaystyle \ mathbb {E} [\ Delta L (t)] \ leqslant B- \ varepsilon \ suma _ {i=1}^{N}\mathbb {E} [Q_{i}(t)]}$

$_$ powyższe _

${\ Displaystyle \ mathbb {E} [L (t )]-\mathbb {E} [L(0)]\leqslant Bt-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb { E} [Q_{i}(\tau )]}$

$Wykorzystanie$ faktu, że przestawienie terminów w powyższym wyrażeniu dowodzi wyniku

Optymalizacja Lapunowa dla sieci kolejkowych

Rozważ tę samą sieć kolejkowania, co w powyższej sekcji. Teraz $_$ sieciową w gnieździe ${\ displaystyle t.}$ Załóżmy, że celem jest ustabilizowanie sieci kolejek przy jednoczesnej minimalizacji średniej czasowej ${\ displaystyle p (t).}$ Na przykład, aby ustabilizować sieć przy jednoczesnym zminimalizowaniu średniej mocy w czasie, ${\ displaystyle p (t)}$ można zdefiniować jako całkowitą moc pobieraną przez sieć w szczelinie t. ${\ displaystyle p (t) = - r (t).}$ maksymalizacji średniej czasu pewnej $t$ , zdefiniować Jest to przydatne do maksymalizacji sieci w całym narzędziu, z zastrzeżeniem stabilności.

Aby ustabilizować sieć, jednocześnie minimalizując średni czas kary $,$ które zachłannie minimalizują ograniczenie następującego dryf plus kara na każde gniazdo ${\ displaystyle t}$ :

${\ Displaystyle \ Delta L (t) + Vp (t)}$

gdzie jest $nieujemną wagą, która jest wybierana zgodnie z potrzebami, aby wpłynąć na kompromis$ zakresie wydajności. Kluczową cechą tego podejścia jest to, że zwykle nie wymaga ono znajomości prawdopodobieństwa losowych zdarzeń sieciowych (takich jak losowe nadejście zadania lub realizacja kanału). Wybór ogranicza się do minimalizacji ograniczenia dryfu w każdym gnieździe, aw przypadku trasowania w sieciach kolejek z wieloma przeskokami ogranicza się do algorytmu $opracowanego$ przez Tassiulasa i Ephremidesa. Używając ${\ Displaystyle V> 0}$$celu$ zdefiniowanie energii przez sieć na gnieździe $w$ do algorytmu plus kara minimalizacji średniej mocy zależnej od stabilność opracowana przez Neely'ego. Używając i używając $\ Displaystyle p (t$$t$ jako ujemna metryka użyteczności kontroli wstępu prowadzi do algorytmu dryfu plus kary dla wspólnej kontroli przepływu i trasowania sieci, opracowanego przez Neely'ego, Modiano i Li.

W tym kontekście ważne jest uogólnienie twierdzenia o dryfie Lapunowa z poprzedniej sekcji. Dla uproszczenia prezentacji załóżmy, że ${\ displaystyle p (t)}$ jest ograniczony od dołu: p ( t ) {\ displaystyle p (t)}

${\ Displaystyle p (t) \ geqslant p _ {\ min} \ quad \ forall t \ w \ {0,1,2,... \}}$

$w przypadkach$$,$ spełnione kara zawsze nieujemna Niech $reprezentuje$${\ displaystyle p (t).}$ czasu Niech ${\ displaystyle V}$ być parametrem używanym do ważenia ważności osiągnięcia celu. Poniższe twierdzenie pokazuje, że jeśli spełniony jest warunek dryfu plus kara, wówczas średnia kara czasowa jest co najwyżej O(1/V) powyżej pożądanego celu, podczas gdy średni rozmiar kolejki wynosi O(V). Parametr można dostroić, aby średnia kara czasowa była tak blisko (lub poniżej) celu, jak to pożądane, z odpowiednim kompromisem w zakresie wielkości $kolejki$

Twierdzenie (optymalizacja Lapunowa). $}$$i$ że istnieją stałe takie , że dla wszystkich $Displaystyle$

${\ Displaystyle \ mathbb {E} [\ Delta L (t) + Vp (t) | Q (t)] \ leqslant B + Vp ^ {*} - \ varepsilon \ suma _ {i = 1} ^ {N} Q_ {i} (t)} Następnie dla wszystkich t > {\ Displaystyle$

wszystkie możliwe wektory $następujący warunek$ plus kara

t $t>0$ the time average penalty and time average queue sizes satisfy:

${\ Displaystyle {\ Frac {1} {t}} \ suma _ {\ tau = 0} ^ {t-1}\mathbb {E} [p(\tau )]\leqslant p^{*}+{\frac {B}{V}}+{\frac {\mathbb {E} [L(0) ]}{Vt}}}$

${\ Displaystyle {\ Frac {1} {t}} \ suma _ {\ tau = 0} ^ {t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau )]\leqslant {\frac {B+V(p^{*}-p_{ \min })}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}}$

Dowód. Biorąc pod uwagę oczekiwania obu stron zakładanego dryfu plus kara i korzystając z prawa iterowanych oczekiwań mamy:

${\ Displaystyle \ mathbb {E} [\ Delta L (t)]+V\mathbb {E} [p(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i }(T)]}$

Zsumowanie powyższego w pierwszych szczelinach i użycie prawa sum teleskopowych daje: ${\ displaystyle t}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ mathbb {E} [L (t)] - \ mathbb {E} [L (0)] + V \ suma _ {\ tau = 0} ^ {t-1} \ mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t-\varepsilon \sum _{\tau =0}^{t-1}\sum _{i=1} ^{N}\mathbb {E} [Q_{i}(\tau )]\\-\mathbb {E} [L(0)]+V\suma _{\tau =0}^{t-1} \mathbb {E} [p(\tau )]&\leqslant (B+Vp^{*})t&&{\text{Since }}L(t),Q_{i}(t)\geqslant 0\\V \sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau )]&\leqslant p^{*}Vt+Bt+\mathbb {E} [L(0)]\ koniec {wyrównany}}}$

$przestawianie$ przez i terminów dowodzi średniej kary w czasie Podobny argument dowodzi, że średni rozmiar kolejki jest ograniczony w czasie.

Powiązane linki

• Dryf plus kara
• Prowadzenie przeciwciśnienia
• Funkcja Lapunowa
• Twierdzenie Fostera
• Funkcja Control-Lyapunova

Podstawowe źródła

• MJ Neely. Stochastic Network Optimization with Application to Communication and Queuing Systems , Morgan & Claypool, 2010.