信赖域方法信赖域方法信赖域方法是求解最优化问题的另一类有效方法,其最初的设计思想可追溯至 Levenberg和
Marquart对 Gauss－ Newton法的修正．
线搜索方法是把一个复杂的最优化问题转化成一系列简单的一维寻优问题,信赖域方法是把最优化问题转化为一系列相对简单的局部寻优问题．
基本思想牛顿法的基本思想是在迭代点
kx
附近用二次函数逼近,
2
1 sGssgfsqxf
k
TT
kkk
并以sqk 的的极小点 ks 修正,kx 得到,.
1 kkk sxx
以上方法只能保证算法的局部收敛性,为了建立总体收敛性算法,我们采用了线搜索技术,虽然这种策略是成功的,但它有一个缺点,即没有进一步利用二次模型．
基本思想牛顿法的基本思想是在迭代点
kx
附近用二次函数逼近,
2
1 sGssgfsqxf
k
TT
kkk
并以sqk 的的极小点 ks 修正,kx 得到,.
1 kkk sxx
以上方法只能保证算法的局部收敛性,为了建立总体收敛性算法,我们采用了线搜索技术,虽然这种策略是成功的,但它有一个缺点,即没有进一步利用二次模型,信赖域方法是另一种新的保证算法总体收敛的方法．
信赖域方法的模型子问题
121m in sBssgfsq kTTkkk
ksts.
其中,,kkk xfgxxs kB 是 Hesse阵kxf2? 的近似
0k 为信赖域半径．
注,(1)这种方法既具有牛顿法的快速局部收敛性,又具有理想的总体收敛性．
(2)不要求目标函数的 Hesse阵是正定的．
(3)利用了二次模型来求修正量,使得目标函数的下降比线性搜索方法更有效．
(4)由于步长受到使 Taylor展开式有效的信赖域的限制,故方法又称为有限步长法．
信赖域半径的选择根据模型函数sq
k
对目标函数xf 的拟合程度来调整信赖域半径,
k?
对于问题 (1)的解,ks 定义比值：
kkk
kkk
k
k
k sqq
sxfxf
r e dP
A r e dr
0
它衡量模型函数sqk 与目标函数xf 的一致性程度．
注,(1) kr 越接近于１,表明模型函数与目标函数的一致性程度越好,可以增大 k? 以扩大信赖域．
(2) 0?kr 不接近于１,可以保持 k? 不变．
(3)kr 接近于零或取负值,表明模型函数与目标函数的一致性程度不好,可以减小 k? 以缩小信赖域．
信赖域算法
Step1,给出,
0 nRx?
信赖域半径的上界,,0,
0
.0,10,10,0 2121 k
Step2,如果,
kg
停止．
Step3,求解子问题 (1)得到,ks
Step4,计算
kk sxf?
和,
kr
令：
o t h e r sx
rsx
x
k
kkk
k
1
1
Step5,校正信赖域半径，令：
221
2111
111
,m in,
),[,
,0
kkkk
kkkk
kkk
r
r
r
Step6,产生,
1?kB
校正,
kq
令,1 kk 转 Step2
注,参数建议取：
1,2,5.0,75.0,01.0 02121
信赖域子问题折线法基本思想如果令信赖域的半径
k?
在区间,0 内连续变化,则问题 (1)的解
ks
在空间 nR 中形成一条光滑的连续曲线,记为.kop? 此时,问题 (1)等价于在信赖域内在最优曲线kop? 上确定一点使二次函数sqk 取极小,即：
k
k
op
k
ssts
sq
,.
m in
由于最优曲线的确定需要计算矩阵
kB
的所有特征值和特征向量,相当费时．
折线法在于用低维空间内满足一定要求的折线,记为,k? 代替最优曲线,通过求解：
k
k
k
ssts
sq
,.
2m in
得问题 (1)的近似解,
ks
注,(1) 求解 (2)的一个突出特点在于,近似折线
k? 一经确定,对于给定的,
k?
无需再解任何线性方程组,即能相当有效的确定问题 (1)的近似解．
(2) 构造近似最优曲线k
op?
的折线时,一般应满足下面基本要求,当点 x 从 kx 出发沿着折线前进时,
(P1)点 x 到 kx 的距离单调增；
(P2)函数值sq
k 严格单调降；
性质 (P1)确保对任意给定的,
k?
折线上的近似解惟一．
性质 (P2)确保在折线上所确定的近似解
ks
能满足收敛性定理的条件．
折线法算法原理 (1970)
连接 Cauchy点 (由最速下降法产生的极小点 C.P.)
和牛顿点 (即由牛顿法产生的极小点 Nkx 1? ）,其连线与信赖域的边界的交点取为,1?kx
显然,.1 kkk xx
当牛顿步 Nks 的长度
k
N
ks
时，
1?kx
就取为,
1Nkx?
对二次模型：
kkTkkkkkk gGggxfgxq 22 21
精确线搜索下,2
kk
T
k
k
k gGg
g
Cauchy步为,.k
kk
T
k
k
T
k
kk
c
k ggGg
gggs
若,
kkk
c
k gs
取,
k
k
k
k ggs
若,
kkk
c
k gs
再计算牛顿步,1 kkNk gGs
若,
k
N
ks
取,1 kkNkk gGss
否则取,ckNkckk ssss
其中? 由方程
k
c
k
N
k
c
k sss
得到．
综上：
k
N
kk
c
kkkk
k
N
kk
c
k
c
k
N
k
c
kk
k
c
kk
k
k
k
k
ssgGx
sssssx
sg
g
x
x
,
,
1
1
双折线法 (1979)
让信赖域迭代中产生的点偏向牛顿方向，
于是把 Cauchy点和牛顿方向上的 N? 点连接起来，
并将这条连线与信赖域边界的交点取为,1?kx
折线 Nkk xPCx 1., 称为单折线．
把 N
kk xNPCx 1?.,
称为双折线．
在双折线情形下：
k
N
kk
c
kkkk
k
N
kk
c
k
c
k
N
k
c
kk
k
c
kk
k
k
k
k
ssgGx
sssssx
sg
g
x
x
1
1
,
,?
其中
,,1,,1
4
kk
T
kkk
T
k
kN
k
N
k gGggGg
g
ss
一般取,2.08.0
例 1,设,2
22141 xxxxf
在当前点,1,1 Tkx?
,21 k 试用双折线法求,1?kx
解,
2
14,2,6,1,1
k
T
k
T
k Ggx
T
kk
N
k gGs
1,
7
31
156.0
469.0
2
6
512
402
k
kk
T
k
kc
k ggGg
g
s
由于,
kcks
计算,?N
ks
有：
684.0
7
32
512
40 2
1
4
kk
T
kkk
T
k
k
gGggGg
g
747.02.08.0
7 4 7.0
3 2 0.0? N
k
N
k ss?
由于,8 1 3.0?
k
N
ks
故取双折线步长为：
1,0 ckNkckk ssss
使得,kks 解二次方程 22?
k
c
k
N
k
c
k sss
得,867.0 因此
6 6 9.0
3 4 0.08 6 7.0? c
k
N
k
c
kk ssss
所以
3 3 1.0
6 6 0.0
1 kkk sxx
Marquart对 Gauss－ Newton法的修正．
线搜索方法是把一个复杂的最优化问题转化成一系列简单的一维寻优问题,信赖域方法是把最优化问题转化为一系列相对简单的局部寻优问题．
基本思想牛顿法的基本思想是在迭代点
kx
附近用二次函数逼近,
2
1 sGssgfsqxf
k
TT
kkk
并以sqk 的的极小点 ks 修正,kx 得到,.
1 kkk sxx
以上方法只能保证算法的局部收敛性,为了建立总体收敛性算法,我们采用了线搜索技术,虽然这种策略是成功的,但它有一个缺点,即没有进一步利用二次模型．
基本思想牛顿法的基本思想是在迭代点
kx
附近用二次函数逼近,
2
1 sGssgfsqxf
k
TT
kkk
并以sqk 的的极小点 ks 修正,kx 得到,.
1 kkk sxx
以上方法只能保证算法的局部收敛性,为了建立总体收敛性算法,我们采用了线搜索技术,虽然这种策略是成功的,但它有一个缺点,即没有进一步利用二次模型,信赖域方法是另一种新的保证算法总体收敛的方法．
信赖域方法的模型子问题
121m in sBssgfsq kTTkkk
ksts.
其中,,kkk xfgxxs kB 是 Hesse阵kxf2? 的近似
0k 为信赖域半径．
注,(1)这种方法既具有牛顿法的快速局部收敛性,又具有理想的总体收敛性．
(2)不要求目标函数的 Hesse阵是正定的．
(3)利用了二次模型来求修正量,使得目标函数的下降比线性搜索方法更有效．
(4)由于步长受到使 Taylor展开式有效的信赖域的限制,故方法又称为有限步长法．
信赖域半径的选择根据模型函数sq
k
对目标函数xf 的拟合程度来调整信赖域半径,
k?
对于问题 (1)的解,ks 定义比值：
kkk
kkk
k
k
k sqq
sxfxf
r e dP
A r e dr
0
它衡量模型函数sqk 与目标函数xf 的一致性程度．
注,(1) kr 越接近于１,表明模型函数与目标函数的一致性程度越好,可以增大 k? 以扩大信赖域．
(2) 0?kr 不接近于１,可以保持 k? 不变．
(3)kr 接近于零或取负值,表明模型函数与目标函数的一致性程度不好,可以减小 k? 以缩小信赖域．
信赖域算法
Step1,给出,
0 nRx?
信赖域半径的上界,,0,
0
.0,10,10,0 2121 k
Step2,如果,
kg
停止．
Step3,求解子问题 (1)得到,ks
Step4,计算
kk sxf?
和,
kr
令：
o t h e r sx
rsx
x
k
kkk
k
1
1
Step5,校正信赖域半径，令：
221
2111
111
,m in,
),[,
,0
kkkk
kkkk
kkk
r
r
r
Step6,产生,
1?kB
校正,
kq
令,1 kk 转 Step2
注,参数建议取：
1,2,5.0,75.0,01.0 02121
信赖域子问题折线法基本思想如果令信赖域的半径
k?
在区间,0 内连续变化,则问题 (1)的解
ks
在空间 nR 中形成一条光滑的连续曲线,记为.kop? 此时,问题 (1)等价于在信赖域内在最优曲线kop? 上确定一点使二次函数sqk 取极小,即：
k
k
op
k
ssts
sq
,.
m in
由于最优曲线的确定需要计算矩阵
kB
的所有特征值和特征向量,相当费时．
折线法在于用低维空间内满足一定要求的折线,记为,k? 代替最优曲线,通过求解：
k
k
k
ssts
sq
,.
2m in
得问题 (1)的近似解,
ks
注,(1) 求解 (2)的一个突出特点在于,近似折线
k? 一经确定,对于给定的,
k?
无需再解任何线性方程组,即能相当有效的确定问题 (1)的近似解．
(2) 构造近似最优曲线k
op?
的折线时,一般应满足下面基本要求,当点 x 从 kx 出发沿着折线前进时,
(P1)点 x 到 kx 的距离单调增；
(P2)函数值sq
k 严格单调降；
性质 (P1)确保对任意给定的,
k?
折线上的近似解惟一．
性质 (P2)确保在折线上所确定的近似解
ks
能满足收敛性定理的条件．
折线法算法原理 (1970)
连接 Cauchy点 (由最速下降法产生的极小点 C.P.)
和牛顿点 (即由牛顿法产生的极小点 Nkx 1? ）,其连线与信赖域的边界的交点取为,1?kx
显然,.1 kkk xx
当牛顿步 Nks 的长度
k
N
ks
时，
1?kx
就取为,
1Nkx?
对二次模型：
kkTkkkkkk gGggxfgxq 22 21
精确线搜索下,2
kk
T
k
k
k gGg
g
Cauchy步为,.k
kk
T
k
k
T
k
kk
c
k ggGg
gggs
若,
kkk
c
k gs
取,
k
k
k
k ggs
若,
kkk
c
k gs
再计算牛顿步,1 kkNk gGs
若,
k
N
ks
取,1 kkNkk gGss
否则取,ckNkckk ssss
其中? 由方程
k
c
k
N
k
c
k sss
得到．
综上：
k
N
kk
c
kkkk
k
N
kk
c
k
c
k
N
k
c
kk
k
c
kk
k
k
k
k
ssgGx
sssssx
sg
g
x
x
,
,
1
1
双折线法 (1979)
让信赖域迭代中产生的点偏向牛顿方向，
于是把 Cauchy点和牛顿方向上的 N? 点连接起来，
并将这条连线与信赖域边界的交点取为,1?kx
折线 Nkk xPCx 1., 称为单折线．
把 N
kk xNPCx 1?.,
称为双折线．
在双折线情形下：
k
N
kk
c
kkkk
k
N
kk
c
k
c
k
N
k
c
kk
k
c
kk
k
k
k
k
ssgGx
sssssx
sg
g
x
x
1
1
,
,?
其中
,,1,,1
4
kk
T
kkk
T
k
kN
k
N
k gGggGg
g
ss
一般取,2.08.0
例 1,设,2
22141 xxxxf
在当前点,1,1 Tkx?
,21 k 试用双折线法求,1?kx
解,
2
14,2,6,1,1
k
T
k
T
k Ggx
T
kk
N
k gGs
1,
7
31
156.0
469.0
2
6
512
402
k
kk
T
k
kc
k ggGg
g
s
由于,
kcks
计算,?N
ks
有：
684.0
7
32
512
40 2
1
4
kk
T
kkk
T
k
k
gGggGg
g
747.02.08.0
7 4 7.0
3 2 0.0? N
k
N
k ss?
由于,8 1 3.0?
k
N
ks
故取双折线步长为：
1,0 ckNkckk ssss
使得,kks 解二次方程 22?
k
c
k
N
k
c
k sss
得,867.0 因此
6 6 9.0
3 4 0.08 6 7.0? c
k
N
k
c
kk ssss
所以
3 3 1.0
6 6 0.0
1 kkk sxx
