|优化 | 大规模锥优化之Splitting Conic Solver(SCS)( 二 )
本文插图
思考(a general question)：任给定一个系统 ， 我们一般怎么判定它是否有解？
思路(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.
推荐阅读
- 模型|REVIT技巧！如何创建能量模型，实现能量优化
- 环球科技在此|推特遭大规模攻击后续：四名黑客浮出水面，有用户数据被下载
- 鞭牛士|微软发警告：大规模Emotet正卷土重来，目标是银行
- 计算机|CCleaner免费清理优化工具
- 互联网|推特大规模被黑 币安、苹果、亚马逊以及前总统 戳进来看看防范建议？
- 互联网|推特遭大规模黑客入侵，多位名人被发文募捐比特币
- 鹏飞奇闻|森林真的是越多越好吗？又是大规模增长，将会引发世界级的灾难
- 比特币|Twitter遭比特币黑客大规模入侵：Apple未能幸免
- 科学探索|智能优化算法研究取得进展
- 技术编程|京东高级算法工程师34页PPT详解基于分布式向量检索系统Vearch的大规模图像搜索【附PPT下载】