论文部分内容阅读
分支定界算法足一种较为常用的全局优化算法,近年来一直是最优化领域的研究热点.但这类算法迭代次数多、运行时间长、求解效率低,很难适合大规模的优化问题.为了克服这些不足,本文在已有的理论基础上,针对非凸二次约束二次规划问题和带有线性多乘积约束的线性规划问题提出改进的分支定界算法.主要内容如下:
首先,简单介绍几种常见的全局优化算法,及本文所研究问题的研究现状、主要结论、一些基本概念和性质.
接着,在第二章和第三章分别给出求解非凸二次约束二次规划问题的两种全局优化算法.在这两章中均足利用二次函数的线性下界函数确定原问题的松弛线性规划,然后通过对可行域所在盒子的不断细分以及一系列松弛线性规划问题的求解,最终得到原问题的近似最优解.并且为了改进算法的收敛性,分别给出区域删除准则和区域收缩策略以删除所考察的子盒子区域中不包含全局最优解的部分.数值算例表明改进后的算法在迭代次数、运行时间方面较一般的分支定界算法都有明显改进.
最后,针对带有线性多乘积约束的线性规划问题给出一全局优化算法.首先利用等价问题及线性化技术构造松弛线性规划问题,然后基于松弛线性规划问题和原问题最优值的上界提出区域删除准则以删除可行域中不包含全局最优解的部分.数值算例表明利用此准则的新算法比一般的分支定界算法在迭代次数、运行时间方面都有明显改进.