1. 项目概述从“硬骨头”到“可啃的骨头”做优化的人尤其是处理过实际工程问题或者金融组合模型的大概率都遇到过一类让人头疼的优化问题目标函数或者约束里包含了两个决策变量乘积的二次项。这类问题在学术上常被归为“二元二次规划”或者更广义的“非凸二次规划”的范畴。它不像线性规划那样有成熟高效的单纯形法或内点法也不像凸二次规划那样可以放心地丢给商业求解器。它的非凸性意味着可行域可能坑坑洼洼存在多个局部最优解而找到那个全局最优解计算上非常困难属于NP-hard问题。我最初接触这类问题是在一个供应链网络设计的项目中成本函数里既有固定成本与是否建仓相关0-1变量又有运输成本与流量相关连续变量而运输成本中有一部分是和流量平方相关的拥堵成本这就构成了一个典型的混合整数非线性规划其中非线性部分就是二元二次项。直接丢给当时常用的求解器要么报错要么运行几个小时也得不到一个可靠的结果。那时候就意识到必须得有一套系统的方法把这块“硬骨头”想办法“软化”让它变得可解。“凸重构”和“外近似”就是两把关键的“锉刀”。这个项目的核心就是探讨如何针对一类特定的二元二次规划问题通过数学上的等价变换凸重构将其非凸的部分暴露或转化再通过构造一系列线性约束外近似从外部逐步逼近原问题的可行域最终将其松弛或转化为一个可以高效求解的混合整数线性规划问题。这不仅仅是理论上的炫技更是工程实践中打通问题求解路径的必备技能。无论你是研究算法理论的学生还是面临实际优化难题的工程师理解这套方法的思路和实操细节都能让你在面对复杂非线性模型时多一份底气和工具。2. 核心思路拆解为什么是“凸重构”加“外近似”要理解这套组合拳我们得先拆开看这两个概念到底在做什么以及它们为什么要配合使用。2.1 二元二次规划的非凸根源一个一般的二元二次项可以写成 $q_{ij} x_i x_j$其中 $x_i$, $x_j$ 是决策变量$q_{ij}$ 是系数。当这个系数 $q_{ij} 0$ 时这个项在某个方向上就是凸的当 $q_{ij} 0$ 时它就是非凸的根源。我们通常说的“非凸二元二次规划”其非凸性往往就来自于一个或多个负系数的二次项。例如一个简单的非凸函数 $f(x, y) -x^2 - y^2$它的海森矩阵是负定的整个函数像一口倒扣的锅到处都是局部极大值但全局最大值在无穷远处这给优化带来了本质困难。在混合整数规划中情况更复杂。比如一个项是 $-x_i x_j$其中 $x_i$ 是0-1变量$x_j$ 是连续变量。这个乘积 $-x_i x_j$ 在 $x_i0$ 时为0在 $x_i1$ 时等于 $-x_j$。你会发现这个关系本身是线性的吗不是因为它包含了乘积。但它可以被精确线性化吗可以但需要引入额外的辅助变量和约束。这就是我们处理这类问题的起点识别出这些导致非凸的“麻烦项”。2.2 凸重构暴露结构创造机会“凸重构”不是指把非凸问题变成凸问题那通常不可能而是指通过变量替换、等式约束引入等方式重新表述原问题使得其中非凸的部分被孤立出来或者呈现出某种特殊的结构从而为后续的近似或精确线性化创造条件。最经典、最常用的凸重构技巧就是引入辅助变量进行替换。对于二元二次项 $x_i x_j$我们引入一个新的连续变量 $w_{ij}$并增加等式约束 $w_{ij} x_i x_j$。这样原目标函数或约束中所有出现 $x_i x_j$ 的地方都可以用 $w_{ij}$ 替换。于是原问题的非凸性就被“转移”并“浓缩”到了这个新引入的等式约束 $w_{ij} x_i x_j$ 上。注意这一步是精确等价变换没有引入任何近似。问题难度没有降低只是形式变了。现在我们的主问题目标和其他约束关于变量 $(x, w)$ 可能是线性的或凸的唯一的“罪魁祸首”就是那一组等式约束 $w_{ij} x_i x_j$。我们的火力就可以集中对付它们。对于不同类型的变量组合这个等式约束的性质不同两个连续变量$w xy$ 定义了一个双曲线面是非凸等式约束。一个0-1变量和一个连续变量$w \delta x$其中 $\delta \in {0, 1}$。这个关系可以通过大M法线性化$0 \le w \le M\delta$, $x - M(1-\delta) \le w \le x$。这是可以精确线性化的。两个0-1变量$w \delta_i \delta_j$ $w$ 也是0-1变量且等价于 $w \le \delta_i$, $w \le \delta_j$, $w \ge \delta_i \delta_j - 1$。这也是可以精确线性化的。所以凸重构后真正的“硬骨头”是那些包含两个连续变量的二次项。我们的“外近似”主要就是用来对付它们的。2.3 外近似用线性“外壳”包裹非凸“内核”既然 $w xy$ 这个等式我们无法在多项式时间内精确处理那么一个自然的想法就是放松它。我们不要求严格相等而是要求 $(x, y, w)$ 落在由这个等式定义的曲面的某个凸包络内。所谓“凸包络”就是包含该曲面的最小凸集。但计算凸包络本身可能和原问题一样难。“外近似”采用了一个更实用、更迭代的思路我不去求整个凸包络我构造一个更大的、容易描述的凸集通常是多面体这个凸集包含了原来的非凸集合。这个更大的凸集称为“外近似”。因为它是原集合的扩大所以在这个外近似集合上求出的最优解其目标函数值不会比原问题的最优值更差对于最小化问题外近似的最优值 ≤ 真实最优值。这个值称为原问题的下界。如何构造外近似呢一个强有力的工具是割平面。观察 $w xy$ 我们可以写出它的一些凸性不等式。例如对于任意实数 $x, y$ 有 $(xy)^2 \ge 0$ 展开得 $x^2 y^2 2xy \ge 0$ 但这并没有直接给出 $xy$ 的界。更常用的技巧是利用一阶泰勒展开或函数的上/下估计算子。以 $f(x, y) xy$ 为例它在任意点 $(x^0, y^0)$ 处的一阶泰勒展开为 $xy \approx x^0 y^0 y^0 (x - x^0) x^0 (y - y^0) y^0 x x^0 y - x^0 y^0$ 但这个展开式只是原函数的一个线性近似它既不是全局上界也不是下界。实际上对于双曲函数 $w xy$ 我们可以推导出两组线性不等式它们共同构成了该等式定义的集合的凸松弛一种外近似 $w \ge L_x y L_y x - L_x L_y$ $w \ge U_x y U_y x - U_x U_y$ $w \le U_x y L_y x - U_x L_y$ $w \le L_x y U_y x - L_x U_y$ 其中 $[L_x, U_x]$ 和 $[L_y, U_y]$ 分别是变量 $x$ 和 $y$ 的上下界。这四道线性不等式构成的四边形区域就包含了曲线 $wxy$。这就是著名的McCormick Envelope它是双线性项最紧的凸松弛即在外近似中是最小的那个。所以外近似的典型做法就是在凸重构引入 $w_{ij}x_i x_j$ 后放弃这个非凸等式转而用一组关于 $x_i, x_j, w_{ij}$ 的线性不等式如McCormick包络来替代它。这样原问题就被松弛为一个混合整数线性规划如果原问题还有其他整数变量或单纯的线性规划。这个MILP/LP问题可以高效求解其解提供了原问题的一个下界。3. 算法框架与实现流程理解了凸重构和外近似的思想后我们需要一个系统的算法框架来利用它们解决原问题。单纯地放松并求解一次松弛问题得到的结果下界可能很弱而且松弛问题的解很可能不满足原问题的非凸等式 $w_{ij}x_i x_j$。因此需要一个迭代过程来逐步收紧外近似逼近最优解。这就是外近似算法的核心。3.1 外近似算法的主循环外近似算法通常是一种割平面法其流程可以概括如下初始化对原问题进行凸重构引入辅助变量 $w_{ij}$ 替换所有二元二次项 $x_i x_j$。确定所有变量的上下界 $[L, U]$。如果问题本身没有给出需要根据问题背景估计一个合理的范围这一步至关重要因为外近似的紧致性依赖于边界。构建初始的外近似模型松弛主问题RMP使用原问题的所有线性约束加上对所有双线性项 $(x_i, x_j)$ 施加的McCormick包络约束或其他松弛约束。此时RMP是一个MILP。求解松弛主问题使用标准的MILP求解器如CPLEX, Gurobi, SCIP求解当前的RMP。记录最优解 $(x^, w^)$ 和最优目标值 $LB$。这个 $LB$ 是原问题全局最优值的一个下界。可行性检查与割平面生成检查当前松弛解 $(x^, w^)$ 对于原问题的非凸等式 $w_{ij} x_i^* x_j^$ 的违反程度。计算每个双线性项的差距 $\delta_{ij} |w_{ij}^- x_i^* x_j^*|$。如果对于所有 $(i,j)$ $\delta_{ij}$ 都小于一个预设的容差 $\epsilon$例如 $10^{-6}$那么当前解对于原问题是近似可行的算法可以终止$(x^*)$ 就是原问题的近似最优解。否则存在较大的违反。我们需要生成“割平面”来排除当前这个不满足原等式的松弛解。割平面是加到RMP上的新的线性约束它必须满足两个性质(a) 被原问题的所有可行解满足(b) 被当前的松弛解 $(x^, w^)$ 违反。对于双线性项 $w xy$ 一种最直接的割平面来自于该函数在点 $(x^, y^)$ 处的梯度不等式。因为 $xy$ 是一个凸函数吗不它不是全局凸的。但我们可以利用其凸/凹部分。将 $xy$ 重写为 $\frac{1}{4}[(xy)^2 - (x-y)^2]$。注意到 $(xy)^2$ 是凸函数$(x-y)^2$ 也是凸函数。因此对于固定的 $(x^, y^)$ 我们可以生成两种割凸性割利用 $(xy)^2$ 在 $(x^, y^)$ 处的梯度不等式$w \ge x^* y y^* x - x^* y^$。这个不等式对于所有 $(x, y, w)$ 满足 $w xy$ 的点都成立吗是的因为 $xy$ 关于 $(x, y)$ 的梯度是 $(y, x)$这个线性函数正是原函数的一个支撑超平面。实际上这就是McCormick包络在点 $(x^, y^*)$ 处产生的边界之一。我们可以将这条割加入RMP。凹性割同理对于 $-(x-y)^2$ 部分也可以生成割平面。更通用的方法是对于每个违反的非凸约束 $w_{ij} x_i x_j$ 我们求解一个线性规划或二阶锥规划子问题来分离出一个最深的割平面如梯度割、外逼近割等。更新与迭代将新生成的割平面加入到RMP中。返回步骤2重新求解加入了新割的RMP。每次迭代新的割平面会切掉一部分松弛可行域使得RMP的解 $(x^, w^)$ 越来越满足 $w_{ij} \approx x_i x_j$同时下界 $LB$ 会不断上升对于最小化问题。终止当满足以下条件之一时停止可行性满足所有 $\delta_{ij} \epsilon$。下界与上界差距小于容差如果我们通过某种启发式方法见3.2节得到了一个原问题的可行解其目标值为 $UB$上界那么当 $|UB - LB| \epsilon$ 时我们找到了全局 $\epsilon$-最优解。迭代次数或时间达到上限。3.2 获取上界启发式方法的重要性外近似算法天然地提供了一个下界 $LB$但我们还需要一个上界 $UB$ 来评估当前解的质量和终止算法。上界来自于原问题的一个可行解。如何得到呢在每次迭代中当我们从RMP得到松弛解 $(x^, w^)$ 后其中的 $x^$ 分量可能“几乎”就是原问题的解只是 $w^$ 不满足 $w_{ij}x_i^* x_j^$。一个非常直接且有效的启发式方法是**固定整数变量和连续变量 $x^$ 然后求解原问题**。具体操作将RMP解中的 $x^$ 值包括整数和连续变量固定代入原问题的模型。此时原问题中所有的双线性项 $x_i x_j$ 都变成了常数 $x_i^x_j^*$因为 $x$ 被固定了。于是原问题退化成为一个简单的线性规划甚至只是计算目标函数值或者是一个关于剩余变量的凸问题。求解这个固定后的子问题如果子问题可行那么我们得到了原问题的一个可行解其目标值记为 $c^T x^* \sum q_{ij}(x_i^* x_j^*)$。这个值就是一个上界 $UB$。我们记录下这个解和 $UB$。如果子问题不可行说明当前松弛解 $x^*$ 虽然满足松弛约束但不满足原问题的某些非线性约束当 $x$ 固定后这些约束可能变得不可满足。这提示我们需要生成能排除这类不可行点的割平面。这个“固定-求解”的启发式过程计算代价通常很小却能极大地加速算法收敛因为它不断为我们提供越来越好的可行解上界。当 $UB$ 和 $LB$ 足够接近时我们就可以很有信心地停止迭代。3.3 关键参数与实现细节在动手实现时有几个参数和细节需要仔细考量变量边界 $[L, U]$ 的估计McCormick包络的紧致性强烈依赖于变量边界。过宽的边界会导致松弛非常弱下界 $LB$ 很差算法需要很多次迭代。因此尽可能获取紧的变量边界。可以通过问题本身的物理意义、约束条件或者运行一个初步的线性化松弛来推导更紧的边界。割平面管理迭代中可能会加入大量割平面导致RMP规模急剧膨胀求解变慢。需要实施割平面管理策略削减定期移除那些长期不活跃对应的松弛变量远离边界的割平面。池化不是每次迭代都加入所有生成的割只加入那些违反程度最深的。懒惰约束回调现代MILP求解器支持回调函数。可以在求解过程中每当找到一个候选整数解时检查其对于原问题非凸等式的可行性并动态添加割平面。这比求解完整个MILP再检查更高效。数值容差 $\epsilon$设置一个合理的可行性容差如 $10^{-6}$和最优性间隙容差如 $10^{-4}$。过于严格会大幅增加计算时间过于宽松则解的质量不高。处理非双线性二次项如果问题中包含像 $x_i^2$ 这样的单项二次项处理方式不同。对于凸的 $x_i^2$系数为正可以直接保留现代求解器能处理凸二次约束。对于非凸的 $x_i^2$系数为负可以引入辅助变量 $w_{ii}$ 和等式 $w_{ii} x_i^2$然后对后者进行外近似。$w x^2$ 的凸包络是两条切线$w \ge 2Lx - L^2$ 和 $w \ge 2Ux - U^2$以及一个割 $w \le (LU)x - LU$。这些线性约束构成了 $w x^2$ 的外近似。4. 实战案例带固定成本的资源分配问题为了让大家有更直观的感受我们考虑一个简化但经典的案例带固定成本的资源分配问题。问题描述假设我们要生产一种产品需要两种资源A和B。资源A的用量为 $x$连续变量吨资源B的用量为 $y$连续变量吨。生产过程中两种资源之间存在协同效应但也是成本来源之一。此外使用每种资源都有一个固定的启动成本例如打开某个设备这由0-1变量 $\delta_A$ 和 $\delta_B$ 表示。 目标是最小化总成本其中包含资源A的可变成本$c_A x$资源B的可变成本$c_B y$资源A的固定成本$f_A \delta_A$ 如果 $x0$则 $\delta_A1$产生此成本资源B的固定成本$f_B \delta_B$资源A和B的协同/冲突成本这是一个二次项假设为 $-q x y$ $q0$负号表示协同效应能降低成本例如一起处理减少能耗但这使得该项非凸。同时我们有产能约束$x \le M_A \delta_A$, $y \le M_B \delta_B$大M约束将连续变量和0-1变量关联以及需求约束$a x b y \ge D$生产必须满足最低需求。此外$x, y \ge 0$。数学模型 Minimize: $c_A x c_B y f_A \delta_A f_B \delta_B - q x y$ Subject to: $x \le M_A \delta_A$ $y \le M_B \delta_B$ $a x b y \ge D$ $x, y \ge 0$ $\delta_A, \delta_B \in {0, 1}$步骤1凸重构识别非凸项$-q x y$。引入辅助变量 $w x y$。目标函数变为$c_A x c_B y f_A \delta_A f_B \delta_B - q w$。 新增非凸等式约束$w x y$。步骤2确定变量边界$x$: 下界 $L_x 0$上界 $U_x M_A$因为当 $\delta_A1$ 时$x$ 最大为 $M_A$当 $\delta_A0$ 时$x0$。$y$: 类似$L_y0$, $U_yM_B$。$w$: 理论上$w$ 的下界是 $L_x L_y 0$上界是 $U_x U_y M_A M_B$。但我们可以推导更紧的界。因为 $w x y$ 且 $x, y \ge 0$所以 $w \ge 0$。另外根据约束 $x \le M_A \delta_A$ 和 $y \le M_B \delta_B$以及 $\delta$ 为0-1变量可知如果 $\delta_A0$ 则 $x0, w0$如果 $\delta_B0$ 则 $y0, w0$。因此$w$ 的上界实际上受限于 $\delta_A$ 和 $\delta_B$ 同时为1。一个紧的上界是 $w \le \min(M_A y, M_B x)$但这非线性。在初始松弛中我们可以先用 $U_w M_A M_B$后续通过割平面收紧。步骤3构建初始外近似模型RMP原问题的线性约束全部保留。 对于非凸约束 $w x y$ 我们用其McCormick包络替代因为 $x, y \ge 0$ McCormick包络简化为两道不等式 $w \ge L_x y L_y x - L_x L_y 0$ 自动满足因为 $w \ge 0$ $w \ge U_x y U_y x - U_x U_y M_A y M_B x - M_A M_B$ $w \le U_x y L_y x - U_x L_y M_A y$ $w \le L_x y U_y x - L_x U_y M_B x$ 注意这里我们用了 $L_xL_y0$ 进行了简化。实际上后三个不等式就是初始的外近似约束。 此外还需要连接 $w$ 和 $\delta$ 的关系。因为 $w x y$ 当 $\delta_A0$ 时 $x0$ 故 $w0$。所以可以添加约束$w \le M_A M_B \delta_A$ 和 $w \le M_A M_B \delta_B$。更紧的约束是 $w \le M_A y$ 和 $w \le M_B x$ 已经隐含了这一点但显式地加上与 $\delta$ 的联系有时能加强松弛。于是初始RMP是一个MILP Minimize: $c_A x c_B y f_A \delta_A f_B \delta_B - q w$ Subject to: $x \le M_A \delta_A$ $y \le M_B \delta_B$ $a x b y \ge D$ $w \ge M_A y M_B x - M_A M_B$ $w \le M_A y$ $w \le M_B x$ $w \le M_A M_B \delta_A$ 可选加强 $w \le M_A M_B \delta_B$ 可选加强 $x, y, w \ge 0$ $\delta_A, \delta_B \in {0, 1}$步骤4迭代求解求解上述RMP得到松弛解 $(x^, y^, \delta_A^, \delta_B^, w^*)$ 和下界 $LB$。检查可行性计算 $|w^* - x^* y^|$。如果大于容差则生成割平面。例如在点 $(x^, y^)$ 处$w x y$ 的梯度割为$w \ge y^x x^* y - x^* y^*$。将此线性不等式加入RMP。固定启发式将 $(x^, y^, \delta_A^, \delta_B^)$ 代入原目标函数计算 $c_A x^* c_B y^* f_A \delta_A^* f_B \delta_B^* - q (x^* y^)$。注意这里我们直接用 $x^y^$ 计算二次项而不是用 $w^$。这个值就是原问题在该点可能不可行但这里我们只计算目标值如果 $\delta$ 满足逻辑且线性约束满足则就是可行的的目标值作为一个上界 $UB$ 的候选。我们需要验证解的可行性检查 $x^* \le M_A \delta_A^$, $y^\le M_B \delta_B^$, $a x^ b y^* \ge D$。如果都满足那么这个 $UB$ 是有效的。重复步骤1-3直到 $UB - LB \epsilon$ 或者迭代次数达到上限。实操心得 在这个具体问题中由于 $\delta$ 是0-1变量我们其实可以对 $w x y$ 进行精确线性化而不必使用外近似迭代因为 $x$ 和 $y$ 都是连续变量但它们的上界与0-1变量 $\delta$ 关联。我们可以引入额外的辅助变量和约束将 $w x y$ 在 $\delta_A$ 和 $\delta_B$ 的不同取值下精确线性化。这通常比外近似迭代更高效。这也引出了一个重要经验永远先检查问题是否有特殊的结构允许精确线性化。外近似是处理一般性非凸问题的通用武器但当问题具有如固定成本、逻辑约束等结构时往往存在更巧妙的精确转化方法。5. 常见陷阱、技巧与进阶讨论在实际应用中直接套用上述标准流程可能会遇到各种问题。这里分享一些踩过的坑和总结的技巧。5.1 外近似不收敛或收敛慢问题迭代了很多次下界 $LB$ 提升缓慢上界 $UB$ 和下界 $LB$ 之间的间隙始终很大。排查与解决检查变量边界这是最常见的原因。过于宽松的 $[L, U]$ 会导致初始McCormick包络非常弱。尝试从问题约束中推导更紧的边界。例如如果有约束 $x y \le 10$ 且 $x, y \ge 0$那么 $x$ 和 $y$ 的上界可以收紧为10而不是随意设定的一个很大值。加强初始松弛除了McCormick包络是否可以添加其他有效的线性不等式例如对于 $w x^2$ 可以添加切线割。对于某些问题可能存在基于多面体理论的更强松弛如 RLT – Reformulation-Linearization Technique 产生的约束。生成更强的割平面标准的梯度割可能不够“深”。可以考虑使用SOCP二阶锥规划分离。对于约束 $w x^2$ 可以写成二阶锥约束 $||(2x, w-1)||_2 \le w1$。当松弛解违反 $w x^2$ 时可以求解一个SOCP分离问题来生成割平面这通常比梯度割更强。管理整数变量如果问题包含很多整数变量松弛问题的MILP本身可能就很难解。可以考虑在迭代初期先放松整数变量为连续变量快速生成一批割平面收紧连续变量的松弛后再恢复整数性进行求解。5.2 数值不稳定与病态问题问题生成的割平面系数非常大或非常小导致求解器出现数值问题求解失败或结果不可信。排查与解决缩放变量在建模之初尽量让变量的量级在1附近。例如如果 $x$ 代表吨范围是0~1000可以考虑将单位改为千吨这样变量范围变成0~1。这能显著改善求解器的数值稳定性。避免过大的大M在连接连续变量和0-1变量的约束中如 $x \le M \delta$$M$ 的值要尽可能紧不要用一个巨大的数。过大的 $M$ 会导致松弛极弱并引发数值问题。容差设置适当调整求解器的整数容差、可行性容差等参数以适应问题尺度。5.3 与现成求解器的协同如今像Gurobi、CPLEX这样的高端商业求解器以及开源的SCIP都内置了处理非凸二次约束包括双线性项的能力。它们内部很可能就使用了类似外近似或空间分支定界的算法。何时自己实现外近似算法研究或教学为了深入理解算法原理。求解器不支持或性能不佳当你的问题有特殊结构或者规模巨大需要高度定制化的割平面和启发式策略时。嵌入在更大规模的算法中例如外近似作为子过程出现在分解算法中。何时直接使用求解器绝大多数情况对于一般规模的MIQCP混合整数二次约束规划直接丢给Gurobi/CPLEX是最快、最稳的选择。它们经过极度优化集成了多种预处理、割平面和启发式技术。操作在建模语言如Pyomo, GAMS, JuMP中直接将二次约束写入模型设置好参数如非凸策略、最优性间隙然后调用求解器即可。重要提示如果你使用求解器务必在模型中将问题正确声明为非凸例如在Gurobi中设置参数NonConvex2。否则求解器可能会将其误判为凸问题而给出错误结果或者直接拒绝求解。5.4 从外近似到全局优化空间分支定界外近似算法通常被嵌入到一个空间分支定界的框架中以求得全局最优解。单纯的割平面法可能无法在有限步内收敛到可行解或者收敛速度很慢。空间分支定界的思路是在外近似迭代中如果上下界 $UB$ 和 $LB$ 的差距始终无法缩小到容差以内则对某个变量通常是导致松弛最松的变量的区间 $[L, U]$ 进行分支分成两个子区域例如$[L, mid]$ 和 $[mid, U]$。在每个子区域上变量有了更紧的边界因此McCormick包络等松弛会变得更紧。在每个子节点上分别运行外近似算法得到该节点上的下界。利用分支定界树的剪枝规则如果一个节点的下界已经超过当前全局上界 $UB$则该节点不可能包含更优解可以剪枝不断搜索整个空间。这样外近似提供了每个节点上的下界计算工具而分支定界框架则系统地枚举空间最终找到全局最优解。像BARON、Couenne这样的全局优化求解器其核心就是基于空间分支定界并结合了外近似、区间分析等多种技术。最后处理二元二次规划这类非凸问题没有银弹。凸重构和外近似提供了一套系统且可靠的框架将难题转化为一系列可求解的MILP子问题。其效能很大程度上取决于你对问题结构的洞察以获取紧的边界和松弛、割平面生成的质量、以及实现上的工程优化。对于实践者我的建议是首先尝试使用成熟的全局优化求解器若遇到性能瓶颈或需要高度定制化再考虑动手实现外近似算法的核心循环并聚焦于如何为你的特定问题生成最强、最有效的割平面。这个过程本身就是对优化理论和工程实践一次极好的锤炼。 非凸二次规划求解：凸重构与外近似算法原理与实践
1. 项目概述从“硬骨头”到“可啃的骨头”做优化的人尤其是处理过实际工程问题或者金融组合模型的大概率都遇到过一类让人头疼的优化问题目标函数或者约束里包含了两个决策变量乘积的二次项。这类问题在学术上常被归为“二元二次规划”或者更广义的“非凸二次规划”的范畴。它不像线性规划那样有成熟高效的单纯形法或内点法也不像凸二次规划那样可以放心地丢给商业求解器。它的非凸性意味着可行域可能坑坑洼洼存在多个局部最优解而找到那个全局最优解计算上非常困难属于NP-hard问题。我最初接触这类问题是在一个供应链网络设计的项目中成本函数里既有固定成本与是否建仓相关0-1变量又有运输成本与流量相关连续变量而运输成本中有一部分是和流量平方相关的拥堵成本这就构成了一个典型的混合整数非线性规划其中非线性部分就是二元二次项。直接丢给当时常用的求解器要么报错要么运行几个小时也得不到一个可靠的结果。那时候就意识到必须得有一套系统的方法把这块“硬骨头”想办法“软化”让它变得可解。“凸重构”和“外近似”就是两把关键的“锉刀”。这个项目的核心就是探讨如何针对一类特定的二元二次规划问题通过数学上的等价变换凸重构将其非凸的部分暴露或转化再通过构造一系列线性约束外近似从外部逐步逼近原问题的可行域最终将其松弛或转化为一个可以高效求解的混合整数线性规划问题。这不仅仅是理论上的炫技更是工程实践中打通问题求解路径的必备技能。无论你是研究算法理论的学生还是面临实际优化难题的工程师理解这套方法的思路和实操细节都能让你在面对复杂非线性模型时多一份底气和工具。2. 核心思路拆解为什么是“凸重构”加“外近似”要理解这套组合拳我们得先拆开看这两个概念到底在做什么以及它们为什么要配合使用。2.1 二元二次规划的非凸根源一个一般的二元二次项可以写成 $q_{ij} x_i x_j$其中 $x_i$, $x_j$ 是决策变量$q_{ij}$ 是系数。当这个系数 $q_{ij} 0$ 时这个项在某个方向上就是凸的当 $q_{ij} 0$ 时它就是非凸的根源。我们通常说的“非凸二元二次规划”其非凸性往往就来自于一个或多个负系数的二次项。例如一个简单的非凸函数 $f(x, y) -x^2 - y^2$它的海森矩阵是负定的整个函数像一口倒扣的锅到处都是局部极大值但全局最大值在无穷远处这给优化带来了本质困难。在混合整数规划中情况更复杂。比如一个项是 $-x_i x_j$其中 $x_i$ 是0-1变量$x_j$ 是连续变量。这个乘积 $-x_i x_j$ 在 $x_i0$ 时为0在 $x_i1$ 时等于 $-x_j$。你会发现这个关系本身是线性的吗不是因为它包含了乘积。但它可以被精确线性化吗可以但需要引入额外的辅助变量和约束。这就是我们处理这类问题的起点识别出这些导致非凸的“麻烦项”。2.2 凸重构暴露结构创造机会“凸重构”不是指把非凸问题变成凸问题那通常不可能而是指通过变量替换、等式约束引入等方式重新表述原问题使得其中非凸的部分被孤立出来或者呈现出某种特殊的结构从而为后续的近似或精确线性化创造条件。最经典、最常用的凸重构技巧就是引入辅助变量进行替换。对于二元二次项 $x_i x_j$我们引入一个新的连续变量 $w_{ij}$并增加等式约束 $w_{ij} x_i x_j$。这样原目标函数或约束中所有出现 $x_i x_j$ 的地方都可以用 $w_{ij}$ 替换。于是原问题的非凸性就被“转移”并“浓缩”到了这个新引入的等式约束 $w_{ij} x_i x_j$ 上。注意这一步是精确等价变换没有引入任何近似。问题难度没有降低只是形式变了。现在我们的主问题目标和其他约束关于变量 $(x, w)$ 可能是线性的或凸的唯一的“罪魁祸首”就是那一组等式约束 $w_{ij} x_i x_j$。我们的火力就可以集中对付它们。对于不同类型的变量组合这个等式约束的性质不同两个连续变量$w xy$ 定义了一个双曲线面是非凸等式约束。一个0-1变量和一个连续变量$w \delta x$其中 $\delta \in {0, 1}$。这个关系可以通过大M法线性化$0 \le w \le M\delta$, $x - M(1-\delta) \le w \le x$。这是可以精确线性化的。两个0-1变量$w \delta_i \delta_j$ $w$ 也是0-1变量且等价于 $w \le \delta_i$, $w \le \delta_j$, $w \ge \delta_i \delta_j - 1$。这也是可以精确线性化的。所以凸重构后真正的“硬骨头”是那些包含两个连续变量的二次项。我们的“外近似”主要就是用来对付它们的。2.3 外近似用线性“外壳”包裹非凸“内核”既然 $w xy$ 这个等式我们无法在多项式时间内精确处理那么一个自然的想法就是放松它。我们不要求严格相等而是要求 $(x, y, w)$ 落在由这个等式定义的曲面的某个凸包络内。所谓“凸包络”就是包含该曲面的最小凸集。但计算凸包络本身可能和原问题一样难。“外近似”采用了一个更实用、更迭代的思路我不去求整个凸包络我构造一个更大的、容易描述的凸集通常是多面体这个凸集包含了原来的非凸集合。这个更大的凸集称为“外近似”。因为它是原集合的扩大所以在这个外近似集合上求出的最优解其目标函数值不会比原问题的最优值更差对于最小化问题外近似的最优值 ≤ 真实最优值。这个值称为原问题的下界。如何构造外近似呢一个强有力的工具是割平面。观察 $w xy$ 我们可以写出它的一些凸性不等式。例如对于任意实数 $x, y$ 有 $(xy)^2 \ge 0$ 展开得 $x^2 y^2 2xy \ge 0$ 但这并没有直接给出 $xy$ 的界。更常用的技巧是利用一阶泰勒展开或函数的上/下估计算子。以 $f(x, y) xy$ 为例它在任意点 $(x^0, y^0)$ 处的一阶泰勒展开为 $xy \approx x^0 y^0 y^0 (x - x^0) x^0 (y - y^0) y^0 x x^0 y - x^0 y^0$ 但这个展开式只是原函数的一个线性近似它既不是全局上界也不是下界。实际上对于双曲函数 $w xy$ 我们可以推导出两组线性不等式它们共同构成了该等式定义的集合的凸松弛一种外近似 $w \ge L_x y L_y x - L_x L_y$ $w \ge U_x y U_y x - U_x U_y$ $w \le U_x y L_y x - U_x L_y$ $w \le L_x y U_y x - L_x U_y$ 其中 $[L_x, U_x]$ 和 $[L_y, U_y]$ 分别是变量 $x$ 和 $y$ 的上下界。这四道线性不等式构成的四边形区域就包含了曲线 $wxy$。这就是著名的McCormick Envelope它是双线性项最紧的凸松弛即在外近似中是最小的那个。所以外近似的典型做法就是在凸重构引入 $w_{ij}x_i x_j$ 后放弃这个非凸等式转而用一组关于 $x_i, x_j, w_{ij}$ 的线性不等式如McCormick包络来替代它。这样原问题就被松弛为一个混合整数线性规划如果原问题还有其他整数变量或单纯的线性规划。这个MILP/LP问题可以高效求解其解提供了原问题的一个下界。3. 算法框架与实现流程理解了凸重构和外近似的思想后我们需要一个系统的算法框架来利用它们解决原问题。单纯地放松并求解一次松弛问题得到的结果下界可能很弱而且松弛问题的解很可能不满足原问题的非凸等式 $w_{ij}x_i x_j$。因此需要一个迭代过程来逐步收紧外近似逼近最优解。这就是外近似算法的核心。3.1 外近似算法的主循环外近似算法通常是一种割平面法其流程可以概括如下初始化对原问题进行凸重构引入辅助变量 $w_{ij}$ 替换所有二元二次项 $x_i x_j$。确定所有变量的上下界 $[L, U]$。如果问题本身没有给出需要根据问题背景估计一个合理的范围这一步至关重要因为外近似的紧致性依赖于边界。构建初始的外近似模型松弛主问题RMP使用原问题的所有线性约束加上对所有双线性项 $(x_i, x_j)$ 施加的McCormick包络约束或其他松弛约束。此时RMP是一个MILP。求解松弛主问题使用标准的MILP求解器如CPLEX, Gurobi, SCIP求解当前的RMP。记录最优解 $(x^, w^)$ 和最优目标值 $LB$。这个 $LB$ 是原问题全局最优值的一个下界。可行性检查与割平面生成检查当前松弛解 $(x^, w^)$ 对于原问题的非凸等式 $w_{ij} x_i^* x_j^$ 的违反程度。计算每个双线性项的差距 $\delta_{ij} |w_{ij}^- x_i^* x_j^*|$。如果对于所有 $(i,j)$ $\delta_{ij}$ 都小于一个预设的容差 $\epsilon$例如 $10^{-6}$那么当前解对于原问题是近似可行的算法可以终止$(x^*)$ 就是原问题的近似最优解。否则存在较大的违反。我们需要生成“割平面”来排除当前这个不满足原等式的松弛解。割平面是加到RMP上的新的线性约束它必须满足两个性质(a) 被原问题的所有可行解满足(b) 被当前的松弛解 $(x^, w^)$ 违反。对于双线性项 $w xy$ 一种最直接的割平面来自于该函数在点 $(x^, y^)$ 处的梯度不等式。因为 $xy$ 是一个凸函数吗不它不是全局凸的。但我们可以利用其凸/凹部分。将 $xy$ 重写为 $\frac{1}{4}[(xy)^2 - (x-y)^2]$。注意到 $(xy)^2$ 是凸函数$(x-y)^2$ 也是凸函数。因此对于固定的 $(x^, y^)$ 我们可以生成两种割凸性割利用 $(xy)^2$ 在 $(x^, y^)$ 处的梯度不等式$w \ge x^* y y^* x - x^* y^$。这个不等式对于所有 $(x, y, w)$ 满足 $w xy$ 的点都成立吗是的因为 $xy$ 关于 $(x, y)$ 的梯度是 $(y, x)$这个线性函数正是原函数的一个支撑超平面。实际上这就是McCormick包络在点 $(x^, y^*)$ 处产生的边界之一。我们可以将这条割加入RMP。凹性割同理对于 $-(x-y)^2$ 部分也可以生成割平面。更通用的方法是对于每个违反的非凸约束 $w_{ij} x_i x_j$ 我们求解一个线性规划或二阶锥规划子问题来分离出一个最深的割平面如梯度割、外逼近割等。更新与迭代将新生成的割平面加入到RMP中。返回步骤2重新求解加入了新割的RMP。每次迭代新的割平面会切掉一部分松弛可行域使得RMP的解 $(x^, w^)$ 越来越满足 $w_{ij} \approx x_i x_j$同时下界 $LB$ 会不断上升对于最小化问题。终止当满足以下条件之一时停止可行性满足所有 $\delta_{ij} \epsilon$。下界与上界差距小于容差如果我们通过某种启发式方法见3.2节得到了一个原问题的可行解其目标值为 $UB$上界那么当 $|UB - LB| \epsilon$ 时我们找到了全局 $\epsilon$-最优解。迭代次数或时间达到上限。3.2 获取上界启发式方法的重要性外近似算法天然地提供了一个下界 $LB$但我们还需要一个上界 $UB$ 来评估当前解的质量和终止算法。上界来自于原问题的一个可行解。如何得到呢在每次迭代中当我们从RMP得到松弛解 $(x^, w^)$ 后其中的 $x^$ 分量可能“几乎”就是原问题的解只是 $w^$ 不满足 $w_{ij}x_i^* x_j^$。一个非常直接且有效的启发式方法是**固定整数变量和连续变量 $x^$ 然后求解原问题**。具体操作将RMP解中的 $x^$ 值包括整数和连续变量固定代入原问题的模型。此时原问题中所有的双线性项 $x_i x_j$ 都变成了常数 $x_i^x_j^*$因为 $x$ 被固定了。于是原问题退化成为一个简单的线性规划甚至只是计算目标函数值或者是一个关于剩余变量的凸问题。求解这个固定后的子问题如果子问题可行那么我们得到了原问题的一个可行解其目标值记为 $c^T x^* \sum q_{ij}(x_i^* x_j^*)$。这个值就是一个上界 $UB$。我们记录下这个解和 $UB$。如果子问题不可行说明当前松弛解 $x^*$ 虽然满足松弛约束但不满足原问题的某些非线性约束当 $x$ 固定后这些约束可能变得不可满足。这提示我们需要生成能排除这类不可行点的割平面。这个“固定-求解”的启发式过程计算代价通常很小却能极大地加速算法收敛因为它不断为我们提供越来越好的可行解上界。当 $UB$ 和 $LB$ 足够接近时我们就可以很有信心地停止迭代。3.3 关键参数与实现细节在动手实现时有几个参数和细节需要仔细考量变量边界 $[L, U]$ 的估计McCormick包络的紧致性强烈依赖于变量边界。过宽的边界会导致松弛非常弱下界 $LB$ 很差算法需要很多次迭代。因此尽可能获取紧的变量边界。可以通过问题本身的物理意义、约束条件或者运行一个初步的线性化松弛来推导更紧的边界。割平面管理迭代中可能会加入大量割平面导致RMP规模急剧膨胀求解变慢。需要实施割平面管理策略削减定期移除那些长期不活跃对应的松弛变量远离边界的割平面。池化不是每次迭代都加入所有生成的割只加入那些违反程度最深的。懒惰约束回调现代MILP求解器支持回调函数。可以在求解过程中每当找到一个候选整数解时检查其对于原问题非凸等式的可行性并动态添加割平面。这比求解完整个MILP再检查更高效。数值容差 $\epsilon$设置一个合理的可行性容差如 $10^{-6}$和最优性间隙容差如 $10^{-4}$。过于严格会大幅增加计算时间过于宽松则解的质量不高。处理非双线性二次项如果问题中包含像 $x_i^2$ 这样的单项二次项处理方式不同。对于凸的 $x_i^2$系数为正可以直接保留现代求解器能处理凸二次约束。对于非凸的 $x_i^2$系数为负可以引入辅助变量 $w_{ii}$ 和等式 $w_{ii} x_i^2$然后对后者进行外近似。$w x^2$ 的凸包络是两条切线$w \ge 2Lx - L^2$ 和 $w \ge 2Ux - U^2$以及一个割 $w \le (LU)x - LU$。这些线性约束构成了 $w x^2$ 的外近似。4. 实战案例带固定成本的资源分配问题为了让大家有更直观的感受我们考虑一个简化但经典的案例带固定成本的资源分配问题。问题描述假设我们要生产一种产品需要两种资源A和B。资源A的用量为 $x$连续变量吨资源B的用量为 $y$连续变量吨。生产过程中两种资源之间存在协同效应但也是成本来源之一。此外使用每种资源都有一个固定的启动成本例如打开某个设备这由0-1变量 $\delta_A$ 和 $\delta_B$ 表示。 目标是最小化总成本其中包含资源A的可变成本$c_A x$资源B的可变成本$c_B y$资源A的固定成本$f_A \delta_A$ 如果 $x0$则 $\delta_A1$产生此成本资源B的固定成本$f_B \delta_B$资源A和B的协同/冲突成本这是一个二次项假设为 $-q x y$ $q0$负号表示协同效应能降低成本例如一起处理减少能耗但这使得该项非凸。同时我们有产能约束$x \le M_A \delta_A$, $y \le M_B \delta_B$大M约束将连续变量和0-1变量关联以及需求约束$a x b y \ge D$生产必须满足最低需求。此外$x, y \ge 0$。数学模型 Minimize: $c_A x c_B y f_A \delta_A f_B \delta_B - q x y$ Subject to: $x \le M_A \delta_A$ $y \le M_B \delta_B$ $a x b y \ge D$ $x, y \ge 0$ $\delta_A, \delta_B \in {0, 1}$步骤1凸重构识别非凸项$-q x y$。引入辅助变量 $w x y$。目标函数变为$c_A x c_B y f_A \delta_A f_B \delta_B - q w$。 新增非凸等式约束$w x y$。步骤2确定变量边界$x$: 下界 $L_x 0$上界 $U_x M_A$因为当 $\delta_A1$ 时$x$ 最大为 $M_A$当 $\delta_A0$ 时$x0$。$y$: 类似$L_y0$, $U_yM_B$。$w$: 理论上$w$ 的下界是 $L_x L_y 0$上界是 $U_x U_y M_A M_B$。但我们可以推导更紧的界。因为 $w x y$ 且 $x, y \ge 0$所以 $w \ge 0$。另外根据约束 $x \le M_A \delta_A$ 和 $y \le M_B \delta_B$以及 $\delta$ 为0-1变量可知如果 $\delta_A0$ 则 $x0, w0$如果 $\delta_B0$ 则 $y0, w0$。因此$w$ 的上界实际上受限于 $\delta_A$ 和 $\delta_B$ 同时为1。一个紧的上界是 $w \le \min(M_A y, M_B x)$但这非线性。在初始松弛中我们可以先用 $U_w M_A M_B$后续通过割平面收紧。步骤3构建初始外近似模型RMP原问题的线性约束全部保留。 对于非凸约束 $w x y$ 我们用其McCormick包络替代因为 $x, y \ge 0$ McCormick包络简化为两道不等式 $w \ge L_x y L_y x - L_x L_y 0$ 自动满足因为 $w \ge 0$ $w \ge U_x y U_y x - U_x U_y M_A y M_B x - M_A M_B$ $w \le U_x y L_y x - U_x L_y M_A y$ $w \le L_x y U_y x - L_x U_y M_B x$ 注意这里我们用了 $L_xL_y0$ 进行了简化。实际上后三个不等式就是初始的外近似约束。 此外还需要连接 $w$ 和 $\delta$ 的关系。因为 $w x y$ 当 $\delta_A0$ 时 $x0$ 故 $w0$。所以可以添加约束$w \le M_A M_B \delta_A$ 和 $w \le M_A M_B \delta_B$。更紧的约束是 $w \le M_A y$ 和 $w \le M_B x$ 已经隐含了这一点但显式地加上与 $\delta$ 的联系有时能加强松弛。于是初始RMP是一个MILP Minimize: $c_A x c_B y f_A \delta_A f_B \delta_B - q w$ Subject to: $x \le M_A \delta_A$ $y \le M_B \delta_B$ $a x b y \ge D$ $w \ge M_A y M_B x - M_A M_B$ $w \le M_A y$ $w \le M_B x$ $w \le M_A M_B \delta_A$ 可选加强 $w \le M_A M_B \delta_B$ 可选加强 $x, y, w \ge 0$ $\delta_A, \delta_B \in {0, 1}$步骤4迭代求解求解上述RMP得到松弛解 $(x^, y^, \delta_A^, \delta_B^, w^*)$ 和下界 $LB$。检查可行性计算 $|w^* - x^* y^|$。如果大于容差则生成割平面。例如在点 $(x^, y^)$ 处$w x y$ 的梯度割为$w \ge y^x x^* y - x^* y^*$。将此线性不等式加入RMP。固定启发式将 $(x^, y^, \delta_A^, \delta_B^)$ 代入原目标函数计算 $c_A x^* c_B y^* f_A \delta_A^* f_B \delta_B^* - q (x^* y^)$。注意这里我们直接用 $x^y^$ 计算二次项而不是用 $w^$。这个值就是原问题在该点可能不可行但这里我们只计算目标值如果 $\delta$ 满足逻辑且线性约束满足则就是可行的的目标值作为一个上界 $UB$ 的候选。我们需要验证解的可行性检查 $x^* \le M_A \delta_A^$, $y^\le M_B \delta_B^$, $a x^ b y^* \ge D$。如果都满足那么这个 $UB$ 是有效的。重复步骤1-3直到 $UB - LB \epsilon$ 或者迭代次数达到上限。实操心得 在这个具体问题中由于 $\delta$ 是0-1变量我们其实可以对 $w x y$ 进行精确线性化而不必使用外近似迭代因为 $x$ 和 $y$ 都是连续变量但它们的上界与0-1变量 $\delta$ 关联。我们可以引入额外的辅助变量和约束将 $w x y$ 在 $\delta_A$ 和 $\delta_B$ 的不同取值下精确线性化。这通常比外近似迭代更高效。这也引出了一个重要经验永远先检查问题是否有特殊的结构允许精确线性化。外近似是处理一般性非凸问题的通用武器但当问题具有如固定成本、逻辑约束等结构时往往存在更巧妙的精确转化方法。5. 常见陷阱、技巧与进阶讨论在实际应用中直接套用上述标准流程可能会遇到各种问题。这里分享一些踩过的坑和总结的技巧。5.1 外近似不收敛或收敛慢问题迭代了很多次下界 $LB$ 提升缓慢上界 $UB$ 和下界 $LB$ 之间的间隙始终很大。排查与解决检查变量边界这是最常见的原因。过于宽松的 $[L, U]$ 会导致初始McCormick包络非常弱。尝试从问题约束中推导更紧的边界。例如如果有约束 $x y \le 10$ 且 $x, y \ge 0$那么 $x$ 和 $y$ 的上界可以收紧为10而不是随意设定的一个很大值。加强初始松弛除了McCormick包络是否可以添加其他有效的线性不等式例如对于 $w x^2$ 可以添加切线割。对于某些问题可能存在基于多面体理论的更强松弛如 RLT – Reformulation-Linearization Technique 产生的约束。生成更强的割平面标准的梯度割可能不够“深”。可以考虑使用SOCP二阶锥规划分离。对于约束 $w x^2$ 可以写成二阶锥约束 $||(2x, w-1)||_2 \le w1$。当松弛解违反 $w x^2$ 时可以求解一个SOCP分离问题来生成割平面这通常比梯度割更强。管理整数变量如果问题包含很多整数变量松弛问题的MILP本身可能就很难解。可以考虑在迭代初期先放松整数变量为连续变量快速生成一批割平面收紧连续变量的松弛后再恢复整数性进行求解。5.2 数值不稳定与病态问题问题生成的割平面系数非常大或非常小导致求解器出现数值问题求解失败或结果不可信。排查与解决缩放变量在建模之初尽量让变量的量级在1附近。例如如果 $x$ 代表吨范围是0~1000可以考虑将单位改为千吨这样变量范围变成0~1。这能显著改善求解器的数值稳定性。避免过大的大M在连接连续变量和0-1变量的约束中如 $x \le M \delta$$M$ 的值要尽可能紧不要用一个巨大的数。过大的 $M$ 会导致松弛极弱并引发数值问题。容差设置适当调整求解器的整数容差、可行性容差等参数以适应问题尺度。5.3 与现成求解器的协同如今像Gurobi、CPLEX这样的高端商业求解器以及开源的SCIP都内置了处理非凸二次约束包括双线性项的能力。它们内部很可能就使用了类似外近似或空间分支定界的算法。何时自己实现外近似算法研究或教学为了深入理解算法原理。求解器不支持或性能不佳当你的问题有特殊结构或者规模巨大需要高度定制化的割平面和启发式策略时。嵌入在更大规模的算法中例如外近似作为子过程出现在分解算法中。何时直接使用求解器绝大多数情况对于一般规模的MIQCP混合整数二次约束规划直接丢给Gurobi/CPLEX是最快、最稳的选择。它们经过极度优化集成了多种预处理、割平面和启发式技术。操作在建模语言如Pyomo, GAMS, JuMP中直接将二次约束写入模型设置好参数如非凸策略、最优性间隙然后调用求解器即可。重要提示如果你使用求解器务必在模型中将问题正确声明为非凸例如在Gurobi中设置参数NonConvex2。否则求解器可能会将其误判为凸问题而给出错误结果或者直接拒绝求解。5.4 从外近似到全局优化空间分支定界外近似算法通常被嵌入到一个空间分支定界的框架中以求得全局最优解。单纯的割平面法可能无法在有限步内收敛到可行解或者收敛速度很慢。空间分支定界的思路是在外近似迭代中如果上下界 $UB$ 和 $LB$ 的差距始终无法缩小到容差以内则对某个变量通常是导致松弛最松的变量的区间 $[L, U]$ 进行分支分成两个子区域例如$[L, mid]$ 和 $[mid, U]$。在每个子区域上变量有了更紧的边界因此McCormick包络等松弛会变得更紧。在每个子节点上分别运行外近似算法得到该节点上的下界。利用分支定界树的剪枝规则如果一个节点的下界已经超过当前全局上界 $UB$则该节点不可能包含更优解可以剪枝不断搜索整个空间。这样外近似提供了每个节点上的下界计算工具而分支定界框架则系统地枚举空间最终找到全局最优解。像BARON、Couenne这样的全局优化求解器其核心就是基于空间分支定界并结合了外近似、区间分析等多种技术。最后处理二元二次规划这类非凸问题没有银弹。凸重构和外近似提供了一套系统且可靠的框架将难题转化为一系列可求解的MILP子问题。其效能很大程度上取决于你对问题结构的洞察以获取紧的边界和松弛、割平面生成的质量、以及实现上的工程优化。对于实践者我的建议是首先尝试使用成熟的全局优化求解器若遇到性能瓶颈或需要高度定制化再考虑动手实现外近似算法的核心循环并聚焦于如何为你的特定问题生成最强、最有效的割平面。这个过程本身就是对优化理论和工程实践一次极好的锤炼。