李雅普诺夫优化

此词条暂由彩云小译翻译，翻译字数共1583，未经人工整理和审校，带来阅读不便，请见谅。

This article describes Lyapunov optimization for dynamical systems. It gives an example application to optimal control in queueing networks.

This article describes Lyapunov optimization for dynamical systems. It gives an example application to optimal control in queueing networks.

这篇文章描述了动力系统的 Lyapunov最佳化。给出了排队网络最优控制的一个应用实例。

= 简介 =

Lyapunov optimization refers to the use of a Lyapunov function to optimally control a dynamical system. Lyapunov functions are used extensively in control theory to ensure different forms of system stability. The state of a system at a particular time is often described by a multi-dimensional vector. A Lyapunov function is a nonnegative scalar measure of this multi-dimensional state. Typically, the function is defined to grow large when the system moves towards undesirable states. System stability is achieved by taking control actions that make the Lyapunov function drift in the negative direction towards zero.

Lyapunov optimization refers to the use of a Lyapunov function to optimally control a dynamical system. Lyapunov functions are used extensively in control theory to ensure different forms of system stability. The state of a system at a particular time is often described by a multi-dimensional vector. A Lyapunov function is a nonnegative scalar measure of this multi-dimensional state. Typically, the function is defined to grow large when the system moves towards undesirable states. System stability is achieved by taking control actions that make the Lyapunov function drift in the negative direction towards zero.

Lyapunov最佳化是指使用李亚普诺夫函数以最佳方式控制动力系统。李亚普诺夫函数广泛应用于控制理论中，以保证系统的不同形式的稳定性。系统在特定时刻的状态通常用多维向量来描述。李亚普诺夫函数是这种多维状态的非负标量度量。通常，函数被定义为当系统向不希望的状态移动时增大。系统的稳定性是通过采取控制措施，使李亚普诺夫函数在负方向上向零漂移来实现的。

Lyapunov drift is central to the study of optimal control in queueing networks. A typical goal is to stabilize all network queues while optimizing some performance objective, such as minimizing average energy or maximizing average throughput. Minimizing the drift of a quadratic Lyapunov function leads to the backpressure routing algorithm for network stability, also called the max-weight algorithm. Adding a weighted penalty term to the Lyapunov drift and minimizing the sum leads to the drift-plus-penalty algorithm for joint network stability and penalty minimization. The drift-plus-penalty procedure can also be used to compute solutions to convex programs and linear programs.

Lyapunov drift is central to the study of optimal control in queueing networks. A typical goal is to stabilize all network queues while optimizing some performance objective, such as minimizing average energy or maximizing average throughput. Minimizing the drift of a quadratic Lyapunov function leads to the backpressure routing algorithm for network stability, also called the max-weight algorithm.L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992. L. Tassiulas and A. Ephremides, "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity," IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993. Adding a weighted penalty term to the Lyapunov drift and minimizing the sum leads to the drift-plus-penalty algorithm for joint network stability and penalty minimization. M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005. L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, vol. 1, no. 1, pp. 1-149, 2006.M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010. The drift-plus-penalty procedure can also be used to compute solutions to convex programs and linear programs.M. J. Neely, "Distributed and Secure Computation of Convex Programs over a Network of Connected Processors," DCDIS Conf, Guelph, Ontario, July 2005

李雅普诺夫漂移是研究排队网络最优控制的核心问题。一个典型的目标是稳定所有的网络队列，同时优化一些性能目标，如最小化平均能量或最大化平均吞吐量。尽量减少二次李亚普诺夫函数的漂移会导致网络稳定性的背压路由算法，也称为最大权重算法。Tassiulas 和 A. Ephremides，“多跳无线网络中约束排队系统的稳定性特性和最大吞吐量调度策略，IEEE 自动控制论文集，vol。37不。12页。1936-1948,1992年12月。Tassiulas 和 A. Ephremides，“具有随机变化连接性的并行队列的动态服务器分配”，IEEE 信息论汇编，vol。39不。2页。466-478,1993年3月。在 Lyapunov 漂移中加入加权惩罚项并使其最小化，得到了求解联合网络稳定性和惩罚最小化的漂移加惩罚算法。尼利，莫迪亚诺，和 C. Li，“异构网络的公平和最佳统计控制”，《科学》杂志。IEEE INFOCOM，2005年3月。无线网络中的资源分配和跨层控制〉 ，《网络的基础与趋势》 ，卷。1号，不。1页。1-149,2006. M.J ・尼利。随机网络优化及其在通信和排队系统中的应用，Morgan & Claypool，2010。漂移加罚过程也可以用来计算凸规划和线性规划的解。“在连接处理器网络上凸程序的分布式和安全计算”，圭尔夫，2005年7月

= Lyapunov 漂移排队网络 =

Consider a queueing network that evolves in discrete time with normalized time slots [math]\displaystyle{ t \in \{0, 1, 2, \ldots\}. }[/math] Suppose there are [math]\displaystyle{ N }[/math] queues in the network, and define the vector of queue backlogs at time [math]\displaystyle{ t }[/math] by:

Consider a queueing network that evolves in discrete time with normalized time slots t \in \{0, 1, 2, \ldots\}. Suppose there are N queues in the network, and define the vector of queue backlogs at time t by:

考虑一个在离散时间演化的排队网络，该网络在{0,1,2，ldot }中具有标准化的时隙 t。假设网络中有 N 个队列，并通过以下方法定义 t 时刻队列积压的向量:

[math]\displaystyle{ Q(t) = (Q_1(t), \ldots, Q_N(t)) }[/math]

Q(t) = (Q_1(t), \ldots, Q_N(t))

Q (t) = (Q _ 1(t) ，ldot，Q _ N (t))

= 二次 Lyapunov 函数 =

For each slot [math]\displaystyle{ t, }[/math] define:

For each slot t, define:

对于每个槽 t，定义:

[math]\displaystyle{ L(t) = \frac{1}{2}\sum_{i=1}^N Q_i(t)^2 }[/math]

L(t) = \frac{1}{2}\sum_{i=1}^N Q_i(t)^2

L (t) = frac {1}{2} sum _ { i = 1} ^ NQ _ i (t) ^ 2

This function is a scalar measure of the total queue backlog in the network. It is called quadratic Lyapunov function on the queue state. Define the Lyapunov drift as the change in this function from one slot to the next:

This function is a scalar measure of the total queue backlog in the network. It is called quadratic Lyapunov function on the queue state. Define the Lyapunov drift as the change in this function from one slot to the next:

这个函数是网络中总队列积压的标量度量。它被称为队列状态的二次李亚普诺夫函数。将 Lyapunov 漂移定义为函数从一个槽到下一个槽的变化:

[math]\displaystyle{ \Delta L(t) = L(t+1) - L(t) }[/math]

\Delta L(t) = L(t+1) - L(t)

Delta L (t) = L (t + 1)-L (t)

= 约束李亚普诺夫漂移 =

Suppose the queue backlogs change over time according to the following equation:

Suppose the queue backlogs change over time according to the following equation:

假设队列积压随着时间的推移而变化，根据以下公式:

[math]\displaystyle{ Q_i(t+1) = \max \left \{ Q_i(t) + a_i(t) - b_i(t), 0 \right \} }[/math]

Q_i(t+1) = \max \left \{ Q_i(t) + a_i(t) - b_i(t), 0 \right \}

Q _ i (t + 1) = max left { Q _ i (t) + a _ i (t)-b _ i (t) ，0 right }

where [math]\displaystyle{ a_i(t) }[/math] and [math]\displaystyle{ b_i(t) }[/math] are arrivals and service opportunities, respectively, in queue [math]\displaystyle{ i }[/math] on slot [math]\displaystyle{ t. }[/math] This equation can be used to compute a bound on the Lyapunov drift for any slot t:

where a_i(t) and b_i(t) are arrivals and service opportunities, respectively, in queue i on slot t. This equation can be used to compute a bound on the Lyapunov drift for any slot t:

其中 a _ i (t)和 b _ i (t)分别是到达和服务机会，在 t 槽的队列 i 中。这个方程可以用来计算任意时隙 t 的 Lyapunov 漂移的界:

[math]\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 }[/math]

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

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

Rearranging this inequality, summing over all [math]\displaystyle{ i, }[/math] and dividing by 2 leads to:

Rearranging this inequality, summing over all i, and dividing by 2 leads to:

重新排列这个不等式，对所有 i 求和，除以2导致:

[math]\displaystyle{ \Delta L(t) \leqslant B(t) + \sum_{i=1}^N Q_i(t) (a_i(t) - b_i(t)) \qquad (Eq. 1) }[/math]

\Delta L(t) \leqslant B(t) + \sum_{i=1}^N Q_i(t) (a_i(t) - b_i(t)) \qquad (Eq. 1)

Delta L (t)等式 B (t) + sum _ { i = 1} ^ N Q _ i (t)(a _ i (t)-b _ i (t)) qquad (Eq。1)

where:

where:

地点:

[math]\displaystyle{ B(t) = \frac{1}{2}\sum_{i=1}^N \left (a_i(t) - b_i(t) \right )^2 }[/math]

B(t) = \frac{1}{2}\sum_{i=1}^N \left (a_i(t) - b_i(t) \right )^2

B (t) = frac {1}{2} sum _ { i = 1} ^ N left (a _ i (t)-b _ i (t) right) ^ 2

Suppose the second moments of arrivals and service in each queue are bounded, so that there is a finite constant [math]\displaystyle{ B\gt 0 }[/math] such that for all [math]\displaystyle{ t }[/math] and all possible queue vectors [math]\displaystyle{ Q(t) }[/math] the following property holds:

Suppose the second moments of arrivals and service in each queue are bounded, so that there is a finite constant B>0 such that for all t and all possible queue vectors Q(t) the following property holds:

假设每个队列中到达和服务的第二个时刻是有界的，因此有一个有限常量 B > 0，这样对于所有 t 和所有可能的队列向量 Q (t) ，以下性质保持不变:

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

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

mathbb { E }[ B (t) | Q (t)]等式 B

Taking conditional expectations of (Eq. 1) leads to the following bound on the conditional expected Lyapunov drift:

Taking conditional expectations of (Eq. 1) leads to the following bound on the conditional expected Lyapunov drift:

取(Eq 的条件期望。1)导出了条件期望 Lyapunov 漂移的下列界:

[math]\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) }[/math]

\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)

mathbb { E }[ Delta L (t) | Q (t)]等式 B + sum _ { i = 1} ^ N Q _ i (t) mathbb { E }[ a _ i (t)-b _ i (t) | Q (t)] qquad (Eq。2)

= 一个基本的李亚普诺夫漂移定理 =

In many cases, the network can be controlled so that the difference between arrivals and service at each queue satisfies the following property for some real number [math]\displaystyle{ \varepsilon\gt 0 }[/math]:

In many cases, the network can be controlled so that the difference between arrivals and service at each queue satisfies the following property for some real number \varepsilon>0:

在许多情况下，网络可以被控制，以便每个队列的到达和服务之间的差异满足下列特性，对于一些实数 varepsilon > 0:

[math]\displaystyle{ \mathbb{E}[a_i(t) - b_i(t) | Q(t)] \leqslant -\varepsilon }[/math]

\mathbb{E}[a_i(t) - b_i(t) | Q(t)] \leqslant -\varepsilon

mathbb { E }[ a _ i (t)-b _ i (t) | Q (t)] leqslant-varepsilon

If the above holds for the same epsilon for all queues [math]\displaystyle{ i, }[/math] all slots [math]\displaystyle{ t, }[/math] and all possible vectors [math]\displaystyle{ Q(t), }[/math] then (Eq. 2) reduces to the drift condition used in the following Lyapunov drift theorem. The theorem below can be viewed as a variation on Foster's theorem for Markov chains. However, it does not require a Markov chain structure.

If the above holds for the same epsilon for all queues i, all slots t, and all possible vectors Q(t), then (Eq. 2) reduces to the drift condition used in the following Lyapunov drift theorem. The theorem below can be viewed as a variation on Foster's theorem for Markov chains. However, it does not require a Markov chain structure.

如果对于所有队列 i，所有槽 t，以及所有可能的向量 Q (t) ，上述结果都适用于相同的 ε，那么(Eq。2)归结为李雅普诺夫漂移定理中的漂移条件。下面的定理可以看作是福斯特马尔可夫链定理的一个变体。但是，它不需要马尔可夫链结构。

Theorem (Lyapunov Drift). Suppose there are constants [math]\displaystyle{ B\geqslant 0, \varepsilon\gt 0 }[/math] such that for all [math]\displaystyle{ t }[/math] and all possible vectors [math]\displaystyle{ Q(t) }[/math] the conditional Lyapunov drift satisfies:

[math]\displaystyle{ \mathbb{E}[\Delta L(t)|Q(t)] \leqslant B - \varepsilon \sum_{i=1}^N Q_i(t). }[/math]

Then for all slots [math]\displaystyle{ t\gt 0 }[/math] the time average queue size in the network satisfies:

[math]\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}. }[/math]

Theorem (Lyapunov Drift).E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan, "Bounds on Average Delays and Queue Size Averages and Variances in Input-Queued Cell-Based Switches", Proc. IEEE INFOCOM, 2001. Suppose there are constants B\geqslant 0, \varepsilon>0 such that for all t and all possible vectors Q(t) the conditional Lyapunov drift satisfies:

\mathbb{E}[\Delta L(t)|Q(t)] \leqslant B - \varepsilon \sum_{i=1}^N Q_i(t).

Then for all slots t>0 the time average queue size in the network satisfies:

\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}.

翻译: 定理(Lyapunov 漂移)。Leonardi，M. Mellia，F. Neri，and M. AjmoneMarsan，“输入排队单元交换机中平均延迟和队列大小的平均值和方差的界限”，Proc。IEEE INFOCOM，2001年。假设有常数 B geqslant 0，varepsilon > 0，使得对于所有 t 和所有可能的向量 Q (t) ，条件 Lyapunov 漂移满足: : mathbb { E }[ Delta L (t) | Q (t)] leqslant B- varepsilon sum _ { i = 1} ^ NQ _ i (t)。然后对于所有的时隙 t > 0，网络中的时间平均队列大小满足: : 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 }。

Proof. Taking expectations of both sides of the drift inequality and using the law of iterated expectations yields:

Proof. Taking expectations of both sides of the drift inequality and using the law of iterated expectations yields:

证据。考虑漂移不平等的双方的期望，并利用迭代期望法则得出:

[math]\displaystyle{ \mathbb{E}[\Delta L(t)] \leqslant B - \varepsilon \sum_{i=1}^N \mathbb{E}[Q_i(t)] }[/math]

\mathbb{E}[\Delta L(t)] \leqslant B - \varepsilon \sum_{i=1}^N \mathbb{E}[Q_i(t)]

mathbb { E }[ Delta L (t)]等倾 B-varepsilon sum _ { i = 1} ^ N mathbb { E }[ Q _ i (t)]

Summing the above expression over [math]\displaystyle{ \tau \in \{0, 1, \ldots, t-1\} }[/math] and using the law of telescoping sums gives:

Summing the above expression over \tau \in \{0, 1, \ldots, t-1\} and using the law of telescoping sums gives:

在{0,1，ldot，t-1}中将上述 τ 表达式相加，并使用叠加和定律给出:

[math]\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)] }[/math]

\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)]

mathbb { E }[ L (t)]-mathbb { E }[ L (0)]等式 Bt-varepsilon sum _ { tau = 0} ^ { t-1} sum _ { i = 1} ^ N mathbb { E }[ Q _ i (tau)]

Using the fact that [math]\displaystyle{ L(t) }[/math] is non-negative and rearranging the terms in the above expression proves the result.

Using the fact that L(t) is non-negative and rearranging the terms in the above expression proves the result.

利用 L (t)是非负的这一事实，重新排列上述表达式中的项，证明了这一结果。

= 排队网络的 Lyapunov最佳化 =

Consider the same queueing network as in the above section. Now define [math]\displaystyle{ p(t) }[/math] as a network penalty incurred on slot [math]\displaystyle{ t. }[/math] Suppose the goal is to stabilize the queueing network while minimizing the time average of [math]\displaystyle{ p(t). }[/math] For example, to stabilize the network while minimizing time average power, [math]\displaystyle{ p(t) }[/math] can be defined as the total power incurred by the network on slot t. To treat problems of maximizing the time average of some desirable reward [math]\displaystyle{ r(t), }[/math] the penalty can be defined [math]\displaystyle{ p(t) = -r(t). }[/math] This is useful for maximizing network throughput utility subject to stability.

Consider the same queueing network as in the above section. Now define p(t) as a network penalty incurred on slot t. Suppose the goal is to stabilize the queueing network while minimizing the time average of p(t). For example, to stabilize the network while minimizing time average power, p(t) can be defined as the total power incurred by the network on slot t.M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks," IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006. To treat problems of maximizing the time average of some desirable reward r(t), the penalty can be defined p(t) = -r(t). This is useful for maximizing network throughput utility subject to stability.

考虑与上一节相同的队列网络。现在将 p (t)定义为时隙 t 上发生的网络惩罚。假设目标是稳定队列网络，同时使 p (t)的时间平均值最小。例如，为了稳定网络，同时使时间平均功率最小化，p (t)可以定义为网络在时隙 t.M 上发生的总功率。“时变无线网络的能量最优控制”，IEEE 信息论汇编，卷。52号，不。7页。2006年7月，2915-2934。为了处理期望报酬 r (t)的时间平均最大化问题，可以定义惩罚 p (t) =-r (t)。这对于在保持稳定的前提下最大化网络吞吐量效用非常有用。

To stabilize the network while minimizing the time average of the penalty [math]\displaystyle{ p(t), }[/math] network algorithms can be designed to make control actions that greedily minimize a bound on the following drift-plus-penalty expression on each slot [math]\displaystyle{ t }[/math]:

To stabilize the network while minimizing the time average of the penalty p(t), network algorithms can be designed to make control actions that greedily minimize a bound on the following drift-plus-penalty expression on each slot t:

为了稳定网络，同时使罚 p (t)的时间平均最小，网络算法可以设计为使控制动作贪婪地使下列漂移加罚表达式在每个时隙 t 上的界最小:

[math]\displaystyle{ \Delta L(t) + Vp(t) }[/math]

\Delta L(t) + Vp(t)

Delta L (t) + Vp (t)

where [math]\displaystyle{ V }[/math] is a non-negative weight that is chosen as desired to affect a performance tradeoff. A key feature of this approach is that it typically does not require knowledge of the probabilities of the random network events (such as random job arrivals or channel realizations). Choosing [math]\displaystyle{ V=0 }[/math] reduces to minimizing a bound on the drift every slot and, for routing in multi-hop queueing networks, reduces to the backpressure routing algorithm developed by Tassiulas and Ephremides. Using [math]\displaystyle{ V\gt 0 }[/math] and defining [math]\displaystyle{ p(t) }[/math] as the network power use on slot [math]\displaystyle{ t }[/math] leads to the drift-plus-penalty algorithm for minimizing average power subject to network stability developed by Neely. Using [math]\displaystyle{ V\gt 0 }[/math] and using [math]\displaystyle{ p(t) }[/math] as the negative of an admission control utility metric leads to the drift-plus-penalty algorithm for joint flow control and network routing developed by Neely, Modiano, and Li.

where V is a non-negative weight that is chosen as desired to affect a performance tradeoff. A key feature of this approach is that it typically does not require knowledge of the probabilities of the random network events (such as random job arrivals or channel realizations). Choosing V=0 reduces to minimizing a bound on the drift every slot and, for routing in multi-hop queueing networks, reduces to the backpressure routing algorithm developed by Tassiulas and Ephremides. Using V>0 and defining p(t) as the network power use on slot t leads to the drift-plus-penalty algorithm for minimizing average power subject to network stability developed by Neely. Using V>0 and using p(t) as the negative of an admission control utility metric leads to the drift-plus-penalty algorithm for joint flow control and network routing developed by Neely, Modiano, and Li.

其中 V 是一个非负权重，根据需要选择以影响性能权衡。这种方法的一个关键特征是，它通常不需要了解随机网络事件的概率(如随机作业到达或通道实现)。选择 V = 0可以使每个时隙的漂移范围最小化，对于多跳排队网络中的路由，可以使用 Tassiulas 和 Ephremides 开发的反压路由算法。利用 V > 0并定义 p (t)作为 t 槽的网络功率使用，导出了满足网络稳定性的漂移加惩罚最小化平均功率算法。使用 V > 0和使用 p (t)作为接纳控制效用度量的负值导致了漂移加罚算法的联合流量控制和网络路由开发的 Neely，Modiano 和 Li。

A generalization of the Lyapunov drift theorem of the previous section is important in this context. For simplicity of exposition, assume [math]\displaystyle{ p(t) }[/math] is bounded from below:

A generalization of the Lyapunov drift theorem of the previous section is important in this context. For simplicity of exposition, assume p(t) is bounded from below:

在这种情况下，对前一部分李雅普诺夫漂移定理的推广是很重要的。为了简单起见，假设 p (t)从下面开始有界:

[math]\displaystyle{ p(t) \geqslant p_{\min} \quad \forall t \in \{0, 1, 2, ...\} }[/math]

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

p (t) geqslant p _ { min } quad for all t in {0,1,2，... }

For example, the above is satisfied with [math]\displaystyle{ p_{\min} = 0 }[/math] in cases when the penalty [math]\displaystyle{ p(t) }[/math] is always non-negative. Let [math]\displaystyle{ p^* }[/math] represent a desired target for the time average of [math]\displaystyle{ p(t). }[/math] Let [math]\displaystyle{ V }[/math] be a parameter used to weight the importance of meeting the target. The following theorem shows that if a drift-plus-penalty condition is met, then the time average penalty is at most O(1/V) above the desired target, while average queue size is O(V). The [math]\displaystyle{ V }[/math] parameter can be tuned to make time average penalty as close to (or below) the target as desired, with a corresponding queue size tradeoff.

For example, the above is satisfied with p_{\min} = 0 in cases when the penalty p(t) is always non-negative. Let p^* represent a desired target for the time average of p(t). Let V be a parameter used to weight the importance of meeting the target. The following theorem shows that if a drift-plus-penalty condition is met, then the time average penalty is at most O(1/V) above the desired target, while average queue size is O(V). The V parameter can be tuned to make time average penalty as close to (or below) the target as desired, with a corresponding queue size tradeoff.

例如，在惩罚 p (t)总是非负的情况下，p _ { min } = 0满足上述条件。设 p ^ * 表示 p (t)的时间平均的期望目标。设 V 是一个用来衡量达到目标重要性的参数。下面的定理表明，如果满足漂移加惩罚条件，那么时间平均惩罚最多超过期望目标 O (1/V) ，而平均队列大小为 O (V)。可以对 V 参数进行调整，使时间平均损失尽可能接近(或低于)所需的目标，并对相应的队列大小进行折衷。

Theorem (Lyapunov Optimization). Suppose there are constants [math]\displaystyle{ \varepsilon \gt 0, V, B \geqslant 0, }[/math] and [math]\displaystyle{ p^* }[/math] such that for all [math]\displaystyle{ t }[/math] and all possible vectors [math]\displaystyle{ Q(t) }[/math] the following drift-plus-penalty condition holds:

[math]\displaystyle{ \mathbb{E}[\Delta L(t) + Vp(t) | Q(t)] \leqslant B + Vp^* - \varepsilon \sum_{i=1}^NQ_i(t) }[/math]

Then for all [math]\displaystyle{ t\gt 0 }[/math] the time average penalty and time average queue sizes satisfy:

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

[math]\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} }[/math]

Theorem (Lyapunov Optimization). Suppose there are constants \varepsilon >0, V, B \geqslant 0, and p^* such that for all t and all possible vectors Q(t) the following drift-plus-penalty condition holds:

\mathbb{E}[\Delta L(t) + Vp(t) | Q(t)] \leqslant B + Vp^* - \varepsilon \sum_{i=1}^NQ_i(t)

Then for all t>0 the time average penalty and time average queue sizes satisfy:

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

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

定理(Lyapunov最佳化)。假设有常数 varepsilon > 0，V，B geqslant 0,和 p ^

• 使得对于所有 t 和所有可能的向量 Q (t) ，以下漂移加罚条件成立: : mathbb { E }[ Delta L (t) + Vp (t) | Q (t)] leqslant B + Vp ^
• -varepsilon sum _ { i = 1} ^ NQ _ i (t) : 然后对于所有T > 0时间平均罚金和时间平均队列大小满足: : frac {1}{ t } sum _ { tau = 0} ^ { t-1} mathbb { E }[ p (tau)]等式 p ^
• + frac { B }{ V } + frac { mathbb { E }[ L (0)]}{ Vt } : frac {1}{ t } sum _ { tau = 0} ^ { t-1} sum _ { i = 1}^ N mathbb { E }[ Q _ i (tau)]等分法{ B + V (p ^
• -p _ { min }(p ^
• -p _ { min })}{ varepsilon } + frac { mathbb { E }[ L (0)]}{ varepsilon t }

Proof. Taking expectations of both sides of the posited drift-plus-penalty and using the law of iterated expectations we have:

Proof. Taking expectations of both sides of the posited drift-plus-penalty and using the law of iterated expectations we have:

证据。考虑双方对漂移加罚的期望，并利用迭代期望定律，我们得到:

[math]\displaystyle{ \mathbb{E}[\Delta L(t)] + V \mathbb{E}[p(t)] \leqslant B + Vp^* - \varepsilon \sum_{i=1}^N \mathbb{E}[Q_i(t)] }[/math]

\mathbb{E}[\Delta L(t)] + V \mathbb{E}[p(t)] \leqslant B + Vp^* - \varepsilon \sum_{i=1}^N \mathbb{E}[Q_i(t)]

mathbb { E }[ Delta L (t)] + V mathbb { E }[ p (t)] leqslant B + Vp ^

• -varepsilon sum _ { i = 1} ^ N mathbb { E }[ Q _ i (t)]

Summing the above over the first [math]\displaystyle{ t }[/math] slots and using the law of telescoping sums gives:

Summing the above over the first t slots and using the law of telescoping sums gives:

将上述总和加在第一个 t 槽上，并使用叠加和定律得出:

[math]\displaystyle{ \begin{align} \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{align} }[/math]

\begin{align}

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

\begin{align}

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

Dividing by [math]\displaystyle{ Vt }[/math] and rearranging terms proves the time average penalty bound. A similar argument proves the time average queue size bound.

Dividing by Vt and rearranging terms proves the time average penalty bound. A similar argument proves the time average queue size bound.

用 Vt 除以重排项证明了时间平均惩罚界。一个类似的参数证明了时间平均队列大小的界限。

Related links

• Drift plus penalty
• Backpressure routing
• Lyapunov function
• Foster's theorem
• Control-Lyapunov function

• Drift plus penalty
• Backpressure routing
• Lyapunov function
• Foster's theorem
• Control-Lyapunov function

= 相关链接 = =

• 漂移加罚金
• 背压路由
• 李亚普诺夫函数
• 福斯特定理
• 控制李亚普诺夫函数

Primary Sources

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

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

= 主要来源 =

• M.J. Neely。随机网络优化及其在通信和排队系统中的应用，Morgan & Claypool，2010。

Category:Networking algorithms Category:Queueing theory

类别: 网络算法类别: 排队论

This page was moved from wikipedia:en:Lyapunov optimization. Its edit history can be viewed at 李雅普诺夫优化/edithistory