解无约束最优化的基于锥模型的过滤集_信赖域方法_孙文瑜(1).pdf

中国科学:数学2012年第42卷第5期:527∼543
www.springerlink.commath.scichina.com

解无约束最优化的基于锥模型的过滤集-信赖域
方法

孙文瑜¬­∗,徐东¬­
¬南京师范大学数学科学学院,南京210046;
­江苏省大规模复杂系统数值模拟重点实验室,南京210046
E-mail:[e-mail]

收稿日期:2012-02-21;接受日期:2012-03-19;*通信作者
国家自然科学基金(批准号:11071122,11171159)和教育部博士点基金(批准号:20103207110002)资助项目

摘要锥模型优化方法是一类非二次模型优化方法,它在每次迭代中比标准的二次模型方法含有更丰
富的插值信息.Di和Sun(1996)提出了解无约束优化问题的锥模型信赖域方法.本文根据Fletcher和
Leyffer(2002)的过滤集技术的思想,在Di和Sun(1996)工作的基础上,提出了解无约束优化问题的
基于锥模型的过滤集信赖域算法.在适当的条件下,我们证明了新算法的收敛性.有限的数值试验结
果表明新算法是有效的.
关键词无约束优化锥模型信赖域方法过滤集方法收敛性
MSC(2010)主题分类65K05,90C30

1引言

本文考虑解无约束优化问题
minf(x);(1.1)
x2Rn
其中f:Rn!R是连续可微函数.解最优化问题(1.1)的数值方法通常基于目标函数的二次模型
1
q(d)=f(x)+gTd+dTBd;(1.2)
kk2k
22
其中,gk=rf(xk);Bk=rf(xk)或者是Hesse矩阵rf(xk)的近似.采用二次函数模型的优化方法
是普遍的,这是因为二次函数模型简单,容易求解,且在极小点x∗附近一般函数可以用一组共心椭球
曲面来逼近.但是,如果目标函数的非二次性态很强,曲率变化剧烈,则二次模型逼近的效果就差.另外,
二次模型并没有充分利用迭代过程中前几次迭代中产生的函数值信息,而数值试验表明这些信息对改
善算法的性态是非常有用的.因此,研究能够包含迭代过程中产生的更多插值信息,产生广义Nowton
方程或广义拟Nowton方程,并结合现代优化技术来构造新型非二次模型优化算法是优化界的新课题
之一.
在非二次模型最优化方法中,常用的有锥模型优化方法[1,2],一般有理模型优化方法[3],齐次函数
模型优化方法[4{7],张量模型优化方法[8{10],三次函数模型优化方法[11{13]等等.本文讨论锥模型类优
化方法.

英文引用格式:SunWY,XuD.Afilter-trust-regionmethodbasedonconicmodelforunconstrainedoptimization(inChinese).
SciSinMath,2012,55(5):527{543,doi:10.1360/012010-137
孙文瑜等:解无约束最优化的基于锥模型的过滤集-信赖域方法

1980年,Davidon[1]提出了共线调比和锥模型优化算法,这种模型能够包含迭代过程中产生的较
丰富的插值信息,能够产生广义Nowton(拟Nowton)方程,是满足要求的有效的非二次模型优化方法
之一.一个典型的无约束优化的锥模型函数为

gTs1sTBs
(s)=f+k+k;(1.3)
kTT2
1+bks2(1+bks)

22
其中,fk=f(xk);gk=rf(xk);Bk=rf(xk)或是Hesse矩阵rf(xk)的近似,bk是水平向量,满
T
足1+bks>0.如果bk=0,则锥模型简化为二次模型.因而,锥模型是二次模型的推广.从锥模型
(1.3)可以得到[][]
T
r1−bksBks
(xk+s)=TITgk+T;(1.4)
1+bks1+bks1+bks

TT
bks1bks
注意到1−T=T=60;故I−T可逆,从而当s满足
1+bks1+bks1+bks

Bks
gk+T=0
1+bks

时,r(xk+s)=0,锥模型(xk+s)有极小点,立得

B−1g
s=−kk:(1.5)
T−1
1+bkBkgk
T−16
因此,如果Bk正定且1+bkBkgk=0,则所求的极小点为

B−1g
x=x−kk:(1.6)
k+1kT−1
1+bkBkgk

显然,如果bk=0,上述迭代格式就简化为Nowton(或拟Nowton)迭代格式

−−1
xk+1=xkBkgk:(1.7)

Sorensen[2]证明了这类锥模型共线调比优化算法的局部Q-超线性收敛性.Ariyawansa[14]修改了
Sorensen的推导,建立了共线调比BFGS和DFP公式之间的对偶关系.Ariyawansa和Lau[15]给出了
共线调比Broyden族