理论部分收敛性分析无约束最优化算法的一般迭代格式
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,计算下降方向,
kd
Step4,计算步长因子,
k?
Step5,令,
1 kkkk dxx 转步２,
精确线搜索方法的收敛性设
kkk gd,? 表示向量 kd 与 kg?
之间的夹角，即：
kk
k
T
k
k gd
gdc o s
定理 1 设 kd 是下降方向,k? 是精确线搜索的步长因子,若存在常数,0?M 使得对所有
,,,0 2 kMdxf kk 则：
,c o s2 1 2 kkkkkk gMdxfxf
证,由假设可知对任意 0 有：
10,
2
1 22
kkk
T
k
k
T
kkkk
ddxfd
dgxfdxf
2221 kkTkk dMdgxf
令：
2
k
k
T
k
dM
dg
由于 k? 是精确线搜索步长，故有：
kkkkkkk dxfxfdxfxf
kkkkkkk dxfxfdxfxf
22
2
1
kk
T
k dMdg
2
2
2
1
k
k
T
k
dM
dg?
22
2
2
2
1
kk
k
T
k
k
dg
dgg
M
kkgM?
22 c o s
2
1?
精确线搜索方法的收敛性定理 2 设梯度xg 在
0xfxfRxL n
上存在且一致连续,采用精确线搜索算法产生的方向 kd 与 kg? 的夹角 k? 满足：
,2k 对某个 0
则或者对某个有限的 k 有,0?kg 或者
,kxf 或者,0?kg
证,假定对所有的kk xfgk,0,? 下有界．
由于kxf 单调下降,故极限存在,因而：
101kk xfxf
反证法,假定 0?kg 不成立,则存在常数 0
和一个子序列使得,kg 从而：
2s inc o s 1 kk
k
k
T
k g
d
dg
又, kTkkkk dgxfdxf
kTkkkk dgxfdxf
kTkkkTkk dggdgxf
3
kk
k
k
T
k
kk ggd
dgdxf
其中 k? 在 kx 与 kk dx 之间．
由于 g 在水平集 L 上一致连续,故存在?
使得当 kd0 时：
421 1 kk gg
依次利用 (2),(3),和 (4)得：
1
2
1
k
k
T
k
k
k
k
k d
dgxf
d
dxf
121 kxf
从而由精确线搜索可得：
11
2
1
k
k
k
kk xfd
dxfxf
这与 (1)矛盾,从而有,0?kg
不精确线搜索方法的收敛性设
kkk gd,? 表示向量 kd 与 kg?
之间的夹角，即：
kk
k
T
k
k gd
gdc o s
定理 3 设函数xf 连续可微,梯度xg 满足
Lipschitz连续条件：
5,zyMzgyg
如果kk dxf 下有界，,0 则对满足 Wolfe
原则的任何 0?k? 均有：
kkkkkk gMdxfxf 22 c o s1
证明,由 Lipschitz条件和原则二得：
kTkkkkkTkkk gdgdxgddM 12
即：
kkk
k
kk gddMd?
c o s1
6c o s1 kkgM
利用原则一和 (6),有：
kTkkkkkk gddxfxf
kkkk gd c o s?
kkkk gMg?
c o s1c o s
kkgM?
22 c os1
不精确线搜索方法的收敛性定理 4 设函数xf 连续可微和下有界,xg 在水平集
0xfxfRxL n
上一致连续．
设不精确线搜索方法采用 Wolfe原则，则：
7.0c o slim kkk g?
如果夹角条件满足，则：
8.0lim kk g
证,由于,0?kTk sg 又由于xf 下有界,因此序列kx 是有定义的,且在水平集 L 中．
反证法,假定 (6)不成立,则存在 0 和子序列，
其指标集为 K，使得,
.,Kk
s
sg
k
k
T
k
于是,由原则一：
,1 k
k
k
T
k
kkk ss
sgsxfxf?
又由于kxf 单调下降,因而收敛的,故
Kks k? 收敛到零．
又由原则二：
0,1 ksgsxgsg kTkkkkTk?
因此,,,
1
1 Kkgsxg
s
sg
kkk
k
k
T
k
由于Kks
k?
收敛到零,故由xg 在水平集上一致连续知上式右边趋于零,从而产生矛盾,
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,计算下降方向,
kd
Step4,计算步长因子,
k?
Step5,令,
1 kkkk dxx 转步２,
精确线搜索方法的收敛性设
kkk gd,? 表示向量 kd 与 kg?
之间的夹角，即：
kk
k
T
k
k gd
gdc o s
定理 1 设 kd 是下降方向,k? 是精确线搜索的步长因子,若存在常数,0?M 使得对所有
,,,0 2 kMdxf kk 则：
,c o s2 1 2 kkkkkk gMdxfxf
证,由假设可知对任意 0 有：
10,
2
1 22
kkk
T
k
k
T
kkkk
ddxfd
dgxfdxf
2221 kkTkk dMdgxf
令：
2
k
k
T
k
dM
dg
由于 k? 是精确线搜索步长，故有：
kkkkkkk dxfxfdxfxf
kkkkkkk dxfxfdxfxf
22
2
1
kk
T
k dMdg
2
2
2
1
k
k
T
k
dM
dg?
22
2
2
2
1
kk
k
T
k
k
dg
dgg
M
kkgM?
22 c o s
2
1?
精确线搜索方法的收敛性定理 2 设梯度xg 在
0xfxfRxL n
上存在且一致连续,采用精确线搜索算法产生的方向 kd 与 kg? 的夹角 k? 满足：
,2k 对某个 0
则或者对某个有限的 k 有,0?kg 或者
,kxf 或者,0?kg
证,假定对所有的kk xfgk,0,? 下有界．
由于kxf 单调下降,故极限存在,因而：
101kk xfxf
反证法,假定 0?kg 不成立,则存在常数 0
和一个子序列使得,kg 从而：
2s inc o s 1 kk
k
k
T
k g
d
dg
又, kTkkkk dgxfdxf
kTkkkk dgxfdxf
kTkkkTkk dggdgxf
3
kk
k
k
T
k
kk ggd
dgdxf
其中 k? 在 kx 与 kk dx 之间．
由于 g 在水平集 L 上一致连续,故存在?
使得当 kd0 时：
421 1 kk gg
依次利用 (2),(3),和 (4)得：
1
2
1
k
k
T
k
k
k
k
k d
dgxf
d
dxf
121 kxf
从而由精确线搜索可得：
11
2
1
k
k
k
kk xfd
dxfxf
这与 (1)矛盾,从而有,0?kg
不精确线搜索方法的收敛性设
kkk gd,? 表示向量 kd 与 kg?
之间的夹角，即：
kk
k
T
k
k gd
gdc o s
定理 3 设函数xf 连续可微,梯度xg 满足
Lipschitz连续条件：
5,zyMzgyg
如果kk dxf 下有界，,0 则对满足 Wolfe
原则的任何 0?k? 均有：
kkkkkk gMdxfxf 22 c o s1
证明,由 Lipschitz条件和原则二得：
kTkkkkkTkkk gdgdxgddM 12
即：
kkk
k
kk gddMd?
c o s1
6c o s1 kkgM
利用原则一和 (6),有：
kTkkkkkk gddxfxf
kkkk gd c o s?
kkkk gMg?
c o s1c o s
kkgM?
22 c os1
不精确线搜索方法的收敛性定理 4 设函数xf 连续可微和下有界,xg 在水平集
0xfxfRxL n
上一致连续．
设不精确线搜索方法采用 Wolfe原则，则：
7.0c o slim kkk g?
如果夹角条件满足，则：
8.0lim kk g
证,由于,0?kTk sg 又由于xf 下有界,因此序列kx 是有定义的,且在水平集 L 中．
反证法,假定 (6)不成立,则存在 0 和子序列，
其指标集为 K，使得,
.,Kk
s
sg
k
k
T
k
于是,由原则一：
,1 k
k
k
T
k
kkk ss
sgsxfxf?
又由于kxf 单调下降,因而收敛的,故
Kks k? 收敛到零．
又由原则二：
0,1 ksgsxgsg kTkkkkTk?
因此,,,
1
1 Kkgsxg
s
sg
kkk
k
k
T
k
由于Kks
k?
收敛到零,故由xg 在水平集上一致连续知上式右边趋于零,从而产生矛盾,
