光滑问题的牛顿法及其延拓.pdf

第4 6卷2期2 0 2 3年6月 辽宁师范大学学报(自然科学版)J o u r n a l o fL i a o n i n gN o r m a lU n i v e r s i t y(N a t u r a lS c i e n c eE d i t i o n)V o l.4 6 N o.2J u n.2 0 2 3 收稿日期:2 0 2 3-0 1-1 5基金项目:辽宁省教育厅科学研究一般项目(L J 2 0 1 9 0 0 5)作者简介:任咏红(1 9 7 3-),女,辽宁朝阳人,辽宁师范大学教授,博士.E-m a i l:r y h o n g 1 6 3.c o m 文章编号:1 0 0 0-1 7 3 5(2 0 2 3)0 2-0 1 5 8-0 5 D O I:1 0.1 1 6 7 9/l s x b l k 2 0 2 3 0 2 0 1 5 8光滑问题的牛顿法及其延拓任咏红,郭智蕊(辽宁师范大学 数学学院,辽宁 大连 1 1 6 0 2 9)摘 要:牛顿法是科学计算中最重要的方法之一,一些重要的数值计算方法的计算速度快的主要原因是与牛顿方向有关系.简述一元函数求根的经典牛顿法及其收敛性定理,并给出几点注记;解释了一元函数到多元映射在分析上的困难,给出求解无约束极小化问题的经典牛顿法及收敛性定理;将光滑映射拓广到半光滑映射,提出半光滑牛顿方法,分析并证明了半光滑牛顿法收敛性定理;以求解互补问题为例说明半光滑牛顿方法具有广泛的应用背景.关键词:经典牛顿法;收敛速度;半光滑牛顿法中图分类号:O 1 7 7.5 文献标识码:A牛顿法是科学计算中最重要的方法之一,如方程求根、无约束优化问题求解、变分不等式求解等许多问题都有牛顿法1-3.经典的牛顿法具有局部收敛性,且在一定条件下具有二阶收敛性,一些重要的数值计算方法计算速度快的原因是与牛顿方向有一定的关系.本文基于光滑问题的牛顿法,给出算法及收敛性定理的几点注记,将光滑映射拓广到半光滑映射,给出半光滑牛顿方法以及收敛性定理,并以求解互补问题为例说明半光滑牛顿方法具有广泛的应用背景.1 光滑问题的牛顿法1.1 一元函数求根的牛顿法一元函数的图像就是一条二维平面上的曲线,它的求根问题从几何的角度,就是找曲线和x轴的交点,此时牛顿法的几何直观非常显然,就是在曲线的当前迭代点处做切线,切线和x轴的交点即下一次的迭代点.从分析的角度,就是一阶T a y l o r展开式求根作为下一个迭代点.考虑一元函数:,它的求根问题即找到或求解一实数z*满足(z*)=0,(1)其中,为连续可微函数.求解问题(1)的牛顿法可以描述如下:步1 选取初始的点z0,置k=0.步2 计算zk+1=zk-(zk)-1(zk).步3 k=k+1,转到步2.第2期任咏红等:光滑问题的牛顿法及其延拓1 5 9 注记1(关于终止条件和对函数可导性的注记)(1)关于终止准则,可以在步1中选择0,在步2计算之后添加终止准则:|(zk+1)|,即这一条件满足时就停止计算,zk+1是近似解.(2)对函数的要求,函数在当前点zk处是可导的,(zk)0.一元函数求根问题的牛顿法具有如下的收敛性和收敛速度定理.定理1 设z*是的零点,在z*附近是连续可微的,(z*)0.则存在0满足,只要z0(z*-,z*+),由牛顿法生成的序列zk 是有定义的且收敛到z*,收敛速度是超线性的.进一步,如果在z*附近是L i p s c h i t z连续的,则收敛速度是二阶的.注记2(关于收敛性定理1的注记)(1)只有初始点z0距离零点很近时算法才是有定义的,算法才是收敛的,这就是牛顿法的局部收敛性.(2)牛顿法的二阶收敛是有条件的,即导数在零点附近的L i p s c h i t z连续性,一般而言,牛顿法只是超线性收敛的.(3)条件“在z*附近是z*连续可微的,(z*)0”意味着存在10满足在(z*-1,z*+1)是连续的且(z)0,z(z*-1,z*+1).由这一分析可知,只要|z0-z*|0以保证迭代点的收敛和超线性收敛速度.1.2 多元方程组求根的牛顿法考虑F:n n,F=(f1,fn),非线性方程组求根问题即找到或求解一向量x*n满足F(x*)=0,(2)其中,F为连续可微函数.比较一元函数求根的牛顿法,从一阶T a y l o r展开式的角度,当前点是xk,下一个迭代点即求F在xk处T a y l o r展开式的根,这通过解一个线性方程组得到.求解问题(2)的牛顿法可以描述如下:步1 选取初始的点x0 n,置k=0.步2 求解下述方程组得xk+1:IF(xk)(x-xk)+F(xk)=0.步3 k=k+1,转到步2.注记3(关于终止条件和函数可导性的注记)(1)IF(x)是F在x处的J a c o b i矩阵,即IF(x)=f1(x)x1f1(x)xnfn(x)x1fn(x)xn.1 6 0 辽宁师范大学学报(自然科学版)第4 6卷(2)关于终止准则,可以在步1中选择0,在步2计算之后添加终止准则:F(xk+1),即,这一条件满足时就停止计算,xk+1是近似解.(3)对函数的要求,函数在当前点xk处是可导的,IF(xk)非奇异.改造一下定理1就得到求解非线性方程组的牛顿法收敛性和收敛速度.定理2 设x*是F的零点,F在x*附近是连续可微的,IF(x*)非奇异.则存在0满足,只要x0B(x*,),由牛顿法生成的序列xk 是有定义的且收敛到x*,收敛速度是超线性的.进一步,如果IF在x*附近是L i p s c h i t z连续的,则收敛速度是二阶的.注记4(关于收敛性定理2的注记)由矩阵的扰动分析原理可知,条件“F在x*附近是连续可微的,IF(x*)非奇异”意味着存在10满足IF在B(x*,1)是连续的且IF(x)在B(x*,1)上是非奇异的,类似地,可知x1-x*=x0-IF(x0)-1F(x0)-x*IF(x0)-1 F(x0)-IF(x0)(x0-x*).显然,IF(x0)-1是有上界的,这需要矩阵的扰动理论,用T a y l o r展开式或中值定理与IF的连续性分析F(x0)-IF(x0)(x0-x*)=o(x0-x*).将这些关键性的困难理清楚之后,完全类似一元函数求根牛顿法的证明就可以证明牛顿法的局部收敛性和超线性收敛速度.1.3 无约束优化的牛顿法求解无约束优化的算法基本上都是基于求到一稳定点,稳定点可以用一方程组来表达,求解这一方程的牛顿法就是无约束优化的牛顿法.也可以从函数在当前点的二阶T a y l o r展开式的角度,视二次函数局部地近似原来的函数,求解次二次函数的极小点,即得到牛顿迭代.考虑无约束极小化问题m i nxnf(x),(3)其中,f:n 是连续可微的实值函数.求解无约束优化问题(3),找到极小点是很困难的,通常求解问题的稳定点,即求解x*n满足f(x*)=0.令F=f,方程组的经典牛顿法即求解问题(3)的牛顿法可以描述如下:步1 选取初始的点x0 n,置k=0.步2 计算xk+1=xk-2f(xk)-1f(xk).步3 k=k+1,转到步2.当然也可以从f在xk处二阶T a y l o r展开的角度得到牛顿法的迭代格式.定义f在xk处二阶T a y l o r展开式为q(x),即q(x)=f(xk)+12,如果 2f(xk)是正定矩阵,则q(x)的极小点即牛顿法的xk+1.定理31 设x*是f的稳定点,f在x*附近是连续可微的,2f(x*)是正定矩阵.则存在0满足,只要x0B(x*,),由牛顿法生成的序列xk 是有定义的且收敛到x*,收敛速度是超线性的.进一步,如果 2f在x*附近是L i p s c h i t z连续的,则收敛速度是二阶的.注记5(关于收敛性定理3的注记)关于条件“2f在x*附近是L i p s c h i t z连续的”是二阶充分性最优条件,即这一条件可以保证f第2期任咏红等:光滑问题的牛顿法及其延拓1 6 1 在x*处的二阶增长条件:存在0,0,满足f(x)f(x*)+x-x*2,xB(x*,).2 牛顿法的延拓由于很多问题,比如互补问题和变分不等式问题,通过等价变换可以表示为方程组的形式,但映射不再是光滑的.如何把光滑性减弱,推广微分,建立基于广义微分的牛顿方法?一个很自然的问题是,如果F:n n在x*附近不是连续可微的,如何用牛顿法?这需要把光滑性性质弱化,用所谓的半光滑性.定义14 设 n是一开集合,称F:n在x*处是半光滑的,如果F在x*处是局部L i p s c h i t z连续的,方向可微的,且对x*附近的x,有F(x)-F(x*)-V(x-x*)=o(x-x*),VF(x).注记6(关于定义1的注记)(1)映射F在x*处是局部L i p s c h i t z连续的指存在0,L0,F(x)-F(y)Lx-y,x,yB(x*,).(2)F(x)是F在x处的广义J a c o b i.若映射F在x*处是局部L i p s c h i t z连续的,则对于0,F在B(x*,)上是几乎处处可微的,记DF=x|F在x处是可微的.定义BF(x)=V:xkDFB(x*,),xkx,V=l i mxkxIF(xk),它被称为B-次微分.B-次微分的凸包被称为F在x处的广义J a c o b i5:F(x)=c o n vBF(x).考虑F:n n,是局部L i p s c h i t z连续的,找到或求解一向量x*n满足F(x*)=0,(4)求解问题(4)的牛顿法可以描述如下:半光滑牛顿法步1 选取初始的点x0 n,置k=0.步2 计算xk+1=xk-Vk-1F(xk),VkF(xk).步3 k=k+1,转到步2.半光滑牛顿法即把光滑牛顿法中的J a c o b i用广义J a c o b i中的一个元素来代替,即如果当前点是xk,则下一迭代点由下述公式生成xk+1=xk-Vk-1F(xk),VkF(xk).定理4 设x*是问题(4)的解,F在x*附近是半光滑的,F(x*)的每一个元素均是非奇异.则存在0满足,只要x0B(x*,),由半光滑牛顿法生成的序列xk 是有定义的且收敛到x*,收敛速度是超线性的.注记7(关于收敛性定理4的注记)条件“F在x*附近是半光滑的,F(x*)的每一个元素均是非奇异”保证了在与x*充分接近的点x处都有F(x)的每一元素是非奇异的,且F(x)的每一元素之逆具有一致的上界,即存在0,常数C0使得xB(x*,),VF(x),V是奇异的,且V-1 C.证 由于F在x*附近是半光滑的,由定义1知,存在0,xB(x*,),VF(x)有F(x)-F(x*)-V(x-x*)=o(x-x*),且V(x-x*)-F(x*;x-x*)=o(x-x*).1 6 2 辽宁师范大学学报(自然科学版)第4 6卷故由注记7可知xk+1-x*=xk-x*-Vk-1F(xk)=Vk-1Vk(xk-x*)-F(xk)Vk-1F(xk)-F(x*)-F(x*;xk-x*)+Vk-1Vk(xk-x*)-F(x*;xk-x*)=o(x-x*),VkF(xk).证毕.问题(4)不是仅在光滑方程组(2)的形式上的推广,而是有重要的背景.考虑非线性互补问题40G(x)H(x)0,(5)其中,G:n n,H:n n是光滑映射.注意a b=0,a0,b0m i na,b=0a+b-a2+b2=0.因此互补问题(5)等价于m i n(G(x),H(x)=0,(6)其中,m i n(G(x),H(x)i=m i nGi(x),Hi(x).同样互补问题(5)等价于F B(G(x),H(x)=0,(7)其中,F B(G(x),H(x)i=Gi(x)+Hi(x)-Gi(x)2+Hi(x)2.容易验证方程(6)和方程(7)均是半光滑方程组,可以用半光滑牛顿法进行求解.参考文献:1 张立卫,单锋.最优化方法M.北京:科学出版社,2 0 1 0:6 8-7 0.2 Q ILQ,S UNJ.An o n s m o o t hv e r s i o no fN e w t o nsm e t h o dJ.M a t h e m a t i c a lP r o g r a mm i n g,1 9 9 3,5 8:3 5 3-3 6 7.3 HA R K E RPT,X I AOB.N e w t o nsm e t h o d f o r t h en o n l i n e a r c o m p l e m e n t a r i t yp r o b l e m:AB-d i f f e r e n t i a b l e e q u a t i o na p p r o a c hJ.M a t h e m a t i c a lP r o g r a mm i n g,1 9 9 0,4 8:3 3 9-3 5 7.4 韩继业,修乃华,戚厚铎.非线性互补理论与算法M.上海:上海科技出版社,2 0 0 6:1 9 7-2 0 7.5 C L A R K EFH.O p t i m i z a t i o na n dn o n s m o o t ha n a l y s i sM.N e wY o r k:S o c i e t y f o r I n d u s t r i a l a n dA p p l i e dm a t h e m a t i c s,1 9 8 3:6 9-7 5.N e w t o nsm e t h o df o r s m o o t hp r o b l e m sa n d i t s e x t e n s i o nR E NY o n g h o n g,G U OZ h i r u i(S c h o o l o fM a t h e m a t i c s,L i a o n i n gN o r m a lU n i v e r s i t y,D a l i a n1 1 6 0 2 9,C h i n a)A b s t r a c t:N e w t o nsm e t h o d i so n eo f t h em o s t i m p o r t a n tm e t h o d s i ns c i e n t i f i cc a l c u l a t i o n.T h em a i nr e a s o nf o r t h e f a s t c a l c u l a t i o ns p e e do f s o m e i m p o r t a n tn u m e r i c a l c a l c u l a t i o nm e t h o d s i s t h a t i t i s r e-l a t e dt oN e w t o nsd i r e c t i o n.T h ec l a s s i c a lN e w t o nsm e t h o da n d i t s c o n v e r g e n c e t h e o r e mf o r f i n d i n gt h er o o to f a f u n c t i o no fo n ev a r i a b l ea r eb r i e f l yd e s c r i b e d,a n ds o m en o t e sa r eg i v e n.T h i sp a p e re x-p l a i n s t h ed i f f i c u l t i e si nt h ea n a l y s i so fu n i v a r i a t ef u n c t i o nt om u l t i v a r i a t em a p p i n g,a n dg i v e st h ec l a s s i c a lN e w t o nm e t h o da n dc o n v e r g e n c e t h e o r e mf o r s o l v i n gu n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m s.T h e s m o o t hm a p p i n g i s e x t e n d e d t o t h e s e m i-s m o o t hm a p p i n g,t h e s e m i-s m o o t hN e w t o nsm e t h o d i sp r o p o s e d,a n dt h ec o n v e r g e n c et h e o r e m o ft h es e m i-s m o o t h N e w t o ns m e t h o di sa n a l y z e da n dp r o v e d.T a k i n gs o l v i n gc o m p l e m e n t a r i t yp r o b l e ma s a ne x a m p l e,t h e s e m i-s m o o t hN e w t o nsm e t h o dh a saw i d ea p p l i c a t i o nb a c k g r o u n d.K e yw o r d s:c l a s s i c a lN e w t o nsm e t h o d;c o n v e r g e n c er a t e;s e m i-s m o o t hN e w t o nsm e t h o d