无导数优化方法的研究---LSEC-Index-Home-Page

无导数优化方法的研究张在坤摘要大多数优化方法都依赖问题的导数信息.但是,在实际应用中,大量问题的导数信息都是不可用的.这就要求我们研究不使用导数信息的方法,这就是本文研究的无导数优化算法.算法的评价是算法研究中的重要问题.我们研究了如何客观可信地评价和比较不同的无导数优化算法.我们用一个例子清楚地说明传统的评价方法对于无导数算法是不可靠的.通过引入统计的方法,我们建立了评价无导数方法的一套新体系.与传统的评价方法相比,新方法不但能够反映算法对计算机舍入误差的稳定性,而且能更可靠的度量算法的计算开销.最小Frobenius范数插值和对称Broyden修正是无导数信赖域方法中最有效的两种建立模型的方式.我们第一次指出了这两种方式在一些情况下的等价性.与这两种模型紧密相关的一个问题是NEWUOA算法的重开始技术.通过修改NEWUOA源代码中的重开始条件,我们给出了一个改进版本的NEWUOA代码.新版代码仅仅删除了原始代码中的四个字母,就显著降低了代码的计算开销,并且明显提高了代码对计算机舍入误差的稳定性.我们系统地比较了最小Frobenius范数模型和对称Broyden修正在NEWUOA算法框架下的表现,并且指出,当求解精度不太高时,最小Frobenius范数模型比对称Broyden修正建立的模型表现更好.这一事实对于实际应用领域很有意义,因为实际的无导数优化问题对解的精度要求往往不高.为了研究无导数优化中有广泛应用的最小范数插值,我们率先将PDE理论中的Sobolev范数和半范数引入无导数算法的研究中.我们用二次函数的系数给出了二次函数在ℓp球上的H0范数和H1半范数的显式表达式.我们证明,最小范数插值实际上是在一个ℓ2球上极小化插值函数的H1半范数.这一观察为理1解最小范数插值提供了有力的工具.通过这一观察,我们首次指出了最小范数插值中两个参量的几何意义.我们将这些理论用于研究扩展的对称Broyden修正,得到了简单并且有效的参数选取方式.到目前为止,无导数方法可求解的问题规模还十分有限.为了求解大规模问题,我们提出了两种无导数的子空间算法.在第一种子空间方法中,利用Hooke-Jeeves模式搜索的思想,针对无导数信赖域方法,我们提出在子空间上求解信赖域子问题的策略.这种子空间策略改善了NEWUOA算法的数值表现.第二种子空间方法,即NEWUOAs(ANEWUnconstrainedOptimizationAlgorithmwithsubspacetechniquebasedonNEWUOA)算法,是本文最大的亮点.其基本想法是,把一个大规模无导数优化问题转化为一系列低维子问题.我们首先研究了一个一般性的子空间算法框架,建立了其全局收敛性和R-线性收敛速度.然后,使用NEWUOA算法作为子问题的求解器,我们不依赖导数地实现了该框架,得到了NEWUOAs算法.我们证明了NEWUOAs算法在理论上的全局收敛性、R-线性收敛速度和计算上的有限终止性.我们还提出了一项预条件技术,显著改善了NEWUOAs算法对坏条件问题的表现.据本文作者所知,这是无导数算法中第一次引入预条件技术.实验证明,NEWUOAs算法不论在函数值计算次数、CPU时间还是对计算机舍入误差的稳定性上都明显优于NEWUOA算法,后者是目前最优秀的无导数算法之一.我们还发现,NEWUOAs算法很适合求解初始点质量较差的问题,这对实际应用领域很有意义,因为很多实际问题很难给出一个好的初始点.不仅如此,对于很多维数高达2000的测试问题,NEWUOAs算法可以在几分钟内求到精度很高的解,且使用的函数值计算次数不超过50000(相当于不到25个单纯形梯度).这是一个突破,因为目前大部分无导数算法(包括NEWUOA算法)至多可以求解几百维的问题;对于它们,2000维的问题几乎是不可求解的.关键词:无导数优化,信赖域方法,二次插值,对称Broyden修正,Sobolev半范数,子空间方法,大规模问题2