一类非凸规划的分支定界算法  

A Branch and Bound Algorithm for a Class of Non-convex Programming Problem

作　　者：陈玉花[1] 李晓爱[2] 申培萍[2] 

机构地区：[1]北京联合大学应用科技学院,北京102200 [2]河南师范大学数学与信息科学学院,河南新乡453007

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

基　　金：国家自然科学基金(11171094;11171368)

摘　　要：针对一类非凸规划问题(NP)提出有效的分支定界算法.首先,利用目标函数的特性将其转化为等价的极小化问题(P),通过对其可行域的细分和求解一系列凸规划问题,不断更新(NP)全局最优值的上下界.为提高计算效率,一个问题的最优解作为下一个问题的初始解,并提出了新的删除技术.理论上证明该算法是收敛的,数值试验结果表明算法是有效可行的.An efficient branch and bound algorithm is proposed for a class of non-convex programming problem （NP）. Firstly, an equivalent minimizing problem （P） is derived by exploiting the characteristics of the objective function of the problem. Through the successive refinement of the feasible region and the solution of a series of the convex programming problems, the upper and lower bounds of global optimal value for （NP） are continuously updated. In order to improve the efficiency of the algorithm, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem. Besides, a new deleting technique is presented. The algorithm is proved to be convergent, and numerical examples show the efficiency and feasibility of the algorithm.

关 键 词：非凸规划 分支定界 全局优化 

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