靳 利

（河南机电高等专科学校基础部，河南新乡 453000）

1 引言

考虑下面凸约束域上的线性比式和问题:

凸约束域上的线性比式和问题（P）在经济、财政等领域有着广泛的应用。此外凸约束域上的凹比凸比式和问题也可转化为问题（P）。［1］虽然问题（P）的目标函数中每一项都是伪单调的，但它们的和既不是拟凸又不是拟凹的，所以问题（P）可能存在多个不是全局最优的局部解，使得求解起来十分困难.目前，线性约束的线性比式和问题（P）已有一些有效算法，［2，3］而问题（P）的算法较少。最近，Benson［4］通过凹极小化给出问题（P）一分支定界算法。本文首先把问题（P）转化为等价问题（Q），然后利用界的放缩技术建立了问题（Q）的松弛凸规划（RCP），通过对（RCP）可行域的细分以及一系列（RCP）的求解过程，从理论上证明了算法的收敛性。最后，数值实验表明该方法是有效可行的。

2 等价问题和凸化技术

显然，若问题RCP（Hk）和Q（Hk）的最优值分别为 v（Hk）和 μ（Hk），则 v（Hk）≤μ（Hk）。

3 分支定界算法及收敛性

下面给出求解问题（P）的分支定界算法，通过求解一系列松弛凸规划RCP，逐步改进问题（Q）最优值的上界和下界，最终确定问题（Q）的全局最优解。假定在算法的第k次迭代中，Lk表示可能存在全局最优解的子长方体构成的集合，对于任意∈Lk，RCP（）的最优值记为 v（），令 vk=min{v（）:∈Lk}，则vk是问题（Q）最优值当前的一个下界。若RCP（）的最优解是问题（P）的可行解，则更新问题（P）最优值的上界μk，选定一子长方体Hk使得v（Hk）=vk，然后将Hk沿最长边平分成两部分，对每一部分求其相应的解，重复这一过程直到满足收敛条件为止。……