这个标题我盯了很久零阶优化系列写到了第五篇前面几篇处理黑箱问题的思路从“猜方向”走到了“建模型”这次要聊的是一种更狠的全局视角——直接测度松弛。很多人一听到“测度”两个字就发怵其实它干的活儿一点也不抽象与其在原始输入空间里一个个试点不如把“找最优解”这件事整个升级成“找一个最优的概率分布”。这一篇我会把原理、算法框架、可复现的代码骨架以及我在实际算例里踩过的坑全部摊开讲清楚适合已经接触过零阶优化或者贝叶斯优化、想把黑箱问题往更全局方向推一把的人。零阶优化、黑箱优化、直接测度松弛这几个关键词看完这篇你会有一种彻底打通的感觉。1. 看懂标题零阶优化与黑箱问题长什么样1.1 黑箱优化到底“黑”在哪黑箱优化这个叫法非常直白你的目标函数就是一个不透明的箱子外部只能往里投输入箱子里面的解析表达式、梯度信息一概看不到然后箱子的输出也就是目标值会返回来。工程里这种问题简直不要太多——比如你调一个机械结构的仿真模型算一次可能要跑好几个小时内部是几千个网格节点的有限元方程你想要的是让某个应力指标最小但你根本写不出“应力 什么函数”的显式表达式更不可能手推梯度。黑箱问题的困难点有两个层面。第一层是信息受限没有梯度所有经典的一阶优化算法直接报废第二层是评估昂贵每次调用箱子都是一次仿真或一次实验所以你不能像深度学习训练那样甩一万个样本进去随便造。零阶优化这个大范畴解决的就是在信息受限、评估预算受限的前提下怎么尽可能高效地逼近最优解。很多人把零阶优化等同于“随机搜索”这是个大误会。零阶优化真正的意思是“不用梯度信息做优化”它下面其实分了三条完全不同的技术路线后面详细拆。1.2 零阶优化家族里的三路人马我把零阶优化家族粗略分成三派。第一派是直接搜索法最典型的就是坐标下降、Nelder-Mead单纯形法它们靠比较函数值的大小来推断搜索方向不需要任何建模。优点是实现极其简单黑箱拿来就用缺点也很要命很容易撞进局部最优而且在高维空间里效率掉得飞快。第二派是基于模型的方法贝叶斯优化是这派里的明星。它的核心思路是先给黑箱函数假设一个概率代理模型通常是高斯过程然后用采集函数决定下一步去哪里采样。这派的好处是样本效率高适合代价极其昂贵的小规模问题但缺点是对模型假设比较敏感而且高维时高斯过程本身也吃不住。第三派就是本篇的主角——基于测度松弛的方法。它既不直接猜方向也不刻意建代理模型而是把优化问题的可行域从“点的集合”扩展成“概率分布的集合”然后把目标函数在这个分布下的期望最小化。听起来绕但它有非常漂亮的数学保证松弛后的目标在测度空间里是线性的可行域是凸的这意味着一堆成熟的凸优化工具可以直接上而且理论上逼近的是一族全局最优解而不是某个局部极值点。直接测度松弛这个名称和贝叶斯优化那种“间接建模”相比区别就藏在“直接”两个字上。它不绕道去拟合一个代理函数再优化代理函数而是直接在测度空间上引入矩条件用半定规划把原问题的全局最优值“逼”出来。2. 直接测度松弛的核心思想拆解2.1 从“逐点优化”到“找分布”视角切换先想一个问题所有点搜索类算法本质上都在干同一件事——从候选点 (x_1,x_2,\dots,x_N) 里挑一个目标值最小的点。换句话你是在一个离散集合上做“选点”。那如果我把这个动作改一下不去挑某一个点而是给每个候选点赋一个权重让所有权重之和等于1然后在所有带权选择里找一个让加权平均目标值最小的组合会发生什么这就是测度松弛最核心的视角切换。一个权重分布在数学上就是一个离散的概率测度它比单点携带的信息多得多。你可以把权重集中在某个点附近那它基本等价于选一个点你也可以把权重摊开成一片区域那它表达的就是“我对这一块区域感兴趣但具体哪个点还不确定”。关键是这一步切换之后目标函数的形式变了。原来 (f(x)) 是一个非凸、没梯度、看不清形状的黑箱函数要直接优化非常头疼。但一旦我们把变量从点 (x) 变成分布 (\mu)目标就变成 (\int f(x)\mathrm{d}\mu(x))。如果 (\mu) 是离散的这个积分就是 (\sum_i p_i f(x_i))——关于 (p_i) 是线性的。线性目标加线性约束再加上凸的可行域这个问题就从“老虎”变成了“猫”。2.2 松弛为什么是“直接”的很多人第一次接触测度松弛时会问这不就是搞了一堆权重去做加权平均吗和随机搜索有什么本质区别区别大了。随机搜索生成一堆样本然后直接比较目标值测度松弛生成一堆样本但最后求解出来的是一个在全体可行分布中满足约束条件且目标最小的分布。它会主动把权重压到最优区域同时又能让一部分概率质量保留在别的区域——“最优分布”不等于“单点集中分布”。真正的“直接”体现在约束构造上。我们并不需要预先知道最优解长什么样只需要做两件事一是要求这个分布是合法的概率分布二是要求它的某些阶矩满足半定约束。矩条件用数学语言表达就是给定单项式基比如一维情况下的 (1,x,x^2,\dots,x^k)我们要求由这些单项式的期望构成的矩矩阵半正定。这个条件来自马尔可夫矩理论它保证存在某个支撑在可行域上的分布能实现这一组矩。你发现没有整个过程没有构建代理函数没有用梯度近似纯粹是在概率分布的“形状空间”里划可行域、算期望、求最小。2.3 马尔可夫矩与对偶性数学直觉这一节我不打算堆定理只讲直觉。为什么矩矩阵半正定这么重要你可以把矩矩阵想象成一张“概率分布的照片底片”。一个分布的所有矩 (y_\alpha\int x^\alpha\mathrm{d}\mu(x)) 如果给全了这个分布的基本形状信息就被抓住了。但随随便便给一组数字 (y_0,y_1,\dots,y_k)它们未必是某个真实分布的矩——矩矩阵半正定这个条件就是用来筛选“这些数字确实是某个分布能产生的矩”的必要条件。拿一维、二阶矩举例子矩矩阵是[ M_2(y)\begin{bmatrix}y_0 y_1\ y_1 y_2\end{bmatrix} ]如果这个矩阵半正定意味着存在一个分布它的总质量是 (y_0)均值为 (y_1/y_0)二阶矩为 (y_2)。这比随便乱猜一组矩要严谨得多。更妙的在它的对偶视角。测度松弛的原始问题是我们上面说的最小化期望它的对偶问题会自然引出多项式平方和SOS表示这给了我们一个双重验证的手段原始问题给出的是最优值的上界或逼近对偶问题给出下界当我们把矩阶数不断往上提上界和下界会从两边夹逼真值。实操里我不会死磕数学对偶但我会用这个gap来判断“当前松弛解得够不够准”这一点到后面讲参数调整的时候非常有用。3. 实操求解过程与最小实现3.1 把黑箱目标转成可计算的形式测度松弛听起来漂亮但真落地必须回答一个现实问题(\int f(x)\mathrm{d}\mu(x)) 里的黑箱函数 (f) 连表达式都没有怎么积分我的做法是用离散分布近似连续分布。具体分三步第一步在决策变量可行域里生成一批候选点 (x_1,\dots,x_N)。这批点不需要多精细均匀网格或者拟随机序列都行数量大概几百到几千看你的评估预算。第二步给每个候选点配权重变量 (p_i \ge 0)并强制 (\sum_i p_i 1)。如果要求分布支撑在整个区域这个约束就足够如果还想让某些矩固定就再塞进矩等式约束。第三步把目标替换成黑箱函数在候选点上的取值与权重的内积 (\sum_i p_i f(x_i))。到这里问题已经变成一个标准凸优化目标线性、约束线性、变量非负再加一个矩矩阵半正定约束。你不需要自己发明算法直接用现成的半定规划求解器就能解。3.2 一个两维测试算例的完整流程我拿一个最经典的二维黑箱测试函数——Rastrigin函数做示例。它的表达式是公开的但使用时不告诉优化器只允许调用函数取值完美模拟黑箱场景[ f(x)20\sum_{d1}^{2}\left[x_d^2-10\cos(2\pi x_d)\right],\quad x_d\in[-2,2] ]这个函数有大量局部极小点真正的全局最小值在原点取值为0非常适合测试全局优化算法。下面我给一段可直接运行的Python骨架代码用cvxpy定义并求解import numpy as np import cvxpy as cp # 黑箱函数只允许调用不允许看解析结构 def blackbox(x): return 20.0 np.sum(x**2 - 10.0 * np.cos(2.0 * np.pi * x)) # 在可行域内生成候选点拟随机网格即可 n_per_dim 40 x1 np.linspace(-2.0, 2.0, n_per_dim) x2 np.linspace(-2.0, 2.0, n_per_dim) X1, X2 np.meshgrid(x1, x2) candidates np.stack([X1.ravel(), X2.ravel()], axis1) # shape (N, 2) N candidates.shape[0] # 批量计算黑箱函数值 f_vals np.array([blackbox(p) for p in candidates]) # 建立测度松弛模型minimize sum(p_i * f(x_i)) p cp.Variable(N, nonnegTrue) constraints [cp.sum(p) 1.0] # 矩矩阵约束这里用一阶矩矩阵演示 # 对二维变量一阶矩矩阵为 [[y00, y10], [y10, y01]] y00 cp.sum(p) y10 cp.sum(p candidates[:, 0]) y01 cp.sum(p candidates[:, 1]) M1 cp.bmat([[y00, y10], [y10, y01]]) constraints.append(M1 0) objective cp.Minimize(f_vals p) prob cp.Problem(objective, constraints) prob.solve(solvercp.MOSEK) # 也可以用 cp.SCS但精度会差一些 # 提取最优分布 best_idx np.argmax(p.value) print(松弛目标值:, prob.value) print(最优权重集中点:, candidates[best_idx]) print(黑箱真实最优值(原点):, blackbox(np.zeros(2)))这段代码跑出来的松弛目标值会明显优于直接随机选点的平均结果而且权重分布的热力图能看出来概率质量基本集中到原点附近。如果我把矩阶数从一阶提到二阶、三阶矩矩阵变成 (4\times4)、(6\times6) 以上的规模松弛目标值会进一步逼近全局最优值0。这就是所谓“层级松弛”的威力——阶数越高、夹逼越紧。3.3 参数怎么选阶数、候选点数、求解器直接测度松弛落地时有三个旋钮是绕不开的矩阶数 (k)、候选点数量 (N)、以及底层求解器。我直接把我自己调参的经验列成一张表参数影响我的建议矩阶数 (k)阶数越高松弛越紧矩矩阵尺寸越大求解越慢先用 (k2) 或 (k3) 快速试探如果gap还不满意再往上提但超过6阶基本只适合低维小规模问题候选点数量 (N)决定离散近似的精细度太大则线性规划部分开销飙升先 (N400) 左右起步观察最优分布权重是否集中在少数点分散就加密网格求解器MOSEK适合SDP精度优先场景SCS适合大规模快速验证SDPT3可作交叉验证我一般先用SCS粗调、再用MOSEK精算两者结果不匹配时重点检查模型约束是否写错候选点数量和解的稳定性之间有个平衡点候选点取得太少分布会被迫挤在少数点上导致矩矩阵条件数变差。我用过一个粗暴但有效的检查方法把候选点数量翻倍如果两次求解的最优目标值差得很远说明当前网格精度不够需要继续加密度。这个方法在低维问题上非常管用几乎不需要额外动脑。4. 实操中会踩的坑与排错思路4.1 矩矩阵不半正定怎么办我最早跑通代码时遇到的最大坑就是明明约束里写了 (M_k \succeq 0)可求解器照样返回“infeasible”或者最优目标值明显异常。排查下来多数原因出在数值扰动上当候选点分布不均匀或者数量太少时低阶矩之间的数值尺度差异太大比如 (y_01)但 (y_2) 可能是几十导致矩阵接近奇异半定约束形同虚设。解决办法有两条路。第一条路是对矩矩阵做正则化在目标函数里加一个很小的 (\epsilon |M_k|_F^2) 项(\epsilon) 取 (10^{-6}) 量级能把数值病态性压下去第二条路是归一化变量把决策变量总体缩放到 ([-1,1]) 区间再构建单项式能显著改善矩矩阵的条件数。这两招我基本每次建模都会用属于标配操作。4.2 维度高时“松弛爆炸”直接测度松弛在天生低维问题上表现极好但一旦维度升高麻烦立刻来。原因是多项式基的数量随维度和阶数组合爆炸——(n) 维变量、最高阶为 (k) 的单项式总数是 (\binom{nk}{k})。简单算笔账(n3) 时二阶基数量是10矩矩阵是 (10\times10)但 (n6) 时二阶基数量跳到28三阶直接变成84。SDP求解器处理两三百维的矩矩阵还能勉强跑再大就是灾难。面对高维黑箱我的做法是别把直接测度松弛当最终工具而是把它当“全局定位器”。先用低阶松弛扫一遍找到最优势分布所在的子区域再切换到局部搜索算法精修。说白了测度松弛的定位是利用它的全局性而不是在超高维空间里强行硬算。4.3 输出带噪声的黑箱真实黑箱大多不干净——仿真器可能有数值噪声实验结果有测量误差。直接测度松弛对噪声的敏感性比贝叶斯优化要高原因很好理解噪声直接污染了 (\sum_i p_i f(x_i)) 这个线性目标优化器会倾向于把权重赋给那些“噪声恰好拉低目标值”的样本点进而产生偏差。对付噪声我有两招。第一招是提前对黑箱输出做平滑同一个候选点多评估几次取平均这招在评估预算允许时最直接第二招是在目标函数中把海塞对角项用样本方差替代掉让优化器主动惩罚不稳定区域。这不算什么高深技巧但实测能把带噪黑箱的收敛质量拉回好几个百分点。4.4 收敛判据怎么定跑完一次松弛怎么知道结果可不可信我的经验是盯“原始-对偶间隙”也就是原问题最优值和对偶问题最优值之间的距离。间隙大说明当前松弛还太松需要加阶间隙小到可接受范围说明加权分布已经基本锁定全局最优区域。我实操时通常用一个两层循环外层循环不断抬高矩阶数内层循环在当前阶数下用不同初始点生成候选网格、求最优分布然后比较相邻两个阶数得到的目标值变化量。如果相邻两阶的变化小于1%我就认为当前解已经足够逼近全局最优没必要再烧计算资源往更高阶冲。这套判据我不能说有多么理论严谨但在工程判断上很稳妥能省下很多无效计算。5. 和其他零阶方法怎么配合5.1 测度松弛当“全局初值器”测度松弛一个很容易被低估的用法是给其他零阶优化器当初始化模块。贝叶斯优化很忌讳从一个远离全局最优的初始点开始跑而测度松弛恰好能给出一个“概率密度最高的全局优势区域”。我在一次6维数值实验里的做法是先用三阶松弛求出最优分布的中心点再用这个中心点作为Nelder-Mead的初始单纯形中心收敛速度和成功率都比纯随机初始化高一大截。配合的关键是别让两个算法各干各的。测度松弛求出的不是单一解而是一个分布这个分布的协方差结构本身就能指导后续局部搜索的探查半径。协方差大的维度说明该方向上的不确定性高局部搜索就应该多花预算去扫协方差小的维度说明已经锁定得很好了局部搜索就不用重复劳动。很多做零阶优化的人忽略了这个信息非常可惜。5.2 后续扩展方向直接测度松弛的思路不止能在静态黑箱优化里用我在强化学习的策略搜索里也见过它的影子——把策略参数空间上的分布当作优化对象用熵正则约束避免过早收敛。最优传输领域里Wasserstein距离的求解底层同样依赖概率测度空间的对偶构造。如果你已经能把我前面那套代码跑通再去啃Lasserre层递和SOS那套文献会发现原来“黑箱优化”和“多项式优化”之间比想象中近得多。我个人后续准备在这个系列里讲一讲带约束的黑箱问题怎么用测度松弛处理比如目标函数本身是黑箱、同时还要满足若干个隐式不等式约束的工程场景那里的松弛构造比无约束情况有意思不少。说到底直接测度松弛最大的价值不是“替代”别的零阶算法而是补齐了“全局视角”这块拼图。真正做工程的人都知道一个再精美的局部搜索算法也架不住初始点落在错误的山头上。而测度松弛这种“先找分布、再谈收敛”的思维方式恰恰是在用结构化的数学语言帮我们回答那个最基本的优化问题全局最优到底在哪个区域这个问题想清楚了后面一切精修都有了方向。每次跑新问题前我提醒自己最多的一句话就是先松弛再精修别一上来就抱着某个局部解猛冲。