A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation
A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation
复制标题
一种新的基于替代方向法和半定松弛的非凸二次规划分支割算法
DOI：
10.1007/s11075-020-01065-7
复制
发表时间：
2021-05
影响因子：
2.1
通讯作者：
Huixian Wu
中科院分区：
文献类型：
--
作者：
Hezhi Luo;Sikai Chen;Huixian Wu
我们考虑具有线性和凸二次约束的非凸二次规划(QP)，它具有广泛的应用，并且已知是NP-难的。在本文中，我们首先证明了交替方向法收敛于基本QP问题的局部解。然后，我们提出了一种新的分支切割算法，通过将交替方向法与半定松弛和析取切割技术相结合，在预先指定的容差范围内找到潜在QP问题的全局最优解。我们证明了算法的全局收敛性质，并估计了算法的复杂性。初步的数值结果表明，对于目标函数中海森矩阵的负特征值个数小于或等于20的中等规模的QP实例，该算法能有效地找到全局最优解。
We consider a non-convex quadratic program (QP) with linear and convex quadratic constraints that arises from a broad range of applications and is known to be NP-hard. In this paper, we first prove that the alternative direction method converges to a local solution of the underlying QP problem. We then propose a new branch-and-cut algorithm that finds a globally optimal solution to the underlying QP problem within a pre-specified?-tolerance by integrating the alternative direction method with semidefinite relaxation and disjunctive cut techniques. We establish the global convergence of the algorithm and estimate its complexity. Preliminary numerical results demonstrate that the proposed algorithm can effectively find a globally optimal solution to medium-scale QP instances in which the number of negative eigenvalues of the Hessian matrix in the objective function is less than or equals 20.
登录
查看更多内容
影响因子：
6.3
作者：
Jieqiu Chen;S. Burer
通讯作者：
Jieqiu Chen;S. Burer
DOI：
10.1007/s101070050003
发表时间：
2000-05
期刊：
Math. Program.
影响因子：
--
作者：
Hoai An Le Thi
通讯作者：
Hoai An Le Thi
影响因子：
2.7
作者：
Shuzhong Zhang
通讯作者：
Shuzhong Zhang
DOI：
10.1016/j.orl.2010.07.008
发表时间：
2010-09
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
R. Cambini;Francesca Salvi
通讯作者：
R. Cambini;Francesca Salvi
影响因子：
2.7
作者：
S. Vavasis
通讯作者：
S. Vavasis