【拟牛顿法】
拼译：quasi-Newton methods
非线性规划的一类计算方法。这类方法的基本思想是利用梯度差来构造满足“拟牛顿方程”的近似海色阵。拟牛顿法具有不需要计算二阶导数、收敛速度快等优点，它是目前求解中小规模(从几个到几百个自变量)的非线性规划问题最有效的数值方法。
第1个拟牛顿法由美国的戴维登(W．C．Davidan)1959年提出。由于戴维登的算法并没有在正式学术杂志上发表，而是在一份Argonne实验室的科研报告中所介绍，故这一算法开始并没受到重视。1963年英国弗莱彻(R．Fletcher)和鲍尔(M．J．D．Powell)对戴维登的算法进行了分析、整理和修改，所以这一算法被人称为DFP方法。此后，拟牛顿法的研究受到许多优化专家的重视。另一个著名的拟牛顿法由布罗伊登(G．C．Broyden)、弗莱彻、戈德法伯(D．Goldfarb)、夏洛(D．F．Shanno)在1970年独立地提出，故被称为BFGS方法。在60年代末期，布罗伊登等人提出对称秩1算法(SR1)，这是形式最简单的对称拟牛顿修正公式。1970年鲍尔将非结称秩1修正公式对称化，导出一个秩2公式，被称为“鲍尔对称化布罗伊登”(PSB)公式。后来，更多的拟牛顿修正公式被提出，著名的有布罗伊登族和黄(H．Y．Huang)族。DFP法、BFGS法和SR1法都属于布罗伊登族。1968年迈尔斯(G．E．Myers)首先发现对于凸的二次函数，精确线搜索下的DFP方法实质上是一个共轭梯度法，从而证明了DFP方法具有二次终止性。1971年鲍尔证明了对于一致凸函数，精确线搜索下的DFP方法是收敛的，且具有Q－超线性收敛性。鲍尔的证明技巧是估计近似海色阵的追迹。他还利用精确线搜索条件导出了一个非常重要的恒等式。1972年狄克逊(L．C．W．Dixon)证明了黄族中所有的拟牛顿法在精确线搜索下产生相同的点列。1973年布罗伊登、丹尼斯(J．E．Dennis)和莫雷(J．J．Moré)提出一种新的分析拟牛顿法收敛性的技巧，他们利用修正矩阵每次修正后范数不可能增加太大这一特性证明了几个著名的拟牛顿法如DFP法、BFGS法以及SR1法等方法在步长为1时的局部超线性收敛性。自从鲍尔证明DFP法的超线性收敛性以来，人们十分关注精确线搜索下的拟牛顿法的收敛阶问题。1973年布尔迈斯特(W．Burmeister)首先证明了DFP法的n步二次收敛性。后来，这一结果被里特尔(K．Ritter)、舒勒(G．Schuller)等人进一步改进，但他们所需的条件太苛刻。在通常的条件下，鲍尔于1984年证明了‖xk+n－x*‖=O(‖xk－x*‖‖xk+1－x*‖)，并且指出拟牛顿法的Q－收敛阶可以小于R－收敛阶。同年，袁亚湘(Y．Yuan)举例证明拟牛顿法的最小Q－收敛阶是1，即不可能存在常数δ＞0使得‖xk+1－x*‖=O(‖xk－x*‖1+δ)。关于非精确线搜索下拟牛顿法的全局收敛性，鲍尔1976年开创性地证明了BFGS方法的收敛性。鲍尔的基本思想是估计修正矩阵的追迹和行列式以及利用它们之间的关系。1986年谢元富利用鲍尔的技巧将鲍尔的关于BFGS法收敛性的结果推广到满足一定条件下的一组拟牛顿法。不足的是，谢元富的条件依赖于修正矩阵的条件数，而当条件数大时，满足要求的拟牛顿法实质上非常接近BFGS方法。1987年，伯德(R．H．Byrd)、诺塞达尔(J．Nocedal)和袁亚湘证明了除DFP法外的整个布罗伊登凸族的全局收敛性。DFP法的全局收敛性至今悬而未决。对于非凸函数的情形，至今仍没有任何全局收敛性结果。当目标函数非凸时的一个主要难点是‖yk‖2／sTyk不一定有界，而
的有界性对于估计近似海色阵的追迹是至关重要的。在假定迭代点列收敛的前提下，鲍尔在1972年证明了如果n=2则精确线搜索下的DFP法必收敛于目标函数的稳定点。1988年濮定国和俞文鲲将鲍尔的结果推广到n＞2。1989年伯德和诺塞达尔提出了用函数ψ(A)=tr(A)－ln(det(A))来研究算法的收敛性。ψ函数技巧可理解为鲍尔分析拟牛顿法收敛性的技巧加工和整理。利用ψ函数分析算法的收敛性更简单、明了。而且ψ函数同时还可用来分析算法的超线性收敛性。不足的是，目前利用ψ函数分析收敛性常要求目标函数一致凸，而鲍尔原始的技巧只需要目标函数是凸的就可以了。另外，现在看来，ψ函数技巧对于分析DFP法的全局收敛性仍然无能为力。分析DFP法全局收敛性的主要难点在于DFP法的修正公式中没有
项，而这一项在BFGS法中可控制Tr(Bk)增长的速度。要证明DFP法的收敛性的关键在于估计∑－
或等价地估计
。另外一种解决这一问题的可能是引入一种新的类似于ψ函数的方法。对于大规模问题，拟牛顿法所需内存很大。为此，1977年佩里(J．M．Perry)和夏洛提出有限内存(Limited Memory)拟牛顿法。有限内存拟牛顿法每若干步迭代后重新置近似海色阵为单位阵，它实质上是共轭梯度法的推广。1989年，诺塞达尔和刘(D．C．Liu)每若干迭代后取近似海色为
得到一个有限内存BFGS方法。早期人们应用拟牛顿法时都是直接修正近似海色阵Bk。这样每次迭代需要求解一个n阶线性方程组。为此，后来人们利用逆矩阵的修正公式直接产生
，但美中不足的是修正Hk的数值稳定性往往比修正Bk要差得多。为了使算法既基于修正Bk，又避免解线性方程组，吉尔(P．E．Gill)和默里(W．Murray)于1972年提出把Bk分解成LDL7的形式，然后每次迭代修正L和D。吉尔和默里的方法具有计算最小、数值稳定等优点，但它的缺点是程序复杂。1987年鲍尔提出修正矩阵Hk的共轭分解。鲍尔的方法是将Hk分解成ZkZkT，然后修正Zk的每一列，使得zk的列向量是共轭方向。这一方法的优点是很便于在并行计算机上实现，而且可对Zk的各列进行加权使得Bk的条件数不太大。关于拟牛顿法的研究成果已有很多，但仍有不少重要的问题待解决，例如：DFP方法对凸函数在非精确线搜索下的全局收敛性、DFGS方法对于非凸函数的收敛性、拟牛顿法在精确线搜索下的收敛速度是否可达到‖xk+1－x*‖=O(‖xk－x*‖‖xk－n+1－x*‖)等。另外，拟牛顿修正公式的新的加权(sizing)技术、列调节(column scaling)技术，有限内存拟牛顿法，可分离优化问题的分块(partitioned)拟牛顿方法，以及并行(parallel)拟牛顿方法等也将是研究的热点。【参考文献】：1 Davidon W C. AEC Res and Dev Report, ANL-5900,19592 Fletcher R, et al. The Computer J, 1963,6:163～1683 BroydenGC. Inst Maths Appl,1970,6:222～2314 Powell M J D. J Inst Maths Appl,1971,7:21～365 Dixon LCW. J Opt Theory Appl, 1972,10:34～406 Dennis J E, et al. Math Comput, 1974,28:549 ～ 5607 M J D Powell. R W Cottle and C. E. Lemke, eds. , Nonin-ear Programming, SIAM -AMS Proceegins vol. IX(SIAM publications,Philadelphia, 1976,53～728 Yuan Y. IMA J. Numer Anal, 1984,4:233～2399 Byrd R, et al. SIAM J Numer Anal, 1987,4:1171～119010 Powell M J D. Math Prog, 1987,38:29～4611 Byrd R, et al. SIAM J Numer Anal,1989,26:727～739(中国科学院计算数学所袁亚湘研究员撰)