论文标题
光谱放松和分支策略，用于全球优化混合二次计划
Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs
论文作者
论文摘要
我们考虑对非convex二次程序和混合二次二次程序的全球优化。我们提出了一个凸二次松弛家族，该家族是通过通过二次矩阵的扰动来凸出非凸二次函数来得出的。我们研究了这些二次放松的理论特性，并表明它们等同于某些特定的半决赛程序。我们还介绍了新型的分支变量选择策略，可以与本文研究的二次松弛一起使用。我们将提出的放松和分支技术整合到全球优化求解器男爵中，并通过对大量问题进行数值实验来测试我们的实现。结果表明，拟议的实施导致男爵的计算时间大大减少，以解决测试问题。
We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. We also introduce novel branching variable selection strategies which can be used in conjunction with the quadratic relaxations investigated in this paper. We integrate the proposed relaxation and branching techniques into the global optimization solver BARON, and test our implementation by conducting numerical experiments on a large collection of problems. Results demonstrate that the proposed implementation leads to very significant reductions in BARON's computational times to solve the test problems.
