优化 | 大规模锥优化之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.