嗫?暁雲?
范文一：Shamanskii修正牛顿法的全局收敛性
曲 阜 师 范 大 学 学 报 第 29 卷 第 2 期 Vol . 29 No . 2
2003 年 4 月 Journal of Qufu Normal University Apr. 2003
Ξ
Sha manskii 修正牛顿法的全局收敛性
王长钰 , 陈元媛 , 杜守强
()第一作者 :男 ,65 岁 ,教授 ;博士生导师 ;曲阜师范大学运筹学研究所 ,273165 ,山东省曲阜市
摘要 :最近由 Lampariello F 和 Sciandrone M 提出了 Shamanskii 修正牛顿法的一种全局收敛技术 ,该文对其 全局收
敛性定理进行了改进和推广使其应用范围更加广泛.
关键词 :无约束优化 ; 全局收敛 ; Shamanskii 修正牛顿法 ; 超线性收敛
() 中图分类号 :O221. 2 文献标识码 :A 文章编号 :1001- 5337 200302- 0001- 03
1 引 言
我们考虑无约束优化问题
( ) min f x, n x ? Rn 1 n ) ( ( ( ) ) 其中 f : R?R为光滑函数. 假设 f x的 Hessian 阵存在 ,且梯度 g x与 Hx在 R上连续. 牛顿法是求解 此类问题的一种有效的方法 ,它一般的迭代公式为
- 1 ) ) ( ( x= x- Hxg x, k = 0 ,1 , . k +1 k kk
) ( 假设 Hx非奇异. 这种迭代形式的一个主要缺点是每次迭代都需要精确计算 Hessian 阵的逆 ,为了克服这 k
一缺点 ,在文献[ 2 ]中提出了 Shamanskii 修正牛顿法 ,其迭代公式为
α( ) () x= x- Dg x, k = 0 ,1 , , 1k +1 k kk k- 1 ) ) ( ( 其中 D= D= H^ x, j = 0 , 1 , , p - 1 ; i = 0 ,1 , , H^ x表示 Hessian 阵或 Hessian 阵的一个 适当修k ip+ j ipip
α) ( 改.为沿方向 d= - Dg x进行线搜索而得到的步长. 据我们所知 ,Shamanskii 修正牛顿法的全局 收敛技术k k kk
很久以来没有进展 ,直到最近 Lamapriello F 和 Sciandrone M 在文献[ 1 ]中提出了 Shamanskii 修正牛顿 法的一种全局收敛技术. 本文在其基础上 ,对收敛性结果进行了改进与有意义的推广 ,使此项技术的应用更 加广泛.
2 预备知识
首先我们给出几个基本假设.
( ) K表示 H^ x需要被计算的那些迭代的集合 ,即 K= { ip} , i = 0 ,1 , . N ipN T ( ) | g xd| kk + +( ) σ?R 为一强迫函数 ,即 aΠ k ? K, ‖d‖ ? N k σ‖d, 其中 : R k‖ σ( ) limt= 0 ] lim t= 0. kk k ?? k ??
( ) b任意一个无限子集 K Α K, N
T ( ) | g xd| kk ) ( lim ‖g x‖ = 0. = 0 ] lim kk ??, k ?K k ??, k ?K ‖d‖ k T ( ) ) ( c下降条件 g xd< 0="" 满足.="" kk="">
Ξ 收稿日期 :2002 - 10 - 04
()基金项目 :国家自然科学基金资助项目10171055
曲阜师范大学学报 (自然科学版) 2003 年2
() 文献[ 1 ]中采用如下线搜索 LS:
1γData :? 0 , δ() ?0 , 1. ,2
Step 0. 令 i = 0.
i δαStep 1. 令 =, 若 3 3 ( α) ( ) γα()f x+ d? f x- ‖d‖2 k kkk
αα成立 ,令 =停 ,否则 ,转 Step 2. k
Step 2. 令 i = i + 1 , 转 Step 1.
δ() α引理 1 总存在一个有限整数 i 使=满足 2式. k i
3 主要结果
在本节中 ,我们给出在更一般条件下的收敛性定理.
() α() ( ) ( ) ( ) 定理 设{ x} 是由迭代 1产生的序列 ,由线搜索 LS得到. 假设 a, b, c成立 , 又设 f 在水平集 kk n) ) ( ) ( ( ) ( L = { x ?R| f x?f x} 上有下界 , g x在包含 L 的一个开集上一致连续 ,则 lim ‖g x‖ = 0. 0kk ??
() ( ) ( ) () 证明 由 2式知 ,{ f x} 单调下降 ,再由条件 f 在水平集 L 上有下界 ,得{ f x} 收敛. 再由 2式得 kkαlim‖d‖= 0. k k k ?? T ( )dx kg kη现在证明必有 lim = 0 成立. 否则 ,存在无穷集 K′ < k="" ,以及=""> 0 ,使得 N N k ??, k ?K ‖d‖ k N T ( ) | g xd| kk
η()?, Π k ? K′. 3 N ‖d‖ k
c ( ) α( ) α设 N = { 0 ,1 , } , N := { k ?N | < :}="" ,="" n:="{" k="" |="" }="" ,0="">< :="">< 1.="" k="" k="">
c c ( ) ( ) αα( ) 情况 1 若 K′?N:是无穷集. 设 k ? K′? N: ,则 ?: . 又因为 ‖d‖?0 , k ??,所以 N N k k k
( ) ‖d‖= 0. 由假设 a得 k lim c ( )k ??, k ?K′ ? N: N T ) c ( | g xd| k k ( ( ) ) ?0 , k ? ?, k ? K′? N:. N σ ‖d‖ k T d| k ( )| g xkc 再由强迫函数的定义得 ( ( ) ) () 0 , k ?? , k K′? N:. 这与 3式矛盾. ?N ‖d‖ k 0 ( ) αδ() 情况 2 若 K′? N :是无穷集. 此时有 < :=""><= 1="" ,故由线搜索="" ls知="" n="" k="" 3ααk="" k="" 3="">
( ) ‖d‖ , k ? K′? N :. k N ) γ ( f - f x> - x+ dk k k δδ2αk T 2 d k αk ?( ) θ‖d‖ , k ? K′? N :,0 <>< 1="" ,="" 即="" k="" n="" k="" 再由中值定理得="" g="" θx+="" d="" ‖d="" γ="" k="" kk=""> - k δ‖ δT 2Tα( ) k α d g x d 2 k k kk )( g θ- g xx+ dk + d‖ , ‖k k k k ‖d‖ ‖d δk kγ > - ‖ δT T2 ) dα( g xdk kkk)αd 2 kk γ- δ()‖d‖, 4 > ( ) ( θk g x- g x+ kk k‖d‖ ‖d‖ δ k k
( ) θ其中 k ? K′?N :,0 < 1.="" n="" k="" ()="" 在="" 4式两端取极限得="">
T ( ) g xd kklim inf ?0. ( )k ??, k ?K′ ? N : ‖d‖ k N T T )) ( ( g x dg xd kkkk( ) () 由假设 c知 lim sup ?0 , 故 lim = 0 与 3式矛盾. ))( ( k ??, k ?K′ ? N : k ??, k ?K′ ? N : ‖d‖ ‖d‖ k k N N
第 2 期 王长钰等 :Shamanskii 修正牛顿法的全局收敛性 3
T ( ) g x d k k( ) 所以综合情况 1 与情况 2 知 lim = 0. 由假设 b得 k ??, k ?K ‖d‖ k N
lim ) ( ()‖g x‖ = 0. 5 kk ??, k ?K N
) ( ) ( Π k ?N ,一定存在整数 l k?[0 , p - 1 ] ,使 k + l k?K,由 N
( ) ( ) ( ( ( ) ) ( ) ) ‖g x‖ ? ‖g x- g xg xxg x‖ + + ‖- g ‖ + ‖‖ kkk k k k +1+ l ( k) - 1+ l ( k) + l ( k)
( ) l k- 1
( ) ( ) ( ) ‖g x- g x‖ + ‖g x‖. k + ik + i - 1k + l ( k) = 6i = 0 () ( ) 再由 5式及 g x一致连续得 lim ( ) ‖g x‖ = 0. 定理得证. kk ??
文献[ 1 ]中的收敛性定理即为下面的推论.
() α() ( ) ( ) ( ) 推论 设{ x} 是由迭代 1产生的序列 ,由线搜索 LS得到 ,假设 a, b, c成立 ,若{ x} 有界 ,则 序kk k列{ x} 的每一个极限点都为 f 的稳定点. k
4 讨 论
α本文采用的线搜索 ,在某些情况下易使步长 很小甚至趋于 0 ,这会在计算过程中导致一种病态现象. k
我们能否提出一种新的搜索技术使其不仅克服病态现象 ,同时也保证 Shamanskii 修正牛顿法的全局收敛性 及超线性收敛速度 ,这将是一个很有意义的研究课题.
参考文献 :
[ 1 ] Lamparillo F , Sciandrone M. Global convergence technique for the Newton method with periodic Hessian evaluation[J ] . J O T A , 2001 ,
() 111 2:341,358.
[ 2 ] Bertsekas D P. Constrained optimization and Lagrange multiplier methods[M]. New York :Academic Press ,1980.
THE GLOBAL CONVERGENCE OF A KIND OF
MODIFIED S HAMANS KII NEWTO N METHOD
WANG Chang- yu , CHEN Yuan- yuan , DU Shou- qiang
( )Institute of Operations Research , Qufu Normal University , 273165 , Qufu , Shandong , PRC
Abstract :Recently , Lampariello F and Sciandrone M propose a global convergence technique for modified Shaman2 skii Newton method. Their global convergence proposition is modified , so that it can be used widely.
Key words :unconstained optimization ; global convergence ; modified Shamanskii Newton method ; superlinear con2 vergence
范文二：【doc】Shamanskii修正牛顿法的全局收敛性
Shamanskii修正牛顿法的全局收敛性 第29卷第2期
2003年4月
曲阜师范大学
JournalofQufuNormalUniversity V01.29No.2
Apr.2003
Shamanskii修正牛顿法的全局收敛性
王长钰,陈元媛,杜守强
(第一作者:男,65岁,教授;博士生导师;曲阜师范大学运筹学研究所,273165,山东省曲阜市)
摘要:最近由Lamr,arielloF和SciandroneM提出了Shamanskii修正牛顿法的一种全局收敛技术,该文对其
全局收敛性定理进行了改进和推广使其应用范围更加广泛. 关键词:无约束优化;全局收敛;Shamanskii修正牛顿法;超线性收敛 中图分类号:0221.2文献标识码:A文章编号:1001.5337(2003)02—0001—03 1引言
我们考虑无约束优化问题
minf(),
ER
其中厂:R一R为光滑函数.假设l厂()的Hessian阵存在,且梯度g()与()在R上连续.牛顿法是求解
此类问题的一种有效的方法,它一般的迭代公式为
+l=一
()一g(),k=0,1,…….
假设H(瓢)非奇异.这种迭代形式的一个主要缺点是每次迭代都需要精确计算Hessian阵的逆,为了克服这
一
缺点,在文献[2]中提出了Shamanskii修正牛顿法,其迭代公式为 +l:—aDg(),=0,1,……,(1)
其中D=D?=Y/(x),,=0,1,……,P一1;i=0,1,……,Y/(x)表示Hessian阵或Hessian
阵的一个
适当修改.a为沿方向d=一Dg()进行线搜索而得到的步长.据我们所知,Shamanskii
修正牛顿法的全局
收敛技术很久以来没有进展,直到最近LamaprielloF和SciandroneM在文献[1]中
提出了Shamanskii修正牛顿
法的一种全局收敛技术.本文在其基础上,对收敛性结果进行了改进与有意义的推
广,使此项技术的应用更
加广泛.
2预备知识
首先我们给出几个基本假设.
表示k(x)需要被计算的那些迭代的集合,即={/p},i=0,1,……. (口)V?,IlIl?[】,其中盯:R一R为一强迫函数,即
im(t)=0lirat=0.
(b)任意一个无限子集KC,
[】:lim,kEllg)lI-0.m?【—1rJ=ul1g川u'
?收稿日期:20o2—10—04
基金项目:国家自然科学基金资助项目(10171055) 砸_r1}『ir丁?
2曲阜师范大学(自然科学版)2003生
(c)下降条件g(T<0满足.
文献[1]中采用如下线搜索(LS):
Data:y?(0,1),?(0,1).
Step0.令0.
Step1.令a:,若
f(+ad)?f()一yalldll
成立,令a=a停,否则,转Step2.
Step2.令=+l,转Step1.
引理l总存在一个有限整数使a=满足(2)式.
3主要结果
(2)
在节甲,我11]给出在史一股条仟卜的收敛性定理?
定理设{}是由迭代(1)产生的序列,a由线搜索(LS)得到.假设(0),(6),(c)成立,又设f在水平集
=
{ERIf()?(.)}上有下界,g()在包含的一个开集上一致连续,则liraIIg(札)II=0. 证明由(2)式知,{()}单调下降,再由条件在水平集L上有下界,得{()}收敛.再由(2)式得
limaIIdII=0.?
现在证明必有.
1im:0成立.否则,存在无穷集c,以及>0,使得
?,kC-K,llakII一"
?,v居?.(3)—]r]T_一?,?^,v.(_j
设N={0,1,……},N(f)={kENla<f},(f)={kENla?f},0<f<1. 情况1若Kn()是无穷集.设kEn(e),则a?.又因为alldll一0,(后一?),所以 limlldkll=0.由假设(a)得
'*.k?KNntt)
【】一0,(后一?,?n()).
再由强迫函数的定义得一0,(后一?,后Kn()).这与(3)式矛盾. 情况2若nN()是无穷集.此时有a<<.=1,故由线搜索(LS)知 (钆+缸)一儿)>一y()llll,J}En).
再由中值定理得g(+警)?1厂妄_不_>一y()IIII,后?Kn?(e),0<<l,即 [g(_g(】+>一y()IIII,
>
[)】一y(詈)IIII,(4)
其中kEKnN(f),0<<1. 在(4)式两端取极限得
一ikmC-N,?.?(r)llnll
由假设(c)知l
,
im
?
su
n
p,?.,故
,
l
?
iran,:.与(3)式矛盾.
一T
第2期王长钰等:Shamanskii修正牛顿法的全局收敛性3 所以综合情况1号隋况2知lim:0.由假设(6)得 ?.?x.,ll口^ll
lim
,
【Ig()【l=0?(5)
Vk?N,一定存在整数f(k)?[0,P一1],使k+f(k)?觚,由 llg(x)ll?llg()一g(+1)ll+…+llg(+f(1)一g(x())ll+llg(+f())ll
f()一1
=
?llg(x)一g(x一.)ll+llg(x?)l『.
再由(5)式及g()一致连续得limllg()ll=0.定理得证.
文献[1]中的收敛性定理即为下面的推论.
推论设{}是由迭代(1)产生的序列,a由线搜索(LS)得到,假设(a),(b),(C)成立,若{}有
界,则
序列{}的每一个极限点都为厂的稳定点.
4讨论
本文采用的线搜索,在某些情况下易使步长a很小甚至趋于0,这会在计算过程中
导致一种病态现象.
我们能否提出一种新的搜索技术使其不仅克服病态现象,同时也保证Shamanskii
修正牛顿法的全局收敛性
及超线性收敛速度,这将是一个很有意义的研究课题.
参考文献:
[1]IAt//It~OF,SciandroneM.GlobalconvergencetechniquefortheNewtonmethodwithperiodicHessianevaluation[J].JOTA,2001,
111(2):341—358.
[2]BertsekasDP.ConstrainedoptimizationandIagrangemultipliermethods[M].NewYork:AcademicPress,1980.
THEGLoBALCoNERGENCEoFAKINDoF
【0ID?『1咂DSHAMANSK?NE?,rI1oNMTHoD
WANGChang-yu,CHENYuan-yuan,DUShou-qiang
(InstituteofOperationsResearch,QufuNormalUniversity,273165,Qufu,Shandong,PRC) Abstract:Recently,LamparielloFandSciandmneMproposeaglobalconvergencetechniqueformodifiedShaman—
skiiNewtonmethod.Theirglobalconvergencepropositionismodified,SOthatitCallbeusedwidely.
Keywords:unconstainedoptimization;globalconvergence;modifiedShamanskiiNewtonmethod;superlinearconv—
ergence
一+『『.百丁丁
范文三：一维凸函数牛顿法的全局收敛性及其应用
一维凸函数牛顿法的全局收敛性及其应用
2002年12月
Dec.,2002
应用数学与计算数学
C0MM.0NAPPL.MATH.ANDC0MPUT
第16卷第2期
VO1.16No.2
一
维凸函数牛顿法的全局收敛性及其应用 徐勤亚
(上海大学数学系,上海,200436)
在一般假设条件下, 摘要:牛顿法是求解非线性方程F(z)=0的一种经典方法.牛顿法只具有局部收敛性.本文证明了一维凸函数牛顿法的全局收敛性,并且给出
了它在
全局优化积分水平集方法中的应用. 关键词:全局优化,牛顿法,全局收敛.
1.引言
考虑非线性方程
F)=0
其中F:R"-+R"是具有如下性质的非线性映射: (1)存在?R"满足F)=0.
(2)F在的某一领域内是连续的.
(3)F()非奇异.
求解问题(1.1)的一个经典算法是牛顿法. 代{):
令k:=0,若F(xk)=0,则算法终止;
给定一初始点XO,计算如下序列{8)和迭
否则,求解方程F()8=一F();
置Xk+l:=Xk+8k.
牛顿法的一个突出优点是:当初始点靠近方程的根时,牛顿法的收敛速度很 快.事实上,牛顿法的收敛速度是衡量其他解决问题(1.1)的方法收敛速度的一个标 准.然而,当初始点0远离方程的根时,牛顿法的收敛性得不到保证.在实际应 用中,我们一般不能给定一个足够好的初始点0,以使得迭代序列收敛于.因此, 牛顿法收敛性的研究是非常必要的.
2.一维凸函数牛顿法的全局收敛性
定理2.1假定f:R---),R在凸集J[)上可微.,是凸的当且仅当
f(Y)一f(x)ft()(一)Vx,g?R
定理2.2假设f:R---),R是连续可微的凸函数;对任意?R,ft()?0.而且 假设f(x)=0有一个解.那么,对任意初始点X0?R,若,()>0对所有都成 立,则牛顿法产生的迭代序列
Xk+1=Xk—ft()一f(xk)(k=0,1,…)
本文2002年4月17日收到
2期徐勤亚:一维凸函数牛顿法的全局收敛性及其应用69 单调递减且收敛于(若,()<0,则单调递增收敛于),而且是唯一的. 证明对任意XO?R,不妨假设f(x)>0,对所有都成立.下面我们将证明序列 {)单调递减且收敛于.由函数凸性及迭代公式可以得到
f(xk)f(xk一1)+,(一1)(一一1)=0(k=1,2…)
由函数的单调性得到:
,(k=1,2,…).
由已知条件得:
Xk+l=一,()一f(xk)
所以我们得到:+1.由此推导出.1im存在.
下面证明极限为.由f(xk)=,)(一+1)可得:
f(xlc)II,)忪一Xk+lI.
令k_?O0,则If(x)I=0,所以f(x)=0.
下面证明的唯一性.设和Y是f(x)=0的不同的两个根.我们有:
0=f(x)一f(Y),(!,)(一!,),
所以Y.同理我们得到Y.即证得:=Y. 3.应用
考虑如下的全局优化问题
(P))
其中,在有界闭箱D?R上连续.定义水平集 Hc={?DIf(x)c).
(3.1)
(3.2)
我们给出了问题(3.1)和求一维凸函数(c)根的等价性.水平值函数vf:R_?R
定义如下;
Yf(c)=/(c一,c())dx(3.3))J 另一水平值函数(c:)
(c)=/(c—fc(x))dx(3.4)J 其中
=
三(3.5)
70应用数学与计算数学16卷
我们给出水平函数和,的一些性质. 定理3.1设,()在紧集D上连续,则Ys(c)是非负,单调不减的凸函数,
(c)=2(c一,c(
『(c)=2/D(
其中?=
证明(1)由定义可知:
(c)=?l.
im
.+.
—
vs(—
c+~c)-一
vs(c)
=
…
lim
.c+Ac-一-,c(叫
=
…
lim
.…\日
(c+Ac-,(c +/[(c+Ac一,())一c—So())]dI
由S(x)在D上连续可知: ?
l
.
im
_?o
(日c+?c)(日c)' 当?H.+?.\日.,我仃]有 C<S(x)C-4-Ac
此蕴含有
(C-4-Ac一,())AC 由(3.8),我们可推得: .
日
(c+Ac-?c(c+?c))
当Ac0,有
h--/ccTAc\Hc (c+Ac-训?
此外,我们可推知:
一
lim
.
1[(c+Ac-
_(c-,(
=
?
li
.
m
.+.1/HAc(2c+Ac-2f())
=
2(c_,(
一
厂n(c一,c(
2期徐勤亚:一维凸函数牛顿法的全局收敛性及其应用71
由式(3.11),(3.12),我们有 (c)=2(c一))(3.13) (2)由二r导数足义日J知: 州:…lim.
=
…
lim
.
[厶,,H(c+Ac-
+[c+Ac-))_(c—))]]
=
2(Hc)
=
2
厂nx()(3.14)
?Hcf3
.
15)
?D\,
由式(3.6),(3.12)和(3.14)可知:(c)为非负,单调不减,凸的.
下面我们可以用(c)和Ml(c)的函数性质,讨论(c)=0或Ml(c)=0与原问
题(P)的全局最优值c之间的关系. 定理3.2如果f(x)在D上连续,c是原问题(P)的全局最优值的充分必要条件
为
(c)=0或Mf(c)=0(3.16) 其中H.?={xlf(x)c,?D)?.
证明(充分性)由于f(x)在D上连续,我们易知,c()在D上连续.由于c一,c?()?
0,?D,故由(c)=0或Ml(c)=0,我们有: (c一fc+())=0
或
c一,c+()=0
因此,对一切的?D,c一,c.()=0.由fc+()定义,可知 =
三'
由此可推知:
f(x)=c,?Hc+.
即:
Hc.={lf(x)c,?D)={lf(x)=c,?D)
(3.17)
(3.18)
(3.19)
10
,??,,【
=
CH
X
中
其
72应用数学与计算数学16卷
换言之,c为/(x)在D上的全局最小值.
(必要性)若c为/(x)在D上的全局最优值,则
Hc?={zI/(x)c,z?D)?.
下面证明intHc??.反证.若intHc+?,则一定存在XO?intHc.,使得/(xo)
与c为原问题(P)的全局极小值矛盾.故
Hc=OHc?={zI,(z),z?D).
(3.20)
<c,此
(3.21)
c为原问题的全局最小值.
事实上,求解问题(3.1)能被转化成求解一维非负递增凸函数(c)的第一个根. 在第二节中我们介绍的一维牛顿法可以用来求解方程(c)=0的根. 参考文献
【1]J.M.OtegaandW.C.Rheinboldt,IterativeSolutionofNonlinearEquationinSeveralVar
iables,
AcademicPress,NewYouk,1970.
I2】
JoseMarioMartinez,LocalConvergenceTheoryofInexactNewtonMethodsbasedonStruc—
turedleastchangeupdats,MathematicsofComputation,Vb1.55,No.191,(7)1990,143—
167.
[3】袁亚湘,孙文瑜:最优化理论和方法,科学出版社,北京,1999.
【4】
RonS.Dembo.Stanley,C.EisenstatandTrondSteihang,InexactNewtonMethods,SIAM J.Numer.Ana1.,V0l19,No.2,400—408,1982.
[5】
R.HorstandH.Tuy,GlobalOptimization:DeterministicApproaches,2ndEdition,Springer. Verlag,Heidelberg,1993.
I6】
MieczyslawAltman,Iterativemethodsofcontractordirections,NonlinearAnalysis:Theory,
MethodsandApplications.4(1980),PP.761—772.
TheGlobalConvergenceoftheNewtonMethod
QINYAXU
(MathematicsDepartment,ShanghaiUniversity,Shanghai20o毒36)
Abstract
NewtonmethodisaclassicalmethodtothenonlinearequationF(x1=0.Itiswell knownthattheNewtonmethodischaracterizedasalocalconvergencealgorithm.However weoftenmeetsomepracticalproblemswhichrequirethefunctionhavethepropertyofglobal convergence.Inthispaper,weprovideglobalconvergenceresultsforNewtonmethodswhen thefunctionsareconvexfunctionsofonedimension.
keywords:Golbaloptimization,Newtonmethod,globalconvergence.
范文四：牛顿迭代的收敛证明
黑 龙 江 科 技 学 院
(计算机与信息工程学院??)
《计算方法》课程论文
牛顿迭代的?收敛条件
班 级: 计算机控制?07-3班 学 号: 29号
姓 名: 韩静
授课教师: 才智 论文成绩:
2009年?5月
1 《计算方法》课程论文
牛顿迭代的?收敛条件
韩静
(黑龙江科技?学院 计算机与信?息工程学院?)
摘 要:给出了牛顿?迭代的广义?收敛条件，并在Ban?ach空间?中建立相应?的收敛定理?。 牛顿迭代法?x0采取的?在此基础上?，找到超过x?0附近的方?程的分步迭?代法，以便找到
更?接近的根源?近似方程。如何利用函?数f ( x )的泰勒级数?前面的一些?方程找到函?
数f ( x ) = 0的根。牛顿迭代方?程的根的重?要方法之一?，其最大的优?点是在方程?f ( x ) = 0有一个单?一的广场附?近的收敛性?，该方法还可?以用来重新?排序方程根?。
关键词:牛顿迭代;优序列;收敛性
On The Conve?rgenc?e Condi?tion Of Newto?n`s Metho?d
Han Jing
(Compu?ter & Infor?matio?n Engin?eerin?g Depar?tment?., Heilo?ngjia?ng Insti?tute of Scien?ce & Techn?ology?)
Abstr?act: A gener?alize?d conve?rgenc?e condi?tion for Newti?on`s metho?d is given? and the corrs?pondi?ng conve?rgenc?e theor?em is estab?lishe?d. Newto?n itera?tive metho?d is based? on diffe?renti?al, diffe?renti?al is used to repla?ce the strai?ght-line curve?, becau?se of irreg?ular curve?s, then we study? a strai?ght line inste?ad of curve?s, the remai?ning diffe?rence? is infin?itesi?mal high-end, high-end if it is infin?itesi?mal, Newto?n itera?tion x0 are taken?, the On this basis?, to find more than the near x0 of the equat?ion with the step-by-step itera?tion in order? to find close?r to the root of the appro?ximat?e equat?ions with. Ways to use funct?ion f (x) the Taylo?r serie?s in front? of a numbe?r of equat?ions to find f (x) = 0 root. Newto?n itera?tion equat?ions are the root for one of the
impor?tant ways, its great?est stren?gth is in the equat?ion f (x) = 0 has a singl?e squar?e of near conve?rgenc?e, and the metho?d can also be used to re-order? equat?ion root.
Key words?: Newto?n`s metho?d ; major?izing? princ?iple ; conve?rgenc?e
1 引言
设f: 是Bana?ch空间E?的某个凸区?域D到同空?间F的非线?性算子，众
所周知，牛顿迭代
2 《计算方法》课程论文
是求解下述?方程最有效?的方法
Kanto?rovic?h L 曾用优函数?分析了牛顿?迭代法的收?敛性。有关这方面?的文献还有?。但其中大部?分的收敛条?件都是:f的一阶导?数满足Li?pschi?tz条件或?者二阶导数?在区域D上?一致有界。这样的条件?通常称为K?antor?ovich?类型的收敛?条件。然而，在很多情况?下，由于函数非?解析而不能?满足条件，为此，有人提出了?收敛的弱条?件。所谓弱条件?指:函数的二阶?导数在区域?内将受到某?一相关函数?的约束，而不是某一?常数。
2 预备知识
为了建立B?anach?空间上牛顿?迭代的收敛?定理，我们先来分?析牛顿迭代?对实函数的?收敛性。实事上，它就是牛顿?迭代的优函?数，定义如下:
引理1
证明引理1?
如果定义
3 《计算方法》课程论文
我们用数学?归纳法证明?
显然，当N=0时成立，设对某个N?时，上式成立，由引理1可?得和，因此有意义?且，由归纳证明?可知序列{tn}收敛的。
引理3
在前面的假?设条件下有?:
4 《计算方法》课程论文
3 主要定理
5 《计算方法》课程论文
4 比较
6 《计算方法》课程论文
参考文献:
1 Kysov?skii L.The major?ant princ?iple and newto?n`s metho?d. Dok Akod Nauk SSSR,1951,8(76):17~20 2 Altma?n M. A genee?ral major?ant princ?iple for funci?tonal? equat?ions. Bull Acad Polon? Sci Ser Math Astro?nom Phys,1961(9):745~750
3 Gragg? W B,Tapia?: R A.Optim?al error? bound?s for the Newto?n-Kanto?rovic?h theor?em.SIAM J Numer? Anal,1974(11):10~13
4 Orteg?a J .The Newto?n-Kanto?rovic?h theor?em.Amer Math Month?ly,1968(75):658~660 徐翠薇 计算方法引?论[M].北京:高等教育出?版社，1997. 5
6 数值分析
范文五：一类非拟牛顿算法的全局收敛性
一类非拟牛顿算法的全局收敛性
3 1 1 2 军张长海, 王玉学, 张立凡,
( 11 大庆石油学院 数学系 ,黑龙江 安达 151400 ; 21 辽河油田职工大学 成教部 ,辽宁 盘锦 124000 ; 31 大庆市工商 张 )局 计算中心 ,黑龙江 大庆 163000
摘 要 :在一定条件下 ,对于一致凸的目标函数 , 证明了带有 Goldstein 线搜索的无约束最优化问题的一类非拟牛顿 算法的全局收敛性.
关 键 词 : 线搜索 ; 非拟牛顿算法 ; 无约束最优化 ; 全局收敛性
中图分类号 :O242 . 23 文献标识码 :A 文章编号 :1000 - 1891 (2001) 02 - 0072 - 04
n ( ) ( ) 对于无约束最优化问题 min f x, x ? R, 假设 f ( x) 二阶连续可微 ,记 f = f ( x ) , g = v f x , k k k k
2 ( ) y= g- g, G= v f x, s = x- x. k k + 1 k k k k k + 1 k 1算法 A 考虑迭代
- 1 ()1 αx = x+ d, d= - B g, k + 1k k k k k k
式中 : B 为 G的近似矩阵 ;α为搜索步长. k k k
令由 B 产生的修正矩阵 B 满足非拟牛顿方程为 k k + 1
T ( ) ()Qt, t ?[ 0 ,1 ] , 2 s B s = k k k + 1 kT T α( ) ) ( ) (式中 : s = d, Qt= ts y+ 2 1 - tf - f - s g. k k k k k k k + 1 k k k
θ由此导出具有双参数 t ,的校正公式为 k
T ( ) Qt B s s B T T k k k kk ()( θ) 3 θ+ B t ,= B - yy + vv , k + 1 k k T T k k k k k2 ( )y s s B s k k kk k
1 yB s k k kT 2 - ) ( 式中 : v= s B sT . T k k k k y s s B s k k k k k
() θ当= 1 时 ,式 3成为 k T T T B s y + ys B yy k k k k k kT k k ( ) ( ) )()( . B t = B - + Qt + s B s 4 k + 1 k T k k k k T 2 ( )y s s y k kk k
- 1 () 当 t = 1 时 ,式 4即为著名的 DFP 公式. 记 H= B ,则 k k T T Hyy H s s k k k k k k ( ) ()+ . Ht= H- 5 k + 1 k T ( )Qt k y Hy k k k
n 假设 (a) f ( x) 在 R中二阶连续可微 ; ( b) 存在常数 m 和 M ,0 < m="">< m="" ,使="">
T 2 2 n m ‖y ‖? yG ( x) y ?M ‖y ‖, ()Π x , y ? R, 6
( ) ( ) 式中 : G x为 f x在点 x 处的 Hesse 矩阵.
引理 1T 2 y‖‖s y k kk ()? m ? ? M , k 7 = 1 ,2 , , T ‖s ‖ k s y k k
收稿日期 :2001 - 02 - 21 ;审稿人 : 王守田
() 作者简介 :张长海1947 - ,男 ,副教授 ,主要从事微分方程数值解与最优化方面的研究.
?72 ?
第 2 期 张长海等 :一类非拟牛顿算法的全局收敛性
? ? T T α()g Hg8 = - s g< +="" k="" k="" k="" kk="" k="" 6="" 6="" k="1" k="1">
σ) (TT T 2 1 - M ρ) (2 1 - M ()? s y?- 9 - s, gs g, k = 1 ,2 ,3 , k kk kk k 2 M - m m ρσρσσ( ) ρ式中 :,为常数 ,适合 0 < 1="" ,且,,="" s,="" g满足不等式="" goldstein="" 线搜索:="" k="" k="" t="" t="" (="" )="" (="" )="" ρ(="" )="" (="" )f="" x+="" s="" x+="" g="" s="" ;="" f="" x+="" s="" x="" σ+="" g="" s="" .="" k="" k="" k="" k="" k="" k="" k="" k="" k="" k="">
β( ) β引理 2 设 a> 0 , b> 0 , k = 1 ,2 , ,且存在正的常数,,使得 k k 1 2
k - 1
βαβb?+ , k()= 1 ,2 ,3 , , 10 k 1 2 j 6 j = 1 ? ? a k 并且< +="" 则="">< +="" k="" 6="" 6="" b="" k="" k="1" k="1">
引理 3 对任意 k ?1 及 t ?0 ,1 ] ,恒有
TT M m ( )s ? Qt ? s y.()11 y k k k k kmM
( ) 证明 由 Qt的定义及泰勒中值定理得 k T T k ) ( ( ) ) (( ) ( ) + 2 1 - t [ f x v f x s ] = Qt = ts y- f x- k + 1k k k kk T T 2 ) ( ) (+ 1 - t s v f xs . k k k ts y k k
() ( ) 式中 : x介于 x和 x之间. 由假设 a, b得 k k + 1 k T 2 2 2 ( ) m ‖s‖ ? s v f xs ?M ‖s ‖ , k k k kk () 又由式 7得 T T s y s yk kk k2 ? ‖s ‖? , k M m
T T T m m ( ) ) (故Qt ? ts y+ 1 - t s y? s y,k k k k kk k M M
T TT M M ( ) ) (且? s y.Qt? ts y+ 1 - ts yk k k k k k k m m
() 即式 11成立.
引理 4 对任何 k ?1 ,有
k
α()? kC , 12 j6 j = 1
式中 : C > 0 为常数.
证明 利用引理 3 和文献2 ]中相应引理.
引理 5T ()13 = 0 . lim g Hg k k k
() 证明 由 g= g+ y和式 5可得 k + 1 k k T T T T g Hg= y Hy+ 2 g Hy+ g Hg= k + 1 k + 1 k + 1k k + 1 kk k + 1 kk k + 1 k TT T T 22 2 ( ) ( ) ( ) s ys y gH y s g T k k k k k k k k k ()14 + 2 + , s g+ gHg- k k k k k T ( )( )( )Qt Qt Qt k k k y Hy k k k
T T 2 2) ( ) ( gH y Ts g Tk k k k k + 1 于是()- H g + . = g H gg15 k + 1 k +1 k + 1 k k k T ( )Qt k y Hg k k k
() 将式 15的下标换成 j ,并在两端对 j 从 1 到 k 求和 ,得 TTk k 2 2 ( ( ))g s Hy g j j j T T j j + 1 ()16 - g Hg+ , = gHg k + 1 k + 1 k + 11 1 1T 6 6 ( )Q t j j = 1 y Hgj = 1 j k j
?73 ?
大 庆 石 油 学 院 学 报 第 25 卷 2001 年
() () () 但由式 11, 8和 9可得 T 2 T k k 2 ( )) s g ( s g T T j j j j + 1 M ?+ 2 s g + s y T?j jj j6 6 ( )Q t m s yj j = 1 j = 1 j j
k 2 2 Tσ ρ) (σ) () ( M 2 2- 1Mm - m + 4 1 - 1 - M ( )()-sg 17 . j j 6 (σ) m 2 1 - Mm j = 1
ρσρσ因对任何满足 0 < 1="" 的和均有="" :="" 22="" 2="" ρ)="" (σ)="" σ)="" σ="" ((()="" (σ="" +="" 4="" 1="" -="" 1="" -="" m=""> 2 [ 1 - + 2- 1] Mm + ) 2 2- 1Mm - m 2 22 2σ () (σ) > 2- 1m ?0 , [ 2 1 - - 1 ] m
() () 故由式 8和 17得 T? 2 ( )s g j j + 1 ()?. 18 < +="" 6="" )(q="" t="" j="" j="1">
() 从而由式 16得 TT? ? 2 2 ( )( )g Hy s g j j j T j j + 1 ()?. 19 < ghg+="">< +="" 1="" 1="" 1t="" 6="" 6="" (="" )="" q="" t="" j="" y="" hy="" j="1" j="" j="" jj="1">
? TT α 由式 (16) , (18) 和 (19) 知 : lim gH g 存在 ,如果 lim ( ) < +="" 这与式="" g="" h="" g=""> 0 ,则由式 8知 :k k k k k k k 6 k ?? k = 1
() () 12矛盾 ,故式 13成立. T T T - s gg Hgg Hg k kk k kk k k() ( ) = 0 ,从而数列 存在一个子列单调下降 ,趋于 令 r= ,则由式 9, 13和 lim k T r r kks y k k
零.
3 ) ( 引理 6 对于 l = mΠM,有
2 2 ()1 , ,1 . ‖g‖ ? l ‖g‖ , j = k , k - 20 j k + 1
证明 见文献[ 3 ] .
() ( ) 定理 假设 a, b成立 ,{ x}为由算法 A 产生的点列 ,如果下列两个条件之一成立 :k
T g Hg k k k2 2 2 () i‖g‖ - ‖g‖ + ‖g‖ = O , k + 1 k k r k T g Hg k k km m () ii当 k 充分大时 , σ, 单调下降 ,且< +="" l="" 1="" -="" r2="" m="" 2="" m="">
3 ( ) 则算法 A 具有全局收敛性 ,即点列{ x}收敛于 f x的唯一极小点 x . k
) ( () ( ) 证明 由假设 a, b可知 , f x为二阶连续可微的一致凸函数 ,因此 ,只须证明
lim inf ‖g‖ = 0 .k k
在式 (5) 两边求迹得
T 2 ‖y‖ y B s k k kk T ) ( ) ( ( ))( ()tr B = tr B - 2 + Qt + s B s , 21 k + 1 k k k k k T T 2 ( )y s s y k k k k
T T s yg Hgj j j j j () () () 将式 21递推 ,并由式 9和 11及 = 得α jr jT k k 2 ‖y‖ y B s T j j jj )) ( ( ))( ( ( )tr B = tr B- 2 Qt + s Bs + ?tr B + k + 1 1 j j j j 1 T T 2 6 6 ( )y s j = 1 s y j = 1 j jj j
2 2 2 k k 2 ( ) r‖g‖ - ‖g‖ - ‖y‖ ()j j + 1 j j 2 M - m M ()α22 + + k .jT 6 6 m σ) (2 1 - g Hg = 1 j = 1 j j j j
() ε 设条件 i成立 ,用反证法 ,假设lim inf ‖g‖> 0 ,则存在> 0 ,使得k k
()ε23 k = 1 ,2 ,3 , . ‖g‖ ?, k
?74 ?
第 2 期 张长海等 :一类非拟牛顿算法的全局收敛性
() 由条件 i知 ,存在常数 L > 0 ,使得 T g Hg2 2 2 j j j ‖g‖ - ‖g‖ - ‖y‖ ?L , j + 1 j j r j 2 2 2 )( g‖ ‖y‖ ‖r‖g‖ - - j j j j + 1 即?L , j = 1 ,2 . ()24 T g Hg j j j
() () () 由式 22, 24和 13得 k 2 mL + M2 M - m ) ) ( ( tr B ?tr B+ k + 1 1 α.()25 + j 6 (σ) 2 - 1 Cm j = 1 2 ‖g‖ k () () ) ( 由式 23和 8及 tr B ?‖B ‖? 知 : k k T g Hg k k k T ? ? ? α ( )g Hg T k k k k 1 ()αα? ?< +="" 26="" g="" hgk="" k="" k="" k="" k2="" 2="" 6="" 6="" 6="" (="" )tr="" b="" ‖g="" ε="" ‖k="" k="" k="1" k="1" k="1">
?
() () α() 由引理 2 及式 25和 26知 < +="" 这与式="" 12矛盾="" ,故lim="" inf="" ‖g‖="0" .k="" k="" 6="" k="" k="1">
() () mΠ2 M] 1 - l 1 - () () λ 令假设条件 ii成立 ,仍反设lim inf ‖g‖> 0 ,则式 23成立 ,令=则 ,k k σ1 -
λ ()0 <>< 1="" .="" 27="" ()="" 由条件="" ii知="" ,存在正整数="" k,使得当="" k="" 时="" ,0="" 0="">
T T T g Hgg Hg k k kk + 1 k + 1 k + 1 g Hg0 0 0 0 0 0 k k k () ??? ?28 , r rr kkk + 1 0 0
() () () 为简便计 ,不妨设 k= 1. 由式 28, 9和 20可得 0
k 222 22 ‖‖- ‖y ‖) ‖‖( r ‖g - ‖g ‖g r ‖g r j j + 1 j j k + 1 k + 1 1 1 ?- - T T T 6 j = 1 g Hgg HggHg j j j1 1 1k + 1 k + 1 k + 1
k 2 r ‖‖g r j + 1 j r k + 1 1 2 2 () - ( TTr1 - l- ‖g‖ l = ‖g‖ - k + 1 k + 1 T T 1 6 g Hgg Hg j j jg HggHg j = 1 j + 1 j + 1 j + 1k + 1 k + 1 k + 11 1 1
m 2 ()1 - l 1 - ‖g‖ k +1 2 2 M ) ()l ‖g‖? ?λ‖B ‖ ?tr ( B )λ. 29 k + 1 k + 1 k + 1 T (σ)1 - g Hgk + 1 k +1 k + 1
() () () () 故由式 22, 29和 27及 12得
k 2 )( t r B M 1 2 M - m α)( .()tr + B ? +30 k + 1 j 6 (λ) λ 1 - C 1 - m(λ) (σ)2 1 - 1 - j = 1 ? () () () () () α因式 30与式 25具有相同的形式 ,且此时式 26成立 ,从而由式 27, 30和引理 2 可知 ,
() + ?与式 12矛盾. 故lim inf ‖g‖= 0 ,定理得证.k k
参考文献 :
陈兰平 ,焦宝聪. 一类非拟 Newton 算法及其收敛性J . 应用数学与计算数学学报 ,1997 ,13 (1) :9,17 . 1 () 张长海 ,王玉学. Goldstein 线搜索下 DFP 算法的全局收敛性J . 大庆石油学院学报 ,2001 ,25 1:76,80 . 2 () 徐大川. DFP 算法的全局收敛性分析J . 计算数学 ,1997 ,19 3:287,292 . 3
?75 ?
Abstracts Journal of Daqing Petroleum Institute Vol . 25 No . 2 J un. 2001 Key word : agile manufacture ; management technique ; integration ; application
() Global convergence property of a cla ss of non2qua si2Ne wton algorithmsΠ2001 ,25 2:72,75 1 1 2 3ZHANG Chang2hai, WANG Yu2xue,ZHANG Li2fan, ZHANG J un
( 1 . Dept of Mathematics , Daqing Petroleum Institute , A nda , Heilongjiang 151400 , China ; 2 . Dept of A dult Edu2 cation , Worker’s Collge of L iaohe Oil Field , Panjin , L iaoning 124000 , China ; 3. Computer Center of Daqing Com2
)mercial Aff airs B ureau , Daqing , Heilongjiang 163000 , China
Abstract : In this paper , under some conditions , we prove the global convergence property of a class of non2quasi2 Newton algorithms for uncontrained optimization problems with Goldstein line search on uniformly convex objective function.
Key words : line search ; non2quasi2Newton algorithms ; unconstrained optimization ; global convergence
() A multi2layer match method f or prediction of production dyna mic of oil or ga s f iledΠ2001 ,25 2:76,78 1 2 2 2 2PENG Xiao2long, FAN J i2zong, ZHAO Yu2ping, SHU Dao2min, ZHANG Ying
( 1 . Dept of Petroleum Engineering , Southwest Petrolum Insitute , N anchong , Sichuan 637000 , China ; 2.
)Zhongyuan Oil Field S ubcompany , Puyang , Henan 457001 , China
() Abstract : A Multi2layer match method of combining classic development model with CDM2 ,1model established by method of cent difference is hold out based on analyzing vary models established by method of centered difference . This method can accurately predict dynamic variety law of production of oil or gas field , it can avoid effect of production wave , then , the error will be under 4 %.
Key words : multi2layer match ; centered difference model ; dynamic simulation ; output prediction
() Application of the economic limited line to oil f ield developmentΠ2001 ,25 2:79,81 1 1 1 2 1ZHAO Yu2ping, WANG Xiu2zhi, FAN ji2zong, L I Feng2jun, ZHANG Ying
( 1 . Zhongyuan Oil Field S ubcompany , Puyang , Henan 457001 , China ; 2. Oil Recovery Plant No. 10 , Daqing
)Oil Field Corp. Ltd . , Daqing , Heilongjiang 151206 , China
Abstract : We have established mathematical model of increasing production limited line of dense well and stimulation well limited line and shut in economic limited line with the application of microeconomic principle and the feature of oil field development . The value of correlation parameters are determined and the concrete application of economic limited line in oil field is discussed here . Under the condition of technology level and management level , economic limited line declines with oil price increasing , contrariwise it increases. With the fixed oil price , the advance of management level can also decline marginal cost and economic limited line . The oil development economic estimate by application of eco2 nomic limited value can provide the gist for gaining the best profit in oil field companies which vary from output type to profit type .
Key words : adjust well ; stimulation well ; well shut in ; cost ; economic limited line ; oil field development
() Fea sibility of photocatalytic oxidation of degra ding polyacryla mide in waterΠ2001 ,25 2:82,83 1 2 1 3 4CHEN Ying, CUI J un2ming, WANG Bao2hui, L I Shu2qin,L IU J u
( 1 . Dept of Petrochemical Engineering , Daqing Petroleum Institute , A nda , Heilongjiang 151400 , China ; 2. Partial Polymer Plant of Daqing Ref inery Company , Daqing , Heilongjiang 163411 , China ; 3 . Center of S ale , Daqing Pet2 rochemical Company , Daqing , Heilongjiang 163711 , China ; 4. Designing Institute of Zhongyuan Oilf ield Petro2
)chemical Complex , Puyang , Henan 457165 , China
Abstact : Oily sewage is very difficult to dispose of in the polymer flooding. Photocatalytic oxidation degrading polyac2
( ) rylamide PAMin water by using semiconductor TiOas catalyst was investigated. The result showed that the lamp2 2
house catalyst was necessary to oxidize PAM in water , energy distributing and intensity of lamp2house remarkably af2 fected the reaction and degradation speed of oil sewage . It is a good method to treat PAM in water by photocatalytic ox2 idation.
?108 ?
转载请注明出处范文大全网 » Shamanskii修正牛顿
