优化 | 大规模锥优化之Splitting Conic Solver(SCS)
『运筹OR帷幄』原创
作者：门泊东吴
编者按
介绍一个基于ADMM的求解大规模锥优化问题的分布式算法：Splitting Conic Solver(SCS) ， 以及其中用到的Homogeneous Self-Dual Embedding 。
优化领域小学生来报道 ， 我之前写过一篇文章 ， 介绍了多核学习(Multiple Kernel Learning)中的优化问题 ， 主要是convex QCQP(quadratically constrained quadratic program)和SDP(semidefinite program) ， 有朋友私信和我讨论具体怎么解这些QCQP和SDP ， 因为如果problem size很大 ， 这些问题其实并不好解 。 在原paper[1]里 ， 作者只是把MKL问题建模成了这些优化问题 ， 并没有探讨太多具体的解法 ， 因为这不是他们主要的contribution；我check了一下他们的numerical experiment ， 几个从UCI repository扒的data set都不大 ， 几百的training data ， 几十的attribute ， 他们的SDP是调用SeDuMi解的 ， QCQP/SOCP (Second Order Cone Program)是调用Mosek解的 ， 当然[1]是一篇04年的paper了 。
一般来说 ， 越是大规模优化问题(Large-scale Optimization Problem)就越是会有结构 ， 这个结构 ， 从分布式优化角度理解 ， 更多指的是可分解结构(Separability Structure) ， 就是“能拆” ， 比如能写成很多term的summation等等 ， 没有可分解结构的大规模优化问题 ， 个人理解 ， 设计算法的难度就会增大 。
求解large-scale SDP的分布式算法 ， 比如[2]和[3] ， 都是针对有特殊结构的SDP的 ， 有一篇分布式算法求解non-convex QCQP的paper[4] ， 也让我印象深刻 ， 它是基于consensus ADMM的思想 ， 把m-constraint QCQP拆成m个1-constraint QCQP ， 很有意思 。 这篇文章想给大家介绍一个基于ADMM的求解大规模锥优化问题的分布式算法：Splitting Conic Solver(SCS)[5] ， 也是Stephen Boyd团队的software之一 ， github地址：https://github.com/cvxgrp/scs 。 其实在读这篇paper之前 ， 我自己就盲猜了猜 ， ADMM怎么解大规模锥优化 ， 不就还是用Boyd那两本小册子的东西嘛：先用ADMM[6]把objective function和constraint拆开 ， 然后往各种cone上面的projection去他那本Proximal Algorithms[7]的第6章找；结果看完后 ， 我发现我想错了 ， 大错特错 ， 图样图森破 ， 在这个算法里 ， ADMM(Operator Splitting)根本就不唱主角 ， 真正的C位应该给这个Homogeneous Self-Dual Embedding(好像也不是他们的原创？比如叶老师的paper[8]里也有) ， 真的很妙、很香 ， 它：1. 能用来判定锥优化问题的infeasibility、unboundedness(对一个solver来说 ， 这个功能相当重要)；2. 能极大地简化算法的迭代步骤 ， 值得我为它专门写一篇文章记录一下 ， 也希望大家以后再提到这个算法 ， 不要再说什么''ADMM解conic'' ， 应该说''Homogeneous Self-Dual Embedding解conic'' 。 学艺不精 ， 一知半(不)解 ， 欢迎大家批评指正 。
一、问题描述
本文插图
1.1 Optimality Condition
本文插图
最后一个complementary slackness condition可以被等价地替换成括号里的条件 。
1.2 Certificates of Infeasibility
本文插图
2. Homogeneous Self-Dual Embedding
本文插图
思考(a general question)：任给定一个系统 ， 我们一般怎么判定它是否有解？
推荐阅读
- 电玩迷|《对马岛之魂》推出翻译优化首日补丁
- 王者荣耀|王者荣耀星元皮肤爆料，蜜橘之夏终有新衣服？回顾优化方案太好笑
- 王者荣耀|猴子伴生皮肤优化，这两点细节值得期待，射手地震级改动，阿离成S级射手
- 浪子归家 | 百度搜索“优化中心”二期上线，产品
- 美国双航母前往南海军演■近年“最大规模演习”！美国双航母前往南海军演
- 南海|近年“最大规模演习”！美国双航母前往南海军演
- 一生防务观察 就不能大规模拉动经济？你也太小看中国了，中国基建完成后
- 驱动之家 Win10优化Chrome：CPU运行效率提高、减少滚动卡死
- 风云点兵|大规模暗杀头目，叙利亚叛军日子不好过：俄叙联军特种兵深夜出动
- 一生防务观察|就不能大规模拉动经济？你也太小看中国了，中国基建完成后