リャプノフ最適化

この記事では、動的システムのLyapunov 最適化について説明します。また、待ち行列ネットワークの最適制御への応用例を示します。

リャプノフ最適化とは、リャプノフ関数を使用して動的システムを最適に制御することです。リャプノフ関数は、さまざまな形式のシステム安定性を確保するために制御理論で広く使用されています。特定の時間におけるシステムの状態は、多くの場合、多次元ベクトルで記述されます。リャプノフ関数は、この多次元状態の非負のスカラー測定値です。通常、関数は、システムが望ましくない状態に向かうと大きくなるように定義されます。システムの安定性は、リャプノフ関数を負の方向にドリフトさせてゼロに向かう制御アクションを実行することで実現されます。

リャプノフドリフトは、キューイングネットワークの最適制御の研究の中心です。典型的な目標は、平均エネルギーの最小化や平均スループットの最大化など、いくつかのパフォーマンス目標を最適化しながら、すべてのネットワークキューを安定させることです。2次リャプノフ関数のドリフトを最小化すると 、ネットワークの安定性のためのバックプレッシャールーティングアルゴリズム（最大重みアルゴリズムとも呼ばれます）が得られます。^{[1] [2]} リャプノフドリフトに重み付きペナルティ項を追加し、その合計を最小化すると、ネットワークの安定性とペナルティの最小化を結合したドリフトプラスペナルティアルゴリズムが得られます。 ^{[3] [4] [5]}ドリフトプラスペナルティ手順は、凸計画と線形計画の解を計算するためにも使用できます。^[6]

正規化されたタイムスロットを持つ離散時間で進化するキューイングネットワークを考えてみましょう。ネットワークにキューがあり、時間におけるキューバックログのベクトルを次のように定義します。 ${\displaystyle t\in \{0,1,2,\ldots \}.}$${\displaystyle N}$${\displaystyle t}$

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

各スロットに対して以下を定義します。 ${\displaystyle t,}$

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

この関数は、ネットワーク内のキューの総バックログのスカラー測定値です。これは、キューの状態に関する2 次 Lyapunov 関数と呼ばれます。Lyapunovドリフトを、この関数の 1 つのスロットから次のスロットへの変化として定義します。

${\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\}}$

ここで、およびは、それぞれ、スロットtのキュー内の到着とサービス機会です。この式を使用して、任意のスロットtのリアプノフドリフトの境界を計算できます。 ${\displaystyle a_{i}(t)}$${\displaystyle b_{i}(t)}$${\displaystyle i}$${\displaystyle t.}$

${\displaystyle Q_{i}(t+1)^{2}=\left(\max \left\{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}}$

この不等式を整理し、すべてを合計して2 で割ると、次のようになります。 ${\displaystyle i,}$

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

どこ：

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

各キューの到着とサービスの 2 番目のモーメントが制限されており、すべてのキュー ベクトルとすべての可能なキュー ベクトルに対して次のプロパティが保持されるような有限定数が存在すると仮定します。 ${\displaystyle B>0}$${\displaystyle t}$${\displaystyle Q(t)}$

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

(式1)の条件付き期待値を取ると、条件付き期待リャプノフドリフトの次の境界が得られる。

${\displaystyle \mathbb {E} [\Delta L(t)|Q(t)]\leqslant B+\sum _{i=1}^{N}Q_{i}(t)\mathbb {E} [a_{i}(t)-b_{i}(t)|Q(t)]\qquad (Eq.2)}$

多くの場合、ネットワークは、各キューの到着数とサービス数の差が、ある実数に対して次の特性を満たすように制御できます。 ${\displaystyle \varepsilon >0}$

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

上記がすべてのキュー、すべてのスロット、およびすべての可能なベクトルに対して同じイプシロンに当てはまる場合、(式 2) は次のリャプノフのドリフト定理で使用されるドリフト条件に簡約されます。以下の定理は、マルコフ連鎖に対するフォスターの定理のバリエーションとして見ることができます。ただし、マルコフ連鎖構造は必要ありません。 ${\displaystyle i,}$${\displaystyle t,}$${\displaystyle Q(t),}$

定理（リャプノフドリフト）。^{[5] [7]}すべての可能なベクトルに対して条件付きリャプノフドリフトが満たす 定数があると仮定します。${\displaystyle B\geqslant 0,\varepsilon >0}$${\displaystyle t}$${\displaystyle Q(t)}$

${\displaystyle \mathbb {E} [\Delta L(t)|Q(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}Q_{i}(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 \mathbb {E} [\Delta L(t)]\leqslant B-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(t)]}$

上記の式を合計し、伸縮和の法則を使用すると次のようになります。 ${\displaystyle \tau \in \{0,1,\ldots ,t-1\}}$

${\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 )]}$

が非負である という事実を利用し、上記の式の項を並べ替えると結果が証明されます。${\displaystyle L(t)}$

上のセクションと同じキューイングネットワークを考えてみましょう。ここで、スロット t で発生するネットワークペナルティを と定義します。目標は、キューイングネットワークを安定化させながら、時間平均を最小化することだとします。たとえば、時間平均電力を最小化しながらネットワークを安定化するには、スロット t でネットワークが負担する総電力として定義できます。^{[8]望ましい}報酬の時間平均を最大化する問題を扱うには、ペナルティを と定義できます。これは、安定性を条件として、ネットワーク全体で効用を最大化するのに役立ちます。^[3]${\displaystyle p(t)}$${\displaystyle t.}$${\displaystyle p(t).}$${\displaystyle p(t)}$ ${\displaystyle r(t),}$${\displaystyle p(t)=-r(t).}$

ペナルティネットワークの平均時間を最小化しながらネットワークを安定化するために、各スロットで次のドリフトプラスペナルティ式の境界を貪欲に最小化する制御動作を行うようにアルゴリズムを設計することができる。^[5]${\displaystyle p(t),}$${\displaystyle t}$

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

ここで、は、パフォーマンスのトレードオフに影響を与えるために必要に応じて選択される非負の重みです。このアプローチの主な特徴は、ランダムなネットワークイベント（ランダムなジョブの到着やチャネルの実現など）の確率に関する知識が通常必要ないことです。を選択すると、スロットごとにドリフトの上限を最小化することに帰着し、マルチホップキューイングネットワークでのルーティングでは、TassiulasとEphremidesによって開発されたバックプレッシャールーティングアルゴリズムに帰着します。 ^{[1] [2]}を使用し、スロットでのネットワーク電力使用量として定義すると、ネットワークの安定性に応じて平均電力を最小化するドリフトプラスペナルティアルゴリズムがNeelyによって開発されました。 ^[8]を使用し、をアドミッション制御ユーティリティメトリックの負として使用すると、Neely、Modiano、およびLiによって開発された、フロー制御とネットワークルーティングを結合するためのドリフトプラスペナルティアルゴリズムがNeely、Modiano、およびLiによって開発されました。^[3]${\displaystyle V}$${\displaystyle V=0}$${\displaystyle V>0}$${\displaystyle p(t)}$${\displaystyle t}$${\displaystyle V>0}$${\displaystyle p(t)}$

この文脈では、前のセクションのリャプノフドリフト定理の一般化が重要です。説明を簡単にするために、が下から制限されていると仮定します。 ${\displaystyle p(t)}$

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

たとえば、ペナルティが常に非負である場合、上記は満たされます。 は、 の時間平均の望ましいターゲットを表します。 は、ターゲット達成の重要性を重み付けするために使用されるパラメーターとします。次の定理は、ドリフトプラスペナルティ条件が満たされた場合、時間平均ペナルティは望ましいターゲットより最大で O(1/V) 高く、平均キュー サイズは O(V) であることを示しています。 パラメーターは、対応するキュー サイズのトレードオフで、時間平均ペナルティを必要に応じてターゲットに近づける (またはターゲットを下回る) ように調整できます。 ${\displaystyle p_{\min }=0}$${\displaystyle p(t)}$${\displaystyle p^{*}}$${\displaystyle p(t).}$${\displaystyle V}$${\displaystyle V}$

定理 (リャプノフ最適化)。すべてのベクトルとすべての可能なベクトルに対して、次のドリフトプラスペナルティ条件が成り立つ ような定数とがあるとします。${\displaystyle \varepsilon >0,V,B\geqslant 0,}$${\displaystyle p^{*}}$${\displaystyle t}$${\displaystyle Q(t)}$

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

そして、すべての時間平均ペナルティと時間平均キュー サイズは次を満たします。 ${\displaystyle t>0}$

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

${\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 \mathbb {E} [\Delta L(t)]+V\mathbb {E} [p(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}\mathbb {E} [Q_{i}(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}\mathbb {E} [p(\tau )]&\leqslant p^{*}Vt+Bt+\mathbb {E} [L(0)]\end{aligned}}}$

項を分割して並べ替えると、時間平均ペナルティの境界が証明されます。同様の議論により、時間平均キュー サイズの境界が証明されます。 ${\displaystyle Vt}$

• ドリフトプラスペナルティ
• バックプレッシャールーティング
• リャプノフ関数
• フォスターの定理
• 制御リアプノフ関数

• MJ Neely.確率的ネットワーク最適化と通信および待ち行列システムへの応用、Morgan & Claypool、2010 年。