最近看了ADMM算法，发现这个算法需要用到许多不少前备知识，在搜索补齐这些知识的过程中感觉网上的资料与总结在零散的同时又不够清晰，在此本文对这一块的内容进行汇总，同时表达自己的一些理解。
目录
拉格朗日乘子法
原问题
问题转换
KKT条件
条件形式
KKT条件推导
KKT条件对于简化求解优化问题的作用
拉格朗日对偶函数
对偶问题
线性约束下拉格朗日函数对偶函数的共轭形式(选读)
对偶上升法
梯度上升法
对偶上升法
罚函数
增广Lagrangian乘子法
ADMM算法（交替方向乘子法）
ADMM算法的一般形式
ADMM算法求解2-block的凸优化问题
ADMM的收敛性证明思路
三个不等式的证明
拉格朗日乘子法
本段内容参考了拉格朗日(Lagrange)乘子法超简说明。
先从物理意义上介绍拉格朗日乘子法。
原问题
我们要解决带有等式约束的最优化问题。为方便书写，以二维函数为例：
maxf(x,y),s.t.g(x,y)=0
用下图表示这个问题。 f(x,y)参数x,y在二维平面内，存在从x,y到f(x,y)的映射，因此其本身是一个曲面，根据f(x,y)大小用等高线（蓝色）表示。g(x,y)=0是二维平面内的一条曲线（红色）。
图片描述
我们要找g(x,y)=0上的一个点，其位于f(x,y)最大的等高线上。
问题转换
step1
求解上述问题等价于：找到g(x,y)=0上的一点，这一点处g(x,y)=0和该点f(x,y)的等高线相切。
这一句怎么理解呢？可以用反例直观地理解。如果g(x,y)=0和该点f(x,y)等高线相交而不相切（如上图所示黑点）。假设蓝色箭头的方向f(x,y)对应等高线的值是递增的，那么如果不相切，图中灰色的点所对应的f(x,y)=d1肯定有d1>d，显然d就不是最大值。只有当g(x,y)=0和f(x,y)等高线相切，其切点才是在g(x,y)=0上f(x,y)值最大的点,该切点也是我们想要找到的点。
step2
在step1中，我们知道了在条件g(x,y)=0的条件下，f(x,y)取最大值的点的位置，就是在两条曲线的切点处。而上述问题又等价于找到g(x,y)=0上的一点，这一点g(x,y)=0和f(x,y)=d的切向量共线，与此相对应，法向量也共线。(切向量与法向量是正交关系)
什么是切向量？简单来说就是曲线的切线的方向向量。这里有关于切向量的一些简单介绍。曲线F(x,y)=0的切线与法线方程 - 百度文库
显然，既然g(x,y)=0与f(x,y)=d相切，那么这两条曲线在切点处具有公共切线，也就是说，在切点处，这两条曲线的切向量方向必定是相同的，而法向量的方向也必定是相同的。
对于f(x,y)=d来说，其法向量为u=(，)
对于g(x,y)=0来说，其法向量为v=(，)
由于法向量共线，那么就有u=v,这里≠0，即有
..........(1)
..........(2)
≠0 ..........(3)
再加上g(x,y)=0..........(4)
此时我们便将寻找切点的任务转化为等价的三个条件，再将这四个条件合成一式。
L(x,y,λ)=f(x,y)−λg(x,y)
∇L(x,y,λ)=0
≠0
其中 ∇表示对三个参数求导。其中 λ称为拉格朗日乘子， L称为拉格朗日函数。
求解
通过∇L=0可以求解出若干组(x,y)，分别代入f(x,y)，找出值最大的一组，即为所求。（注意∇L=0只是f(x,y)在条件g(x,y)=0上取得最优值的必要条件而非充分条件。当问题属于凸优化问题时，∇L=0所求得的解才是最优解。）
KKT条件
条件形式
我们直接给出kkt条件，再对kkt条件进行说明与推导。
参考自KKT条件介绍，设目标函数f(X)，X是一个多维向量，不等式约束为g(X)，等式约束条件h(X)。此时的约束优化问题描述如下：
则我们定义不等式约束下的拉格朗日函数L，则L表达式为：
其中f(x)是原目标函数，hj(x)是第j个等式约束条件，λj是对应的约束系数，gk是不等式约束，uk是对应的约束系数。
此时若要求解上述优化问题，可以通过引入KKT条件来简化计算，KKT条件如下：
对于以上KKT条件，(1)是对拉格朗日函数取极值时候带来的一个必要条件，(2)是拉格朗日系数约束（同等式情况），(3)是不等式约束情况，(4)是互补松弛条件，(5)、(6)是原约束条件。
对于一般的任意问题而言，KKT条件是使一组解成为最优解的必要条件，当原问题是凸问题的时候，KKT条件也是充分条件。
KKT条件推导
对于条件(1)已经在第一节拉格朗日乘子法做了详细的解释。
对于条件(2),其实也已经在第一节做了解释，即g(x,y)=0与f(x,y)=d在切点处，切线的法向量共线，也即方向相同1，有u=v,若=0则无法体现共线的条件。同时还有另一种解释，若=0，那么 *hj(x)=0，hj(x)的取值对的取值无影响。
(不过我看一些书籍里面没有这个条件，我问过我们最优化的老师也说不用，本人也偏向不用这个条件。我们这里假设只有等式约束，那么拉格朗日函数就为,当等式约束h(x)≠0时，,而当等式约束成立h(x)=0，，设置的目的就是为了有前述的关系，所以这里对并未做什么约束，所以可以取）
对于条件(3)，由于，所以；因此 仅有在下才能取得最大值，故这是KKT第三个条件必须要成立的原因——即第三个条件满足时，它意味着有 ，接下来就是求解 ，所以该过程又可记为：,条件(3)就是为了使这条关系成立而设置的。
对于条件(4),是为了使关系式成立，详细推导见下文。
条件(5)(6)分别为原问题的等式与不等式约束。
KKT条件对于简化求解优化问题的作用
接下来说说KKT条件对于简化求解优化问题的作用。为了简化问题，我们假设最优化问题中约束条件只有不等式约束。假设问题如下：
我们将问题写成拉格朗日函数的形式如下：
其中 L(x,λ) 被称为拉格朗日函数，系数 λ 被称为拉格朗日乘子或者对偶变量。通过 ∇ 计算后，可得到候选集，然后从候选集中验算选择满足条件的结果即可。（ ∇：依次对函数所有自变量求偏导）
拉格朗日对偶函数
对于定义域 D 上 x 的所有取值，拉格朗日函数的最小值即为拉格朗日对偶函数(dual function)：
该式表示：将 x 视为常数，而则是只关于自变量 的函数。对整个定义域 D 内所有的 x 值，都有与之对应的关于只关于自变量 的函数，这些函数集合在整个自变量取值范围中的最小值，即为拉格朗日对偶函数 。
所以恒成立，即拉格朗日对偶函数是最优解的下界
对偶问题
最重要的地方来了！我们的目标是要求出，但是往往按照先求再求的顺序进行求解的话，会遇到求解过于复杂等问题。这个时候需要将转化为即的形式了，从而通过改变求解顺序达到简化计算的目的。
但是是否等于呢？
在KKT条件下，答案是等于的。详细证明过程如下图所示。转自
深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件
转化后的形式就是原优化问题的拉格朗日对偶问题(dual problem)。
通过转换求解顺序，最终求得的最优解。
线性约束下拉格朗日函数对偶函数的共轭形式(选读)
转自拉格朗日函数、对偶上升法、对偶分解法
考虑线性约束（即自变量的幂均为 1）下的最优化问题：
其共轭形式求解如下
即
这里的与上文的是一样的，只是换了个符号。对于共轭函数的理解，可以理解为直线到的最大距离，关于这部分的更多知识，大家可以阅读【优化】共轭函数。
对偶上升法
梯度上升法
在讲如何利用前面讲的KKT条件进行对偶上升法之前，先简单回顾一下梯度上升法。转载自梯度的方向为什么是函数值增加最快的方向？
以二元函数为例(多元函数可以此类推)，我们想要求出函数在点(x0,y0)处沿某一方向的方向导数，可以按照变化率的定义去求解，即只需求出函数的增量与自变量沿着某一方向增量比值的极限即可。假设某一方向的单位向量为，为此向量与x轴正向夹角，显然根据的不同，此向量可以表示任意方向的单位向量。
此时函数沿此方向的变化率为
公式证明见方向导数公式的证明
对偶上升法
转自拉格朗日函数、对偶上升法、对偶分解法
回到一般问题。
对偶上升法的关键就是利用上文求 时，把求解顺序从转化为，然后按照后者的顺序来进行迭代求解的。
对偶上升法处理步骤：
1、假设,已经是对偶问题的最优解。
2、求解,得到,。
3、显然。
4、利用梯度上升法更新对偶问题最优解：
5、按 1~4 迭代进行。
罚函数
原文可见罚函数与增广Lagrangian乘子法
罚函数法是一种广泛采用的约束优化方法，有时也称为惩罚，其基本原理是通过采用罚函数或障碍函数，将约束条件整合进优化目标中去。继续考虑我们的一般问题：
我们用D表示x的可行域，用S表示整个搜索空间。有两种添加惩罚项的方法，一种是加性，即在x脱离可行域的时候给f(x)加上一个大于0的项p(x)，另一种是乘性，即在x脱离可行域的时候给f(x)乘一个大于1的项p(x)。通常采用的还是加性罚函数，将原始约束优化问题转变成无约束优化问题：
这里是惩罚参数。
对于等式约束，可以定义罚函数：
它对满足等式约束的x无影响，对违反等式约束的x施加惩罚。
对于不等式约束，可以定义两类罚函数，外罚函数和内罚函数。外罚函数例如：
r可取1或2。外罚函数对所有违背不等式约束的点进行惩罚。
内罚函数例如
或
内罚函数对“企图”不满足不等式约束的点进行惩罚，也称为障碍函数。
外罚函数对可行域之外的所有点进行惩罚，是不等式约束优化问题的精确解，是最优设计方案；而内罚函数阻挡了可行边界的点，得到的解只满足严格不等式，是一种次优解。外罚函数可以用不可行点启动，收敛慢，内罚函数的启动点必须是可行点，选择起来存在困难，但是收敛比较快。结合等式约束的罚函数，得出同时有等式和不等式约束的混合罚函数法：
（1）混合外罚函数法
（2）混合内罚函数法
增广Lagrangian乘子法
基于Lagrangian乘子法的对偶上升法的主要缺点是：
（1）只有当约束优化目标具有局部凸结构的时候，对偶的无约束问题才是良好定义的，λ的更新才是有意义的；
（2）Lagrangian目标函数的收敛比较费时，因为Lagrangian乘子λ的更新是一种上升迭代，只能适度地加速收敛。
罚函数的不足在于收敛慢，大的惩罚参数容易引起转化后的无约束问题的病态，从而造成算法的数值不稳定性。
将两种方法结合起来的增广Lagrangian乘子法是能够减缓二者缺点的一种简单有效的途径。
我们假设优化问题只有等式约束h(x),对Lagrangian目标函数添加罚函数组成。
这就是增广Lagrangian乘子法。可以看出，若ρ=0，增广Lagrangian乘子法退化为Lagrangian乘子法；若 λ = 0，增广Lagrangian乘子法退化为标准罚函数法。
在求解Lρ最优值的时候，用到了上文讲过的对偶上升法，对参数的迭代更新如下所示：
（步长也可以取不同的)
增广Lagrangian乘子法相比于Lagrangian乘子法的优点是，不要求f(x)具有局部凸结构，因此适用范围更广。
ADMM算法（交替方向乘子法）
ADMM算法的一般形式
参考自ADMM算法（交替方向乘子法）
ADMM认为，在统计学与机器学习中，经常会遇到大尺度的等式约束优化问题，即 的维数 n很大。如果x可以分解为几个子向量，即，其目标函数也可以分解为：
则大尺度的优化问题可以转化为分布式优化问题。相应的，等式约束矩阵Ax=b也分块为：
于是增广Lagrangian目标函数可以写作：
其中对于每一个子块，在中，等式约束项为：
惩罚项使用了二次范数平方的形式进行表示：
再采用对偶上升法，即可得到能进行并行运算的分散算法：
（步长也可以取不同的)
这里的是可以独立更新的。由于以一种交替的或序贯的方式进行更新，所以称为“交替方向”乘子法（ADMM算法）。
ADMM算法求解2-block的凸优化问题
参考自ADMM算法的详细推导过程是什么？
经典的ADMM算法适用于求解如下2-block的凸优化问题（ 是最优值，令 ,表示一组最优解）：
Block指可以将决策域分块，分成两组变量， , 这里面 ,,, 都是凸的。
可以写出这个凸优化问题的增广拉格朗日函数:
那么ADMM，也就是所谓“交替方向”的乘子法就是在原基础上（x,z一起迭代）改成x,z单独交替迭代（如果有更多block也是类似）。即ADMM算法为
本节最后，我们指出ADMM算法形式的另一种等价形式。如果定义所谓的残差（residual）为，那么注意到再定义 作为所谓scaled dual variable，我们有
即我们可以改写ADMM算法形式为
这个形式就比前面那个更简洁些，我们一般叫前一种形式为ADMM的unscaled形式，而这种就自然是scaled形式了。很多ADMM分析都是基于这个scaled形式的。
ADMM的收敛性证明思路
在两个不太强的假设前提下，本节给出ADMM基本形式的收敛性证明的思路。
假设1： 的解是存在的。
假设2：（非增广）拉格朗日函数至少有一个至少有一个鞍点（saddle point），即原问题和对偶问题的最优值相等（有kkt点的意思）。
基于这两个假设，我们证明如下结果：
残差收敛。随着 ， 也就是说最终我们的解是可行（feasible）的。目标函数值收敛。随着 ，, 也就是说最终我们的目标函数值是最优的。对偶变量收敛。，随着也就是最终对偶变量的值收敛到某个对偶变量的最优解。
注意这里隐含了一个ADMM的有意思的特性，即原变量，primal variable， , 不一定会收敛到一个最优解 。
先定义一个李雅普诺夫函数（Lyapunov function）,
和对偶空间上的残差。
证明的思路主要由三个不等式组成。
注意不等式 (*)说明 的序列是单调递减的，这样我们就知道 和 序列都是有上界的。因此对 k求和我们就有
这就直接表明了随着 。 然后，基于我们知道 和 的右边项随着 都是趋近于0的，这样就得到了随着 。 因此我们就知道，证明了这三个不等式就能直接推出我们所要的收敛性结果。
下一节就给出三个不等式的证明。顺序是先证明，再证明 。
三个不等式的证明
变形完毕。
一文详解从拉格朗日乘子法 KKT条件 对偶上升法到罚函数与增广Lagrangian乘子法再到ADMM算法（交替方向乘子法）
