论文部分内容阅读
对于无约束优化来说,有很多基于导数之上的方法,例如:最速下降方法,拟牛顿方法等等。其中,拟牛顿法还具有局部超线性收敛性,是很有效的算法.但是,在实际生活中,存在一些来自于物理、化学、经济等方面的问题,其目标函数的导数是不可用或不可信赖的。面对这一类问题,只有少数方法是适用的。模式搜索方法就是其中之一.
模式搜索方法是一类直接方法.它起源于20世纪60年代,由于其简单性及实用性该方法一直被广泛使用至今.该方法不需要目标函数的导数,只需要通过函数值的比较来选取新的迭代点。因此我们实际只需要函数值的排序即可.但是,这种简单性会降低算法的效率并使用较多的函数值.
一般说来,想改善模式搜索算法有两个方面的困难:一是迭代点接受条件的选择;二是寻查方向集的选取.对于后者,在过去寻查方向集通常由一组Rn中的基向量及其负方向组成.尽管这样的寻查方向集可以搜索到全空间,但是由于寻查方向个数太多会导致算法效率的降低。近期,正基、共轭性及并行运算等很多技术都被广泛用来解决这一问题,尤其是正基.当正基被引入寻查方向集时,较之以前的同类方法最多可以节约近一半数量的寻查方向.不过与此同时也产生了一个新的问题,那就是在算法中如何具体去选择一系列的正基,这在已有文献中少有猎涉.
基于以上的考虑,我们对模式搜索方法进行了研究,在迭代点接受准则,正基生成和寻查方向集等三个方面作了一些工作.
在迭代点接受准则方面:
(1)滤波方法被用于建立新迭代点接受准则,从而得到一个基于滤波之上的模式搜索方法。在该方法中,由于迭代点接受条件的放松,使得在寻查范围得以扩大的基础上算法收敛性仍能得到保证.
(2)在基于滤波之上的模式搜索算法中,由于滤波的使用,使得算法生成的迭代点序列并非单调下降。这促使我们将非单调技术引入其中去进一步改进迭代点的接受准则,原方法被进一步更新并能避免算法早熟.
在正基的生成方面:
(1)我们将BFGS算法引入模式搜索方法中,从而得到了一种基于拟牛顿方法之上的模式搜索方法.该方法结合了BFGS算法及一般模式搜索算法的优点.在对近似Hessian矩阵进行分解的过程中可以产生一系列具有共轭性质的基,从而可以生成一系列正基.同时,方向的共轭性有益于模式搜索过程的进行.进一步的,BFGS算法的引入可以加快模式搜索方法的收敛并且能够减少函数值的使用。
(2)除了BFGS算法以外,拟牛顿方法还包含其他一些有效算法,例如对称秩一算法(SR1算法)等等。近来的一些研究结果表明当SR1校正和其他的一些拟牛顿校正(如DFP校正,BFGS校正)同时可用时,SR1校正更为有效.同时,在SR1算法中近似Hessian矩阵序列可以收敛到精确Hessian矩阵(在解点处).因此,我们可以仿照第五章的算法将基于最优性条件之上的自调比对称秩一算法(OCSSR1算法)应用到模式搜索算法中,其结果更好。
在寻查方向集方面:
(1)迭代子空间极小化方法是一类针对于大型问题的优化方法。而模式搜索方法的最大缺陷就在于寻查方向过多,这将会消耗大量的函数值.同时,寻查方向的个数是与问题的维数紧密相关的。因此,基于迭代子空间极小化方法的思想,我们提出了一个改善了的模式搜索方法.在每一次迭代时,我们都建立一个低维的子空间,并且在这个子空间中实施模式搜索,而非在原空间中.这就使得寻查方向的个数有所减少,从而函数值的使用数目也大大降低.
我们用一些经典的优化测试问题(见附件A)进行了数值试验,结果表明我们所提出的方法是有用且有效的。与其他一些无导数方法进行相比,有时其更具优越性.