Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

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

 

链接: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 等价

 

 

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

 

 

 

二、Primal Perspective

 

2.1  Gradient descent method

 

考虑无约束优化问题

 

 

2.2  Proximal point method

 

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

 

 

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

 

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

 

2.3  Proximal Gradient Method

 

考虑可分离凸问题:

 

 

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

 

三、Dual Perspective

 

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

 

3.1  Dual (sub)gradient descent method

 

考虑线性约束凸问题:

 

 

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

 

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

 

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

 

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

 

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

 

 

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

 

对于最后一个问题,

 

 

3.2  Dual proximal point method

 

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

 

 

 

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

 

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

 

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

 

3.3  Dual proximal gradient method

 

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

 

 

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

 

 

 

 

 

可以看到这个方法很像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

 

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注