拟牛顿法

---

非线性规划的一类计算方法。

这类方法的基本思想是利用梯度差来构造满足“拟牛顿方程”的近似海色阵。拟牛顿法具有不需要计算二阶导数、收敛速度快等优点，它是目前求解中小规模(从几个到几百个自变量)的非线性规划问题最有效的数值方法。

第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年证明了‖x_k+n－x^*‖=O(‖x_k－x^*‖‖x_k+1－x^*‖)，并且指出拟牛顿法的Q－收敛阶可以小于R－收敛阶。

同年，袁亚湘(Y．Yuan)举例证明拟牛顿法的最小Q－收敛阶是1，即不可能存在常数δ＞0使得‖x_k+1－x^*‖=O(‖x_k－x^*‖^1+δ)。

关于非精确线搜索下拟牛顿法的全局收敛性，鲍尔1976年开创性地证明了BFGS方法的收敛性。鲍尔的基本思想是估计修正矩阵的追迹和行列式以及利用它们之间的关系。

1986年谢元富利用鲍尔的技巧将鲍尔的关于BFGS法收敛性的结果推广到满足一定条件下的一组拟牛顿法。不足的是，谢元富的条件依赖于修正矩阵的条件数，而当条件数大时，满足要求的拟牛顿法实质上非常接近BFGS方法。

1987年，伯德(R．H．Byrd)、诺塞达尔(J．Nocedal)和袁亚湘证明了除DFP法外的整个布罗伊登凸族的全局收敛性。

DFP法的全局收敛性至今悬而未决。

对于非凸函数的情形，至今仍没有任何全局收敛性结果。当目标函数非凸时的一个主要难点是‖y_k‖²／sTy_k不一定有界，而的有界性对于估计近似海色阵的追迹是至关重要的。

在假定迭代点列收敛的前提下，鲍尔在1972年证明了如果n=2则精确线搜索下的DFP法必收敛于目标函数的稳定点。1988年濮定国和俞文鲲将鲍尔的结果推广到n＞2。

1989年伯德和诺塞达尔提出了用函数ψ(A)=tr(A)－ln(det(A))来研究算法的收敛性。

ψ函数技巧可理解为鲍尔分析拟牛顿法收敛性的技巧加工和整理。

利用ψ函数分析算法的收敛性更简单、明了。而且ψ函数同时还可用来分析算法的超线性收敛性。

不足的是，目前利用ψ函数分析收敛性常要求目标函数一致凸，而鲍尔原始的技巧只需要目标函数是凸的就可以了。另外，现在看来，ψ函数技巧对于分析DFP法的全局收敛性仍然无能为力。分析DFP法全局收敛性的主要难点在于DFP法的修正公式中没有项，而这一项在BFGS法中可控制T_r(B_k)增长的速度。要证明DFP法的收敛性的关键在于估计∑－或等价地估计。

另外一种解决这一问题的可能是引入一种新的类似于ψ函数的方法。

对于大规模问题，拟牛顿法所需内存很大。

为此，1977年佩里(J．M．Perry)和夏洛提出有限内存(Limited Memory)拟牛顿法。有限内存拟牛顿法每若干步迭代后重新置近似海色阵为单位阵，它实质上是共轭梯度法的推广。

1989年，诺塞达尔和刘(D．C．Liu)每若干迭代后取近似海色为得到一个有限内存BFGS方法。

早期人们应用拟牛顿法时都是直接修正近似海色阵B_k。这样每次迭代需要求解一个n阶线性方程组。为此，后来人们利用逆矩阵的修正公式直接产生，但美中不足的是修正Hk的数值稳定性往往比修正B_k要差得多。

为了使算法既基于修正B_k，又避免解线性方程组，吉尔(P．E．Gill)和默里(W．Murray)于1972年提出把B_k分解成LDL⁷的形式，然后每次迭代修正L和D。吉尔和默里的方法具有计算最小、数值稳定等优点，但它的缺点是程序复杂。1987年鲍尔提出修正矩阵H_k的共轭分解。鲍尔的方法是将H_k分解成Z_kZ_k^T，然后修正Z_k的每一列，使得zk的列向量是共轭方向。这一方法的优点是很便于在并行计算机上实现，而且可对Z_k的各列进行加权使得B_k的条件数不太大。

关于拟牛顿法的研究成果已有很多，但仍有不少重要的问题待解决，例如：DFP方法对凸函数在非精确线搜索下的全局收敛性、DFGS方法对于非凸函数的收敛性、拟牛顿法在精确线搜索下的收敛速度是否可达到‖x_k+1－x^*‖=O(‖x_k－x^*‖‖x_k－n+1－x^*‖)等。

另外，拟牛顿修正公式的新的加权(sizing)技术、列调节(column scaling)技术，有限内存拟牛顿法，可分离优化问题的分块(partitioned)拟牛顿方法，以及并行(parallel)拟牛顿方法等也将是研究的热点。

。【参考文献】：

1 Davidon W C. AEC Res and Dev Report, ANL-5900,1959

2 Fletcher R, et al. The Computer J, 1963,6:163～168

3 BroydenGC. Inst Maths Appl,1970,6:222～231

4 Powell M J D. J Inst Maths Appl,1971,7:21～36

5 Dixon LCW. J Opt Theory Appl, 1972,10:34～40

6 Dennis J E, et al. Math Comput, 1974,28:549 ～ 560

7 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～72

8 Yuan Y. IMA J. Numer Anal, 1984,4:233～239

9 Byrd R, et al. SIAM J Numer Anal, 1987,4:1171～1190

10 Powell M J D. Math Prog, 1987,38:29～46

11 Byrd R, et al. SIAM J Numer Anal,1989,26:727～739

(中国科学院计算数学所袁亚湘研究员撰)

上一篇：信赖域法
下一篇：现代科技综述大辞典上目录

"拟球状面心电位场拟球状面心电位场

---

系我国学者尹炳生教授于1980年提出的一种有关心电图导联理论的假说。

尹氏根据头胸导联体表实测数据，将实际的体表心电位场简化，提出了“拟球状面心电位场波阵面传递假说”。尔后通过运用四维显示等技术观察体表的心电三维动态演变过程，一系列实验资料证明，正常机体体表心电位场是拟球状面场而不是偶极场。1．拟球状面心电位场假说要点：(1)心电活动的本质：心脏除极与复极过程是一种生物电磁扰动过程，以有限的速度(3×10⁸m／s)向外传播，这种生物电磁波是一种缓变的低能级的电磁波。心电场是一种缓变的时变场，体表心电变化与心脏源的电活动之间可以看成没有时相差异(因为λ≥r)，这样，虽然每一瞬间场量服从静态场和恒定场的规律，可以用静电场的规律来求解电场，用恒定场的规律来解磁场，但是并不意味著可以否定心电场、心磁场的源一电荷、电流的时变特性。

(2)心电极化波：心电在体传播的主要方式是心电极化波。根据Durrer除极等时图，可推理心电源是聚偶极子场源，心电应沿两个相反的方向向空间扩布。

由于心脏的肌肉构成了几近封闭的多个出入口的囊，心内膜方向的电活动被迫汇在一起。心腔内血池是一个大的均质良导体，心内膜面电活动的不均一性形成区域性电位差，在血池中生成局部传导电流，致使心内膜方向的心电场强度极大地衰减，难以外传(在导管术中见到右心房内P波远大于QRS波群，右心室内只见QRS波而无P波就是一个最佳例证)。从整体角度看，心脏的偶极电活动就转化成一个类单源状态，心脏可以看成是一个类单源场源，它处在一个含有大量“有极分子”的非均匀而有限的弱导电媒质里。

在心电活动过程中，心外膜面电活动向外传播，H₂O等“有极分子”沿心电场方向取向极化，以极化波形式向外扩布；被细胞膜分隔包围的体液中的离子，则可能形成细胞内涡电流，对电场起著较大的衰减作用；含有气泡结构和富含脂质的肺脏阻抗更高，衰减能力更强。这种非均匀性明显地影响著体表电位的分布。(3)心电场的不均一性：由于心电场源各方向强度不等，体腔内各方向对电场强度的衰减程度不一，导致在体表各方位上同一瞬间的波阵强度有或大或小的差异，总的趋向是沿心底到心尖的轴线左前下场强较强，右后上场强较弱；同一瞬间各方位波阵的相位亦有或大或小的差异，可同相，也可反相，这取决于心脏各部分除极与复极的方向和强度。

(4)“0球面”：以右前额作共同参比点，设其电位与相位为“0”。将参比点等效为一个等电位球面－－“0球面”，在该球面中心设有不均匀的聚偶极子场源0。在心电活动周期中，体表任一测试点A的电位与相位在“0球面”相应点A′上沿法线运动。若场源0发出正相波阵(P、R、T波阵)，电力线指向外，探查电极在A点上录得正相P波、R波和T波；若发出负相波阵(q、S波阵)，电力线方向指向内，则在A点上录得负相的q波及S波。心电活动障碍时，心电位场发生相应的畸变，则录得各种异常的心电图。2．拟球状面心电位场与心电图各波的关系：运用拟球状面心电位场假说对头胸导联体表心电图的形成解释如下：(1)P波：心脏兴奋从窦房结开始，经过房间束和结间束。

心房肌除极一方面由右上后向左下前传播，另一方面由心内膜向心外膜方向进行。右后上方位P波阵较弱，在该方向往往录不到P波(如AR₃处)；其余方位的P波阵较强，通常录得正相P波。(2)q波：任一部位的QRS波群都是由心室肌先后除极的3个波阵(Q、R、S)在同一部位融合而成。当心室除极20～30ms时，室间隔除极形成一个指向DRI(V₁)方向的不完整的拟球状面除极区，体表胸骨体部偏右开始出现R波阵，背向的部位可能形成一个不完整的Q波阵。在一般情况下，D′R12、DRI、DLI(HV_3RHV_1、2)等部位可录得R波，在背部EL₅～EL₇(H_V7～₉)到ER₅～ER₇(HV_7R～_9R)可录得q波，且小于1／4R，小于0．04s。(3)R波：心室兴奋20～30ms后，心室除极区形成完整的拟同心圆状除极带并向外扩展，由心内膜指向心外膜，形成完整的正相R波阵向外扩布。

在体表120点阵列里，头胸导联均可取得R波。心底部及右心室形成的场强较弱，相应方位测得的R波振幅较低；左心室及心尖部形成的场强较强，相应方位测得的R波振幅较高。

(4)S波：在舒张期末，心室内充满血液，像个收口的坛子；心肌纤维走行方向呈螺旋状并向瓣膜区汇合；心室除极向心底部、动脉圆锥部和心尖部的最后除极区集中。对体表而言，除极方向发生变化，由正对体表变为背向体表，形成负相S波阵。

它依赖于动脉圆锥部心肌的结构与电生理特点，在该部正对的胸骨体及两旁(D′R1₂、DR₁、DL₁、D′_L12即HV_3R、HV_1～3)体表的心电图S波振幅较深，出现率达100%；向左右两侧推移，各测试点的S波逐渐变浅，出现率逐渐降低，背部可低达12．03%。在心尖部最后除极区，除极方向一方面由内向外，另一方面向最后除极点集中，故该部位形成的负相S波阵常较弱，膈面导联HR₃、H₀、HL₃(以及Ⅲ、aVF、Ⅱ等)的S波振幅浅于心窝部，且出现率低，约为1／3。

(5)T波：心室复极由心外膜向心内膜方向进行，构成正相T波阵向外扩布，电变化梯度较低，持续时间较长，故录得之T波比R波振幅低宽且正立。从动态的二维图与三维图来看，均呈典型的正相单向性，是一个完整的正相拟球面波阵，而面对心底部的AR₃、CR₆等处的T波十分低平，说明该方向T波阵很弱。