第
32
卷第
6
期
太原科技大学学报
Vo
l.
32
No.6
2011
年
12
月
JOURNAL
OF
TAIYUAN
UNIVERSITY
OF
SCIENCE
AND
TECHNOLOGY
Dec.2011
文章编号
:1673
-2057(2011 )06 -0483
-05
一种求解不定信赖域子问题的双割线折线法
邵安，王希云
(太原科技大学应用科学学院，太原
030024)
摘
要:结合利用
Hessian
阵的特征值性质，针对
Bk
是不定的情况，提出了一种双喜
rJ
线折线法来求
解不定的信赖域子问题，并从理论上分析了当
Bk
不定时，双割线折线路径的合理性，且给出了算法的收
敛性质。最后，详细的数值试验表明，算法是有效的。
关键词:信赖域方法;子问题;双割线折线法;不定矩阵
中图分类号
:0221
文献标志码
:A
本文讨论无约束优化问题:
minf(x)
(1)
其中
，j
:R
n
→
R
是二次连续可微函数。信赖域
方法是在每次迭代求解信赖域子问题:
min qk(8)
=grδ+
护
T
B
山
t.
11δ11
::::;
6
k
(2)
的解品，其中
gk
= 'ïJ
f(x
k
)
,Bk E
R
nxn
是近似于
Hes
slan
阵
'ïJ
2f(
x)
的对称矩阵
，
6
k
是信赖域半径。当
6
k
变化时，式
(1)的解
A
形成一条空间曲线，称为
最优曲线。
求解子问题的最优解是通过构造各种折线法
来近似求解的。
Powell[l]
提出了一种单折线法来求
解子问题;
Dennis
和
Mei[2]
提出了双折线法;赵英良
与徐成贤
[3]
提出了切线单折线法，这条折线路径能
更靠近牛顿方向。但这三种折线法是在
Bk
正定时
提出的。为了解决
Bk
不正定情况，陈俊
[4]
提出了
不定折线路径求解非单调自适应信赖域算法;随
后，赵丹
[5]
提出了混合折线法来求解不定的信赖域
子问题;郭飞艳阳]构造出一个带有线搜索的自适应
混合折线信赖域算法;赵绚
[7]
阐述了一类新的带线
搜索的自适应非单调信赖域算法。本文针对且是
不定的情况，通过
Bunch
-
Parlett
分解[剖，构造了一
种双割线折线法，该折线法不仅能求解不定的信赖
收稿日期
:2011
-0
5-19
基金项目:山西省自然科学基金
(2008011013)
域子问题，且使折线路径能更快地靠近牛顿方向，
并从理论上分析了双割线折线路径对于
Bk
是不定
时的合理性，且给出了算法的收敛性质。最后试验
表明本文的算法是有效的。
1
不定的双割线折线法的基本思想
1.1
对称正定矩阵码的构造
对于
Bk
是不正定的情况，一般采用
Bunch-Par
lett
分解
[8]
对任何对称矩阵矶，总存在排列矩阵
P
，
使得
pTBkP
=
WkL
T
.
其中
，
L
是单位下三角矩
阵
，
Dk
是块对角矩阵，其块的阶数是
1
或
2.
为方便
起见，不妨设排列矩阵
P=l
，
即
:Bk
=WkL
T
.
设
λl'
λ2
，…
，
Ån
是
Dk
的特征值，叫，屿，…，叽为对应的特
征向量，令
Vk
=
(Vl'
屿，…
，
Vn)T
，
下面分两种情况构
造
GK[5]:
(1)当
λI
>0
，
i=I
，
2
，
…
，
n
时，令:
G
k
=
(LVk)Dk(LV
k
)
T ,
一
1
1 1
其中
，
Dk
=
diag(
一一…一)
;
(3)
λλλn
(2)
当引，
s.
t.λz
运
0
时，令:
Gk=(LVk)Dk(LVk)T
,
(4)
其中
，
Dk
=
diag(
矶，也，…
，
dJ
，
d
i
=
作者简介:邵安(1
982
-)男，硕士研究生，主要研究方向为最优化理论与应用。
资源评论
