论文部分内容阅读
全局最优化问题的一般表述形式为:其中(P)min f(x)<,s.t.x∈X>其中x∈R是决策变量,f(x)为目标函数,X∈R为约束集或可行域.特别地,如果约束集X=R,则最优化问题(P)称为无约束最优化问题.反之,若约束集X分别由等式或不等式约束函数构成时,问题(P)则称为约束最优化问题.本文着重讨论无约束最优化问题的理论和方法.求解全局优化的方法在科学技术、工程设计、经济管理等方面有着广泛的应用.近几十年来,全局优化的研究取得了相当的进展,许多学者提出了不同的求解全局优化问题的算法.目前,主要有以下几种途径:区间算法、积分水平集法、打洞函数法和填充函数法等.前两种算法虽然有比较好的收敛性和全局解判别准则,但是对于Lipschitz常数、一致连续常数、有界的高阶导数、水平集等全局信息非常难获取.相比之下,处理局部信息我们已经有很多完善的方法.打洞函数法和填充函数法即利用成熟的局部极小点求解方法并构造辅助函数来达到搜索全局解的目的,但其缺点是缺乏终止准则.本文研究的核心是填充函数的理论、算法及其应用.填充函数算法最早由西安交通大学的葛人溥教授提出.先前研究中,带有两个或一个参数的填充函数均已得到应用.但由于参数选择比较困难,对一些填充函数而言,如果参数选取不当,很容易造成全局最优点的丢失,或者求出的点不是目标函数更小的极小点.于是,针对[1]文中葛人溥提出是否存在无参数填充函数的问题,我们作了深入研究并给予肯定的答复,构造出无参数填充函数P(x,x*).数值结果表明算法是有效的.在P(x,x*)基础上,我们作进一步推广,构造出带参数的填充函数P(x,x*,μ)和P(x,x*,μ,ρ),并比较P(x,x*)和P(x,x*,μ)的算法.第三章重点改进了原始的填充函数定义,要求原先只在线上有极小点的填充函数存在局部极小点.我们构造出填充函数P(x,x*,ε),并论证了新定义下的填充函数性态更优越.最后一章,我们将辅助函数P(x,x*)和L(x,x*,μ)引入非线性整数规划问题,提出整点的邻域、局部极小点和全局极小点的概念.在此基础上,给出P(x,x*)和L(x,x*,μ)满足的性质,并证明它们是离散概念下的填充函数.我们发现有效求解连续问题的填充函数同样可以有效地求解离散问题.如何构造性态更理想、算法效率更高的填充函数,以及如何将求解连续规划问题相应的填充函数更有效地运用在非线性整数规划问题值得进一步研究.