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

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

本文提出一种基于输出空间分支定界算法(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.