作者：邓康康
邓康康，福州大学应用数学系在读博士生，研究方向:运筹优化算法设计与应用、流形优化。
编者按
这篇文章介绍三个方法在原始问题和对偶问题下的形式，分别为：梯度方法（gradient descent method），临近点方法（proximal point method）以及临近梯度方法（proximal gradient method），感受下对偶的魅力。这里主要参考的是印卧涛老师的slide，有兴趣的可以看他的主页。
我们分为三部分，第一部分讲一下共轭函数的概念以及一些性质。第二部分描述了三个常见的优化方法。第三部分讲述这些方法应用在对偶问题上如何去刻画。
一、共轭函数（conjugate function）
接下来我们分析下共轭函数的一些性质，这将会在对偶方法中的推导起到关键的作用。因为对偶问题中目标函数就是原问题目标函数的共轭形式。所以我们要研究一下共轭函数的次梯度，以及什么情况下光滑。在得到共轭函数次梯度前，我们需要下面这个定理：
proof. （为了完整性，我给出证明，不想看的可以跳过，记住结论就行。）
（这个叫Fenchel's inequality）
二、Primal Perspective
2.1.Gradient descent method
2.2. Proximal point method
2.3. Proximal Gradient Method
三、Dual Perspective
下面我将首先得到原问题的对偶问题，然后利用上面提到的三个方法去求解，最后通过formulation，观察他们在转化到原始角度下是什么样的形式。
3.1. Dual （sub）gradient descent method
（上式不够严谨，次梯度为集合，所以应该是属于的关系，这里为了表达的简化，约定一下）
如果d是光滑的，那么上式就为梯度下降。就这样结束了吗？并没有，虽然这样看起来很简洁，但问题是我们不知道d(y)这个函数的显式表达形式是什么，甚至连是不是可微的也不知道，也就没有办法去求解它的梯度了。下面我来回答三个问题：
首先我们发现d(y)可以表达为：
其次，我们知道一个函数的强凸性对应于其共轭函数的光滑性。所以当f是强凸的时候，它的共轭才会是光滑的，进一步d(y)才光滑(函数内线性复合不改变光滑性）。
最后，对于次梯度而言，
3.2. Dual proximal point method
考虑上述的线性约束问题（6），这次我将proximal point method应用到对偶问题中，即
现在的问题是计算梯度，由上一节中可以知道：
这也等价于增广拉格朗日方法（ALM）。所以我们有结论：
原始问题的ALM方法等价于对偶问题下的临近点方法
绕了半天，结果出来个已经存在的方法
3.3. Dual proximal gradient method
考虑可分离线性约束问题：
我们利用临近梯度方法求解该对偶问题（14），具体的迭代为：
四、总结
这里我只介绍了三种方法在对偶角度下的形式，事实上，任意的方法都可以用到对偶问题上，比如：
■ 对偶问题下的Douglas-Rachford splitting方法等价于原始问题的ADMM方法
■ 对偶问题下的Peaceman-Rachford splitting方法等价于原始问题的对称ADMM方法
有时候还会有意想不到的结果。比如文献【7】就是将ALM（增广拉格朗日方法）应用到对偶问题上，再结合稀疏结构，加速了计算。
参考文献
【1】A.Beck. First-order methods in optimization[M]. SIAM, 2017.
【2】Splitting methods in communication, imaging, science, and engineering[M]. Springer, 2017.
【3】Y.Chen. Large-Scale Optimization for Data Science，ELE522，lecture notes，Princeton University
【4】 L. Vandenberghe. Optimization methods for large-scale systems, EE236C lecture notes,UCLA.
【5】Ryu E K, Boyd S. Primer on monotone operator methods[J]. Appl. Comput. Math, 2016, 15(1): 3-43.
【6】https://www.math.ucla.edu/~wotaoyin/index.html
【7】Li X, Sun D, Toh K C. A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems[J]. SIAM Journal on Optimization, 2018, 28(1): 433-458.
文章作者：邓康康
联系客服
