整理2021年11月8日的笔记时翻到一页纸标题只写了半行字半定规划SDP。那天我在调一个图划分问题的松弛折腾到很晚随手记下来的SDP要点如今回头看竟然成了之后好几个项目的解题地基。半定规划这个名字听起来很数学但本质其实不难它就是把线性规划里的“非负向量”约束换成“半正定矩阵”约束。它之所以值得花时间去啃是因为它能做很多线性规划做不了的事——给组合优化提供强松弛、把非凸的秩问题转换成凸问题、把控制理论里的稳定性条件写成可求解的矩阵不等式。这篇文章适合正在跟整数规划、非线性约束、低秩恢复打交道或者被某个看似简单却死活解不动的小模型卡住的人读。我会把核心原理、应用范式、求解器选型以及实际踩坑的过程都捋一遍尽量说人话。1. 线性松弛为什么挡不住这种问题从最大割说起1.1 一个让线性松弛当场翻车的例子最大割问题是SDP最经典的出场场景。问题本身很直白给你一张无向图每条边带权重把顶点分成两组让“两端不在同一组”的边权重总和尽量大。这是个NP-hard问题聚类、电路划分、网络设计里都藏着它的变体。第一次接触这类问题时大多数人会尝试整数规划建模。对每条边(i,j)引入变量表示两端是否同组最直接的做法是用x_i±1编码组别然后最大化∑ w_ij · (1 - x_i x_j) / 2这里x_i x_j1表示同组该边不贡献x_i x_j-1表示异组贡献w_ij。理想情况是让x_i只取±1但那是整数规划不好解。所以经典的松弛思路是允许x_i落在[-1,1]区间把问题变成线性规划。这个松弛在理论上是成立的——可行域变大了最优值只会更好。但问题是它好得过头了。我在一个模拟项目X里测过一张单位权随机图整数最优割大约能拿到总边权的84%线性松弛给出来的上界却在92%以上。这个上界虚高到没法用来做分支定界的剪枝几乎等于没给信息。原因在于[-1,1]这个盒子太松松弛解可以让每条边都“半贡献”把这个割的边数同时挣满这在真正的离散解里根本做不到。换成SDP之后情况完全不一样。做法是把标量x_i升级成向量v_i约束张成Gram矩阵X其中X_ii1X_ijv_i^T v_j。允许X_ij在[-1,1]之间连续变化但要求整个Gram矩阵半正定。同样是那张随机图SDP给出来的上界只比整数最优高两三个百分点。这就是SDP在组合优化里最核心的价值松弛质量紧边界有用。1.2 为什么SDP松弛更紧一个几何直觉很多人第一次看到“把标量升级成向量”会觉得莫名其妙这不是把简单问题搞复杂了吗但如果从几何角度理解就顺了。线性松弛相当于把{-1,1}^n的顶点集合放进一个n维立方体。立方体是凸的好优化但它的体积远大于离散点真正的凸包尤其在组合结构复杂时立方体的很多角落在组合意义上根本不可达。SDP则不同它把每个顶点映射为单位球上的一个向量可行域变成所有Gram矩阵的集合——你可以让某些边的内积给到部分的贡献但这些内积必须来自一组真实存在的欧氏空间向量不能每个方向都撒谎。举个例子三条边的三角形如果想让三条边同时贡献接近满分线性松弛可以说“每条边都切一半”三个x_i_i的对都取接近0目标值虚高。但SDP里三个向量两两夹角不能同时接近180°Gram矩阵半正定这个约束会把这种不可能直接判死。所谓“半正定约束没有时间先后它管的是全局一致性”这就是SDP比LP紧的几何本质。2. 半定锥、LMI与对偶SDP的数学骨架2.1 标准形式从头到尾只有三个要素SDP的标准形式写出来非常简短min tr(C X) s.t. tr(A_i X) b_i, i 1,...,m X ⪰ 0且X为对称矩阵这里tr(AX)是矩阵内积等于把两个矩阵对应元素相乘再求和。X ⪰ 0表示X是半正定矩阵所有特征值非负。三个要素分别是线性目标、线性等式约束、半定矩阵锥约束。跟线性规划相比唯一的变化就是约束从“x ≥ 0”变成了“X ⪰ 0”。但这一变表达力就完全不同了。标量版本里x_i≥0是一些独立的半射线矩阵版本里X ⪰ 0是整个半定锥它对矩阵整体结构施加约束能把“这些向量之间满足某种内积关系”这种全局性质直接表达出来。很多看起来完全非线性的问题放进这个框架里反而变成凸问题。2.2 LMI与Schur补把二次约束翻译进半定世界线性矩阵不等式LMI是SDP最常见的表述形式。它一般写成F(x) A_0 ∑ x_i A_i ⪰ 0其中A_i是常数对称矩阵x是决策向量。只要目标函数是线性的这整个问题就是一个SDP。之所以强调LMI是因为大量工程约束都不是天然写成SDP的标准形式而是能通过LMI等价转化。最常用的翻译工具是Schur补。比如我要表达“t ≥ x^T x”这个二次约束它本身是凸的但没法写进线性规划。通过Schur补可以写成[ I, x ] [ x^T, t ] ⪰ 0这个分块矩阵半正定等价于t ≥ x^T x。看起来只是换了个写法但在求解上是从“非线性约束”变成了“矩阵锥约束”直接落入SDP的射程。我做传感器定位项目时这个技巧几乎天天用——把距离约束的平方项塞进矩阵的角落问题就从“不知道从哪下手”变成了“标准的凸优化”。2.3 对偶与Slater条件求解器真正在解什么SDP的拉格朗日对偶写出来跟原始问题长得非常对称max b^T y s.t. C - ∑ y_i A_i ⪰ 0弱对偶始终成立任意原始可行点的目标值都不小于任意对偶可行点。但真正让求解器能高效工作的是强对偶也就是原始最优值等于对偶最优值而这需要在原始问题里存在一个严格可行点某个X满足等式约束并且X严格正定所有特征值都大于0。这个条件叫Slater条件。大多数SDP求解器同时维护原始路径和对偶路径靠两者之间的对偶间隙来判断收敛。如果问题里没有严格可行点对偶路径会一直不稳求解器要么慢得要命要么直接报不可行。我在实际项目里吃过这方面的亏——模型的理论形式看着没问题等式约束也都对得上但变量被约束在低秩流形上整个可行集里找不到一个严格正定的点求解器就是不给面子。解决办法通常是在目标里加一个很小的正则项比如εtr(X)或者把某些等式约束放宽到带ε的区间把问题推向内点存在的情形。2.4 多项式时间可解为什么SDP能上工程SDP是凸优化最经典的算法是内点法。它的思路是在目标函数上叠加一个对数障碍项比如min tr(CX) - μ log det(X)然后沿着μ递减的路径做牛顿迭代。每步牛顿法要分解一个大型矩阵代价大约O(n^3)但迭代次数只需要约O(√n log(1/ε))——这里的n是矩阵维度ε是目标精度。这意味着求解时间随问题规模是多项式增长而不是指数爆炸这是SDP能用于实际工程的根本保证。不要被“矩阵”这个外壳吓住从计算复杂度框架看SDP和LP非常接近只是每一步要多拆一个更大的矩阵。实际表现上几千维以内的SDP在主流求解器上都能在几秒到几分钟内收敛到1e-6左右的精度完全够用。3. 四个能直接抄的SDP应用范式松弛、核范数、李雅普诺夫与定位3.1 最大割的经典套路SDP求解随机舍入最大割的完整流程值得认真走一遍它是理解SDP后处理的标准模板。第一步建模目标。设X是Gram矩阵约束X_ii1最大化∑ w_ij (1 - X_ij)/2。求解SDP得到最优的X*。第二步特征分解。把X*写成VΛV^T取特征向量矩阵V每一行就是原问题顶点对应的高维向量v_i。第三步随机舍入。生成一个标准高斯随机向量r对所有顶点计算s_isign(r^T v_i)s_i为1的顶点归入A组-1归入B组。第四步重复多次。采样几百上千个随机方向取切割权重最大的一次作为最终解。这个流程里最关键的理解点是SDP解出来的不是一组离散标签而是一组连续向量。标签是在后处理阶段“舍入”出来的舍入质量直接决定最终结果。理论上有保证期望切割权重不低于SDP最优值的0.878倍这是经典结果。实际跑下来通常更好尤其在冗余采样几百组随机向量后经常能拿到0.9以上的近似比。3.2 核范数最小化把非凸秩问题变成凸问题推荐系统里的矩阵补全图像修复里的低秩重构本质都在做同一件事有一个大矩阵只知道部分元素想恢复整个矩阵而且相信真实矩阵是低秩的。直接最小化rank(X)是非凸的几乎没法解。但rank函数有一个凸包络核范数也就是所有奇异值之和。把目标换成min ||X||_*问题变成凸的。更有意思的是核范数可以写成SDPmin (1/2)(tr(U) tr(V)) s.t. [ U, X; X^T, V ] ⪰ 0这个等价关系在工程上意味着什么意味着低秩恢复可以被一套标准的凸优化工具链处理不需要给每个问题手写专用算法。这在以前是不可想象的。我在一个图像去噪的demo里试过噪声污染了大约60%的像素点核范数SDP恢复出来的矩阵在视觉上几乎看不出缺失痕迹。3.3 李雅普诺夫稳定性控制里的SDPSDP不只是离散优化和机器学习的工具控制理论里它几乎是标配。一个线性系统dx/dt Ax怎么判断它是否稳定可以找一个李雅普诺夫函数V(x)x^T P x如果P正定并且V沿系统轨迹单调下降系统就稳定。这个条件写成矩阵不等式就是P ≻ 0, A^T P P A ≺ 0两个都是矩阵不等式变量是P这正是标准SDP。求解之后不仅能判断稳定性还能拿P去构造控制器或者在满足LMI约束的前提下进一步优化某个性能指标比如最小化某个衰减率这些追加约束都还是SDP。这个应用提醒我SDP的覆盖面远比单纯“组合优化松弛”要宽它本身就是处理矩阵层面约束的通用语言。3.4 传感器定位提升半定松弛丢弃秩约束传感器定位问题是一个特别好的范式平面上布了N个节点只知道部分两两距离测量值想估计每个节点的真实坐标。约束长这样(p_i - p_j)^T (p_i - p_j) d_ij^2这是非凸的二次等式直接解非常困难。SDP的做法是把这个非线性问题“提升”到矩阵空间。定义P为坐标矩阵d×n构造分块矩阵Y [I, P; P^T, Q]其中Q是对称矩阵。注意如果Q恰好等于P^T P那么Y自动半正定而且秩等于d。所以原始问题等价于Y ⪰ 0、Y的某些固定块已知、外加rank(Y)d。丢掉秩约束保留半正定和固定块约束就是一个SDP。这个“提升到矩阵 半定松弛 丢秩”的配方可以迁移到很多几何问题上包括相机位姿估计、分子构象恢复等。我自己的体会是看到“二次等式约束”先别慌先想能不能把它塞进一个分块矩阵的Schur补里往往答案就出来了。4. 求解器实战场内点法、一阶法与建模接口怎么选4.1 两类主流求解器精度还是规模半定规划的求解器大体可以分两类选错了会非常难受。类型每步代价迭代次数适用规模典型表现内点法型O(n^3)约O(√n log(1/ε))几千维以内稳健gap能到1e-8一阶法型O(nnz)依赖稀疏度几百到几万受精度影响大超大规模稀疏矩阵快但高精度收敛慢内点法型的看家本领是精度和稳健性适合验证模型、产出基准解、处理中小规模问题。一阶法型更适合超大规模、稀疏结构明显、只需要近似解做快速探索的场景。我现在的习惯是首次接触一个问题永远先用内点法在小规模数据上跑出目标值的基准再切到一阶法去逼近。否则你会分不清误差是来自松弛模型本身还是来自算法没收敛。4.2 建模接口三行代码声明一个半定变量SDP建模接口已经做得很成熟核心抽象就三个元素半定矩阵变量、等式约束、线性目标。以某通用凸优化建模接口为例最大割的SDP松弛写起来大约是这样的概念代码# 概念代码最大割SDP松弛 X Semidefinite(n) # 声明n×n半定矩阵变量 constraints [X[i][i] 1 for i in range(n)] objective sum(w[i][j] * (1 - X[i][j]) / 2 for i j) prob Minimize(-objective) # 等价于最大化 prob.solve()这段代码几乎和数学公式一一对应不用手动推导对偶形式不用管内点法的具体步进策略。声明变量、写约束、设目标、调求解器四步走完。这也是我推荐每个人都应该学一点SDP建模的原因数学底子要求不高收益却非常实在。4.3 求解参数与终止判据调什么、什么时候调拿回一个SDP模型求解参数通常不需要大动但有几个点值得了解。第一是初始点给X传一个合理的正定矩阵比如单位阵的倍数往往能显著减少收敛时间。第二是终止间隙gap建模阶段如果只是探索解的行为gap设在1e-3到1e-4足够如果要拿去做后续精确验证压到1e-7更稳。第三是迭代上限大规模一阶法给一个较大的上限然后盯着gap下降曲线看而不是干等它结束。如果返回状态是原始不可行或无界不要急着改约束先跑一个小规模代理问题把目标系数缩小十倍看问题形态有没有变化。无界问题通常表现为目标函数在某个可行方向上能无限下降不可行问题则要检查是否有冗余等式约束或者你手动构造一个明显可行的X代入约束验证一下。这两件事做下来大部分建模初期的问题都能定位。5. 我踩过的三个SDP数值坑从报错到修复的完整链路5.1 坑一约束系数尺度悬殊gap卡死不动现象很典型求解器迭代了上千次gap停在1e-3附近死活不下来目标值却在微小的范围内抖动。我的排查链路是先打印约束矩阵A_i的元素绝对值和分布。结果发现有些约束的系数集中在1e7量级另一些只有1e-7。这样量级悬殊的系数放在同一个SDP里等价于把一个椭球拉伸得极扁牛顿步在数值上非常不稳定。SDP的内点法对尺度是敏感的尽管数学上同比例缩放不影响最优解但在浮点数世界里等价不等于可计算。修复方式很简单把所有约束矩阵和目标矩阵统一除以最大系数的绝对值也就是整体缩放到0.1到10的区间内。做完之后同一求解器gap很快降到1e-7。验证方式也简单两次求解的目标值一致但收敛路径和精度完全不同。这个坑是隐藏的因为目标值看着没变如果把解拿去做特征分解特征向量会被数值噪声污染得一塌糊涂后续舍入和恢复步骤全崩。5.2 坑二模型看似可行其实没有Slater点有一次在模拟项目X里做传感器定位求解器报原始不可行。我很确定约束方程组有解因为所有测量值都是真实的不存在矛盾。仔细排查后发现问题出在“几何退化”。所有传感器的真实坐标落在一个低维子空间里比如全部共线这导致任何满足等式约束的Y矩阵在对应方向上的特征值自动变成0整个可行集里找不到一个严格正定的内点。也就是说虽然可行集非空但Slater条件不满足对偶问题失效求解器只能判定原始不可行。修复的方法是加正则项给目标函数加上δ·tr(X)δ取1e-6左右相当于把可行集朝内点方向“推”了一下。这会对最优值引入δ量级的扰动但对大多数工程应用来说可以接受。这个坑的教训是SDP数学上写着“半正定”求解器数值上要的是“正定”这两个状态之间的差距往往就是一次求解成功和失败的分界线。5.3 坑三随机舍入前忘了清洗特征向量最大割流程走到最后一步SDP解出来了gap已经到1e-6随机超平面舍入的结果却惨不忍睹近似比只有0.6左右远低于0.878的理论保障。一开始我以为是随机种子问题多跑几组还是没有改善。后来查了解矩阵本身发现问题出在求解器默认容差下X*带着微小的负特征值。特征分解之后负特征值对应在特征向量里的小尾巴会让向量长度漂移有些向量的模长变成了0.985或者1.03而舍入算法假设它们严格落在单位球上符号判断的准确率自然掉得厉害。修复方式是在舍入之前做清洗把特征值做clip负值截断为0重新构造一个尽量贴近原始解的半正定矩阵再对所有向量归一化到单位长度。清洗之后重新跑几千组随机超平面近似比稳定回到了0.9附近。这一步的代码其实只有几行但效果立竿见影现在它已经成为我所有SDP后处理流程的固定环节。5.4 建模完成后必做的三问检查法踩过这么多坑之后我给自己定了一个SDP模型提交前的三问检查第一问约束里有没有冗余等式冗余约束会让对偶尺度退化有时还会在Slater点附近制造数值陷阱能删就删。第二问是否存在严格正定的可行点如果X_iI或者某个合理构造的正定矩阵代入都不满足约束就要考虑加正则项。第三问目标函数有没有无用的常数项常数项不影响最优解但会影响对偶gap的读数干扰你看收敛曲线。这三问花不了五分钟但能避免大多数“求解器莫名其妙不工作”的局面。最后再分享一个我最近一直在用的习惯每个SDP模型求解完成后别急着看目标值先打印最优X的特征值谱。如果谱在某个k之后迅速衰减说明这个松弛的解本质上是低秩的后处理阶段完全可以把尾部噪声权重丢掉转成普通的结构化问题如果谱从头到尾都拖得很长说明模型大概率太松得回去补约束。这个检查十秒钟就能做完却能省下大量在舍入阶段试错的时间。