SCA缩写（SCA（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
参考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.
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！