交替方向乘子法（ADMM）的基本原理&ADMM在分布式并行计算中的应用
作者：覃含章
编者按
本文介绍ADMM最基本情形的推导。通过这篇文章，你将了解ADMM算法的基本思路，收敛性分析的基本原理，和它理论上的一些局限性。
本文的内容主要来自著名的讲义：
Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends® in Machine learning, 2011, 3(1): 1-122.
正文开始前多说几句。Stephen Boyd作为一名优化科学家，除了自己的很多研究，这辈子最杰出的贡献就是广泛地将优化理论严谨地介绍给了工程界。其中，ADMM就是一个很重要的例子。这个方法其实理论优化界早就研究了几十年（何炳生老师语），但是也只是到了最近几年，如Boyd包括Stanford的Yinyu Ye老师等人，才对这方面的研究进行了“再挖掘”，引起了大家的广泛注意。
经典的ADMM算法适用于求解如下2-block的凸优化问题（
是最优值，令
表示一组最优解）：
Block指我们可以将决策域分块，分成两组变量，
这里面
都是凸的。分成2-block是因为3-block及以上的问题性质会差一点，分析起来不太好说清楚（虽然实际当中基本上几个block都可以用，一般都会收敛...）。
那么我们这里就可以写出这个凸优化问题的增广拉格朗日函数（augmented Lagrangian function）：
注意到这个增广的意思就是在原来的拉格朗日函数后面加了个平方的正则项（系数
），这个主要是为了不需要
一定要是严格凸（strictly convex）/值域有限（只要是一般的凸函数就行了）然后也能保证收敛性。然后我们对
用dual ascent（对偶上升法），或者也就是拉格朗日乘子法就知道可以有这样一个算法形式：
Dual ascent的原理非常简单，本质上来说就是primal variable迭代方向取拉格朗日函数对primal variable的次微分，dual variable迭代方向取拉格朗日函数对dual variable的次微分（这里的话就是
）。这也是所谓拉格朗日乘子法的一般思路（method of multipliers）。当然这边还有一些细节，比如对偶变量迭代步长选了
。所以如果对这方面基础知识不太熟悉的同学，可以从比如S. Boyd and L. Vandenberghe的凸优化书第五章看起。我们这边只讨论ADMM形式的收敛证明。
那么ADMM，也就是所谓“交替方向”的乘子法就是在原基础上（
一起迭代）改成
单独交替迭代（如果有更多block也是类似）。即，我们的ADMM算法为
在两个不太强的假设前提下，本节给出ADMM基本形式的收敛性证明的思路。
假设1：凸函数
是closed和proper的。
假设2：（非增广）拉格朗日函数
至少有一个鞍点（saddle point）。
假设1等价于epigraph
都是非空的闭凸集（closed nonempty convex set），也就是说
，
的解一定是存在的。注意，这个假设仍然没有限制
一定要是可微（differentiable）的。
假设2主要是为了保证强对偶（strong duality）对这个问题成立（在假设1成立的基础上），即原问题和对偶问题的最优值相等。熟悉凸优化理论的同学应该一下子就能明白，这边就留给大家作为思考。注意假设2也没有怎么限制
，比如它们都可以不是满秩（full rank）的。
基于这两个假设，我们证明如下结果：
残差收敛。随着
也就是说最终我们的解是可行（feasible）的。
目标函数值收敛。随着
也就是说最终我们的目标函数值是最优的。
对偶变量收敛。随着
也就是最终对偶变量的值收敛到某个对偶变量的最优解。
注意这里隐含了一个ADMM的有意思的特性，即原变量，primal variable，
不一定会收敛到一个最优解
好了，为了说明思路，一开始我们先定义一个李雅普诺夫函数（Lyapunov function），
和对偶空间上的残差
证明的思路主要由三个不等式组成。
注意不等式
说明
的序列是单调递减的（利用李雅普诺夫函数的证明思想最初来自于控制领域，这里可能看的不是很明显，熟悉控制理论的同学就应该觉得trivial了），这样我们就知道
和
序列都是有上界的。因此对
求和我们就有
,
这就直接表明了随着
然后，基于
我们知道
的右边项随着
都是趋近于0的，这样就得到了随着
因此我们就知道，证明了这三个不等式就能直接推出我们所要的收敛性结果。
下一节就给出三个不等式的证明。顺序是先证明
所以我们看到其实掌握了证明的主要思路，具体证明其实没什么技术难度，顶多就是algebra稍微有点绕。这也是ADMM算法分析的一般特点，我们这还是最基本的情况，复杂情况的分析就是绕得多了（主要是因为迭代的时候各种“交替”）...
注意我这边只给出了关于ADMM算法收敛到最优可行解（原变量还不一定最优）和最优目标函数值的证明。这里我完全没有讨论收敛速率的问题。收敛速率，在很多其它优化算法里面都是比较容易分析的，像一阶二阶算法，内点法等等。但在ADMM的分析里面，收敛速率分析确实是这块领域的一大难点。事实上，实际当中你如果写代码跑ADMM会发现它不像那些梯度下降，牛顿法，很容易快速收敛到一个较高的误差精度，ADMM实际的收敛速度往往比那些算法慢得多。。ADMM的主要应用，主要是在解空间规模非常大的情况下（比如
都是存储空间上GB的矩阵），这个时候很多传统的方法不好用，强制需要分块求解，而且对解的绝对精度往往要求也没那么高。当然，然后你还得祈祷在primal space上argmin那个迭代的形式比较简单。。
不过这个算法分析起来确实各种难点。除了最前面已经提到从2-block到multi-block的推广不trivial。还有一个实际中常用的trick不好分析：往往这个
如果变速率，即取成一个递减的
序列效果会比现在固定值要好。这种变步长的ADMM分析起来相比基础版也是会困难很多...
最后说一下如果我们固定
，实际中跑算法可以怎么设定终止条件。一个常用的终止条件就是当原空间和对偶空间的残差
都比较小的时候终止。原理的话，从收敛性证明我们知道
所以如果
小了，我们就知道
和
的差（gap）也就比较小了。这也是primal-dual优化算法常用的一种终止条件。具体来说，我们的终止条件可以取成：
里面的
可以取成比如
这个量级。
二、ADMM在分布式并行计算中的应用
作者：王志涛
转载自公众号：智能驾驶课题组
摘要：智能汽车的网联化协同驾驶将进一步提升道路交通的通行效率。随着受控车群规模的增长，所求解的问题规模增加迅速，这对云控或边缘平台的计算效率提出了很高的要求。智能驾驶课题组（iDLab）提出了一种适用于大规模网联车群集中式控制的并行求解算法，将问题计算复杂度将多项式级降低为线性级。通过引入一致性约束解耦原问题，进一步结合ADMM（交替方向乘子法）框架分解为一系列可并行计算的子问题，每一个子问题可分配一个计算单元，利用单元之间的信息交互达到最优解的一致性收敛，实现了大规模网联多车协同问题的并行加速求解。
1.介绍
通过ADMM（交替方向乘子法）框架对大规模智能网联汽车协同控制问题进行求解。通过对车车间的约束进行解耦，将问题分解为可以同时求解而不是顺序计算的子问题。之后利用计算节点组成的集群网络对问题进行并行求解，以期望达到计算复杂度与规模无关的目的，从而极大提高求解效率，拓展问题的求解规模。由于车辆之间的空间位置关系复杂多变，车车交互耦合难以处理；因此如何应用合理的解耦方案，实现车车耦合约束的分解，从而实现并行计算是本工作的研究重点。课题组研究工作的主要贡献：a.设计了用于分布式计算方法部署的计算节点网络结构。b.提出了用于求解大规模协同控制问题的并行计算方法。
2. 交替方向乘子法
科学研究与工程实践中，诸多问题都可以构建为凸优化问题。当规模较大时，计算效率往往成为问题求解的瓶颈。将问题进行解耦，使其可以分布式并行计算，是解决大规模问题求解效率低的可行方案之一。交替方向乘子法（alternating direction method of multipliers, ADMM），适用于大规模凸优化问题的分布式并行求解。ADMM提出于上个世纪70年代，经过多年的研究，理论逐渐完善，由于它在机器学习、网络优化等领域应用，受到研究界的关注。ADMM适用于求解如下2-block的优化问题：
其中, , , , ，与均为凸函数。ADMM的求解思路如下，为了处理约束，首先将问题写为增广拉格朗日乘子的形式：
该问题可以通过对偶上升进行迭代：
该过程相当于迭代求解的过程。
ADMM在对偶上升法的基础之上，将与单独交替迭代，即：
这使得与为可分解函数（类似于这种形式）时，问题的求解过程可以实现解耦，从而为分布式并行计算提供了条件。
3.网联多车协同控制问题的构建
首先，构建集中式协同的最优控制问题。思路是采用分层式处理方案，首先每个车辆从导航模块获取各自的行驶路线；之后以此为参考轨迹行驶，由于参考轨迹未考虑约束关系，时空上存在重叠，导致车车间有碰撞风险，因此需要在行驶过程中进行动态避撞。
工作用图论来描述整个车群系统，构建车车交互拓扑图。车车交互拓扑图为一无向图，即节点间不存在次序关系。图中每一节点和每一辆车相对应，图中的边对应两辆车间存在的潜在冲突关系。同时，可以定义与每一个节点有邻接关系的节点集合为该节点邻域。通过邻域节点的定义，构建如下的车车避撞约束：
该约束为一个非凸约束，而非凸约束在优化问题中比较难以处理，工作结合车辆的空间位置变化特点和有限时域优化问题的特性，利用泰勒展开线性化的方式，将非凸约束转化为凸约束近似处理。
据此，构建如下的集中式最优控制问题
在优化问题中以车辆待优化的性能指标为目标函数，同时考虑自车动力学约束，以及车车交互拓扑图描述的协同避撞约束。
4.并行求解算法设计
对该最优控制问题中的耦合关系进行分析。利用指示函数，可以将约束写入目标函数中，得到一个更为简洁的问题形式。
对优化问题新的形式进行分析，问题分为两个加和部分，分别为自车性能部分和交互约束部分。两部分的变量存在重叠而互相关联，造成整个问题耦合在一起，如何对这一约束进行解耦，是实现并行计算的关键。我们期望对问题的原形式进行变形，令其可以通过ADMM框架进行分解，以期实现问题解耦及并行计算。首先观察原问题，自车性能部分与交互约束部分变量相同，互相重叠，造成两部分耦合。工作通过引入一致性约束的方法对原问题进行处理，从而实现解耦。方法流程如下：对交互约束部分的求解变量生成一个与之前不同的副本。为了使得问题的与原来等价，通过引入约束，使这两部分的变量相等于同一个值，从而做到问题的不变，因为该约束形式是使不同变量相等于同一个值，因此称之为一致性约束，而这种优化形式称为一致性优化问题。下图展现了这一变换过程。
经过转化后，可以发现，一致性优化问题的形式与ADMM求解的优化形式相同。因此，该一致性优化问题也可以通过三步迭代求解，并且发现迭代的求解过程可以并行进行。一致性优化问题按照ADMM的三步迭代求解，需要分别更新三种变量，分别是：第一步更新一致性变量，第二步更新控制变量，第三步更新对偶变量。第一步：
第二步：
第三步：
每一步迭代过程中，其他步骤更新的变量都为定值，这就实现了不同变量约束的解耦。而由于问题的加和形式，每一步迭代更新中，加和形式内部的各个变量独立无关。以上两点特性，使得我们通过ADMM迭代求解一致性优化问题，得到并行求解算法。为了算法的部署，还需要设计一个可以实现并行计算的计算节点组成的集群网络。我们以车辆交互拓扑图为基础，图中与每辆车对应的绿色节点负责更新自车本地优化问题的控制量和对偶量的更新。
进而为每一条边分配一个红色节点，用于更新避撞约束部分的控制量和对偶量。绿色节点和红色节点统称为从节点。最后，为了进行一致性变量的更新，为每一个绿色节点和与之对应的红色节点集匹配一个黄色节点，称为主节点。主节点与从节点分别负责完成各自的计算任务，同时二者之间进行通讯，交换计算所需的信息。之后通过不断迭代，算法不断逼近最优点。设定包括原始变量半径和对偶变量半径的收敛条件，当收敛条件达到时，算法终止。
5.算法性能验证
智能驾驶课题对所提出的集中式协同控制及其并行求解算法的效果进行验证。计算环境为8线程机器，即计算节点数量为8个。优化问题的求解器为qpOASES，并行计算的多线程API为OpenMP。对三种比较典型的场景进行仿真，分别是多车道超车，以及两种无信号交叉口的通行场景。
传统求解方法由于计算复杂度始终与车辆数量相关，随着规模增大，求解负担急剧增加，也限制了问题的求解规模。所提出的并行计算方法，当网络计算节点数量有限时，算法的计算复杂度为线性级，即此时计算时间与车辆规模呈线性增长。仿真结果验证了所提出并行算法的计算效率和对于大规模场景的适用性。
6.结论
课题组研究工作提出了一种适用于大规模智能网联汽车协同控制的并行计算方法。算法通过引入一致性约束实现了优化问题中约束的解耦，实现了集中式问题的并行求解。仿真结果证明了本工作提出的并行算法相对于集中式求解，降低了计算复杂度，解决了问题求解时间随车辆规模多项式攀升的难题，为云控网联式自动驾驶奠定了基础。
参考文献：
[1]S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.
[2]Z. Wang, Y. Zheng, S. Li, K. You, K. Li., “Parallel Optimal Control for Cooperative Automation of Large-scale Connected Vehicles via ADMM,” In:2018 21st International Conference on Intelligent Transportation Systems (ITSC). IEEE, 2018. p. 1633-1639.
[3]S. Li, Z. Wang, Y. Zheng, Q. Sun, J. Gao, F. Ma, K. Li, “Synchronous and Asynchronous Parallel Computation for Large-Scale Optimal Control of Connected Vehicles,” Under reviewing, 2019.