Lyapunov optimization是Michael J. Neely发展起来的网络优化理论，可以参考[1,2]。因为网络研究中缺乏理论，简单好使的算法，没有高大上的公式吓人，好像就不能发到高级别的期刊上。Lyapunov optimization有几个公式，就成为一个发论文的模板。只要找到一个问题背景，把公式套进去，就是一篇。关于这理论[3]的引用量已经达到1500多次了，但是很难找到相关的代码！
我很早就知道这个理论。于是花了几天，研究了一下，没办法，眼红呀！看了几篇文章[4,5,6]，这几篇文章不仅名字类似，内容也感觉是一个模子制造的。
知乎上有答主对这个方向有几句评价[7]。我就不过多评价了，毕竟我没有相关的测试。
[4]中的公式推导，还是挺容易理解的。我就按照这个模板，换个场景，稍微地推导一下。
如上图所示的排队系统，数据包的入队速度是
a
(
t
)
a(t)
a(t)，出队速度是
b
(
t
)
b(t)
b(t)，目标是是怎么样调整
a
(
t
)
a(t)
a(t),使得队列mean rate stable，同时达到最大的用户满意度。用户的满意度，采用效用函数衡量，
U
=
β
×
l
o
g
(
a
)
U=\beta\times log(a)
U=β×log(a)。请求的数据流速率
a
(
t
)
a(t)
a(t)越大，用户的满意度越高，但是会造成很长的队列占用。
队列占用，用
Q
Q
Q表示。Q的变化方程：
Q
(
t
+
1
)
=
max
[
Q
(
t
)
−
b
(
t
)
,
0
]
+
a
(
t
)
Q(t+1)=\max[Q(t)-b(t),0]+a(t)
Q(t+1)=max[Q(t)−b(t),0]+a(t)
队列mean rate stable的含义是：
lim
T
→
∞
E
(
Q
(
t
)
)
T
=
0
\lim_{T\to\infty}\frac{\mathbb{E}(Q(t))}{T}=0
T→∞limTE(Q(t))=0
优化方程：
max
U
s
u
b
j
e
c
t
lim
T
→
∞
E
(
Q
(
t
)
)
T
=
0
\max U \\ subject \lim_{T\to\infty}\frac{\mathbb{E}(Q(t))}{T}=0
maxUsubjectT→∞limTE(Q(t))=0
定义
L
(
t
)
=
Q
(
t
)
2
2
L(t)=\frac{Q(t)^2}{2}
L(t)=2Q(t)2，
Δ
L
(
t
)
=
L
(
t
+
1
)
−
L
(
t
)
\Delta L(t)=L(t+1)-L(t)
ΔL(t)=L(t+1)−L(t)。
Δ
L
(
t
)
\Delta L(t)
ΔL(t)被称为lyapunov drift。
Q
(
t
+
1
)
2
=
{
max
[
Q
(
t
)
−
b
(
t
)
,
0
]
+
a
(
t
)
}
2
≤
Q
(
t
)
2
+
b
(
t
)
2
+
a
(
t
)
2
−
2
b
(
t
)
Q
(
t
)
+
2
∗
Q
(
t
)
(
a
(
t
)
−
b
(
t
)
)
−
2
∗
a
(
t
)
b
(
t
)
≤
Q
(
t
)
2
+
b
(
t
)
2
+
a
(
t
)
2
+
2
∗
Q
(
t
)
a
(
t
)
Q(t+1)^2=\{\max[Q(t)-b(t),0]+a(t)\}^2\\ \leq Q(t)^2+b(t)^2+a(t)^2-2b(t)Q(t)+2*Q(t)(a(t)-b(t))-2*a(t)b(t)\\ \leq Q(t)^2+b(t)^2+a(t)^2+2*Q(t)a(t)
Q(t+1)2={max[Q(t)−b(t),0]+a(t)}2≤Q(t)2+b(t)2+a(t)2−2b(t)Q(t)+2∗Q(t)(a(t)−b(t))−2∗a(t)b(t)≤Q(t)2+b(t)2+a(t)2+2∗Q(t)a(t)
Q
(
t
+
1
)
2
−
Q
(
t
)
2
≤
b
(
t
)
2
+
a
(
t
)
2
+
2
∗
Q
(
t
)
a
(
t
)
Q(t+1)^2-Q(t)^2\leq b(t)^2+a(t)^2+2*Q(t)a(t)
Q(t+1)2−Q(t)2≤b(t)2+a(t)2+2∗Q(t)a(t)
Δ
L
(
t
)
≤
B
+
Q
(
t
)
a
(
t
)
\Delta L(t)\leq B+Q(t)a(t)
ΔL(t)≤B+Q(t)a(t)
假设存在
B
≥
b
(
t
)
2
+
a
(
t
)
2
2
B\geq \frac{ b(t)^2+a(t)^2}{2}
B≥2b(t)2+a(t)2。不必较真，全是为了凑出来！
定义lyapunov drift reward，
Δ
L
(
t
)
−
V
U
\Delta L(t)-VU
ΔL(t)−VU，V是一个常数。想要获取一个大的满意度，却会导致
Δ
L
(
t
)
\Delta L(t)
ΔL(t)增加，所以定义lyapunov drift reward，权衡两项，使得aggregate plus最优。这个问题就转化为根据队列占用长度，调节速率的问题。
min
Q
(
t
)
a
(
t
)
−
V
U
\min Q(t)a(t)-VU
minQ(t)a(t)−VU
上式可以求导，可得
Q
−
β
×
V
a
×
l
n
2
Q-\frac{\beta\times V}{a\times ln2}
Q−a×ln2β×V。使其为0,求得速率控制公式：
a
(
t
)
=
β
×
V
Q
(
t
)
×
l
n
2
a(t)=\frac{\beta\times V}{Q(t)\times ln2}
a(t)=Q(t)×ln2β×V
最终效果如何呢，不知道。参数
V
,
β
V, \beta
V,β可以慢慢选，直到出现需要的数据。
[8]中有给出了相应的代码实现。
[1]Lyapunov optimization-wiki
[2] home page
[3] Stochastic Network Optimization with Application to Communication and Queueing Systems
[4] Quality-oriented Rate Control and Resource Allocation in Time-Varying OFDMA Networks
[5] Joint Rate Control and Power Allocation for Non-Orthogonal Multiple Access Systems
[6] Joint rate control and power allocation for low-latency reliable D2D-based relay network
[7] 李雅普诺夫优化问题？
[8] https://github.com/CrQiu/Lyapunov-optimization
