当前位置:首页 » 《随便一记》 » 正文

SCA(successive convex approximation)学习

1 人参与  2023年05月02日 17:37  分类 : 《随便一记》  评论

点击全文阅读


参考1 https://www.zhihu.com/question/424944253

successive: 连续的含义,就是通过不断的迭代去完成的。

convex: 就是说在迭代的过程中采用的是凸函数来代替非凸函数。
在这里插入图片描述

参考2 https://zhuanlan.zhihu.com/p/164539842

在这里插入图片描述
在这里插入图片描述
两者前三点要求相同,分别是

近似函数连续性近似函数和原函数在近似点函数值相同近似函数和原函数在近似点的一阶导数(方向导数)相同

第四点不同
SCA 要求近似函数是凸函数 而MM要求近似函数在近似点是原函数的upper bound(在原函数“上面“).

Part II A. SCA 算法

SCA的出现是为了解决实际应用中满足MM的条件的近似函数很难找的问题 (主要是第四点,满足uppder bound 又好解的近似函数很难找)。 然而根据no free lunch 的原则,我们在寻找近似函数上省了力气,就得在求解的时候付出更多力气。这是因为近似函数如果不满足upper bound那么直接取近似函数的最小值会导致“步子迈的太大”“走过了”的情况。如图1所示 y t + 1 y^{t+1} yt+1为近似函数的最小值,它“超过了”目标函数的local minima. 因此需要调整步长。调整的方法非常简单,采用moving average(移动平均?),公式如下
在这里插入图片描述
Block Successive Convex Approximation
在这里插入图片描述

参考1 https://www.zhihu.com/question/424944253

successive: 连续的含义,就是通过不断的迭代去完成的。

convex: 就是说在迭代的过程中采用的是凸函数来代替非凸函数。
在这里插入图片描述

参考2 https://zhuanlan.zhihu.com/p/164539842

在这里插入图片描述
在这里插入图片描述
两者前三点要求相同,分别是

近似函数连续性近似函数和原函数在近似点函数值相同近似函数和原函数在近似点的一阶导数(方向导数)相同

第四点不同
SCA 要求近似函数是凸函数 而MM要求近似函数在近似点是原函数的upper bound(在原函数“上面“).

Part II A. SCA 算法

SCA的出现是为了解决实际应用中满足MM的条件的近似函数很难找的问题 (主要是第四点,满足uppder bound 又好解的近似函数很难找)。 然而根据no free lunch 的原则,我们在寻找近似函数上省了力气,就得在求解的时候付出更多力气。这是因为近似函数如果不满足upper bound那么直接取近似函数的最小值会导致“步子迈的太大”“走过了”的情况。如图1所示 y t + 1 y^{t+1} yt+1为近似函数的最小值,它“超过了”目标函数的local minima. 因此需要调整步长。调整的方法非常简单,采用moving average(移动平均?),公式如下
在这里插入图片描述
Block Successive Convex Approximation
在这里插入图片描述
在这里插入图片描述
红框是寻找参数 α \alpha α的过程。
对比MM
在这里插入图片描述
多了搜索参数和移动平均的过程。

SCA算法的收敛

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
[2]的文章 Regularized Robust Estimation of Mean and Covariance Matrix Under Heavy-Tailed Distributions https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7069228

参考4 Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization https://arxiv.org/pdf/1801.08266.pdf

论文Meisam Razaviyayn, “Successive Convex Approximation: Analysis and Applications”

https://conservancy.umn.edu/bitstream/handle/11299/163884/Razaviyayn_umn_0130E_14988.pdf?sequence=1

块坐标下降法(BCD)被广泛用于求多个块变量的连续函数f的最小值。在该方法的每次迭代中,优化单个变量块,而其余变量保持固定。为了保证BCD算法的收敛性,每个块变量的子问题需要求解到其唯一的全局最优解。不幸的是,这个要求对于许多实际场景来说常常限制性太强。在这篇论文中,我们首先研究了一种替代的非精确BCD方法,它通过连续地最小化f的一系列逼近来更新变量块,这些逼近要么是f的局部紧上界,要么是f的严格凸局部逼近。考虑不同的块选择规则,例如循环(Gauss-Seidel)、贪婪(Gauss-Southwell)、随机化或甚至多个(并行)同时块。我们刻画了这类方法的收敛条件和迭代复杂度界,特别是对于目标函数不可微或非凸的情况。同时,利用交替方向乘子法(ADMM)的思想,对存在线性约束的情况进行了简要的研究。除了确定性情形外,还研究了由随机变量参数化的代价函数的期望值最小化问题。基于逐次凸逼近思想,提出了一种非精确样本平均逼近(SAA)方法,并研究了其收敛性。我们的分析统一和推广了许多经典算法已有的收敛性结果,如BCD方法、凸函数差分(DC)方法、期望最大化(EM)算法以及经典的随机(次)梯度(SG)方法,这些算法都是大规模优化问题的流行算法.
在论文的第二部分,我们将我们提出的框架应用于两个实际问题:无线网络中的干扰管理和稀疏表示的字典学习问题。首先,研究了这些问题的计算复杂性。然后利用逐次凸近似框架,提出了求解这些实际问题的新算法。通过对真实的数据的大量数值实验对所提出的算法进行了评估。

参考4 Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization https://arxiv.org/pdf/1801.08266.pdf

https://www.cnblogs.com/kailugaji/p/11731217.html

G. Scutari, F. Facchinei, P. Song, D. P. Palomar, and J.-S. Pang, “Decomposition by partial linearization: Parallel optimization of multiuser systems,” IEEE Trans. on Signal Processing, vol. 63, no. 3, pp. 641–656, Feb. 2014.

F. Facchinei, G. Scutari, and S. Sagratella, “Parallel selective algorithms for nonconvex big data optimization,” IEEE Trans. on Signal Processing, vol. 63, no. 7, pp. 1874–1889, April 2015.


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/60262.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 男友车祸断腿时,我和新欢在车内拥吻高分言情_陈行简江若***新书_小说后续在线阅读_无删减免费完结_
  • 完结文重生高考填报志愿时,我放任全班上大专好文分享列表_完结文重生高考填报志愿时,我放任全班上大专好文分享(颜禾晚宋津年叶淼淼)
  • 陆寒澈沈秋晚小说完本+外篇(相逢难逃别离)畅享阅读
  • 雪上春霜删减内容修复版本(温观意陆一然)_雪上春霜删减内容修复版本(温观意陆一然)
  • 骤雨淋落晚星(林晚星裴临川)全书浏览_骤雨淋落晚星全书浏览
  • 全书浏览重生高考填报志愿时我放任全班上大专+后续(叶淼淼宋津年颜禾晚)_重生高考填报志愿时我放任全班上大专+后续(叶淼淼宋津年颜禾晚)全书结局
  • 他的甜撩藏不住附加黎初谢时晏:结局+番外免费品鉴(他的甜撩藏不住)全本浏览阅读连载中
  • 全文他死遁后逼疯清冷女权臣+完结+后续(苏煜顾宛柔)列表_全文他死遁后逼疯清冷女权臣+完结+后续
  • 暑假毕业旅游,班花将我们身份证交给黑导游(江诗晗)全书浏览_暑假毕业旅游,班花将我们身份证交给黑导游全书浏览
  • 重生到高考前,我放任竹马为爱私奔新上热文_裴文远柳雨文远完结版_小说后续在线阅读_无删减免费完结_
  • 雨织离歌浮生浅节选_沈翊鸣苏之雨小姐完整文本_小说后续在线阅读_无删减免费完结_
  • 鬓边不是牡丹红精选(盛惟芳萧既明贺锦)_鬓边不是牡丹红精选盛惟芳萧既明贺锦

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1