首页 | 本学科首页   官方微博 | 高级检索  
     检索      

解带有二次约束非凸二次规划问题的一个分枝缩减方法
引用本文:高岳林,尚有林,张连生.解带有二次约束非凸二次规划问题的一个分枝缩减方法[J].运筹学学报,2005,9(2):9-20.
作者姓名:高岳林  尚有林  张连生
作者单位:1. 上海大学数学系,上海,200444;西北第二民族学院信息与计算科学系,宁夏,银川,750021
2. 上海大学数学系,上海,200444;河南科技大学数理系,河南,洛阳,471003
3. 上海大学数学系,上海,200444
基金项目:The work is supported by the Foundation of Natural Science China (grants 10271073) the Natural Science Foundation of National Committee in China in 2005.
摘    要:在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.

关 键 词:运筹学  非凸二次规划  二次约束  全局优化  分枝缩减方法  外逼近方法  二级剖分技术

A Branch and Reduce Approach for Solving Nonconvex Quadratic Programming Problems with Quadratic Constraints
Gao Yuelin,Shang Youlin,ZHANG Liansheng.A Branch and Reduce Approach for Solving Nonconvex Quadratic Programming Problems with Quadratic Constraints[J].OR Transactions,2005,9(2):9-20.
Authors:Gao Yuelin  Shang Youlin  ZHANG Liansheng
Abstract:The paper presents a branch and reduce approach for solving nonconvex quadratic programming problems with quadratic constraints, which organically combines outer approximation method with branch and bound scheme. In the proposed algorithm, we propose a new linear programming relaxation to determine a low bound of the global optimal value for the original problem over each rectangle, and give a rectangle two-level partition method to deeply partition for each rectangle, and use reducing and deleting techniques on a rectangle to accelerate the convergence of the proposed algorithm. Under the assumption that the feasible point of the original problem is known, the proposed algorithm guarantees an e-approximate global optimal solution in finite number of iterations.We show with a numerical example that the proposed algorithm is efficient.
Keywords:Operations research  nonconvex quadratic programming  quadratic constraints  global optimization  branch and reduce method  outer approximation method  two-level partition technique
本文献已被 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号