24

原始对偶角度下的几类优化方法

 4 years ago
source link: https://flashgene.com/archives/81895.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

来源:最优化理论和一阶方法知乎专栏

链接:https://zhuanlan.zhihu.com/p/92230537

这篇文章介绍三个方法在原始角度和对偶角度下的形式,分别为:梯度方法(gradient descent method),临近点方法(proximal point method)以及临近梯度方法(proximal gradient method),感受下对偶的魅力。主要参考的是wotao yin的slide,有兴趣的可以看他的主页( 链接: https://www.math.ucla.edu/~wotaoyin/index.html )。

一、 共轭函数(conjugate function)

定义1(共轭函数):

接下来我们分析下共轭函数的一些性质,这将会在对偶方法中的推导起到关键的作用。因为对偶问题中目标函数就是原问题目标函数的共轭形式。所以我们要研究一下共轭函数的次梯度,以及什幺情况下光滑。

在得到共轭函数次梯度前,我们需要下面这个定理:

定理1(conjugate subgradient theorem) :令函数 f 是convex proper and closed. 那幺下面三条对任意 x,y 等价

3IrAbyy.png!web

proof. (为了完整性,我给出证明,不想看的可以跳过,记住结论就行。)

IBnIJzU.jpg!web

EFrYzyz.jpg!web

二、Primal Perspective

2.1  Gradient descent method

考虑无约束优化问题

3uQFjmA.jpg!web

2.2  Proximal point method

当问题(1)中的函数可能不光滑的时候,我们可以用临近点方法 ,具体地,该方法有如下形式:

Mnq2YzJ.jpg!web

对目标函数求导,我们得到另外一个形式:

这个形式在对偶角度下需要用到 。

2.3  Proximal Gradient Method

考虑可分离凸问题:

aiAfmua.jpg!web

这个算法有很多的变种,比如着名的FISTA。

三、Dual Perspective

下面我将首先得到原问题的对偶问题,然后利用上面提到的三个方法去求解,最后通过formulation,观察他们在转化到原始角度下是什幺样的形式。

3.1  Dual (sub)gradient descent method

考虑线性约束凸问题:

uimIzeU.jpg!web

如果d是光滑的,那幺上式就为梯度下降。就这样结束了吗?并没有,虽然这样看起来很简洁,但问题是我们不知道d(y)这个函数的显式表达形式是什幺,甚至连是不是可微的也不知道,也就没有办法去求解它的梯度了。下面我来回答三个问题:

d(y)的表达形式是怎样的?

d(y)什幺时候是可微的?

d(y)的次梯度表达形式是怎样的?

首先我们发现d(y)可以表达为:

AvMVfqY.jpg!web

其次,我们知道当f是强凸的时候,它的共轭才会是光滑的,进一步d(y)才光滑。

对于最后一个问题,

r6ZR7jF.jpg!web

3.2  Dual proximal point method

考虑上述的线性约束问题(6),这次我将PPA应用到对偶问题中,即

M7b22uR.jpg!web

ri63Qnb.jpg!web

这也等价于增广拉格朗日方法(ALM)。所以我们有结论:

原始问题的ALM方法等价于对偶问题下的临近点方法

绕了半天,结果出来个已经存在的方法。

3.3  Dual proximal gradient method

考虑可分离线性约束问题 :

I3AFjin.jpg!web

首先(13)的拉格朗日函数为:

Yfe2Af3.jpg!web

ANbIjaM.jpg!web

UrqyYn7.jpg!web

26nAvqi.jpg!web

可以看到这个方法很像ADMM,差别就在于对于x子问题,ADMM用的是增广拉格朗日函数,而这个方法用的是拉格朗日函数。

四、总结

这里我只介绍了三种方法在对偶角度下的形式,事实上,任意的方法都可以用到对偶问题上,比如:

对偶问题下的 Douglas-Rachford splitting 方法等价于原始问题的 ADMM 方法

对偶问题下的 Peaceman-Rachford splitting 方法等价于原始问题的 对称ADMM 方法

有时候还会有意想不到的结果。比如我的另一篇文章( 链接: https://zhuanlan.zhihu.com/p/92230537 ),就是将 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


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK