랴푸노프 최적화

이 기사는 역동적인 시스템에 대한 랴푸노프 최적화를 설명한다.그것은 대기 중인 네트워크에서 최적의 제어를 위한 애플리케이션을 예시한다.

소개

랴푸노프 최적화는 역동적인 시스템을 최적으로 제어하기 위해 랴푸노프 함수를 사용하는 것을 말한다.랴푸노프 기능은 제어 이론에서 광범위하게 사용되어 다른 형태의 시스템 안정성을 보장한다.특정 시간에 시스템의 상태는 다차원 벡터로 설명되는 경우가 많다.랴푸노프 함수는 이 다차원 상태의 비음성 스칼라 측도다.일반적으로 이 기능은 시스템이 바람직하지 않은 상태로 이동할 때 커지도록 정의된다.시스템 안정성은 랴푸노프 함수를 0으로 향하는 부정적인 방향으로 드리프트하는 제어 조치를 취함으로써 달성된다.

랴푸노프 드리프트는 대기 중인 네트워크의 최적 제어 연구의 중심이다.일반적인 목표는 평균 에너지를 최소화하거나 평균 처리량을 극대화하는 것과 같은 일부 성능 목표를 최적화하는 동시에 모든 네트워크 대기열을 안정화하는 것이다.2차 리아푸노프 함수의 드리프트를 최소화하면 네트워크 안정성을 위한 역압 라우팅 알고리즘(max-weight algorithm이라고도 한다.^[1][2]랴푸노프 드리프트에 가중 벌칙 용어를 추가하고 합계를 최소화하면 공동 네트워크 안정성과 벌점 최소화를 위한 드리프트 플러스 벌칙 알고리즘으로 이어진다.^[3][4][5]드리프트 플러스 벌칙 절차는 볼록 프로그램과 선형 프로그램에 대한 해결책을 계산하는 데도 사용될 수 있다.^[6]

대기 중인 네트워크를 위한 Lyapunov 드리프트

표준화된 시간 슬롯 $t{\displaystyle }$ ${\displaystyle \in \{0,}$ ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle \dots \}}$ .${\displaystyle$ t$\in \{0,1,2,\ldots$\}}}. 네트워크에 $N{\displaystyle }$ ${\displaystyle N}$ 대기열이$$ 있다고 가정하고$$, $t{\displaystyle }$ ${\displaystyle t}$ 시간의 대기열 백로그 벡터를 다음과 같이$$ 정의하십시오.

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

2차 랴푸노프 함수

각 슬롯 $t{\displaystyle }$, ${\displaystyle t,}$에 대해 다음을 정의하십시오$$.

${\displaystyle L(t)={\frac {1}{1}:{2}}\sum _{i=1}^{N}Q_{i}(t)^{2}}$

이 함수는 네트워크의 총 대기열 백로그에 대한 스칼라 측도다.큐 상태에서 2차 랴푸노프 함수라고 한다.Lyapunov 드리프트를 한 슬롯에서 다음 슬롯으로 이 기능의 변경으로 정의하십시오.

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

랴푸노프 표류지 경계

대기열 백로그가 시간 경과에 따라 다음 방정식에 따라 변경된다고 가정해 보십시오.

${\displaystyle Q_{i}(t+1)=\max \left\{{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}}}}$

${\displaystyle \mathrm{여기}}$서 $i{\displaystyle {}_{}}$( t${\displaystyle }$) ${\displaystyle a_{i}(t)}$ 및 $b$ ${\displaystyle i_{}t)}$ ${\displaystyle b_{i}(t)$는 각각 슬롯 $t{\displaystyle .}$ ${\displaystyle t.}$의 대기열 $i{\displaystyle }$ ${\displaystystyle$ i$}$에서 도착 및 서비스 기회다$$.$$ 이 방정식은 모든 슬롯 t에 대한 Lyapunov 드리프트의 바운드를 계산하는 데 사용할 수 있다.

${\displaystyle Q_{i}(t+1)^{2}}=\왼쪽(\max \left\{Q_{i}(t)+a_{i}(t)-b_{i}(t),0\right\}\right)^{2}\leqslant \left(Q_{i}(t)+a_{i}-b(t)\right)^{2}}$

$모든{\displaystyle }$ i ,${\displaystyle i}$을(를) 요약하고$$ 2로 나누면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle \Delta L(t)\leqslant B(t)+\sum _{i=1}^{{N}Q_{i}(t)(a_{i}-b_{i}(t)\qquad(Eq.1)}$

여기서:

${\displaystyle B(t)={\frac {1}{1}:{2}}\sum _{i=1}^{N}\왼쪽(a_{i}(t)-b_{i}(t)\right)^{2}}$

각 대기열에서 두 번째 도착 및 서비스 모멘트가 되어 모든 $t{\displaystyle }$ ${\displaystyle t}$ 및$$ 가능한 모든 대기열 벡터 $Q{\displaystyle }$( t${\displaystyle }$) ${\displaystyle Q(t)}$에 대해 과 같은 속성이 유지된다고 가정하십시오.

${\displaystyle \mathb {E} [B(t) Q(t)]\leqslant B}$

(Eq.1)의 조건부 기대치를 취하면 조건부 기대 랴푸노프 표류에 대해 다음과 같은 바운드가 발생한다.

${\displaystyle \mathb {E}[\Delta L(t) Q(t)]\leqslant B+\sum _{i=1}^{{N_{i}(t)\mathb {E}[a_{i}-b_{i}(t) Q(t)]\qqd(E2}$

기본 랴푸노프 표류 정리

많은 경우에, 네트워크는 각 대기열의 도착과 서비스 간의 가 일부 실수 >> $(\displaystyle \varepsilon >0}$에 대해 다음과 같은 속성을 만족하도록 제어될 수 있다

${\displaystyle \mathb {E}[a_{i}(t)-b_{i}(t) Q(t)]\leqslant -\varepsilon }}$

위의 내용이 모든 대기열 $i{\displaystyle }$, ${\displaystyle i,}$ 모든$$ 슬롯 $t{\displaystyle }$, ${\displaystyle$ t$,}$ 및 가능한$$ 모든 $벡터{\displaystyle }$ Q${\displaystyle }$(${\displaystyle t}$)${\displaystyle }$, ${\displaystyle$ Q$(t)$에 대해 동일한 엡실론을 유지한다면 (Eq 2)는 다음의$$ Lyapunov 드리프트 정리에 사용되는 드리프트 조건으로 감소한다.아래의 정리는 마르코프 사슬에 대한 포스터의 정리에 대한 변형으로 볼 수 있다.그러나 마르코프 체인 구조를 필요로 하지 않는다.

정리(Lyapunov 드리프트).^[5][7]모든 $t{\displaystyle }$ ${\displaystyle t}$ 및 가능한$$ 모든 $벡터{\displaystyle }$ Q${\displaystyle }$( t${\displaystyle }$) ${\displaystyle Q(t)}$에 대해$$ 조건부 Lyapunov 드리프트를 만족하는 ,> 0 ${\displaystyle B\geqslant$ 0$,\varepsilon >0}$이 있다고 가정합시다.

${\displaystyle \mathb {E}[\Delta L(t) Q(t)]]\leqslant B-\barepsilon \sum _{i=1}^{N}Q_{i}(t).}$

그런 다음 모든 t> ${\displaystyle t>0}$에 대해 네트워크의 시간 평균 대기열 크기가 다음을 충족한다.

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

증거. 표류 불평등 양쪽에 대한 기대와 반복된 기대의 법칙을 사용하면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle \mathb {E}[\Delta L(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}\mathb {E}[Q_{i}(t)]}}$

위의 표현을 $\tau {\displaystyle \{0}$, ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle }$, t - ${\displaystyle 1\}}$ ${\displaystyle \tau \in \{0,1,\ldots,t-1\}$에 요약하고$$ 텔레스코핑 합계의 법칙을 사용하면 다음과 같은 효과를 얻을 수 있다.

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

$L{\displaystyle }$( ${\displaystyle t}$) ${\displaystyle L(t)}$이(가) 음이 아니라는 사실을 이용하여 위의 표현에서 용어를 재배열하여 결과를 증명한다.

네트워크 대기열에 대한 Lyapunov 최적화

위의 섹션과 동일한 대기열 네트워크를 고려하십시오.이제 $p{\displaystyle }$ (${\displaystyle }$t${\displaystyle }$)$$${\displaystyle p(t)}$을(를) 슬롯 t . {\$displaystyle$ t$.}$에서 발생하는 네트워크 벌칙으로 ${\displaystyle \mathrm{정의}}$하십시오. p${\displaystyle }$( ${\displaystyle t}$${\displaystyle }$)$$. {\$displaystyp p(t$)의 시간 평균을 최소화하면서 대기열 네트워크를 안정화하는 것이 목표라고 가정하십시오$.$$}$ 예를$$ 들어 시간 ${\displaystyle \mathrm{평균}}$ 전력을 최소화하면서 네트워크를 안정시키기 위해 $p{\displaystyle }$( t${\displaystyle }$) ${\displaystyle p(t)}$을(를) 슬롯 t의 네트워크에서 발생하는 총 전력으로 정의할 수 있다$$.^[8]일부 바람직한 보상 $r{\displaystyle }$(${\displaystyle t}$) , ${\displaystyle$ r$(t$)의 시간 평균을 최대화하는 문제를 다루기 위해$,}$ $벌칙$은 p${\displaystyle }$(${\displaystyle t}$)${\displaystyle }$= - ${\displaystyle r}$( ${\displaystyle t}$)${\displaystyle }$.$${\$displaystyle p(t)=-r(t$)를 정의할 수 있다$.$$}$ 안정성의$$ 영향을 받는 네트워크 처리량 유틸리티를 최대화하는 데 유용하다.^[3]

벌칙 $p{\displaystyle }$( ${\displaystyle t}$)${\displaystyle }$, ${\displaystyle p(t$)의 시간 평균을 최소화하면서 네트워크를 안정화하기 위해$,$ 각 $슬롯{\displaystyle }$ t ${\displaystyle t}$에서 다음과 같은 드리프트 플러스 벌칙 식에 대한 경계를 탐욕스럽게 최소화하는 제어 작업을 하도록 네트워크$$ 알고리즘을 설계할 수 있다$.$^[5]

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

여기서 $V{\displaystyle }$ ${\displaystyle V}$은(는) 성능 트레이드오프에 영향을 미치도록 선택한 음이 아닌 가중치입니다.이 접근법의 주요 특징은 일반적으로 무작위 네트워크 사건의 확률에 대한 지식이 필요하지 않다는 것이다(예: 무작위 직업 도착 또는 채널 실현).$V{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle V=0}$을 선택하면 슬롯마다 드리프트의 바인딩을 최소화하고 멀티홉 대기열 네트워크에서 라우팅의 경우 Tassiula와 Ephremides가 개발한 백압 라우팅 알고리즘으로 감소한다.^[1][2] $t{\displaystyle }$ ${\displaystyle t}$에서 V> 0 ${\displaystyle$V>0$}$을(를) 사용하고 $p{\displaystyle }$( t${\displaystyle }$) ${\displaystyle p(t)$을 네트워크 전력 사용으로$$ 정의하면 Neely가 개발한 네트워크 안정성에 따라 평균 전력을 최소화하는 드리프트 플러스 페널리티 알고리즘으로 이어진다$$.^[8]> ${\displaystyle V>0}$을(를) 사용하고 p${\displaystyle }$( ${\displaystyle t}$) ${\displaystyle$ p$(t)}$을(를) 승인 제어 유틸리티 메트릭의 음으로 사용하면$$ 닐리, 모디아노, 리에 의해 개발된 공동 흐름 제어 및 네트워크 라우팅에 대한 드리프트 플러스 페널리티 알고리즘으로 이어진다.^[3]

앞 절의 랴푸노프 표류 정리의 일반화는 이 맥락에서 중요하다.간단히 설명하려면 $p{\displaystyle }$ (${\displaystyle t}$) ${\displaystyle p(t)}$이(가) 아래로부터 경계라고 가정하십시오.

$\displaystyle p(t)\geqslant p_{\min }\forall t\in \{0,1,2,...\}}$

예를 들어 $패널티{\displaystyle }$ p (${\displaystyle t}$) ${\displaystyle$ $p_{\min }=0}$이(가) 항상 음이 아닌 경우$$ 위의$$ 내용은 ${\displaystyle {pmin}_{}}$= ${\displaystyle 0}$ ${\displaystyle$ $p(t)$으로 만족한다.${\displaystyle p}$$∗{\$가 $p{\displaystyle }$(${\displaystyle }$t )${\displaystyle }$. ${\displaystyle p(t$)의 시간 평균에 대해 원하는 목표를 나타내도록$$ 한다$.$$}$ $V{\displaystyle }$ ${\displaystyle V}$을(를) 대상 충족의 중요성에 무게를 두는 데 사용되는 매개 변수가 되도록$$ 하십시오$$.다음 정리는 드리프트 플러스 벌칙 조건이 충족되면 시간 평균 벌칙이 원하는 목표값보다 최대 O(1/V) 높은 반면 평균 대기열 크기는 O(V)임을 보여준다.$V{\displaystyle }$ ${\displaystyle V}$ 매개$$ 변수를 조정하여 해당 대기열 크기 트레이드오프를 통해 원하는 대로 목표물에 가까운 시간 평균 벌칙을 만들 수 있다.

정리(Lyapunov Optimization)모든 $t{\displaystyle }$ ${\displaystyle t}$ 및$$ 한 모든 벡터 $){\displaystyle Q($t){\displaystyle Q($t)}$에 대해 상수 > $0,$ $, B, Geqslant 0,$ $displaystyle$ p$^{*}$이 있다고$$ 가정합시다.

${\displaystyle \mathb {E}[\Delta L(t)+Vp(t) Q(t)]\leqslant B+Vp^{*-\varepsilon \sum _{i=1}^{N}Q_{i}(t)}$

그런 다음 t> ${\displaystyle t>0}$에 대해 시간 평균 벌칙 및 시간 평균 대기열 크기가 다음을 충족한다.

${\displaystyle {\frac{1}{t}\sum _{\\tau-1}\mathb {E}[p(\tau )]\leqslant p^{*}+{\frac{B}+{\frac {E}[L(0)]{Vt}}}}}{V}}}}}{V}}}}}}}}}}}}{V}}}}}{V}}}}}}}}}}}}}{V}}}}}}}}}}}}}}}$

${\displaystyle {\frac {1}{t}}\sum _{\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}}}$

증거. 양쪽에 대한 기대와 양쪽에 대한 기대, 그리고 우리가 가지고 있는 반복된 기대의 법칙을 이용하여:

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

위의 $내용$을 첫 번째$$t {\$displaystyle$t$$} 슬롯에 걸쳐 요약하고 텔레스코핑 합계의 법칙을 사용하면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle {\begin{aligned}\mathbb {E} [L(t)]-\mathbb {E} [L(0)]+V\sum _{\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\sum _{\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}\mathb {E}[p(\tau )]\leqslant p^{*}Vt+Bt+\mathb {E}[L(0)]\ended}}}}}}}}$

$V{\displaystyle }$ ${\displaystyle t}$ ${\displaystyle Vt}$로 나누고 용어를$$ 재배치하는 것은 시간 평균 페널티 바인딩이 입증된다.유사한 인수가 시간 평균 대기열 크기 바인딩을 증명한다.

관련 링크

• 드리프트 플러스 페널티
• 역압 라우팅
• 랴푸노프 함수
• 포스터의 정리
• 컨트롤-랴푸노프 함수

참조

기본 소스

• M. J. 닐리Morgan & Claypool, 2010년 통신 및 대기열 시스템에 대한 응용을 통한 확률적 네트워크 최적화.