MSA（the Method of Successive Averages）算法的满足条件是怎么来的？

此文章属于文献研读内容，文章内容来源于以下文献
Warren B. Powell, Yosef Sheffi , (1982) The Convergence of Equilibrium Algorithms with Predetermined Step Sizes. Transportation Science ,16(1):45-55. http://dx.doi.org/10.1287/trsc.16.1.45

摘要

MSA算法可用于求解交通分配问题的均衡解，在算法迭代的过程中在目标函数的下降方向事先设定一个步长序列，所设定的步长序列在满足一定条件的情况下，可以确保目标函数最终收敛于均衡解。以下将分析所设定的步长序列的满足条件，给出算法的收敛证明。

前言

通常，求解最小规划问题的经典迭代方式即为确定目标函数的下降方向，并在每次迭代时沿下降方向，选择一个可以使得目标函数最小化的步长。然而，目标函数沿下降方向的变化情况难以评估，若选择步长不当，目标值也能也会变大，可参见优化算法----模拟退火算法（Simulated Annealing,SA）一文中的第一个图形。因此，一些问题的解难以确定。本文主要针对一类交通分配问题展开研究，其目标函数基于路径构建，所研究问题不适用于大型交通网络。

本文研究的分配算法，其步长为一个提前确定的序列，序列元素与目标函数的变化情况无关。本文会分别针对确定以及logit依赖的随机交通分配问题证明MSA算法的收敛性。

MSA算法

MSA算法简介与来源

定义$x^k$为第$k$次迭代的决策变量，${\alpha }_k,(0\le {\alpha }_k\le 1)$为第$k$次迭代的步长，$d^k$为一个可行的下降方向
一般地，可通过如下迭代表达式最小化凸函数$F(\mathbf{x})，\mathbf{x}\in R^n$
$$x^{k+1}=x^k+{\alpha }_k{d}^k.\text{\hspace{1em}(1)}$$在大多数问题中，所选择的迭代步长${\alpha }_k$需要使得目标函数在一次次的迭代过程中沿下降方向$d^k$不断减小。MSA算法的核心即为每一次迭代所需的步长，其取值的大小不依赖于目标函数，迭代过程中的步长构成的序列若满足如下条件$$\sum _{k=1}^{\infty }{\alpha }_k=\infty ,\text{\hspace{1em}(2)}$$和$$\sum _{k=1}^{\infty }{\alpha }_k^2<\infty ,\text{\hspace{1em}(3)}$$则在一定的条件下，决策变量序列$x^k$将收敛于最优值。
MSA算法的提出可追溯至 Robbins & Monroe ，该文章主要分析如何求解一个单变量不可精确测量的函数的最大值或根，同样应用方程（1）进行迭代，但其下降方向$d^k$仅可近似估测。该文章的最著名拓展为 Blum 一文。

Robbins.H & Monroe.S ,1951. A Stochastic Approximation Method, Ann. Math. Stat. 22, 400-407.
Blum.J,1954. Multidimensional Stochastic Approximation Methods, Ann. Math. Stat. 25, 737-744.

算法收敛性证明

收敛性证明的方法改编自Blum一文中的证明。
最小化一个实值函数$F(\mathbf{x}),\mathbf{x}\in S$，其中$S\subset R^n$为一个给定的紧且凸的向量集合。假定使得$F(\mathbf{x})$取得最小值的自变量的取值为${\mathbf{x}}^{\ast }$,使用方程（1）进行迭代。

命题 给定具有连续一阶导数和二阶导数的凸函数$F(\mathbf{x})$，若以下条件成立，即$$\begin{array}{rl}& \sum _{k=1}^{\infty }{\alpha }_k=\infty ;\sum _{k=1}^{\infty }{\alpha }_k^2<\infty ,\\ & -\infty <F({\mathbf{x}}^{\ast })\le mi{n}_{||\mathbf{x}-{\mathbf{x}}^{\ast }||>\delta ,\mathbf{x}\in S}F(\mathbf{x})<\infty ;\delta >0,\\ & ma{x}_{||\mathbf{x}-{\mathbf{x}}^{\ast }||>\delta ,\mathbf{x}\in S}\nabla F(\mathbf{x}{)}^{{}^{\prime }}\mathbf{d}<0;\delta >0,\\ & ma{x}_{\mathbf{x}\in S,0\le \psi \le 1}({\mathbf{d}}^k{)}^{{}^{\prime }}{\nabla }^{2}F(\mathbf{x}+\psi {\alpha }_k{\mathbf{d}}^k){\mathbf{d}}^k<B<\infty ,\end{array}\text{\hspace{1em}(4.1)(4.2)(4.3)(4.4)}$$其中$B>0$为一个充分大的有界上界，
则由迭代方程（1）得到的决策变量序列$x^k,k=1,2,\dots$最终收敛于${\mathbf{x}}^{\ast }$。

证明. 应用泰勒定理可得，对于某个$\psi$, $0\le \psi \le 1$有如下等式成立：
$$F({\mathbf{x}}^{k+1})=F({\mathbf{x}}^k)+{\alpha }_k\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k+\frac{1}{2}{\alpha }_k^2(d^k{)}^{{}^{\prime }}{\nabla }^{2}F(\mathbf{x}+\psi {\alpha }_k{\mathbf{d}}^k){\mathbf{d}}^k.\text{\hspace{1em}(5)}$$迭代并关于$k$从1到$N$叠加可得$$F({\mathbf{x}}^{N+1})=F({\mathbf{x}}^1)+\sum _{k=1}^N{\alpha }_k\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k+1/2\sum _{k=1}^N{\alpha }_k^2({\mathbf{d}}^k{)}^{{}^{\prime }}{\nabla }^{2}F({\mathbf{x}}^k+\psi {\alpha }_k{\mathbf{d}}^k){\mathbf{d}}^k，\text{\hspace{1em}(6)}$$应用条件(4.4)，并令$\bar{\alpha }$为收敛序列${\alpha }_k^2$的极限，即 $li{m}_{N\to \infty }{\sum }_{k=1}^N{\alpha }_k^2=\bar{\alpha }$，则对（6）式两侧取极限，有如下不等式成立$$li{m}_{N\to \infty }F({\mathbf{x}}^{N+1})<F({\mathbf{x}}^1)+\sum _{k=1}^{\infty }{\alpha }_k\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k+1/2B\bar{\alpha },\text{\hspace{1em}(7)}$$根据条件（4.3）可知，${\sum }_{k=1}^{\infty }{\alpha }_k\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k<0$，然而由（4.2）可知，（7）式左侧的表达式是有界的，则可得${\sum }_{k=1}^{\infty }{\alpha }_k\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k$是有界的，即$$-\infty <\sum _{k=1}^{\infty }{\alpha }_k\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k\le 0,\text{\hspace{1em}(8)}$$又因为${\sum }_{k=1}^{\infty }{\alpha }_k=\infty$，则一定有$$li{m}_{k\to \infty }\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}{\mathbf{d}}^k=0.\text{\hspace{1em}(9)}$$则根据（4.3），可以得知$$\underset{k\to \infty }{\lim }{\mathbf{x}}^k={\mathbf{x}}^{\ast }.\text{\hspace{1em}(10)}$$

使用MSA算法对确定性网络均衡问题收敛性的验证

考虑确定性网络均衡问题，假定路段出行成本函数仅为其自身流量的函数，根据Beckmann et al.，确定性网络均衡问题等价于求解如下约束最小化问题$$mi{n}_{\mathbf{x}\in S}F(\mathbf{x})=\sum _{a\in A}{\int }_0^{x_a}{t}_a(\omega )d\omega ,\text{\hspace{1em}(11)}$$其中$S$为所有可行路段流量的集合，满足如下约束条件$$\begin{array}{rl}& x_a=\sum _{rs\in D}\sum _{l\in Q_{r}s}{f}_l^{rs}{\delta }_{al}^{rs}\forall a\in A,\\ & \sum _{l\in Q_{rs}}{f}_l^{rs}=q_{rs}\forall rs\in D,\end{array}\text{\hspace{1em}(12.1)(12.2)}$$
其中
$A=$ 组成交通网络的有向弧集合，$|A|=m$,
$D=$ 起讫点集合，
$Q_{rs}=$ 连接起点$r$与终点$s$的路径集合，
$x_a=$ 弧$a$上的流量，
$f_l^{rs}=$ 连接起讫点$rs$的路径$l$上的流量，
$q_{rs}=$ 起讫点 $rs$ 间的出行需求，
$t_a(.)=$ 弧$a$上的出行时间函数，
${\delta }_{al}^{rs}=1$ 若弧$a$在连接起讫点$rs$的路径$l$上；否则，${\delta }_{al}^{rs}=0$.
如下，将通过展示条件（4.1）-（4.4）成立来求解优化问题（11）的解。如（1），定义迭代过程$${\mathbf{x}}^{k+1}={\mathbf{x}}^{k+1}+{\alpha }_k{\mathbf{d}}^k,\text{\hspace{1em}(13)}$$并令${\alpha }_k=1/k$，满足条件 (4.1)，下降方向 ${\mathbf{d}}^k={\mathbf{y}}^k-{\mathbf{x}}^k$，其中 ${\mathbf{y}}^k$ 为如下无约束优化问题的解$$mi{n}_{\mathbf{y}\in S}G(\mathbf{y})=F({\mathbf{x}}^k)+\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}(\mathbf{y}-{\mathbf{x}}^k).\text{\hspace{1em}(14)}$$因为$F(.)$ 为严格的凸函数，且有界，因此条件（4.2）成立。此外，令$\mathbf{y}={\mathbf{x}}^k$，则根据（14）式可得 $G(\mathbf{y})=F({\mathbf{x}}^k)$，说明 $G({\mathbf{y}}^k)\le F({\mathbf{x}}^k)$，或者对于任意的 ${\mathbf{y}}^k\ne {\mathbf{x}}^k$，有下列不等式成立$$\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}({\mathbf{y}}^k-{\mathbf{x}}^k)\le 0,\text{\hspace{1em}(15)}$$因为目标函数$F(\mathbf{x})$为凸函数，且定义域为凸集，因此一定存在$\mathbf{y}\in S$使得$mi{n}_{\mathbf{y}\in S}\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}({\mathbf{y}}^k-{\mathbf{x}}^k)=0$，因为路段成本函数为仅关于自身流量的连续函数，目标函数（11）具有严格凸性，因此最值点唯一，即当且仅当 ${\mathbf{x}}^k={\mathbf{x}}^{\ast }$时，有 $\nabla F({\mathbf{x}}^k{)}^{{}^{\prime }}({\mathbf{y}}^k-{\mathbf{x}}^k)=0$，即若$\mathbf{x}\ne {\mathbf{x}}^{\ast },\mathbf{x}\in S$时，有$\nabla F(\mathbf{x}{)}^{{}^{\prime }}(\mathbf{x}-{\mathbf{x}}^k)<0$，条件（4.3）成立。

注记： 根据Weiterstrass定理，定义在紧集上的连续函数一定存在最值点。更进一步地，若目标函数为严格凸函数，且可行域为凸集，则最优解${\mathbf{x}}^{\ast }$唯一。
证明：反证法。设目标函数为$F(x)$，$F(x)$为严格凸函数，假定当目标函数为严格凸函数时，最优解不唯一。同时假定${\mathbf{x}}_1$，${\mathbf{x}}_2$均为最优值点，即$F({\mathbf{x}}^1)=F({\mathbf{x}}^2)=F({\mathbf{x}}^{\ast })$，则根据严格凸函数的定义有，对于任意的$\lambda \in [0,1]$，有$$F[\lambda {\mathbf{x}}_1+(1-\lambda ){\mathbf{x}}_2]<\lambda F({\mathbf{x}}_1)+(1-\lambda )F({\mathbf{x}}_2)=F({\mathbf{x}}^{\ast }),$$上式与${\mathbf{x}}^{\ast }$为最值点矛盾。
更多Weiterstrass定理内容，可参见博文凸优化问题最优解存在且唯一的条件。

最后验证条件（4.4）.通过计算可得$${\nabla }^{2}F(\mathbf{x})=\left[\begin{array}{c}\frac{d{t}_1(x_1)}{d{x}_1}0\dots 0\\ 0\frac{d{t}_2(x_2)}{d{x}_2}\dots 0\\ ⋮⋮\dots ⋮\\ 00\dots \frac{d{t}_m(x_m)}{d{x}_m}\end{array}\right],$$因此，$$({\mathbf{d}}^k{)}^{{}^{\prime }}{\nabla }^{2}F(\mathbf{x}){\mathbf{d}}^k=\sum _{a\in A}(d_a^k{)}^2(d{t}_a(x_a)/d{x}_a),\text{\hspace{1em}(16)}$$根据假设$d{t}_a(x_a)/d{x}_a$为有界的，且根据出行需求的有界性可知 $d_a^k=y_a^k-x_a^k$ 是有界的，因此可知（16）式的左侧一定有界，因此条件（4.4）成立，算法的收敛性得以验证。

使用MSA算法对随机网络均衡问题收敛性的验证

应用上述符号定义，logit选择模型依赖的随机均衡条件为$$f_l^{rs}=q_{rs}(e^{-\theta c_l^{rs}}/\sum _{m\in Q_{rs}}{e}^{-\theta c_m^{rs}});\forall l\in Q_{rs}\forall rs\in D,\text{\hspace{1em}(17)}$$其中$$c_l^{rs}=\sum _{a\in A}{\delta }_{al}^{rs}{t}_a(x_a)\forall l\in Q_{rs},\forall rs\in D,\text{\hspace{1em}(18)}$$$Q_{rs}$为起讫点$rs$间所有的路径集合，$\theta$ 为感知系数。根据Fisk，条件（17）与（18）为如下凸规划问题的一阶最优条件：
$$mi{n}_{f_l^{rs}}F(\mathbf{x})=(1/\theta )\sum _{rs\in D}\sum _{l\in Q_{rs}}{f}_l^{rs}ln{f}_l^{rs}+\sum _{a\in A}{\int }_0^{x_a}{t}_a(\omega )d\omega ,\text{\hspace{1em}(19)}$$
s.t.$$\begin{array}{rl}& \sum _{l\in Q_{rs}}{f}_l^{rs}=q_{rs}；\forall rs\in D,\\ & x_a=\sum _{rs\in D}\sum _{l\in Q_{rs}}{f}_l^{rs}{\delta }_{al}^{rs};\forall a\in A,\\ & f_l^{rs}\ge 0\forall l\in Q_{rs},\forall rs\in D.\end{array}\text{\hspace{1em}(19.1)(19.2)(19.3)}$$

Fisk. C., 1980. Some developments in equilibrium traffic assignment methodology, Trans. Res. 14B, 243-256.

类似于上一节的证明，为了证明收敛性，需要确定上述（4.1）-（4.4）四个条件成立，定义迭代方程为${\mathbf{x}}^{k+1}={\mathbf{x}}^k+{\alpha }_k{\mathbf{d}}^k$，且${\alpha }_k=1/k$，下降方向 ${\mathbf{d}}^k={\mathbf{y}}^k-{\mathbf{x}}^k$，目标路段流量为$$y_a=\sum _{rs\in D}\sum _{l\in Q_{rs}}{q}_{rs}(e^{-\theta c_l^{rs}}/\sum _{m\in Q_{rs}}{e}^{-\theta c_m^{rs}}){\delta }_{al}^{rs},\text{\hspace{1em}(20)}$$需注意的是随机用户均衡问题中的变量为路径变量，但算法本身仅需要路段流量，因此可避免路径枚举。
根据目标函数（19）的严格凸性可知，条件（4.2）成立。令$\tilde{S}$为所有可行路径流量的集合，定义$\mathbf{g}，\mathbf{h}$为对应于$\mathbf{y}$，$\mathbf{d}$ 的路径向量，$$g_l^{rs}=q^{rs}(e^{-\theta c_l^{rs}}/\sum _{m\in Q_{rs}}{e}^{-\theta c_m^{rs}}),$$以路径流量为变量的下降方向 $\mathbf{h}=\mathbf{g}-\mathbf{f}$，因为路径分配函数的连续性，路径变量与路段变量一一对应，因此有$${\mathbf{f}}^{k+1}={\mathbf{f}}^k+(1/k){\mathbf{h}}^k,\text{\hspace{1em}(21)}$$则$$\begin{array}{rl}(\partial F(\mathbf{f})/\partial f_l^{rs})& =(1/\theta )[1+ln{f}_l^{rs}]+c_l^{rs}\\ & =(1/\theta )+(1/\theta )[ln{f}_l^{rs}-ln{q}^{rs}\ast (e^{-\theta c_l^{rs}}/\sum _{m\in Q_{rs}}{e}^{-\theta c_m^{rs}})]\\ & +(1/\theta )ln(q^{rs}/\sum _{m\in Q_{rs}}{e}^{-\theta c_m^{rs}})\\ & =(1/\theta )[ln{f}_l^{rs}-ln{g}_l^{rs}]+U_{rs}\end{array}$$其中$U_{rs}$ 为所有不包含路径$l$的项，则有$$\begin{array}{rl}{\nabla }_{\mathbf{f}}F(\mathbf{f}{)}^{{}^{\prime }}\mathbf{h}& =\sum _{rs\in D}\sum _{l\in Q_{rs}}[(1/\theta )(ln{f}_l^{rs}-ln{g}_l^{rs})+U_{rs}]\ast [g_l^{rs}-f_l^{rs}]\\ & =\sum _{rs\in D}\sum _{l\in Q_{rs}}[(1/\theta )(ln{f}_l^{rs}-ln{g}_l^{rs})][g_l^{rs}-f_l^{rs}]\\ & +\sum _{rs\in D}{U}_{rs}\sum _{l\in Q_{rs}}(g_l^{rs}-f_l^{rs})\end{array}\text{\hspace{1em}(22)}$$因为${\sum }_{l\in Q_{rs}}{g}_l^{rs}={\sum }_{l\in Q_{rs}}{f}_l^{rs}=q_{rs}$，因此（22）式的第二项为0。又根据函数的单调性可知$(ln{f}_l^{rs}-ln{g}_l^{rs})](g_l^{rs}-f_l^{rs})\le 0$，当且仅当$g_l^{rs}=f_l^{rs}$ 时$(ln{f}_l^{rs}-ln{g}_l^{rs})](g_l^{rs}-f_l^{rs})=0$，因此有条件（4.3）成立。
最后验证条件（4.4）.经计算可得$$\frac{{\partial }^{2}F}{\partial f_l^{rs}\partial f_k^{rs}}=(1/\theta )({\delta }_{k,l}/f_l^{rs})+\sum _{a\in A}(d{t}_a/d{x}_a){\delta }_{al}^{rs}{\delta }_{ak}^{rs}，\text{\hspace{1em}(23)}$$ ${\delta }_{k,l}$为克罗内克算子，即有${\delta }_{k,l}=1$，若$k=l$；否则 ${\delta }_{k,l}=0$。根据假设，所有的路段出行时间都是有界的，因此一定存在一个上界$\hat{c}$为路网中最长路径上的可能路径出行时间。若$V^{rs}$为给定OD对间的所有流量，$V^{rs}>0$，则所有路径上流量的最下界，可通过设定$c_l^{rs}=\hat{c}$，$c_k^{rs}=0，k\ne l$ 计算得出，从而有$${\hat{f}}_l^{rs}=(V^{rs}{e}^{-\theta \hat{c}})/(e^{-\theta \hat{c}}+(|Q^{rs}|-1)),\text{\hspace{1em}(24)}$$$|Q^{rs}|$为起讫点$rs$间的所有路径的数量。令 ϵ = m i n r s { f ^ l r s } \epsilon=min_{rs}\{\hat{f}_l^{rs}\} ϵ=minrs​{f^​lrs​}，因而可得$0<ϵ<f_l^{rs}$。又因为$d{t}_a/d{x}_a$有界，则（23）式有界。从而可得条件（4.4）成立。