第
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
-)男,硕士研究生,主要研究方向为最优化理论与应用。