从算子角度理解优化方法

知行编程网 2022-06-11 13:00 知行编程网 | 隐藏边栏 | 抢沙发 | 4 0

文章评分 0 次，平均分 0.0 ：

来自 | 知乎作者 | 邓康康

地址 | https://zhuanlan.zhihu.com/p/150605754

编辑 | 深度学习这件小事

本文仅作学术交流，如有侵权，请联系后台删除

在求解一个优化问题时，我们可以采用不同的优化方法，而这些方法又可以从不同角度去理解。这篇文章我想讲下如何从算子角度出发去理解许多已存在的优化方法。有错误的地方欢迎大家指出来。

我们考虑一个非线性映射的零点问题，也就是求解一个使得非线性映射满足

这个怎么和优化问题联系起来呢，大概是三个角度：

1. 对于无约束凸问题，其最优解等价于求解梯度等于零，这时的就是其梯度。

2. 对于约束优化问题，我们可以转化为一个无约束的对偶问题，这时的A就是对偶问题的梯度

3. 仍然是约束优化问题，我们可以求解其KKT系统，这时的A就是由KKT条件组成的一个非线性方程组。

求解问题（1）的方法就是稳定点迭代，也就是找一个算子，迭代去寻找解：

这个要满足一些条件。

1. 问题（1）的解是算子的稳定点，也就是满足

2. 上述迭代可以收敛到稳定点，或者收敛的速度怎么去分析，这需要满足一些性质，比如nonexpansive，contractive，averaged operator等. 这些性质是分析稳定点迭代收敛性的关键。

开始我们讲了问题（1）怎么和优化问题联系起来，接着我们讲下稳定点迭代怎么和优化方法联系起来。这里介绍了的几种情况，然后说明其如何应用到优化问题中去。关于收敛性的东西不讲。

1.Forward operator：

1.1.考虑凸问题

这个问题可以转化为。令，我们应用forward operator去求解该方程

这就是梯度算法。

1.2.考虑线性约束问题

因为是约束问题，所以不能用梯度等于0去求解，一个思路就是分析其对偶问题。该问题的对偶问题为

令 ,这等价于求解。那么forward operator 就是

关键在于次梯度怎么求，在我之前文章（邓康康：原始对偶角度下的几类优化方法）中有提到过：

其中，为拉格朗日函数。所以迭代（7）等价于

这就是dual descent method, 或者叫Uzawa method。

2. Backward operator：

这个算子也叫resolvent operator。首先推导下稳定点迭代：

整合一下得到：，而这就等价于找到一个满足

这就是proximal point iteration。接下来我们将该算子应用到上面讲到的A的三种情况。

2.1. 还是考虑问题（3），我们运用这个算子得到：

这等价于

整合一下我们知道

这就是临近点算法。

2.2.接下来关注问题（5）的对偶问题

，令。那么backward operator 就是

这等价于一下迭代过程：

其中 ,这个推导过程见（邓康康：原始对偶角度下的几类优化方法），这就是增广拉格朗日方法。

2.3. 仍然是考虑问题（5），但这次我们考虑的是其KKT系统

首先问题（5）kkt条件可以表示为：

我们令，那么backward operator的稳定点迭代为：

根据（9）式，我们知道上述迭代等价于寻找使得满足

从第二行得到：

从第一行得到：

把（13）中的代到（14）得到：

这等价于

总结一下（13）和（16）得到最终迭代形式为：

这个方法叫做临近增广拉格朗日方法。

前面讲的都是求解问题。接下来考虑两个的情况，也就是：

我们用到的算子叫做分裂算子。

3.Forward backward splitting

这个算子很好理解，就是前面讲到的两个算子的组合。具体形式为：

考虑可分得优化问题：

其中是一个光滑函数。这个问题等价于找到满足

我们令，这样就可以运用Forward backward算子：

有了前面两节的讨论，我们知道：

是一个梯度迭代，

是一个临近点迭代。

所以结合起来得到：

这就是临近梯度算法。

4.Douglas-Rachford splitting

为了简洁，我用和分别表示基于A,B的backwood operator。那么Douglas-Rachford splitting可以表示为：

考虑可分问题:

他的对偶问题是：

其中

我们令 ,这样就可以应用Douglas-Rachford splitting：

拆分一下：

再引入一个新的变量

再引入

根据前面backward operator的推导，我们知道临近点迭代等价于增广拉格朗日方法，所以第一行就等价于：

将代入第二行得到：类似的第二行就等价于：

最后再看下第三行：

代入到(19)的更新中：

现在我们把的更新放在一起：

这就是ADMM算法。

5.Peaceman-Rachford splitting

这个算子的稳定点迭代等价于对称ADMM方法。也就是：

这个方法我第一次见是在何炳生老师（我老师的老师）的一个讲座上，用变分不等式的框架去分析的，还举了个挑担子的例子，说两边一样重（对称）才能跑得快，印象深刻。

总结

1. 这些算子怎么来的呢？用forward来举例吧，我们本来要求 ,这等价于 ,然后令右边的为 ,左边为新的迭代点，这样就得到了forward算子。其他的类似，都是这种思想去得到的，但也不能乱来。。你要满足一些性质，不然收敛不了的。

2. 可能有些人会困惑，为什么这些算子的稳定点迭代刚好就对应于一个已知的优化方法呢，到底是算子先出来还是这些优化方法先出来，在提出二者的时候，是独立的还是参考了对方，我也困惑。。比如临近点迭代应用到对偶问题为什么刚好就是增广拉格朗日方法。。这纯属巧合吗，如果是这样，那数学太美了

3. 上面提到的都是一阶算法，其实也可以用牛顿法去做，刚才说到的很多问题可以转化为求解 ,进而我们又可以去设计一个算子 ,并且最优解满足。那么我可以直接应用牛顿法去求解这两类非线性方程组。

<p><br  /></p><p style="white-space: normal;text-align: center;"><strong style="color: rgb(0, 0, 0);font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;letter-spacing: 0.544px;widows: 1;background-color: rgb(255, 255, 255);font-size: 16px;max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong>完<strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong></span></strong></span></strong></p><pre><pre style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;white-space: normal;font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;widows: 1;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section><p style="margin-bottom: 15px;padding-right: 0em;padding-left: 0em;max-width: 100%;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 25.5938px;letter-spacing: 3px;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;font-size: 16px;font-family: 微软雅黑;caret-color: red;box-sizing: border-box !important;overflow-wrap: break-word !important;">为您推荐</span></strong></span></p><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;">MIT校长评中美科技竞赛：胜利不是期盼对手的失利</p><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="font-size: 14px;">GitHub重大更新：在线开发上线，是时候卸载IDE了</span></p><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="font-size: 14px;">美国官宣117000名 IT 人失业，真是史无前例！</span><br  /></p><p style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;">数据分析入门常用的23个牛逼Pandas代码</p><section style="margin: 5px 8px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;">特朗普拿H1B签证开刀，LeCun吴恩达等实名谴责！<br  /></section></section></section></section></section></section></section></section></section>

本篇文章来源于: 深度学习这件小事

本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！

知行编程网关注：1 粉丝：1

这个人很懒，什么都没写

内容反馈

你可能也喜欢

热评文章

发表评论

联系我们

标签云

推广返利