本文主要是介绍理解ADMM, ALF和Split Bregman,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
理解ADMM, ALM和Split Bergman
- 引言
- Alternating Direction Method of Multipliers
- Augmented Lagrangian Multipliers
- 小结
- Splitt Bregman
引言
在图像去模糊,低光照图像增强和去噪等任务时,我们都会引入各种先验或约束项来缓解这些t逆问题(inverse problems)的病态性(ill-posedness)。比如,我们会用 L 2 L_2 L2, L 1 L_1 L1等约束图像的光滑性,或者梯度的稀疏性。在贝叶斯框架,如最大后验估计(MAP), 变分法(variational method),求解这些问题都需要相关的优化算法。在很多文章中都会说,我用了啥方法求解,对于我这个优化理论的小白来说,实在是一头雾水。我本来打算系统地学习优化理论,但是我发现,等自己什么都了解一下再去做科研黄花菜都凉了。且不说都学不学得会,就算学会了也不一定都能用到。于是我决定不再做一个“仓鼠”, 总是收藏各种资源。我要把在解决具体问题过程中遇到的相关算法吃透。
以下介绍ADMM, ALF和Split Bergman,算作一个知识输出。一方面有利于自己组织知识结构,另一方面也希望可以给同行做点微不足道的贡献。
Alternating Direction Method of Multipliers
ADMM: 交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是求解约束问题的最优化算法框架, 通常解决的是等式优化问题。主要思路就是“各个击破,分而治之”,将一个大的全局的问题分解为几个子问题(sub-problem):原始变量、分裂变量以及对偶变量(即拉格朗日系数,Lagrange coefficient)三种变量的交替更新^ 1。从其命名我们可以知道,“交替”是一个很重要的策略。这个算法是每个子问题就是求解一个分量,与此同时固定其他分量。整个优化就是一个大循环,大循环中有几个小循环,这些小循环就是子问题的优化过程^ 2
Augmented Lagrangian Multipliers
ALM: 在谈增广拉格朗日函数(Augmented Lagrangian Multipliers, ALM)前,我们要讲Lagrangian Multipliers,这就是高数课本中的那个拉格朗日(他来了!他来了!)函数,那时我们要求解一个目标函数 f ( x , y ) f(x, y) f(x,y)的极值,另外要有一个限制条件 g ( x , y ) = c g(x, y)=c g(x,y)=c。
我们那个时候是怎么做的呢?我们会构造一个新的函数 L ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) L(x, y,\lambda)=f(x, y)+\lambda(g(x, y)-c) L(x,y,λ)=f(x,y)+λ(g(x,y)−c)。值得注意的是 λ \lambda λ就是上面所说的拉格朗日系数,也就是对偶变量。然后我们会分别对 x , y , λ x,y,\lambda x,y,λ求偏导: ∂ L ∂ x = 0 , ∂ L ∂ y = 0 , ∂ L ∂ λ = 0 \frac{\partial L}{\partial x}=0,\frac{\partial L}{\partial y}=0,\frac{\partial L}{\partial \lambda}=0 ∂x∂L=0,∂y∂L=0,∂λ∂L=0。
对于ALM, 我们要关注的是"Augmented",所谓“增广”,大白话就是加了东西嘛?在LF基础上, ALM加了对约束增加一个惩罚项(这是一个二次惩罚项)。这篇博文中讲,之所以加上这么一个惩罚项,是因为LF还不够“凸”(越“凸”越强,我笑了!)。引入惩罚就是把约束问题变成非约束问题^ 3(”非约束“和”凸“是等价的概念嘛?如果你有相关理论解释请留言吧!)。在另外一篇博文中分析了为什么加的是惩罚项是二次的原因:
至于为什么加的是二次惩罚项,主要因为我们求解的问题有个前提:针对于等式约束或者小于等于型不等式约束,恰能用二次惩罚项建模
在某乎中有人评论道:
Lagrange Multiplier可以看成是linear penalty,Augmented Lagrangian可以看成是linear+quadratic penalty。Augmented Lagrangian等式约束更容易被满足,即Augmented Lagrangian的收敛性更强,收敛速度也会快一些。
总而言之,针对于上面举的一个LM例子,最终的ALF表示为:
L ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) + ρ 2 ∥ g ( x , y ) − c ∥ 2 L(x, y,\lambda)=f(x, y)+\lambda(g(x, y)-c)+\frac{\rho }{2}\left \| g(x, y)-c\right \|^2 L(x,y,λ)=f(x,y)+λ(g(x,y)−c)+2ρ∥g(x,y)−c∥2
针对于这个ALF函数,ADMM的流程如下:
- 求解 x x x(同时固定 y , λ y,\lambda y,λ), x k + 1 = arg min x L ( x , y k , λ k ) x^{k+1}= \underset{x}{\argmin}L(x,y^k,\lambda^k) xk+1=xargminL(x,yk,λk)
- 求解 y y y(同时固定 x , λ x,\lambda x,λ), y k + 1 = arg min y L ( x k + 1 , y , λ k ) y^{k+1}= \underset{y}{\argmin}L(x^{k+1},y,\lambda^k) yk+1=yargminL(xk+1,y,λk)
- 求解 λ \lambda λ(上面已经得到了 x k + 1 , y k + 1 x^{k+1},y^{k+1} xk+1,yk+1), λ k + 1 = λ k + ρ ( g ( x k + 1 , y k + 1 ) − c ) \lambda^{k+1}= \lambda^k+\rho(g(x^{k+1},y^{k+1})-c) λk+1=λk+ρ(g(xk+1,yk+1)−c)
小结
我们针对ALM和ADMM做一个小小的总结:
- LF收敛困难,但是函数几个方向是可以分解的。
- 为提高收敛性,ALF在LF基础上引入二次惩罚项,但二次惩罚项破坏了LF的可分解特性
- ADMM就是为了解耦同时又可以保证ALF的收敛性而被提出(只是众多方法中的一种,欢迎补充)。因此有人总结道:ADMM=Augmented Lagrangian+Alternating Direction Minimization, 即ALF早就有了,ADMM只是一种交替优化的一种方式^ 4。
Splitt Bregman
Splitt Bregman: 在约束图像梯度方面, L 1 L_1 L1比 L 2 L_2 L2更稀疏,但也更难以求解。分裂Bregman迭代算法是为了求解 L 1 L_1 L1正则约束的优化问题的(这篇文章谈到ADMM也可以求解 L 1 L_1 L1正则约束问题)。本质上与ADMM一样, 并无区别,这篇博文谈到分裂Bregman只是缩放版的ADMM(截至本文完成时,我只是一个门外汉,先蹲个坑,以后会比较两者区别)。
最后贴一个S. Boyd的论文中ADMM的Matlab代码网页,这里有许多examples.
这里还有一篇文章对S. Boyd的2011年的文章《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》翻译和总结,推荐阅读:
[1] http://joegaotao.github.io/cn/2014/02/admm
这篇关于理解ADMM, ALF和Split Bregman的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!