优化 | 大规模锥优化之Splitting Conic Solver(SCS)

最后更新：2020-07-04 10:52:23 手机定位技术交流文章

“战略还是战略”的由来

作者:门普·吴栋

编者按

介绍了一种基于ADMM的求解大规模圆锥优化问题的分布式算法:分裂圆锥解算器和齐次自对偶嵌入。

优化领域的小学生报告说，我以前写过一篇文章，介绍了多核学习中的优化问题，主要是凸QQQP(四次约束二次规划)和SDP(半定规划)。一个朋友给我发了一封私人信件，讨论如何解决这些QCQP和SDP，因为如果问题规模很大，这些问题就不容易解决。在原始文件中

1.1优化条件

最后一个互补缺失条件可以用括号中的条件等效替换。

1.2不可行性证明

2.同质自对偶嵌入

一个一般性的问题:给定一个系统，我们通常如何确定它是否有解决方案？

一般的方法是:先放松这个系统，用一定的方案构造一个新的系统，一定的方案集可以使系统回到原来的系统；然后，通过解的不同值来判断原系统的解。

2.1为什么称之为同构嵌入？

2.2为什么称之为自对偶嵌入？(自我双重属性)

3.齐次自对偶嵌入的算子分裂方法

让我们谈谈算法、ADMM的基本原理、算法流程和博伊德的小册子

3.2简化算法

接下来，让我们看一下SCS如何使用自对偶属性来简化ADMM算法的流程。

3.2.1初步简化

3.2.2第二步简化

4.在末尾写

好的，我计划写很多关于这个算法的内容，以及其他的收敛，实现细节，数值等等。，感兴趣的学生可以去看看报纸；他们自己；总而言之，SCS确实是一个漂亮的算法，许多设计细节都相当巧妙，这在博伊德的许多作品中都可以感觉到。

参考

[1]兰克立，克里斯蒂亚诺尼，巴特利特，加维和乔丹，用半定规划学习核矩阵，机器学习研究杂志，5(1):272，2004 .

[2] A. Kalbat和J. Lavaei，可分解半定规划的快速分布式算法，2015年第54届美国电气与电子工程师学会决策与控制会议(CDC)，第1741749页，2015 .

[3]帕克扎德，汉森，安德森和兰策，分布式半定规划及其在大规模系统分析中的应用，美国电气和电子工程师学会自动控制学报，63(4): 1041058，2017 .

[4]黄国明，西迪洛普洛斯，通用二次约束二次规划的共识-ADMM，美国电气与电子工程师学会信号处理学报，64(20): 5295310，2016 .

[5]贝奥多诺霍，朱英，帕里克和博伊德，通过算子分裂和齐次自对偶嵌入的二次曲线优化，优化理论与应用杂志，169(3): 1042 - 1068，2016 .

[6] S. Boyd，N. Parikh，E. Chu，B. Peleato，J. Eckstein等，通过交替方向乘数法的分布式优化和统计学习，机器学习的基础和趋势，3(1): 1 - 122，2011 .

[7] N. Parikh，S. Boyd和其他人，《最近算法，优化的基础和趋势》，1(3): 127 - 239，2014。

[8]。叶，内点算法，理论与分析，2011。