New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
复制标题
基于替代方向法和凸松弛的具有少量负特征值的二次规划新全局算法
DOI：
10.1007/s12532-018-0142-9
复制
发表时间：
2018-08
影响因子：
6.3
通讯作者：
Jiming Peng
中科院分区：
文献类型：
--
作者：
Hezhi Luo;Xiaodi Bai;Gino Lim;Jiming Peng
我们考虑一个二次规划与几个负特征值（QP-r-NE）的线性和凸二次约束，涵盖了许多应用程序，是NP-困难的，即使有一个负特征值（QP 1 NE）。在本文中，我们首先介绍了一个新的全局算法（ADMBB），它集成了几个简单的优化技术，如交替方向法，分支定界，找到一个全局最优解的基础QP在一个预先指定的公差。我们建立的ADMBB算法的收敛性和估计其复杂性。其次，我们开发了一个全局搜索算法（GSA）的QP 1 NE，可以找到一个最佳的解决方案QP 1 NE的公差和估计的最坏情况下的复杂性界。初步的数值结果表明，当r ≤ 10时，ADMBB算法能有效地找到大规模QP-r-NE问题的全局最优解，并且GSA算法在大多数QP 1 NE问题上的性能优于ADMBB算法.作为本次提交的一部分进行评审的软件被赋予DOI（数字对象标识符）https://doi.org/10.5281/zenodo.1344739。
We consider a quadratic program with a few negative eigenvalues (QP-r-NE) subject to linear and convex quadratic constraints that covers many applications and is known to be NP-hard even with one negative eigenvalue (QP1NE). In this paper, we first introduce a new global algorithm (ADMBB), which integrates several simple optimization techniques such as alternative direction method, and branch-and-bound, to find a globally optimal solution to the underlying QP within a pre-specified -tolerance. We establish the convergence of the ADMBB algorithm and estimate its complexity. Second, we develop a global search algorithm (GSA) for QP1NE that can locate an optimal solution to QP1NE within -tolerance and estimate the worst-case complexity bound of the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to large-scale QP-r-NE instances when r ≤ 10, and the GSA outperforms the ADMBB for most of the tested QP1NE instances. The software reviewed as part of this submission was given the DOI (digital object identifier) https://doi.org/10.5281/zenodo.1344739.
登录
查看更多内容
影响因子：
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