求解一类广义线性乘积和规划问题的输出空间分支定界算法  

An Output-space Branch and Bound Algorithm for Solving a Sum of Generalized Linear Multiplicative Programming

作　　者：刘霞 高岳林 张博[1,3] 黄小利 LIU Xia;GAO Yuelin;ZHANG Bo;HUANG Xiaoli(School of Mathematics and Statistics,Ningxia University,Yinchuan 750021,China;Ningxia Key Laboratory of Intelligent Information and Data Processing,North Minzu University,Yinchuan 750021,China;Ningxia Scienti c Computing and Intelligent Information Processing Collaborative Innovation Center,North Minzu University,Yinchuan 750021,China)

机构地区：[1]宁夏大学数学统计学院,宁夏银川750021 [2]宁夏科学计算与智能信息处理协同创新中心北方民族大学,宁夏银川750021 [3]宁夏智能信息与大数据处理重点实验室北方民族大学,宁夏银川750021

出　　处：《应用数学》2022年第3期680-694,共15页Mathematica Applicata

基　　金：国家自然科学基金项目(11961001);宁夏高等教育一流学科建设基金(NXYLXK2017B09);北方民族大学重大专项(ZDZX201901)。

摘　　要：本文提出一种基于输出空间分支定界算法(OSBBA)求解一类广义线性乘积和规划问题(GLMP)的ε全局最优解.通过对问题(GLMP)的非线性等价问题(EGGP)的约束条件采用两种不同的松弛方法,得到相应的线性松弛问题(GLRP).再利用算法(OSBBA)在输出空间不断地分支来迭代求解问题(GLRP),直至逼近问题(EGGP)的ε全局最优解.同时,算法(OSBBA)的收敛性证明和计算复杂度分析表明该算法在理论上是有限迭代终止的.最后,数值实验验证并分析了算法的有效可行性.An output-space branch and bound algorithm(OSBBA)is proposed to deal with the sum of generalized linear multiplicative programming(GLMP)with generalized linear multiplicative constraints.Firstly,the corresponding linear relaxation problem(GLRP)was obtained by using different linear relaxation methods for constraints of the equivalence problem(EGGP).Then,based on the output space,the algorithm(OSBBA)iteratively solves the problem(GLRP)until theεglobal optimal solution of the problem(EGGP)is approached.Meanwhile,the convergence proof and computational complexity analysis show that algorithm(OSBBA)can be terminated in finite iterations with a given precision.Finally,the proposed algorithm is verified validity and feasibility through numerical experiments.

关 键 词：广义线性乘积规划 全局优化 分支定界 输出空间 线性松弛 

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