求非凸二次规划全局最优解的分解线性化方法  

A Decomposition and Linearization Method for Globally Solving Nonconvex Quadratic Programming

作　　者：申培萍[1] 裴永刚[1] 顾敏娜[2] 

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

出　　处：《河南师范大学学报（自然科学版）》2008年第3期128-130,共3页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金(10671057);河南省高校科技创新人才计划;河南省教育厅自然科学基金

摘　　要：对非凸二次规划(QP)问题提出新的确定性全局优化算法,该算法先对目标函数进行分解得到可分的等价问题,再根据相应函数的线性下估计建立原非凸二次规划的线性松弛规划,同时在分枝定界方法中使用区域删减准则来加速算法的收敛性.理论分析和数值计算表明提出的算法是收敛且有效的.A new deterministic approach is presented for globally solving nonconvex quadratic programming （QP）. This algorithm first decomposes the objective function of （QP） to obtain a seperable equivalent problem, then a relaxation linear programming of QP is given according to a linear under-estimator of the corresponding objective function. In addition,a region deleting or reducing rule is used to accelerate the convergence of the proposed branch-and-bound algorithm. The theoretical analysis and numerical computation show that the proposed method is convergent and efficient.

关 键 词：非凸二次规划 分解线性化 区域删减 分枝定界 

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