论文摘要
本文研究了连续全局优化的水平值逼近理论与算法。在本文中给出了两种关于连续全局优化问题的水平值逼近算法,并对算法的收敛性、计算复杂性及其数值实验性能等方面做了一系列的理论分析和数值试验。本文取得的主要研究成果如下:第一,提出了一种求解全局优化问题的确定型水平值逼近算法。这种算法是基于用牛顿切线法求解关于水平值的单变量函数方程v（c）=0而构造的。我们引入了水平值函数v（c）,通过研究其性质,得到了构造确定型水平值逼近算法相应的理论依据。此后构造了确定型水平值逼近算法的概念算法并证明了概念算法的收敛性。然后构造了基于数论技术求积分的实现算法,经过验证,可以发现实现算法满足不精确牛顿方法的收敛性条件,从而证明了实现算法的收敛性。我们将上述确定型水平值逼近算法推广到求解目标函数为丰满函数（robust）的全局优化问题。特别地,我们构造了基于重点取样的Monte-Caurlo算法的实现算法,并证明了实现算法的收敛性。数值实验表明,这种实现算法具有广泛的适用性、较高的数值精度以及较高的实现效率。此外,我们还研究了不同的取样分布在实现算法中的实现效果。第二,提出了一种求解全局优化的随机型水平值逼近算法,研究了算法的收敛性及计算复杂性。这种算法结合了纯粹更新算法、纯粹随机搜索算法和重点样本的思想,成功利用了相对熵算法的基本思想。该算法具有渐近收敛性,期望多项式时间复杂性,同时由于算法对问题的解析性质要求极少（实际上只用到问题的函数值）,因此具有广泛的适用性,适合于工程计算。数值实验结果表明了算法的有效性。我们将随机型水平值逼近算法推广到求解二次整数凸规划问题上,结果表明求解二次整数凸规划的随机型水平值逼近算法与一些经典的随机型整规划算法相比,在计算精度和计算时间上具有一定的优势。第三,本文对两种比较经典的全局优化算法进行了修正。首先给出了修正的积分水平集算法,由于我们有效地结合了重点取样和相对熵算法的主要思想,使得修正算法既保持了原来水平集算法的高效率和高精度,又克服了它在实现算法收敛性分析方面的困难。最后,本文对相对熵算法做了修正,在选取。精英样本”时,选取那些落入当前水平集的样本点,保证了修正算法的渐近收敛性。数值实验说明,这两种修正的算法至少保持了原来算法在计算效率与计算精度上的优势,并且具有理论上的收敛性。全文结构做如下安排:第一章,对全局优化的理论与算法的进展概貌作一系列介绍,扼要阐述了本文的主要工作。第二章和第三章,提出了一种全局优化的确定型水平值逼近算法和它的两种实现算法-基于数论技术的实现算法与基于重点取样的实现算法,研究了算法的收敛性。第四章,提出了一种全局优化的随机型水平值逼近算法,研究了算法的收敛性、计算复杂性,并将它推广应用于求解离散规划问题中去。第五章,我们对两种经典的全局优化算法-积分水平集算法与相对熵算法做了修正,证明了修正算法的收敛性,数值算例说明了修正算法的有效性。在本文最后的第六章,对全文进行了总结,提出了今后的研究设想。