二次比式和问题的加速分枝定界算法  

Accelerating Branch and Bound Algorithm for Sum of Quadratic Ratios Problem

作　　者：李晓爱[1] 刘金伟[2] 申培萍[1] 

机构地区：[1]河南师范大学数学与信息科学学院,新乡453007 [2]新乡学院数学系,新乡453003

出　　处：《应用数学学报》2011年第4期712-722,共11页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(10671057)资助项目

摘　　要：本文给出非凸二次约束上二次比式和问题(P)的一个新的加速分枝定界算法.该算法利用线性化技术建立了问题(P)的松弛线性规划问题(RLP),通过对其可行域的细分和求解一系列线性规划问题,不断更新(P)的全局最优值的上下界.为了提高收敛速度,从最优性和可行性两方面,提出了新的删除技术,理论上证明该算法是收敛的,数值试验表明了算法的有效性和可行性.The paper presents a new accelerating branch and bound algorithm for solving sum of quadratic ratios problem with nonconvex quadratic constraints（P）.The algorithm establishes the linear relaxation programming problem（RLP） of problem（P） utilizing the linearizing technique.Through the successive refinement of the feasible region and the solution of a series of the linear programming problems,the upper and lower bounds of global optimal value are continuously updated.In order to accelerate convergence,a new deleting technique is given according to the optimality and feasibility.The proposed algorithm is proved to be convergent,and the numerical experiments show the efficiency and feasibility.

关 键 词：二次比式和 加速分枝定界 全局优化 删除准则 

分 类 号：O221.2[理学—运筹学与控制论]