一类带有常系数线性乘积规划问题的分支定界缩减方法

摘要

We propose a new branch and bound reduction algorithm for solving a class of linear multiplicative programming problems with constant coefficients. Firstly, by utilizing the convex envelopes of the products of two variables, the lower and upper bounds for the multiplications in the objective and constraint functions are determined. And we use these bounds to construct the corresponding convex programming relaxation for the original problem. Then, resorting to the hyper-rectangular reduction strategy, a new branch and bound reduction algorithm is designed. It is shown that this new algorithm is globally convergent. Numerical examples are presented to illustrate the effectiveness of the proposed algorithm.%本文给出了一种求解带有常系数线性乘积规划问题的分支定界缩减算法.我们首先利用两个变量乘积的凸包络技术,分别得到目标函数与约束函数中乘积的上界与下界估计,由此构造出原问题的一个松弛凸规划问题.在此基础之上,借助超矩形的缩减技术,提出了确定原问题全局最优值下界的分支定界缩减算法,并从理论上分析了算法的收敛性.最后,利用数值实验验证了算法的有效性与可行性.