A continuous approch for globally solving linearly constrained quadratic
A continuous approch for globally solving linearly constrained quadratic
复制标题
DOI：
10.1080/02331930108844555
复制
发表时间：
2001
期刊：
影响因子：
2.2
通讯作者：
Hoai An Le Thi;P. D. Tao
中科院分区：
文献类型：
--
作者：
Hoai An Le Thi;P. D. Tao
在一个连续的方法，我们提出了一个有效的方法来全局求解线性约束二次零一规划被认为是一个直流（凸函数的差异）计划。研究了有限收敛的直流优化算法（DCA）与分支定界法的结合。我们在分支过程中使用矩形二等分，而边界过程是通过从当前最佳可行点（上限）应用直流算法，并通过最小化当前细分域上目标函数的严格凸低估（下限）进行的。DCA在包含所考虑问题的可行域的新多面体的顶点集中生成点序列。此外，如果一个整数是整数，那么所有后续的迭代也是整数.我们的组合算法收敛到一个整数近似解，所以经常.最后，我们给出了几个测试问题的计算结果多达1800变量...
In a continuous approach we propose an efficient method for globally solving linearly constrained quadratic zero-one programming considered as a d.c. (difference of onvex functions) program. A combination of the d.c. optimization algorithm (DCA) which has a finite convergence, and the branch-and-bound scheme was studied. We use rectangular bisection in the branching procedure while the bounding one proceeded by applying d.c.algorithms from a current best feasible point (for the upper bound) and by minimizing a well tightened convex underestimation of the objective function on the current subdivided domain (for the lower bound). DCA generates a sequence of points in the vertex set of a new polytope containing the feasible domain of the problem being considered. Moreover if an iterate is integral then all following iterates are integral too.Our combined algorithm converges so quite often to an integer approximate solution.Finally, we present computational results of several test problems with up to 1800 var...