Globally solving nonconvex quadratic programming problems via completely positive programming
Globally solving nonconvex quadratic programming problems via completely positive programming
复制标题
DOI：
10.1007/s12532-011-0033-9
复制
发表时间：
2011-11
影响因子：
6.3
通讯作者：
Jieqiu Chen;S. Burer
中科院分区：
文献类型：
--
作者：
Jieqiu Chen;S. Burer
非凸二次规划（QP）是在线性约束下优化一般二次函数的NP-难问题。本文提出了一种新的全局优化算法，该算法结合了文献中的两个思想--基于一阶KKT条件的有限分支和完全正（或余正）规划的多面体半定松弛.通过一系列的计算实验比较新算法与现有的代码在一组不同的测试实例，我们证明了新算法是一个有吸引力的方法，全局求解非凸QP。
Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.