2025-11-13T13:58:10.839999

Proximity results in convex mixed-integer programming

Kocuk, Ramirez
We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of the continuous relaxation when the recession cone is full-dimensional. If the recession cone is not full-dimensional we give sufficient conditions to obtain a finite integrality gap. We then specialize our analysis to second-order conic IPs. In the case the feasible region is defined by a single Lorentz cone constraint, we give upper bounds on proximity and integrality gap in terms of the data of the problem (the objective function vector, the matrix defining the conic constraint, the right-hand side, and the covering radius of a related lattice). We also give conditions for these bounds to be independent of the right-hand side, akin to the linear IP case. Finally, in the case the feasible region is defined by multiple Lorentz cone constraints, we show that, in general, we cannot give bounds that are independent of the corresponding right-hand side. Although our results are presented for the integer lattice $\mathbb{Z}^n$, the bounds can be easily adapted to work for any general lattice, including the usual mixed-integer lattice $\mathbb{Z}^{n_1}\times\mathbb{R}^{n_2}$, by considering the appropriate covering radius when needed.
academic

Proximity results in convex mixed-integer programming

基本信息

  • 论文ID: 2501.00638
  • 标题: Proximity results in convex mixed-integer programming
  • 作者: Burak Kocuk (Sabancı University), Diego A. Morán R. (Rensselaer Polytechnic Institute)
  • 分类: math.OC (Optimization and Control)
  • 发表时间: 2024年12月31日
  • 论文链接: https://arxiv.org/abs/2501.00638

摘要

本文研究凸整数规划(IP)与其连续松弛之间的接近性(proximity)和整数间隙(integrality gap)问题。作者证明了当连续松弛可行域的recession cone是满维的时，这些值可以用recession cone的参数进行上界估计。对于非满维recession cone的情况，给出了获得有限整数间隙的充分条件。文章特别分析了二阶锥整数规划，在单一Lorentz锥约束的情况下，用问题数据给出了接近性和整数间隙的上界，并提供了这些界与右端项无关的条件。

研究背景与动机

问题定义与重要性

  1. 核心问题：研究凸整数规划min⁡{αTx:x∈S∩Zn}\min\{\alpha^T x : x \in S \cap \mathbb{Z}^n\}与其连续松弛min⁡{αTx:x∈S}\min\{\alpha^T x : x \in S\}之间的距离关系，其中S⊆RnS \subseteq \mathbb{R}^n是凸集。
  2. 两个关键概念：
    • 接近性(Proximity)：连续松弛最优解到最近整数可行解的距离
    • 整数间隙(Integrality gap)：整数规划最优值与连续松弛最优值的差
  3. 研究意义：
    • 量化松弛质量，为算法设计提供理论基础
    • 在凸二次博弈等应用中具有重要价值
    • 扩展线性整数规划的经典结果到非线性情况

现有研究局限性

  1. 线性情况已有完备结果：Cook等人证明了线性IP的接近性界与右端项无关
  2. 非线性情况研究有限：仅限于可分凸函数或可分二次函数的特殊情况
  3. 缺乏一般性框架：缺少处理一般凸约束集合的系统性方法

核心贡献

  1. 一般凸IP的接近性结果：当recession cone满维时，给出了与最优解无关的接近性和整数间隙上界
  2. 二阶锥IP的专门分析：为简单二阶锥集合提供了结构性结果和接近性界
  3. 右端项依赖性分析：证明了多Lorentz锥约束情况下，界一般不能与右端项无关
  4. 混合整数格推广：结果可扩展到一般格Zn1×Rn2\mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}
  5. 反例构造：通过具体例子说明非线性情况的复杂性

方法详解

理论框架

1. 一般凸集的接近性分析

定理2（满维recession cone情况）： 设SS为凸集，其recession cone K:=rec.cone(S)K := \text{rec.cone}(S)是正则的。对x^∈Sx̂ \in S，有：

Proxx^(S):=min⁡x∈S∩Zn∥x−x^∥2≤n2(1ΨK,∥⋅∥2+1)\text{Prox}_{x̂}(S) := \min_{x \in S \cap \mathbb{Z}^n} \|x - x̂\|_2 \leq \frac{\sqrt{n}}{2}\left(\frac{1}{\Psi_{K,\|\cdot\|_2}} + 1\right)

其中ΨK,∥⋅∥\Psi_{K,\|\cdot\|}是锥KK的关键参数：

ΨK,∥⋅∥:=max⁡d∈K{min⁡f∈K∗{fTd:∥f∥∗=1}:∥d∥=1}\Psi_{K,\|\cdot\|} := \max_{d \in K} \left\{\min_{f \in K^*} \{f^T d : \|f\|_* = 1\} : \|d\| = 1\right\}

2. 混合整数格的覆盖半径

定义4：满维混合整数格L(E,F)={Ez+Fy:z∈Zn1,y∈Rn2}L(E,F) = \{Ez + Fy : z \in \mathbb{Z}^{n_1}, y \in \mathbb{R}^{n_2}\}的覆盖半径为：

μ(E,F)=max⁡x{min⁡x′{∥x−x′∥2:x′∈L(E,F)}:x∈Rn}\mu(E,F) = \max_x \left\{\min_{x'} \{\|x - x'\|_2 : x' \in L(E,F)\} : x \in \mathbb{R}^n\right\}

关键性质（事实1）：对于正交表示，μ(E,F)=μ(E)\mu(E,F) = \mu(E)，即覆盖半径仅依赖于整数分量。

二阶锥规划的专门方法

1. 二次集合的结构分析

对于二次集合Q={x∈Rn:xTMx−2βTx+γ≤0}Q = \{x \in \mathbb{R}^n : x^T M x - 2\beta^T x + \gamma \leq 0\}，根据矩阵MM的特征值分类：

  • 椭球：M≻0M \succ 0
  • 抛物面：M⪰0M \succeq 0，λn=0\lambda_n = 0
  • 双曲面/平移锥：MM有负特征值

2. 两种分析方法

方法1：接近性驱动

  • 给定边界点x^x̂，寻找包含整数点的足够大椭球
  • 利用内逼近技术和覆盖半径理论

方法2：整数间隙驱动

  • 通过水平集分析Sδ={x∈S:xn=δ}S_\delta = \{x \in S : x_n = \delta\}
  • 寻找半径足够大的椭球截面

技术创新点

  1. 锥参数ΨK\Psi_K的计算：对Lorentz锥，证明了ΨLn,∥⋅∥2=1\Psi_{L^n,\|\cdot\|_2} = 1
  2. 大球包含性质：证明了无界二次集合包含任意大的满维球
  3. 椭球内逼近：构造了二次集合的椭球内逼近，用于接近性分析

实验设置

理论验证例子

例子5（抛物面情况）

考虑二阶锥IP： inf⁡x∈Z2{α1x1+α2x2:∥[x1−b112x2−b2]∥2≤12x2−d}\inf_{x \in \mathbb{Z}^2} \left\{\alpha_1 x_1 + \alpha_2 x_2 : \left\|\begin{bmatrix} x_1 - b_1 \\ \frac{1}{2}x_2 - b_2 \end{bmatrix}\right\|_2 \leq \frac{1}{2}x_2 - d\right\}

通过参数选择α=[1,1]T\alpha = [1,1]^T, b=[4N+12,4N]Tb = [4N+\frac{1}{2}, 4N]^T, d=4N−14Nd = 4N - \frac{1}{4N}，得到整数间隙： IG(N)=N+516N−12IG(N) = N + \frac{5}{16N} - \frac{1}{2}

例子6（椭球与半空间交）

inf⁡x∈Z2{x2:x12+x22≤(N+1)2,x1≥12}\inf_{x \in \mathbb{Z}^2} \{x_2 : x_1^2 + x_2^2 \leq (N+1)^2, x_1 \geq \frac{1}{2}\}

整数间隙为IG(N)=N+34IG(N) = \sqrt{N + \frac{3}{4}}，显示与右端项的依赖关系。

实验结果

主要理论结果

1. 椭球情况（命题6）

对椭球S={x:∥Qx−p∥2≤r}S = \{x : \|Qx - p\|_2 \leq r\}： Proxx^(S)≤2∥Q(QTQ)−1∥2μ(Q)\text{Prox}_{x̂}(S) \leq 2\|Q(Q^TQ)^{-1}\|_2 \mu(Q)IG(S)≤2∥Q(QTQ)−1α∥2μ(Q)IG(S) \leq 2\|Q(Q^TQ)^{-1}\alpha\|_2 \mu(Q)

2. 抛物面情况（命题8）

Proxx^(S)≤n2+Γx^(M,β,γ,n2)\text{Prox}_{x̂}(S) \leq \frac{\sqrt{n}}{2} + \Gamma_{x̂}\left(M, \beta, \gamma, \frac{\sqrt{n}}{2}\right)

其中Γ\Gamma通过半定规划求解。

3. 整数间隙驱动方法的界

椭球（命题13）：

  • 情况1：IG(S)≤q12−4q2q0−q2≤2μ(Qˉ)2−q2+14IG(S) \leq \sqrt{\frac{q_1^2 - 4q_2q_0}{-q_2}} \leq 2\sqrt{\frac{\mu(\bar{Q})^2}{-q_2} + \frac{1}{4}}
  • 情况2：IG(S)≤μ(Qˉ)−q2+1IG(S) \leq \frac{\mu(\bar{Q})}{\sqrt{-q_2}} + 1

抛物面（命题14）： IG(S)≤μ(Qˉ)2q1+1IG(S) \leq \frac{\mu(\bar{Q})^2}{q_1} + 1

界的比较与紧性

例子8-9验证了不同方法得到的界：

  • 右端项相关界：精确匹配实际整数间隙
  • 右端项无关界：渐近匹配，提供了实用的上界估计

相关工作

线性整数规划

  • Cook等人(1986)：线性IP的接近性界与右端项无关
  • 最近进展：Paat等人、Eisenbrand等人的改进结果

非线性情况

  • 有限研究：主要限于可分函数情况
  • 缺口：缺少一般凸约束的系统性分析

锥规划理论

  • 利用了锥对偶理论和二阶锥的几何性质
  • 扩展了混合整数格的覆盖半径理论

结论与讨论

主要结论

  1. 满维recession cone：可以得到与问题数据无关的接近性界
  2. 简单二阶锥集合：在某些条件下可以得到与右端项无关的界
  3. 多锥约束：一般情况下界必须依赖于右端项
  4. 方法论：提供了两种互补的分析方法

局限性

  1. 计算复杂性：某些界的计算需要解半定规划
  2. 紧性：部分界可能不够紧，存在改进空间
  3. 适用范围：主要针对二阶锥约束，其他锥类型需要进一步研究
  4. 实际应用：理论结果到实际算法的转化需要进一步工作

未来方向

  1. 其他锥类型：扩展到半定锥、指数锥等
  2. 算法设计：基于接近性结果设计高效算法
  3. 界的改进：寻找更紧的界，特别是常数因子的改进
  4. 计算方法：开发高效计算覆盖半径和锥参数的方法

深度评价

优点

  1. 理论贡献显著：首次系统性地分析了凸整数规划的接近性问题
  2. 方法创新：提出了两种互补的分析框架
  3. 结果完备：涵盖了多种重要的几何对象（椭球、抛物面、双曲面）
  4. 技术深度：巧妙结合了凸分析、格理论和锥优化
  5. 反例构造：通过具体例子清晰说明了非线性情况的本质困难

不足

  1. 计算可行性：部分结果需要解半定规划，计算成本较高
  2. 界的紧性：某些情况下界可能过于保守
  3. 实用性：理论结果与实际算法设计的距离较大
  4. 覆盖范围：主要关注二阶锥，其他重要锥类型覆盖不足

影响力

  1. 理论影响：为凸整数规划理论奠定了重要基础
  2. 方法论价值：分析框架可推广到其他问题
  3. 实用潜力：为算法设计提供了理论指导
  4. 学科交叉：连接了优化理论、几何学和数论

适用场景

  1. 算法分析：评估启发式算法的性能界
  2. 问题建模：指导凸整数规划的建模选择
  3. 理论研究：为进一步的理论发展提供基础
  4. 应用领域：库存管理、电力系统、工程设计等具体应用

参考文献

论文引用了29篇重要文献，主要包括：

  1. Cook, W. et al. (1986) - 线性IP接近性的经典结果
  2. Belotti, P. et al. (2013, 2017) - 二次曲面的特征化理论
  3. Ben-Tal, A. & Nemirovski, A. (2001) - 现代凸优化理论
  4. Bertsimas, D. & Weismantel, R. (2005) - 整数优化基础理论
  5. Paat, J. et al. (2020) - 混合整数规划的最新进展

这篇论文在凸整数规划的接近性分析方面做出了重要的理论贡献，为这一重要问题提供了系统性的分析框架，具有很高的学术价值和潜在的应用前景。