交替方向乘子法

交替方向乘子法是一种具有并行计算能力，解决凸优化问题的算法。本文主要介绍了交替方向乘子法的形成和内容，第一部分先简要介绍了优化问题和凸优化问题，以便明白交替方向乘子法解决的是什么问题。第二部分依次介绍了拉格朗日函数，拉格朗日对偶函数和拉格朗日对偶问题，最终想说明在强对偶成立下，原始优化问题的最优解可以通过拉格朗日对偶问题这一无约束凸优化问题的最优解获得，主要参考了《Convex Optimization》一书。自第三部分开始，我们介绍的具体算法均是基于强对偶条件的成立，因此均属于凸优化问题求解算法。第三部分介绍了在严格凸目标函数下求解拉格朗日对偶问题的两种算法—对偶上升法和对偶分解法。第四部分介绍了加强拉格朗日方法，它弱化了对偶上升法的严格凸函数要求，但同样损失了对偶分解法并行计算的能力，推动了交替方向乘子法的提出,主要参考了《Multiplier and gradient methods》这篇文章。第五部分介绍了交替方向乘子法的内容，优缺点和应用方向。第三部分和第五部分主要参考了《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》这篇文章。

优化问题和凸优化问题

1.优化问题

优化问题的定义是在给定的约束条件下，通过选择一组变量致力于使目标函数取到最大值或最小值。根据约束条件的不同，优化问题分为无约束优化问题，含等式约束的优化问题和含不等式约束的优化问题。优化问题的一般数学形式表示为：

其中为一个列向量，为目标函数，为不等式约束函数和为等式约束函数。

2.凸优化问题

凸优化问题是在优化问题的基础上进一步要求目标函数为凸函数，的定义域为凸集。凸集的定义为，若，集合S为凸集。凸函数的定义为凸集S为x的定义域，，若，则f为凸函数；如果取不到等号，f为严格凸函数。当目标函数是凸函数时，凸优化问题存在唯一解，即凸优化问题的局部最优解就是全局最优解。

拉格朗日对偶问题

对于一个优化问题来说，约束条件的存在给直接求解目标函数最值增添了不少阻碍。在这种情况下，可以借助拉格朗日函数将原始的优化问题（下文均简称原始问题）转化为对偶问题，这样原始问题的解就可以通过对偶问题的来求解。

1.拉格朗日函数

原始问题为（1）的拉格朗日函数引入了2类拉格朗日乘子和，

其中。拉格朗日函数一方面可以看成是关于的函数，那么拉格朗日函数就是原始问题中目标函数和约束函数的线性加权；另一方面也可以看成是关于拉格朗日乘子和的一阶多项式函数。

2.拉格朗日对偶函数

取拉格朗日函数关于的下确界，得到关于拉格朗日乘子和的函数，称为拉格朗日对偶函数，表达式为。无论原始问题的目标函数的凹凸性如何，其拉格朗日对偶函数总是个凹函数。

拉格朗日对偶函数具有一个重要性质，如果原始问题最优解对应的目标函数值为，则

这个性质反映了拉格朗日对偶函数是原始问题最优值的一个下界，向我们揭示了在某些条件成立下，可以通过最大化拉格朗日对偶函数以等价原始问题最优值这一思路。

3.拉格朗日对偶问题

基于性质（2），我们试图最大化拉格朗日对偶函数，并且由于是凹函数，因此最大化属于凸优化问题，这个凸优化问题被称为拉格朗日对偶问题，

如果拉格朗日对偶问题的最优解为和，其对应的拉格朗日对偶函数的最优值为，根据性质（2）可知。当时，定义为弱对偶；当时，定义为强对偶。对于弱对偶来说，只要可以求出拉格朗日对偶问题的最优解，就总是成立的。可究竟什么条件下强对偶成立，此时，我们可以用最优化拉格朗日对偶问题（无约束凸优化问题）代替最优化原始问题（有约束优化问题）呢？

面临上面这个问题，Slater条件可以用于帮助判断，Slater条件是强对偶成立的充分条件，即Slater条件下强对偶成立。若原问题目标函数f是凸函数，非边界定义域中存在点x，使等式和非等式约束全部成立，则强对偶成立。

在通过Slater条件验证出强对偶成立下，，可以通过求解拉格朗日对偶问题来得到原始问题的最优解,因为两个问题的最优解一样。主要求解思路包括两部分，先最大化拉格朗日对偶函数得到关于拉格朗日乘子的最优解和，再在和已知的情况下最小化拉格朗日函数得到最优解,数学形式如下，

对偶上升法和对偶分解法

在强对偶成立的条件下，本部分将在上述求解思路的基础上详细介绍求解拉格朗日对偶问题最优解的具体算法—对偶上升法和对偶分解法。对偶上升法和对偶分解法均要求原始问题目标函数是个严格凸函数，因此，这两个方法均是凸优化问题的求解算法。

1.对偶上升法

在原始问题目标函数是严格凸函数的条件下，假使第次迭代后，原问题的解为，拉格朗日对偶问题得到了最优解为，则第次迭代时

i.求解原始问题的最优解

ii.求解拉格朗日对偶问题的最优解

由于这一步骤是要最大化拉格朗日对偶函数这一凹函数，因此使用梯度上升法求解拉格朗日乘子，

2.对偶分解法

若原始问题的目标函数f(x)可以依分解，,原始问题的约束条件也可以分解，，,则此时拉格朗日函数也可以被分解为

这样求解关于整体的原始问题最优解就可以转变为同时求解个单个的原始问题最优解，进而求解整体的拉格朗日对偶问题也可以通过求解个的拉格朗日对偶问题来实现。这样对偶上升法就演变为对偶分解法，此算法具有并行计算的能力。

的拉格朗日对偶问题的算法过程与对偶上升法一致，假使第次迭代后，原问题的解为，拉格朗日对偶问题得到了最优解为，则第次迭代时

加强拉格朗日方法

无论是对偶上升法还是对偶分解法，两者的前提都是要求原始问题的目标函数为严格凸函数。这个要求在实际问题很难达到，我们希望严格凸的假设限制能够被弱化为只要求目标函数为凸函数。因此加强拉格朗日方法出现，它通过构建了一个新的加强拉格朗日函数来实现目标函数为凸函数的假设，它也属于凸优化问题的求解算法。下文中加强拉格朗日算法均针对的是只含等式约束的凸优化问题，

加强拉格朗日方法的核心在于构建了一个新的加强拉格朗日函数，它在基础拉格朗日函数的基础上添加了罚函数，

经过验证，加强拉格朗日函数在最优点处的一阶导数和二阶微分性质均与普通拉格朗日函数L在最优点处的一致。因此，在强对偶成立的情况下，原始问题的最优解不仅可以通过拉格朗日对偶问题来求解，还可以通过加强拉格朗日对偶问题。

假设加强拉格朗日方法的算法第次迭代后，原问题的解为，加强拉格朗日对偶问题得到了最优解为，则第次迭代时

i.求解原始问题的最优解

ii.求解加强拉格朗日对偶问题的最优解

假设是第次迭代时加强拉格朗日函数的的最小值，则

因此，加强拉格朗日对偶问题的最优解为

加强拉格朗日方法不仅仅要求凸目标函数，还对外生参数比较鲁棒，任意大于0的值对求得的原始问题最优解不会产生很大的影响。但对比对偶分解法来说，由于罚函数是二阶形式导致加强拉格朗日方法不具有分解和并行计算的能力。

交替方向乘子法的提出是为了弥补加强拉格朗日方法不能分解的缺点，这个方法既吸取了加强拉格朗日乘子法的弱限制条件，只要求目标函数为凸函数即可，又结合了交替方向法来实现变量的单独交替迭代。但交替方向乘子法实现并行计算的思想与对偶分解法不同，对偶分解法是通过分解原始问题的目标函数和约束函数进而分解拉格朗日函数并单个优化实现的，而交替方向乘子法由于加强拉格朗日函数存在二阶形式的罚函数无法分解并优化，它是通过先将全部参数分块，再更新一组参数同时固定其他参数来进行优化的。虽然在理论上我们可以将全部变量划分为p组，但实际应用中交替方向乘子法通常将全部变量划分为2组变量，这是因为p组变量的交替方向乘子法存在不收敛的情况。

下文中交替方向乘子法将全部变量分为两组变量，，其原始问题（等式约束的凸优化问题）如下，

其中。交替方向乘子法的第一步要先根据原始问题建立一个加强拉格朗日函数

若使用加强拉格朗日法，和只能作为一个整体被求解，。但交替方向乘子法通过固定并更新，交替地求解和的最优解，算法形式如下，

若原始问题的目标函数和均是非空闭凸函数，并且其拉格朗日函数的鞍点存在，这样交替方向乘子法的算法收敛。

与梯度下降法，牛顿法等相比较，交替方向乘子法有着更大的收敛误差和较慢的收敛速度，但在数据规模和解空间非常大，并且不要求解的高精度时，一些方法不再适合，这时采用交替方向乘子法将变量分块并单独交替迭代求解，把一个大优化问题变为可分布式同时求解的多个子问题，因此交替方向乘子法常用于分布式并行计算中。

参考文献

[1] Faybusovich L . Convex Optimization-S.Boyd and L. Vandenberghe[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL AC, 2006.

[2] Hestenes M R . Multiplier and gradient methods[J]. Journal of Optimization Theory & Applications, 1969, 4(5):303-320.

[3] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein and others, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends® in Machine Learning, 3(1):1-122, 2011.

[4] C. Chen, B. He, Y. Ye and X. Yuan, The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent, Mathematical Programming, 155(1-2):57-79, 2016.

[5]Eckstein J ,  Yao W . UNDERSTANDING THE CONVERGENCE OF THE ALTERNATING DIRECTION METHOD OF MULTIPLIERS: THEORETICAL AND COMPUTATIONAL PERSPECTIVES[J]. Pacific Journal of Optimization, 2015, 11(4):619-644.

- END -