1. 从“难啃的骨头”说起二元二次规划的挑战在工程优化、金融投资组合、机器学习模型调参甚至是一些生产调度问题里我们常常会遇到一类“看起来简单实则暗藏玄机”的数学问题。它的形式可能是这样的你需要在一堆限制条件下找一个决策变量的组合让一个目标函数的值最小或最大。这个目标函数里包含了决策变量之间的乘积项比如x1 * x2而变量本身可能还只能是0或1整数变量。这类问题在学术上被称作混合整数二次规划或者更具体一点当变量是二元0/1时就是二元二次规划。我第一次在实际项目中撞上它是在为一个通信基站做资源分配模型的时候。目标是最小化总功耗功耗和各个信道开关状态0/1变量以及发射功率连续变量有关其中就包含了“开关状态”与“功率值”的乘积项。当时我的第一反应是扔给一个通用的求解器结果要么是求解器直接报错“模型非凸”要么就是运行了几个小时还在“思考”给出的解质量堪忧。这让我意识到这类问题之所以是优化领域的“硬骨头”核心原因在于它的非凸性。简单来说在一个凸优化问题里你从起点往任何方向走目标函数值的变化趋势是“友好”的局部最优就是全局最优求解器有成熟高效的算法如内点法可以快速找到答案。但非凸问题就像一片崎岖的山地充满了局部低谷局部最优解你很容易掉进一个坑里就以为到了最低点但实际上远处可能还有个更深的峡谷全局最优解。二元二次规划由于二次项和整数约束的耦合绝大多数情况下都是非凸的。直接求解全局最优解在理论上属于NP-hard问题计算复杂度随着变量数量指数级增长对于实际问题几乎不可行。那么面对这块“硬骨头”我们是不是只能束手无策或者退而求其次接受一个很差的解当然不是。工业界和学术界发展出了一系列精巧的“化骨绵掌”其核心思想可以概括为将原问题转化为一个更容易求解的近似问题并且保证转化后的解对于原问题是可行的甚至能给出原问题最优解的一个界限。今天要深入讨论的“凸重构”和“外近似”正是这类方法中极具代表性的两种策略。它们不是魔法不能瞬间解决所有问题但为我们提供了系统性的、可计算的处理框架。2. 核心思路拆解凸重构与外近似的哲学在深入技术细节之前我们有必要先理解这两种方法背后的基本哲学。它们的目标一致——处理非凸的二元二次规划但路径截然不同。凸重构的思路更像是一种“内部改造”。它承认原问题的非凸结构但试图通过引入新的辅助变量和约束在更高的维度上重新描述这个问题使得在新空间里问题的松弛形式即暂时忽略整数约束允许变量在0到1之间连续取值变成一个凸优化问题。这个新构造的凸问题称为原问题的凸松弛。为什么这么做有帮助因为凸问题太好解了我们可以快速求解这个凸松弛问题得到原问题最优值的一个下界对于最小化问题。这个下界非常宝贵它告诉我们“全局最优解再差也不会比这个值更好了。”这为后续的精确算法如分支定界法提供了关键的剪枝依据。常见的凸重构技术包括二次约束二次规划重构和半定规划松弛。外近似的思路则像是一位“外部雕塑家”。它不直接改变问题的内部结构而是用一系列“更简单”的约束通常是线性约束从外部包裹住原问题复杂的可行域。这些线性约束构成的集合包含了原问题的所有可行解但范围更大因此叫“外近似”。然后在这个被线性约束包围的、更大的集合上求解优化问题。由于线性规划有极其高效的单形法或内点法求解速度飞快。通过迭代不断添加新的线性约束来收紧这个外部包裹使其越来越贴近原问题的真实可行域从而逼近最优解。混合整数线性规划的外近似法就是典型代表。两者的关系可以打个比方原问题是一个形状不规则的非凸物体。凸重构像是给它套上一个量身定做的、光滑的凸形外壳凸包络外壳完全包裹物体且表面光滑易处理。外近似则是用很多个平面去搭建一个多面体笼子笼子完全罩住物体虽然初始的笼子很宽松但可以通过不断增加平面线性约束让笼子越来越贴合物体表面。在实际应用中这两种方法并非泾渭分明而是常常结合使用。例如先用凸重构得到一个高质量的下界再在外近似的框架下利用这个下界来加速整数解的搜索过程。3. 技术深潜凸重构的常见手法与实现现在让我们深入到凸重构的具体技术层面。假设我们有一个标准的二元二次规划问题其一般形式为最小化x^T Q x c^T x满足Ax ≤ b,x_i ∈ {0, 1}对于所有i其中Q是一个对称矩阵通常非正定导致非凸x是二元决策变量向量。直接处理这个模型很困难。凸重构的关键在于处理目标函数中的二次项x_i * x_j。我们引入一个新的矩阵变量W令W_{ij} x_i * x_j。当x_i是0或1时这个关系等价于三个线性约束W_{ij} ≤ x_i,W_{ij} ≤ x_j, 以及W_{ij} ≥ x_i x_j - 1。同时对于对角元素由于x_i^2 x_i因为0^20, 1^21我们有W_{ii} x_i。于是原目标函数x^T Q x可以重写为∑_{i,j} Q_{ij} W_{ij}这是一个关于W和x的线性函数原问题被重构为最小化∑_{i,j} Q_{ij} W_{ij} c^T x满足Ax ≤ bW_{ij} ≤ x_i,W_{ij} ≤ x_j,W_{ij} ≥ x_i x_j - 1对所有 i≠jW_{ii} x_ix_i ∈ {0, 1},W_{ij} ≥ 0注意这个重构本身并没有改变问题的本质整数约束和非凸性被“隐藏”在了W_{ij} x_i * x_j这个等式关系里。如果我们现在松弛掉x_i的整数约束允许0 ≤ x_i ≤ 1我们得到的就是原问题的一个线性规划松弛。这个松弛通常比较弱给出的下界可能不够紧。为了得到更强的凸松弛我们需要在更高维度上施加凸约束。这就引出了半定规划松弛。我们注意到矩阵[1; x] [1; x]^T是一个秩为1的半正定矩阵。如果我们定义一个新的矩阵变量Y [1; x] [1; x]^T那么Y必须满足Y ≽ 0半正定rank(Y) 1并且Y的某些元素对应x_i和x_i*x_j。去掉这个难以处理的秩1约束rank(Y)1只保留Y ≽ 0我们就得到了原问题的一个半定规划松弛。具体来说令Y [ 1, x^T; x, X ]其中X是一个n x n的矩阵我们期望X ≈ xx^T。那么原目标函数x^T Q x可以表示为Q • X矩阵内积是线性的。原问题的半定规划松弛为最小化Q • X c^T x满足Ax ≤ b可以线性化后作用于YY ≽ 0Y_{11} 1Y_{1, i1} Y_{i1, 1} x_i对于 i1,...,nY_{i1, j1} X_{ij}对于 i, j1,...,nx_i ∈ [0, 1]连续松弛这个松弛的质量即下界的紧度通常远好于简单的线性规划松弛因为它捕获了变量之间的二次相关性。求解半定规划虽然比线性规划慢但仍有成熟的内点法算法属于凸优化范畴可以高效求解。在实际编程中我们可以使用像CVXPYPython、YALMIPMATLAB这样的建模语言直接描述半定规划松弛然后调用MOSEK、SDPA等求解器进行计算。关键步骤在于正确构建矩阵Y和约束。# 示例使用CVXPY构建一个简单二元二次规划的SDP松弛 import cvxpy as cp import numpy as np # 假设问题min x^T Q x c^T x, x in {0,1}^2 Q np.array([[2, -1], [-1, 2]]) c np.array([-3, -3]) n len(c) x cp.Variable(n) # 连续松弛后的变量 X cp.Variable((n, n), symmetricTrue) # 构建增广矩阵Y的约束 Y cp.bmat([[1, x.T], [x, X]]) constraints [Y 0] # 半正定约束 constraints [cp.diag(X) x] # X_ii x_i constraints [x 0, x 1] # 目标函数Q • X c^T x objective cp.trace(Q X) c.T x prob cp.Problem(cp.Minimize(objective), constraints) prob.solve(solvercp.MOSEK) # 需要安装MOSEK或其他SDP求解器 print(松弛后最优值下界: , prob.value) print(松弛解 x: , x.value)这段代码求解了松弛问题得到的prob.value是原问题全局最优值的一个下界。x.value是连续解通常不是整数需要后续处理。4. 外近似法用线性割平面步步紧逼如果说凸重构是从“内部本质”出发进行改造那么外近似法就是从“外部边界”入手通过不断添加线性不等式称为割平面来逼近最优解。对于混合整数非线性规划最经典的外近似法是线性化外近似也称为割平面法或线性外包络法。考虑一个更一般的混合整数非线性规划问题其中包含二元变量y和连续变量x约束中包含y和x的乘积项等非线性项。外近似法的核心思想是首先松弛掉整数约束并将所有非线性约束在其当前解点处进行一阶泰勒展开用线性约束替代。这样就得到了一个线性规划松弛问题。求解这个线性规划松弛。如果解满足整数约束那么它就是原问题的一个可行解不一定最优。如果不满足我们就需要添加新的线性约束割平面这个约束能够“割掉”当前的非整数解但不会“割掉”任何原问题的可行整数解。将新约束加入线性规划重新求解。如此迭代直到找到满足整数约束的解并且证明其最优性通常通过上下界收敛来判断。对于二元二次规划关键是如何为二次项x_i * x_j其中至少一个是二元变量生成有效的线性割平面。一个强大的工具是McCormick包络。对于乘积w x * y其中x ∈ [x^L, x^U],y ∈ [y^L, y^U]McCormick包络给出了w的紧凸包络即最好的线性外近似它由以下四个线性不等式定义w ≥ x^L * y y^L * x - x^L * y^Lw ≥ x^U * y y^U * x - x^U * y^Uw ≤ x^L * y y^U * x - x^L * y^Uw ≤ x^U * y y^L * x - x^U * y^L当y是二元变量0或1时区间[y^L, y^U]就是[0, 1]。代入McCormick包络我们可以得到关于w x_i * x_j或w x_i * y_j的线性不等式。这些不等式被直接添加到模型中替代原来的二次项等式约束w x_i * x_j。由于包络性质这样得到的线性规划松弛的解一定满足原问题的所有可行解都在其可行域内且提供了一个下界。外近似法的强大之处在于它的迭代性。初始的松弛可能很弱下界很差。但在求解线性规划得到分数解后我们可以基于这个分数解生成额外的、更紧的割平面。例如提升割平面或半定割平面。这些割平面能有效缩小松弛可行域提升下界加速算法收敛。在实际实现中现代混合整数规划求解器如Gurobi, CPLEX的内核就集成了外近似法的思想。当你将一个包含二次约束和整数变量的模型输入Gurobi时它内部会自动进行线性化使用McCormick包络等并在分支定界树的每个节点上可能还会添加额外的割平面来加强松弛。作为用户我们通常不需要手动实现外近似迭代但理解其原理对于设置求解器参数、解读日志信息和调试模型至关重要。例如在Gurobi中对于非凸二次问题需要将参数NonConvex设置为2。求解器会采用空间分支Spatial Branch-and-Bound结合外近似的方法来寻找全局最优解。查看求解日志你可能会看到“添加了XX个线性化约束”这样的信息这就是外近似在起作用。5. 实战融合在分支定界框架中协同作战在现实中无论是凸重构还是外近似很少单独用于求解一个完整的混合整数非线性规划问题。它们更常见的角色是作为全局优化算法主要是分支定界法的核心组件。分支定界法通过系统性地枚举候选解空间来寻找最优解而凸重构和外近似则负责在每一个枚举节点子问题上提供高质量的下界从而大量剪枝避免无效搜索。一个典型的求解流程如下预处理与模型构建对原二元二次规划进行凸重构例如引入W矩阵或采用SDP松弛或者直接使用其线性外近似如McCormick包络构建初始的连续松弛问题称为根节点松弛。求解根节点松弛求解这个凸问题线性规划、二次约束二次规划或半定规划得到原问题最优值的一个初始下界LB以及一个可能不满足整数约束的连续解x*。分支如果x*中某个二元变量x_i的值是分数比如0.7则创建两个新的子问题。在第一个子问题中添加约束x_i 0在第二个子问题中添加约束x_i 1。这样就将原问题空间一分为二。定界与剪枝对每个新生成的子节点再次求解其松弛问题需要在父节点模型基础上添加分支约束。得到该子问题的新下界LB_child。剪枝规则1界限剪枝如果LB_child已经大于当前已知的全局上界UB来自某个可行整数解的目标值那么这个子节点及其所有后代都不可能包含比当前最优解更好的解直接剪掉该分支。剪枝规则2整数性剪枝如果子节点松弛解的所有二元变量都恰好是0或1那么这个解就是原问题在该子空间内的一个可行整数解。更新全局上界UB min(UB, 目标值)。节点选择与迭代从所有活跃未剪枝的子节点中选择一个通常选下界最小的希望更快找到好解回到步骤3继续分支。同时在任意节点求解松弛后可以基于当前分数解动态生成额外的割平面外近似添加到该节点的模型中然后重新求解以得到更紧的下界这称为割平面回调。终止当全局上界UB和所有活跃子节点下界中的最小值min(LB_active)之间的差距小于预设容忍度时算法终止。UB对应的解即为全局 ε-最优解。在这个过程中凸重构的质量决定了初始下界的紧度而下界的质量直接决定了分支定界树早期剪枝的效率。一个紧的下界能更快地抬高“门槛”让许多分支在早期就被剪掉。而外近似割平面则是在搜索过程中动态加强每个节点松弛的工具它能持续改进下界是加速收敛的关键。我个人的经验是对于规模中等变量数在几百以内、二次项结构特殊如对角占优、稀疏的问题采用半定规划松弛作为分支定界的下界计算器效果非常显著常常能将求解时间从数小时缩短到几分钟。而对于规模更大、结构更一般的问题基于线性外近似McCormick的方法结合现代MIP求解器强大的割平面生成能力往往是更稳健和通用的选择。6. 避坑指南与性能调优心得理论很美好但实际应用时坑不少。这里分享几个从项目实践中总结的关键点和避坑技巧。坑1模型规模爆炸凸重构特别是引入W矩阵或半定规划松弛会显著增加变量和约束的数量。对于原问题有n个二元变量引入W矩阵会增加O(n^2)个变量。半定规划松弛的变量矩阵是(n1) x (n1)的虽然利用对称性可以减少但规模依然可观。这会导致松弛问题本身求解就很耗时。应对策略利用问题的稀疏性。如果原矩阵Q非常稀疏即大多数x_i*x_j项不存在或系数为0那么对应的W_{ij}或X_{ij}也无需全部引入。只对Q中非零元素对应的二次项进行重构。在建模时仔细检查问题结构避免创建不必要的变量。坑2松弛过弱下界毫无用处有时即使做了凸重构得到的下界仍然非常松散比如下界是-1000而实际最优值可能在-100附近。这样的下界在分支定界中几乎无法帮助剪枝算法退化为近乎完全的枚举。应对策略添加有效不等式在重构模型中加入原问题特有的、能加强松弛的约束。例如对于二元变量最简单的有x_i^2 x_i这已经体现在W_{ii} x_i中。更进一步如果问题有基数约束如恰好选k个物品可以加入相应的线性不等式。采用分层松弛先尝试简单的线性松弛如果下界太差再升级到更强的半定规划松弛。或者在分支定界树的上层节点使用强但耗时的松弛如SDP在深层节点使用快但弱的松弛如LP。检查外近似的紧度对于使用McCormick包络的情况二元变量的边界[0,1]是固定的但连续变量的边界[x^L, x^U]可能很宽。通过预处理或其他约束收紧这些边界可以显著加强McCormick包络从而提升下界质量。坑3数值稳定性问题半定规划求解器对数值非常敏感。当问题条件数大或者矩阵Q的元素量级差异巨大时求解可能失败或给出错误结果。应对策略问题缩放在构建模型前尝试对变量和目标函数进行缩放使系数矩阵的元素量级尽可能接近比如都在1e-2到1e2之间。这是一门艺术但对求解稳定性影响巨大。求解器参数调整增加求解器的迭代次数限制、提高最优性容忍度、或调整预处理参数。例如在MOSEK中可以调整MSK_DPAR_INTPNT_CO_TOL_REL_GAP等参数。降级使用如果SDP求解持续失败考虑降级使用二次约束二次规划重构如果问题能转化为凸的QCQP或者直接依赖线性外近似。坑4陷入局部最优或搜索停滞在外近似或分支定界中算法可能很早就找到一个还不错的可行解然后花费大量时间去证明它的最优性或者在一个看起来有希望但实际上没有更好解的分支上深挖。应对策略启发式生成可行解在分支定界开始前或过程中使用简单的启发式方法如四舍五入松弛解、局部搜索快速找到一个高质量的可行整数解以此设置一个紧的初始上界UB。一个好的上界能立刻剪掉大量分支。调整搜索策略不要总是使用“深度优先”或“最坏下界优先”。尝试“最佳估计搜索”它综合考虑了下界和估计的目标值。在Gurobi中对应参数MIPFocus可以设置为2侧重寻找更优可行解或3侧重改进下界证明最优性。设置时间/迭代限制对于大规模问题可能无法在可接受时间内得到证明的最优解。设定一个时间限制或节点数限制并接受当前找到的最佳可行解作为近似最优解。最后工具的选择至关重要。对于研究或小规模问题CVXPYYALMIP专用SDP求解器MOSEK, SDPA的灵活性无与伦比。对于大规模的工业级问题成熟的商业求解器如Gurobi和CPLEX对非凸混合整数二次规划的支持已经非常强大它们内部集成了多种凸重构、外近似和分支定界策略并且经过了极度优化。我的建议是除非有非常特殊的结构需要定制化松弛否则优先尝试使用Gurobi/CPLEX并仔细阅读其关于非凸问题处理的文档合理设置参数往往能事半功倍。
