导　　师： 张连生

学科专业： G0105

授予学位： 博士

作　　者： ;

机构地区： 上海大学

摘　　要： 全局优化问题广泛见于工程、国防、经济等诸多重要领域，是数学规划理论的一个重要研究领域。本文首先讨论一类特殊结构的全局优化问题：二次规划的全局优化问题。我们给出了0-1二次规划的全局最优性条件，并讨论了其相应的算法。然后，对于一般结构的全局优化问题，我们给出了一个新的无参数的填充函数方法。 本论文的第一章介绍全局优化理论的一些研究成果。第二章讨论无约束0-1二次规划的全局最优性条件。在第二节得到一个充分条件和一个必要条件的基础上，希望能够得到一些充要条件。为此，首先在第三节中给出在线性约束条件下，(-X)成为一个凸的二次函数的全局极大点的充分必要条件。从这个结论出发，在第四节，我们得到了无约束0-1二次问题全局最优的充分必要条件及其等价形式。在第五节，将注意力放在全局最优的必要条件上。得到的必要条件都不含对偶变量，仅用到原问题的数据。这样，这些条件在实际中都是可以被检验的。进一步，为了使必要条件在实际中易被检验、易操作，本文降低了必要条件中的维数，在比原问题维数更低的空间中，给出一些简洁的必要条件，以达到方便检验的目的。 在第三章，进一步研究有约束的0-1二次规划的全局最优条件。对于带有线性不等式约束的0-1二次问题，在第一节中得到了它全局最优的充分条件和必要条件。必要条件也不含对偶变量。当系数矩阵正定时，建立了原0-1问题的解与松弛问题的解之间的联系。对于带有线性等式约束的0-1二次问题，本文在第二节证明了一个带有线性等式约束的0-1二次规划问题，它的全局最优解集和其相应的罚问题的全局最优解集是相等的。这样，带有线性等式约束的0-1二次问题的解，可以通过无约束0-1二次规划问题的解得到。第三章的另一个内容是讨论0-1二次规划问题的实际应用。将得到的一些结论运用于极大团问题和二次分派问题，得出了一些相关的结论。 将全局最优条件发展成为可实现的算法，是全局优化研究中的重要的工作。本文的第四章讨论无约束0-1二次规划问题的算法。首先将原0-1问题化为一个等价的半正定的0-1二次问题。在得到这个半正定二次问题的松弛解X之后，取与X“最接近的”0-1解Y，在一定的条件之下，Y就是原0-1问题的全局最优解。由于松弛后的问题是凸的二次规划问题，可以在多项式时间内求解，所以，本文的算法是可实现的。为了确定Y是否是原问题的最优解，设计了三种算法。在研究了第二章所给出的一些充分条件之间的关系之后，在第四章第四节，进一步讨论了这种方法能够成功的一些条件。 对于一般结构的全局优化问题，全局优化的算法研究始终是人们关注的问题。在第五章，分别对整变量的和连续变量的全局优化问题，讨论求解它们的无参数的填充函数方法。 目前已有的一些填充函数一般带有一个或两个参数。在实际的计算过程中，往往要花费很多的时间和内存来确定适当的参数值。另外，用填充函数方法解决整变量的全局优化问题，这也是一个重要的研究方向。基于此，在第五章第二节首先针对非线性规划中整变量的全局优化问题，给出一个无参数的填充函数方法。按照填充函数方法的基本思想，给出了修正的填充函数的定义。在定义中，强调它能帮助作者找到比当前局部极小值具有更小目标函数值的点。理论分析和数值计算的结果都表明，本文所构造的无参数的填充函数，可以有效地使目标函数F(X)离开当前的局部极小点，并跳过很多局部极小点，最终找到全局极小点。而且，无论是目标函数还是填充函数，它们需要赋值的点在所有的可行点中占的比例很小。对于连续变量的全局优化问题，在第五章第三节同样给出了其修正的填充函数定义。并构造了满足这个定义的填充函数。随后，讨论了它的一些理论性质并进行了数值计算。由于无需调节参数，这个新的填充函数是有效的并且是简便的。

关 键 词： 二次规划 全局优化 全局最优性条件 填充函数 整数规划 非线性规划

分 类 号： [O221.4]

领　　域： [理学] [理学]