Relaxing Nonconvex Quadratic Functions by Multiple Adaptive Diagonal Perturbations
Relaxing Nonconvex Quadratic Functions by Multiple Adaptive Diagonal Perturbations
复制标题
DOI：
10.1137/140960657
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
Hongbo Dong
中科院分区：
文献类型：
--
作者：
Hongbo Dong
当前全局解决混合整数（非凸）二次约束规划问题（MIQCP）的瓶颈仍然是构造强大但计算成本低的凸松弛，特别是当存在密集二次函数时。我们提出了一种基于多重对角扰动的切割面方法，用于导出具有可分离约束的非凸二次问题的凸二次松弛。我们的松弛也可以实现为 Buchheim 和 Wiegele 提出的半定松弛的半无限凸公式的外部近似。相应的分离问题是一个高度结构化的半定规划（SDP），具有凸但非光滑的目标函数。我们建议使用专门的障碍坐标最小化算法来解决这个分离问题。对随机生成实例的数值实验表明我们的方法非常有前途。我们还讨论了如何将我们的方法应用于 MIQCP 的更一般情况。
The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained programming problems (MIQCPs) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We propose a cutting-surface method based on multiple diagonal perturbations to derive convex quadratic relaxations for nonconvex quadratic problems with separable constraints. Our relaxations can also be realized as outer-approximations of a semi-infinite convex formulation of a semidefinite relaxation proposed by Buchheim and Wiegele. The corresponding separation problem is a highly structured semidefinite program (SDP) with a convex but nonsmooth objective function. We propose solving this separation problem with a specialized barrier coordinate minimization algorithm. Numerical experiments on randomly generated instances show that our approach is very promising. We also discuss how to apply our method to more general cases of MIQCPs.