两类全局优化问题的一种新的分支减小定界算法

摘要

分支定界算法是全局优化主要算法之一，被广泛地应用于整数规划和非线性规划等优化模型中，近年来一直是最优化领域的研究热点．在过去的几年里，人们一直在寻找求解效率高，迭代次数少，运行时间短的新方法，以便求解实际生产中大规模优化问题.本文是在已有理论的基础上，针对符号几何规划问题和非线性比式和问题，提出一种新的有效方法-分支减小定界算法，主要内容如下：
　　 第一章，概述全局优化常用的算法，及本文所研究问题的背景与现状，并简单介绍本文所做的工作．
　　 第二章，给出用新的分支减小定界算法求解符号几何规划问题的主要步骤．这一章是利用线性化方法和线性下估计函数，确定原问题的松弛线性规划，然后把可行域逐渐剖分加细，同时相应的构造出使目标函数值单调增加的下界序列和单调减小的上界序列，当上界和下界相等或它们的差值满足误差要求时，得到问题的近似最优解．特别的，在减小部分，两个减小操作能够删掉一大部分不存在最优解的区域．并证明了算法能收敛到原问题的全局最优解，最后的数值结果表明提出的算法是可行和有效的．
　　 第三章，针对非线性比式和问题，首先引进p个变量和p个约束，这比其他方法引进的个数都少，把原问题转化为一个等价的规划问题，再由指数变换及线性下估计函数得到另一个等价规划问题，利用新的分支减小定界算法求解这个等价问题，在求解问题之前，首先调用这个算法求解引进变量的上界和下界，得到的所有引进变量的上下界比其他方法好得多，数值结果也充分表明该方法在迭代次数，运行时间方面较其他方法有明显的改进．