一类DC规划问题的分支定界算法  

A Branch and Bound Algorithm for a Class of DC Programming Problems

作　　者：申培萍[1] 王凯民 朱泽怡 SHEN Peiping;WANG Kaimin;ZHU Zeyi(College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China)

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

出　　处：《应用数学》2020年第2期393-398,共6页Mathematica Applicata

基　　金：国家自然科学基金(11671122,11871196);河南省高等学校重点科研项目(17A110006)。

摘　　要：本文针对一类带有箱子和线性不等式约束的特殊DC规划问题,提出了一种分支定界算法.首先将原问题转化为其等价问题,然后利用目标函数的特点将等价问题松弛为凸规划问题,通过求解一系列凸规划问题得到原问题的最优解,最后给出算法的收敛性证明.数值实验表明该算法是可行有效的.In this paper,we propose a branch and bound algorithm for a class of DC programming problems with box and linear inequality constraints.Firstly,the original problem is transformed into its equivalent problem,and then the matrix decomposition technique is used to relax the equivalent problem into a convex programming problem.The optimal solution of the original problem is obtained by solving a series of convex programming problems.Finally,the convergence proof of the algorithm is given.Numerical results show the feasibility and efficiency of the proposed algorithm.

关 键 词：DC规划 凸松弛 分支定界 

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