有哪些品牌做打底衫的网站,论mvc框架在网站开发的应用,Wordpress主题里的幻灯片怎么设置,网站页面头部设计说明这篇文章是我之前一篇文章的兄弟篇#xff0c;没看过的可以看下面这个。邓康康#xff1a;求解稀疏优化问题——半光滑牛顿方法zhuanlan.zhihu.com我们考虑的问题仍然是如下的一般问题#xff1a;其中 ,并且 特别大#xff1b;表示一个凸可微函数#xff0c;例如 表示一…这篇文章是我之前一篇文章的兄弟篇没看过的可以看下面这个。邓康康求解稀疏优化问题——半光滑牛顿方法zhuanlan.zhihu.com我们考虑的问题仍然是如下的一般问题其中 ,并且 特别大 表示一个凸可微函数例如 表示一个闭真凸函数一般为稀疏正则函数比如 LASSO Fused LASSOClustered LASSO等通过引入变量 我们先把P转化为约束问题于是我们得到P的对偶问题为 在之前的那篇文章中我提到了怎么利用增广拉格朗日方法ALM去求解对偶问题D,该方法中的子问题采用的是半光滑牛顿法。 主要idea大概分为三步将原问题转化为对偶问题利用增广拉格朗日方法求解对偶问题子问题采用半光滑牛顿法主要代价在于半光滑牛顿法而由于非光滑函数 的稀疏性导致子问题中的Jacobian矩阵也是稀疏的进而大大降低了该方法的计算量。本质上这个方法是一个应用于对偶问题上的增广拉格朗日方法。这篇文章我们换个角度从原始问题P出发去设计算法。在我的另一篇文章中邓康康原始对偶角度下的几类优化方法zhuanlan.zhihu.com里面讲到了 对偶问题上的临近点方法等价于原问题上的增广拉格朗日方法。而对偶问题的对偶问题是原问题。所以我们是不是有 原始问题上的临近点方法等价于对偶问题上的增广拉格朗日方法所以这篇文章我们来讲述临近点方法应用到原始问题。参考的是孙老师的两篇文章见文章末尾的参考文献。一、邻近算子和Moreau Envelope首先我给出一些需要用到的一些定义和性质。定义1.临近算子 2. Moreau envelope性质 是光滑函数并且它的梯度为: Moreau分解 Moreau envelope分解二、临近点方法求解原问题首先临近点方法有如下迭代形式其中 表示罚参数。现在关键在于这个子问题怎么求这要是没有 就好了直接一个临近算子就搞定。 既然不好求那我们就变成对偶问题去看看。首先对1做变量替换转化为约束问题构建拉格朗日函数那么其对偶问题为我们最终要求的就是对偶问题D.1。需要说明一下这里的原始问题P.1和对偶问题D.1是针对临近点方法的子问题而言的。我们来看一下对偶问题D.1的目标函数 的表达式其中第一部分关于 的问题是一个临近算子最后一个等式就是将 的临近算子表达式代入。显然上式看起来很复杂接下来我们来简化上式第一个等式用到了定义2第二个等式用到了性质3。最终我们将对偶问题D.1转化为如下问题定义 为这个函数跟 邓康康求解稀疏优化问题1——增广拉格朗日方法半光滑牛顿方法中的函数一模一样。 求到了对偶变量 之后最终我们是要去得到 . 在式子3中我们知道二者的关系是 综合一下最终的迭代过程为 其中 问题的求解采用的是半光滑牛顿法具体的jacbi矩阵怎么求稀疏性怎么利用参考下面这篇文章邓康康求解稀疏优化问题1——增广拉格朗日方法半光滑牛顿方法zhuanlan.zhihu.com三、半光滑牛顿法求解对偶问题D.1根据上面的推导我们知道求解对偶问题D.1等价于求解因为上述问题是个凸问题我们只要找到梯度等于0的点即可 首先根据 是个强凸函数所以其共轭 是光滑的再结合性质1我们知道 是一个光滑函数其梯度表达式为第一个等式用到了性质1第二个等式用到了性质2。这里说一下为什么是半光滑牛顿法因为虽然函数光滑但临近算子的存在导致这个函数的梯度不是光滑的。有了梯度之后我们来求解其广义Jacobian矩阵。第一部分 通常很简单比如二范数的平方。因此求二阶导也不需要什么计算量。关键的地方在于计算后面这部分。当 是稀疏正则的时候我们发现它的临近算子的导数通常是稀疏的。举例1范数正则当 其临近算子的导数 是一个对角矩阵且对角元为这样的话8的后面这部分我们只需要计算由非零元对应矩阵 的列构成的子矩阵相乘即可当非零元较少的时候这个计算量是很小的。最后我们给出半光滑牛顿法的迭代过程其中 。半光滑牛顿法迭代完之后令 .这样就完成了临近点方法的第k次迭代。再说一下5是我们的外迭代也就是临近点方法求解原问题。而8是用半光滑牛顿法求解5中的第一个子问题。Over二、总结最后梳理下这篇文章的idea临近点方法求解原问题将子问题转化到对偶形式半光滑牛顿法求解对偶问题在之前那篇文章中增广拉格朗日方法中的罚参数就对应于这里临近点方法的罚参数。二者的迭代是一样的只不过在参数的选择和收敛性分析方面会有不同。不同角度理解问题得到不同的方法虽然本质上是一样的但由此带来的延伸就不一样了在增广拉格朗日方法和临近点方法上的改进可以完全不同。欢迎关注我的专栏最优化理论和一阶方法zhuanlan.zhihu.com详细内容和理论证明可以看孙德锋老师主页知乎 - 安全中心www.polyu.edu.hk参考文献[1] Zhang Y, Zhang N, Sun D, et al. A Proximal Point Dual Newton Algorithm for Solving Group Graphical Lasso Problems[J]. arXiv preprint arXiv:1906.04647, 2019.[2] Lin M, Sun D, Toh K C, et al. A dual Newton based preconditioned proximal point algorithm for exclusive lasso models[J]. arXiv preprint arXiv:1902.00151, 2019.
