Enhancing Semidefinite Relaxation for Quadratically Constrained Quadratic Programming via Penalty Methods
Enhancing Semidefinite Relaxation for Quadratically Constrained Quadratic Programming via Penalty Methods
复制标题
通过惩罚方法增强二次约束二次规划的半定松弛
DOI：
10.1007/s10957-018-1416-0
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Jiming Peng
中科院分区：
文献类型：
--
作者：
Hezhi Luo;Xiaodi Bai;Jiming Peng
二次约束二次规划有着广泛的应用，被认为是最难的优化问题之一。近年来，半定松弛已成为二次约束规划的一种流行方法，并在文献中报道了许多结果。在本文中，我们首先讨论了如何评估二次约束规划与其半定松弛之间的差距。在估计间隙的基础上，我们讨论了如何基于半定松弛构造二次约束规划的精确惩罚函数。然后，我们基于二次约束线性规划的半定松弛引入了一种特殊的惩罚方法，从而得到所谓的条件拟凸松弛。我们证明了条件拟凸松弛能提供比标准半定松弛更严格的界。通过探索条件拟凸松弛模型的各种性质，提出了求解条件拟凸松弛模型的两种有效方法：迭代法和二分法。报道了有希望的数值结果。
Quadratically constrained quadratic programming arises from a broad range of applications and is known to be among the hardest optimization problems. In recent years, semidefinite relaxation has become a popular approach for quadratically constrained quadratic programming, and many results have been reported in the literature. In this paper, we first discuss how to assess the gap between quadratically constrained quadratic programming and its semidefinite relaxation. Based on the estimated gap, we discuss how to construct an exact penalty function for quadratically constrained quadratic programming based on its semidefinite relaxation. We then introduce a special penalty method for quadratically constrained linear programming based on its semidefinite relaxation, resulting in the so-called conditionally quasi-convex relaxation. We show that the conditionally quasi-convex relaxation can provide tighter bounds than the standard semidefinite relaxation. By exploring various properties of the conditionally quasi-convex relaxation model, we develop two effective procedures, an iterative procedure and a bisection procedure, to solve the constructed conditionally quasi-convex relaxation. Promising numerical results are reported.
登录
查看更多内容
影响因子：
5.4
作者：
J. Rhys
通讯作者：
J. Rhys
影响因子：
2.7
作者：
D. Vandenbussche;G. Nemhauser
通讯作者：
D. Vandenbussche;G. Nemhauser
影响因子：
2.7
作者：
Shuzhong Zhang
通讯作者：
Shuzhong Zhang
影响因子：
2.7
作者：
Anureet Saxena;Pierre Bonami;Jon Lee
通讯作者：
Anureet Saxena;Pierre Bonami;Jon Lee
DOI：
10.1007/978-1-4615-2025-2
发表时间：
1995
期刊：
--
影响因子：
--
作者：
R. Horst;P. Pardalos;H. Romeijn
通讯作者：
R. Horst;P. Pardalos;H. Romeijn