一类单调非凸约束最优规划修正的新型分枝定界算法  

A New Modification Branch-and-bound Algorithm for a Class of Optimization Programs under Monotonic Non-convex Constraint

作　　者：杜廷松[1] 费浦生[2] 蹇继贵[3] 

机构地区：[1]三峡大学理学院,湖北宜昌443002 [2]武汉大学数学与计算科学学院,湖北武汉430072 [3]三峡大学非线性与复杂系统研究所,湖北宜昌443002

出　　处：《应用数学》2008年第4期765-770,共6页Mathematica Applicata

基　　金：国家自然科学基金项目(数学天元基金10726016);湖北省教育厅优秀中青年科技创新团队项目(D200613002;T200809)

摘　　要：本文讨论了一类单调非凸约束最优规划的目标函数和约束集的结构特征性质.阐明了如何将所考虑的问题等价地转化为一个递增函数在另一个递增函数水平集上的极大优化问题.在此基础上提出了一个我们称之为修正的新型分枝定界算法.新算法的修正之处是在计算新的极点时,采用了一个有效的新的区域删除模式以构造越来越小的Polyblock集覆盖EnH且不含y,以排除问题(P)可行域中不存在全局ε-最优解的部分.最后,证明了算法的收敛性.初步的数值实验表明算法是有效可行的,可应用于求解更广的一类非凸最优规划.In this paper, we investigate some basic properties of the objective function and the constraint set of a class of optimization programs with an additional monotonic non-convex constraint. It is introduced how to convert the original probiem into a new optimization problem,i, e. ,maximizing an increasing funtion over the level set of another increasing function. A new modification branch-and-bound algorithm is developed on the basis of devising efficient solution strategies. The major improvement of the proposed algorithm is that it can construct a smaller polyblock by using a new region-deleting principles. The polyblock still covers E ∩ H but excluding y ,and deletes the subregion without containing the ε-optimal solutions of the problem （P）. Finally,the convergence of the algorithm is proofed. Computation results indicate that the algorithm is not only feasible but also effective. It can be used to solve a broad class of non-convex optimization programs.

关 键 词：单调非凸约束 分枝定界算法 外逼近算法 

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