公司新闻

交替方向乘子法(ADMM)算法原理详解

日期:2022-05-23 10:28:24 作者:乐鱼在线 来源:乐鱼体育安卓版下载 阅读:18

  作为统计学专业研究高维统计问题的菜鸟,自从学了 ADMM 算法,内心极度膨胀(不是)

  (正经)ADMM 算法提供了一个求解含线性等式约束优化问题的框架,方便我们将原始的优化问题拆解成几个相对好解决的子优化问题进行迭代求解。这种“拆解”的功能是 ADMM 算法的核心要义。

  去年刚学 ADMM 的时候写过一个 notes,按自己的想法整理了一套理解 ADMM 算法原理的流程,贴出来和大家交流交流~

  简单来讲,这一优化问题的目标函数包含两组可分离自变量(和),且存在线性等式约束。对于这一优化问题,ADMM 算法首先对目标函数进行增广,将原始优化问题转化为:

  这个更新步骤还是很容易看明白的。但朋友,你懵逼了没有?至少我第一次看这玩意的时候是不知道这三个更新步骤是什么意思的。后来看了 CMU 那个凸优化的课才慢慢搞清楚这个脑洞是怎么开来的。今天来说道说道......

  其中:,,三个函数均为凸函数。我们假设该优化问题存在可行解(设可行区域为)。并设为最优值点,为其中的最优解。

  根据这个不等式,我们发现对于函数而言,在任意满足条件的取值处,我们都有。

  ▲ Tibshrani课件上的一个二元优化问题的例子。把原问题目标函数曲面和对偶问题目标函数曲面画在了一张图里~ (不过要注意看坐标第一维和第二维坐标的定义(x1/u1, x2/u2)。本来原目标函数和对偶问题目标函数的自变量是不同的,但这图换了坐标之后把它两叠在了一起)

  另外,从另一个角度想,如果我们可以证明(强对偶性),那其实我们可以通过求解对偶问题得到原问题的最优取值,同时也可以很方便地得到最优解。后面的对偶梯度下降和 ADMM 其实都可以看成是这个路子。

  具体来看的话,我们假设对偶问题的最优解是,这个时候因为,之前那个很长一段的不等式里的不等号可以全换成等号,也就是:

  你看,这个时候你要求解最优解就容易多了,最简单的是去解这个优化问题:,没了约束条件,各种方法(什么梯度下降,牛顿法)就都好使了~

  ps.根据 Slaters condition,其实很多优化问题都满足的强对偶性。Slaters condition 说明,如果原优化问题是凸的(,,三个函数均为凸函数),且存在强可行的解(strictly feasible)满足:,(注意这儿是严格的不等号),那这个优化问题就满足强对偶性。

  接下来开始讲讲对偶梯度下降法。这个方法其实就用到了对偶问题和原问题之间的关联,本质上是使用梯度下降的方法把对偶问题给解出来,然后也得到原问题的最优解。

  简单来讲,包络定理其实研究的是:对于一个带超参数的优化问题而言,这个超参数的变动会对这一优化问题的最优值产生什么样的影响。

  一句话概括下,包络定理其实说的是:优化问题的最优值对超参数的偏导数等于拉格朗日函数函数在最优点处对该超参数的偏导。

  共轭函数的一个最有用的性质是:即使函数不是凸函数,它的共轭函数仍然是凸函数。其他的一些讨论可以参考这个知乎问题共轭函数的意义。

  因为函数是凸函数,我们知道这个优化问题是满足强对偶性的(根据 Slaters condition),也即可以通过求解对偶问题帮助解决原问题。

  这儿我们选择使用梯度下降法(这儿是求 max,可能得叫梯度上升~)求解这个对偶问题,我们先算一下梯度,发现:

  根据,我们现在可以设计如下的梯度上升算法来求解对偶问题,其中第步迭代的更新公式为:

  具体把之前介绍过的梯度计算细节加进去就构成了完整的对偶梯度下降算法(dual gradient descent)。其中它在第步迭代的更新步骤包括:

  ps.是对偶问题的解好理解,是原问题的解这个要稍微绕一步:注意到更新步骤 1,我们可以得知,当算法收敛时有,所以根据之前对偶问题那一块的内容(就那个很长的不等式那儿)就是原问题的解。

  观察一下这个迭代步骤和 ADMM 的迭代步骤,是不是有点像?但 ADMM 的自变量是包含和两部分的,也就是目标函数对于自变量是可以写成两部分可分离的情况。那这儿有没有对应的一个形式?肯定是有的。。。

  对偶梯度下降法在目标函数对于是可分离的情况下可以有更简单的计算方式(其实就是各个分量拆开),对应的算法叫对偶分解(Dual Decomposition)。

  具体来看的话,我们假设自变量,且有其中为相关的分量()。假设目标函数可以写成可分离的形式,也即:

  因此,使用对偶梯度下降法对这个问题求解时,第一步对的更新可以分解成几个同步进行的小步骤:

  其实这个对偶分解更像是对偶梯度下降里头一个计算上的 trick~ 因为优化分量往往比优化一个合起来的目标函数简单。ADMM 之所以好用,很大一个原因也是因为这个。

  当然,ADMM 算法和“对偶梯度下降+对偶分解”这个解法还是有差别的。我们还差最后一小块砖:增广拉格朗日方法~

  增广拉格朗日方法其实和对偶梯度下降法只有一点点点点点点差别。只是这个方法对原始的目标函数做了一步增广使目标函数变得更“凸”了一些,也是算法更 robust 了一些。具体来看的话,我们考虑下面这个优化问题:

  是一个惩罚参数(penalty parameter)(实际里感觉一般设成 1 就差不多了)。很明显,这个优化问题和原始的优化问题是一样的。

  这儿还有一个细节,第二步梯度下降的学习率直接取了,这个选择有助于更好地收敛~

  这个式子说明:每一步迭代之后,我们得到的都满足原优化问题的 dual feasibility。!这个性质保证了,我们只需要关注 primal feasibility,当 primal feasibility 也得到满足的话,迭代的结果就是最优值。这一定程度上也加快了算法收敛速度。

  然而这么做的代价是:增广后的目标函数和拉格朗日函数不再是可分离的,所以我们不能像前面对偶分解那样简便地做计算。比如,假如我们的目标函数可以写成:

  ADMM 算法实际上就是为了解决增广拉格朗日算法不能做分解的问题。它考虑了自变量由两个部分(标准的 ADMM 只针对两个部分的情况,虽然很多时候多个部分的情况在实际中也能收敛)组合而成时候,如何分解优化的问题。

  这边把文章最前面写的 ADMM 部分的介绍再搬运一遍下来(人类的本质是复读机......hhhh)

  和增广拉格朗日算法相比,上述步骤里对于的更新步骤是一致的,差别在前两步:这两个步骤按顺序地对两个自变量分量和进行了更新。

  这个算法在一定条件下是可以证明收敛的。可以看 Boyd 的 ADMM 小册子或者看这儿 ADMM 算法的详细推导过程是什么?- 覃含章的回答~

  我们刚刚介绍过,标准的 ADMM 算法里头对应的增广拉格朗日函数是如下式子~ 后续对和都是基于这个式子。

  这个式子本质上就是把一次项的部分凑到前面的二次项里面,使得整个拉格朗日函数形式更加简单,写程序推公式的时候更方便一些。是与无关的量(对参数更新没有帮助)。

  关于和的选取,Boyd 给出了如下建议值,该值由绝对部分和相对部分构成,具体而言:

  高维统计里面往往需要求解 “loss+penalty”形式的优化问题,其中 loss 部分往往是可导的;而 penalty 部分往往是不可导的(比如惩戒)。这个时候没法使用普通的梯度下降法、牛顿法是没法求解的。这个时候就需要使用其他的优化算法求解,比如:近端梯度下降(proximal gradient descent),坐标下降法(Coordinate Descent)等等。ADMM 也是里面很常用的方法。

  假设自变量矩阵,因变量,系数向量。此时 Lasso 需要求解如下优化问题:

  这儿我们引入了一个新的变量把惩戒项里的替换掉,这样分开可以更为方便地进行优化。我们使用 Scaled Form ADMM 进行求解。写出这个问题的拉格朗日函数(忽略优化无关项):

  这其中,第 1 步为二次优化问题,有显示解(凑平方或者求导都行);第 2 步也有显示解,其中函数

  如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。

  总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。

  PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。

  • 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注

  • 稿件建议以markdown格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题

  • PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算

  • 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者

  • 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿

乐鱼在线
乐鱼在线 @ 版權歸所有 乐鱼在线