技术摘要：非凸 QCQP 的联合范围不等式

问题陈述

本文研究了为非凸二次约束二次规划（QCQP）生成有效割平面（cutting planes）的挑战，这类问题是混合整数非线性规划（MINLP）中的核心类别。虽然标准的松弛方法，如重构线性化技术（RLT）和半正定规划（SDP）松弛（例如 Shor 松弛），可以提供凸近似，但它们通常面临紧致度与稀疏性之间的权衡。具体而言，特征值重构和稠密 SDP 约束通常会破坏原始问题的稀疏性，导致生成的割平面计算成本高昂，难以集成到 MINLP 求解器中。作者寻求一种能够保持底层 QCQP 公式稀疏性，同时利用非凸几何特性的强有效不等式框架。

方法论：投影-提升法（Project-Then-Lift Approach）

作者提出了一种受用于混合整数线性规划（MILP）中混合整数舍入（MIR）不等式启发的“投影-提升”策略。该方法流程如下：

1. 基础不等式与投影：
   从扩展 QCQP 公式（涉及变量 $x$ 和提升矩阵 $X$）的两个基础有效不等式开始，作者定义了一个仿射映射 $A_{JR}$，将这些不等式投影到二维图像空间中。设基础不等式为 $\phi_i + \langle \Theta_i, X \rangle + \theta_i^\top x \geq 0$（其中 $i=1,2$）。投影将可行 $(X, x)$ 对映射到向量 $y = (y_1, y_2)$，其中 $y_i$ 对应第 $i$ 个不等式的左手边。

2. 联合范围分析：
   该方法的核心是对与基础不等式相关的两个二次函数 $f_1(x)$ 和 $f_2(x)$ 的联合范围（joint range）进行分析。可行投影点的集合是该联合范围与由基础不等式定义的单纯形锥 $K_{JR}$ 的交集。

   • 非凸情况： 作者刻画了当联合范围是非凸时其闭凸包。他们证明了在特定条件下（二次部分的线性相关性），联合范围具有显式的非凸形式，例如边界或抛物面碗（parabolic bowl）的外部。
   • 凸情况： 当联合范围是凸的时，他们提供了一个半正定规划（SDP）表示。

3. 凸包刻画与不等式推导：
   作者对投影集的凸包（$H_{JR} = \text{cl}(\text{conv}(F(\mathbb{R}^n) \cap K_{JR}))$）进行了闭式描述。

   • 对于非凸情况，凸包通过将单纯形锥与抛物面碗或其补集进行相交来描述，这通常导致由锥射线退出非凸集的点所定义的“割线”（secant）割（即交集割）。
   • 对于凸情况，凸包通过支撑函数进行描述，从而导致一个受 SDP 约束的分离问题。

4. 提升与稀疏性保持：
   在二维图像空间中导出的有效不等式通过仿射映射的逆映射提升回原始的 $(X, x)$ 空间。至关重要的是，由于投影是基于仅有的两个基础不等式，生成的提升不等式会继承这些基础不等式的稀疏性（支撑集）。这避免了与全量 SDP 松弛相关的稠密性问题。

5. 割线混合联合范围不等式：
   通过扩展 MIR 的概念，作者引入了“割线混合联合范围不等式”。这些不等式涉及从基础不等式中提取“混合”项（分数线性组合或连续变量）以形成一个满足非凸抛物条件的核对（core pair）。这使得该方法能够处理类似于 MIR 处理 MILP 中分数项的更复杂的结构。

核心贡献

• 闭式凸包： 本文提供了一个完整的、闭式的描述，用于刻画两个二次函数的联合范围与单纯形锥交集的凸包。这包括针对各种配置（例如顶点在抛物面碗内部/外部、回归射线）的显式几何描述。
• 新的割平面族： 作者引入了联合范围不等式和割线混合联合范围不等式。这些不等式对于扩展的 QCQP 公式是有效的，并通过在投影的 2D 空间中进行交集割来导出。
• 稀疏性保持： 与标准的基于 SDP 的割不同，所提出的不等式是稀疏的。用于生成每个不等式的支持集严格受限于那两个基础不等式。
• 凸情况下的 SDP 表示： 对于凸联合范围，作者提供了一个半正定表示，为线性化 Shor 的 SDP 松弛提供了一条稀疏路径。
• 算法分类： 提出了一个算法，用于将联合范围分类为凸或非凸，并确定其具体的几何形状（例如抛物边界、实区域或穿孔平面）。

结果

论文报告了通过几何实验对比所提联合范围不等式与标准第一层 RLT 松弛强度的初步结果。

• 指标： 强度通过 RLT 松弛的投影面积与联合范围凸包投影面积之比来衡量。比例越低，表示割平面越强（面积缩减越大）。
• 发现：
  • 在“未裁剪”（unclipped）情况下，即联合范围完全包含在锥内时，割平面没有提供额外的缩减（比例为 1）。
  • 在非平凡的非凸情况下（例如“弦截断碗”和“射线截断碗”），联合范围凸包显著减少了投影面积。不同维度和配置下的面积比值的移动几何平均值约为 0.108 到 0.490 之间。
  • 凸联合范围的情况（Case 7）也展示了实质性的面积缩减（比例在 0.219 到 0.403 之间）。
  • 结果表明，所提方法可以显著收紧通过 RLT 构建的投影松弛。

意义与主张

作者声称这项工作弥合了交集割的几何强度与 MINLP 求解器计算必要性之间的鸿沟。

• 几何与维度的分离： 主要意义在于将困难的几何步骤（处理非凸性）与环境维度解耦。复杂的几何问题是在存在闭式解的低维（2D）空间中解决的，而最终的割平面在原始高维空间中保持稀疏。
• 利用非凸性： 该框架明确地暴露并利用了非凸联合范围，这是依赖于“隐藏凸性”（如 S-lemma）或标准凸松弛的方法无法触及的。
• MIR 的泛化： 该方法将成功的“投影-提升”范式推广到了非线性 QCQP 领域，提供了一种生成强有力割平面的机制，而无需要求稠密的矩阵约束。
• 未来方向： 作者谦虚地指出，在完整的 MINLP 求解器中进行系统性研究超出了目前的研究范围。他们将自动选择有效的基不等式对作为未来的主要研究方向，建议可以借鉴类似于用于 MIR 分离的启发式方法，通过“对齐”二次系数来诱导必要的非凸几何结构。