二元二次规划求解：凸重构与外近似方法详解

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^2=0, 1^2=1），我们有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≠j）W_{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（可以线性化后作用于Y）Y ≽ 0Y_{11} = 1Y_{1, i+1} = Y_{i+1, 1} = x_i（对于 i=1,...,n）Y_{i+1, j+1} = X_{ij}（对于 i, j=1,...,n）x_i ∈ [0, 1]（连续松弛）

这个松弛的质量（即下界的紧度）通常远好于简单的线性规划松弛，因为它捕获了变量之间的二次相关性。求解半定规划虽然比线性规划慢，但仍有成熟的内点法算法，属于凸优化范畴，可以高效求解。

在实际编程中，我们可以使用像CVXPY（Python）、YALMIP（MATLAB）这样的建模语言，直接描述半定规划松弛，然后调用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), symmetric=True) # 构建增广矩阵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(solver=cp.MOSEK) # 需要安装MOSEK或其他SDP求解器 print("松弛后最优值（下界）: ", prob.value) print("松弛解 x: ", x.value)

这段代码求解了松弛问题，得到的prob.value是原问题全局最优值的一个下界。x.value是连续解，通常不是整数，需要后续处理。

4. 外近似法：用线性割平面步步紧逼

如果说凸重构是从“内部本质”出发进行改造，那么外近似法就是从“外部边界”入手，通过不断添加线性不等式（称为割平面）来逼近最优解。对于混合整数非线性规划，最经典的外近似法是线性化外近似，也称为割平面法或线性外包络法。

考虑一个更一般的混合整数非线性规划问题，其中包含二元变量y和连续变量x，约束中包含y和x的乘积项等非线性项。外近似法的核心思想是：

1. 首先，松弛掉整数约束，并将所有非线性约束在其当前解点处进行一阶泰勒展开，用线性约束替代。这样就得到了一个线性规划松弛问题。
2. 求解这个线性规划松弛。如果解满足整数约束，那么它就是原问题的一个可行解（不一定最优）。如果不满足，我们就需要添加新的线性约束（割平面），这个约束能够“割掉”当前的非整数解，但不会“割掉”任何原问题的可行整数解。
3. 将新约束加入线性规划，重新求解。如此迭代，直到找到满足整数约束的解，并且证明其最优性（通常通过上下界收敛来判断）。

对于二元二次规划，关键是如何为二次项x_i * x_j（其中至少一个是二元变量）生成有效的线性割平面。一个强大的工具是McCormick包络。对于乘积w = x * y，其中x ∈ [x^L, x^U],y ∈ [y^L, y^U]，McCormick包络给出了w的紧凸包络（即最好的线性外近似），它由以下四个线性不等式定义：

1. w ≥ x^L * y + y^L * x - x^L * y^L
2. w ≥ x^U * y + y^U * x - x^U * y^U
3. w ≤ x^L * y + y^U * x - x^L * y^U
4. w ≤ 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. 实战融合：在分支定界框架中协同作战

在现实中，无论是凸重构还是外近似，很少单独用于求解一个完整的混合整数非线性规划问题。它们更常见的角色，是作为全局优化算法（主要是分支定界法）的核心组件。分支定界法通过系统性地枚举候选解空间来寻找最优解，而凸重构和外近似则负责在每一个枚举节点（子问题）上，提供高质量的下界，从而大量剪枝，避免无效搜索。

一个典型的求解流程如下：

1. 预处理与模型构建：对原二元二次规划进行凸重构（例如引入W矩阵或采用SDP松弛），或者直接使用其线性外近似（如McCormick包络）构建初始的连续松弛问题（称为根节点松弛）。
2. 求解根节点松弛：求解这个凸问题（线性规划、二次约束二次规划或半定规划），得到原问题最优值的一个初始下界LB，以及一个可能不满足整数约束的连续解x*。
3. 分支：如果x*中某个二元变量x_i的值是分数（比如0.7），则创建两个新的子问题。在第一个子问题中，添加约束x_i = 0；在第二个子问题中，添加约束x_i = 1。这样就将原问题空间一分为二。
4. 定界与剪枝：对每个新生成的子节点，再次求解其松弛问题（需要在父节点模型基础上添加分支约束）。得到该子问题的新下界LB_child。
   • 剪枝规则1（界限剪枝）：如果LB_child已经大于当前已知的全局上界UB（来自某个可行整数解的目标值），那么这个子节点及其所有后代都不可能包含比当前最优解更好的解，直接剪掉该分支。
   • 剪枝规则2（整数性剪枝）：如果子节点松弛解的所有二元变量都恰好是0或1，那么这个解就是原问题在该子空间内的一个可行整数解。更新全局上界UB = min(UB, 目标值)。
5. 节点选择与迭代：从所有活跃（未剪枝）的子节点中，选择一个（通常选下界最小的，希望更快找到好解），回到步骤3继续分支。同时，在任意节点求解松弛后，可以基于当前分数解，动态生成额外的割平面（外近似），添加到该节点的模型中，然后重新求解，以得到更紧的下界，这称为割平面回调。
6. 终止：当全局上界UB和所有活跃子节点下界中的最小值min(LB_active)之间的差距小于预设容忍度时，算法终止。UB对应的解即为全局 ε-最优解。

在这个过程中，凸重构的质量决定了初始下界的紧度，而下界的质量直接决定了分支定界树早期剪枝的效率。一个紧的下界能更快地抬高“门槛”，让许多分支在早期就被剪掉。而外近似（割平面）则是在搜索过程中动态加强每个节点松弛的工具，它能持续改进下界，是加速收敛的关键。

我个人的经验是，对于规模中等（变量数在几百以内）、二次项结构特殊（如对角占优、稀疏）的问题，采用半定规划松弛作为分支定界的下界计算器，效果非常显著，常常能将求解时间从数小时缩短到几分钟。而对于规模更大、结构更一般的问题，基于线性外近似（McCormick）的方法结合现代MIP求解器强大的割平面生成能力，往往是更稳健和通用的选择。

6. 避坑指南与性能调优心得

理论很美好，但实际应用时坑不少。这里分享几个从项目实践中总结的关键点和避坑技巧。

坑1：模型规模爆炸凸重构，特别是引入W矩阵或半定规划松弛，会显著增加变量和约束的数量。对于原问题有n个二元变量，引入W矩阵会增加O(n^2)个变量。半定规划松弛的变量矩阵是(n+1) x (n+1)的，虽然利用对称性可以减少，但规模依然可观。这会导致松弛问题本身求解就很耗时。

• 应对策略：利用问题的稀疏性。如果原矩阵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（侧重改进下界，证明最优性）。
  • 设置时间/迭代限制：对于大规模问题，可能无法在可接受时间内得到证明的最优解。设定一个时间限制或节点数限制，并接受当前找到的最佳可行解作为近似最优解。

最后，工具的选择至关重要。对于研究或小规模问题，CVXPY+YALMIP+专用SDP求解器（MOSEK, SDPA）的灵活性无与伦比。对于大规模的工业级问题，成熟的商业求解器如Gurobi和CPLEX对非凸混合整数二次规划的支持已经非常强大，它们内部集成了多种凸重构、外近似和分支定界策略，并且经过了极度优化。我的建议是，除非有非常特殊的结构需要定制化松弛，否则优先尝试使用Gurobi/CPLEX，并仔细阅读其关于非凸问题处理的文档，合理设置参数，往往能事半功倍。