优化 | 大规模锥优化之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)：任给定一个系统，我们一般怎么判定它是否有解？