优化 | 大规模锥优化之Splitting Conic Solver(SCS)( 二 )
思路(a general method)：先对这个系统进行松弛 ， 构造一个一定有解的新系统 ， 而且某一组解一定能让该系统退回到原系统；然后通过解得的解的不同取值来判定原系统的求解情况 。
本文插图
本文插图
本文插图
2.1 为啥叫Homogeneous Embedding？
本文插图
2.2 为啥叫Self-Dual Embedding？(Self-Dual Property)
本文插图
本文插图
3. Operator Splitting Method on Homogeneous Self-Dual Embedding
下面开始讲算法 ， 关于ADMM的基本原理、算法流程 ， Boyd的小册子[6]当然是第一应该要看的 ， 也可以阅读公众号的两外两篇文章：《【优化】交替方向乘子法(ADMM)的基本原理》和《优化|浅谈交替方向乘子法(ADMM)的经典使用》 。
3.1 Basic Algorithm
本文插图
本文插图
3.2 Simplified Algorithm
下面 ， 我们来看一下SCS是如何利用Self-Dual property来简化ADMM算法流程的 。
本文插图
3.2.1 First-step Simplification
本文插图
本文插图
本文插图
本文插图
3.2.2 Second-step Simplification
本文插图
本文插图
4.写在最后
OK ， 关于这个算法 ， 我就打算写这么多了 ， 剩下的convergence、implementing detail、numerical等等 ， 有兴趣的同学可以自己去看paper；总而言之 ， SCS真的是个漂亮的算法 ， 很多设计细节都颇具匠心 ， Boyd的很多work都有这种感觉 。
参考文献
[1] G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui and M. I. Jordan, Learning the kernel matrix with semidefinite programming, Journal of Machine Learning Research, 5(Jan): 27 - 72, 2004.
[2] A. Kalbat and J. Lavaei, A fast distributed algorithm for decomposable semidefinite programs, 2015 54th IEEE Conference on Decision and Control (CDC), pages 1742-1749, 2015.
[3] S. K. Pakazad, A. Hansson, M. S. Andersen and A. Rantzer, Distributed semidefinite programming with application to large-scale system analysis, IEEE Transactions on Automatic Control, 63(4): 1045-1058 , 2017.
推荐阅读
- 电玩迷|《对马岛之魂》推出翻译优化首日补丁
- 王者荣耀|王者荣耀星元皮肤爆料，蜜橘之夏终有新衣服？回顾优化方案太好笑
- 王者荣耀|猴子伴生皮肤优化，这两点细节值得期待，射手地震级改动，阿离成S级射手
- 浪子归家 | 百度搜索“优化中心”二期上线，产品
- 美国双航母前往南海军演■近年“最大规模演习”！美国双航母前往南海军演
- 南海|近年“最大规模演习”！美国双航母前往南海军演
- 一生防务观察 就不能大规模拉动经济？你也太小看中国了，中国基建完成后
- 驱动之家 Win10优化Chrome：CPU运行效率提高、减少滚动卡死
- 风云点兵|大规模暗杀头目，叙利亚叛军日子不好过：俄叙联军特种兵深夜出动
- 一生防务观察|就不能大规模拉动经济？你也太小看中国了，中国基建完成后