梯度法和共轭梯度法
1,无约束最优化问题
2,梯度法
3,共轭梯度法
一, 无约束最优化问题
无约束最优化问题
nRxts
xf
?..
)(m i n
有一阶连续偏导数。其中 )( xf
解析方法,利用函数的解析性质构造迭代公式使之收敛到最优解。
二, 梯度法（最速下降法）
迭代公式,kkkk dxx ???? 1
如何选择下降最快的方向？
)( kxf?
)( kxf?? 函数值下降最快的方向
函数值增加最快的方向
函数值下降的方向
kx
梯度法（最速下降法）：
也称为最速下降方向；搜索方向：,)(.1 kk xfd ???
。即满足取最优步长搜索步长 )(m i n)(,:.2 kkkkkk dxfdxf ??? ? ???
梯度法算法步骤：
。令允许误差给定初始点 1,0,.1 1 ??? kRx n ?;)(.2 kk xfd ???计算搜索方向
kkk xd ?? 否则，求最优步长为所求极值点；则停止计算，若,||||.3 ?
。使得 )(m i n)( kkkkk dxfdxf ?? ? ???
。转令令 2,1:,.4 1 ????? kkdxx kkkk ?
,)1,2(,3)(m i n:,12221 Txxxxf ??? 设初始点为用最速下降法求解例
。求迭代一次后的迭代点 2x
解：,)6,2()( 21 Txxxf ???
.)6,4()( 11 Txfd ???????
.)61,42(11 Tdx ??? ?????
，令 2211 )61(3)42()()( ????? ?????? dxf
)(m i n ???求解
0)61(36)42(8)( ??????? ????令 62131 ?? ?
Tdxx )31 8,3136(1112 ????? ?
收敛性
)(m i n)( kkkkk dxfdxf ?? ? ???
。则有 0)( ??? kTkkk ddxf ?
性质,
证明,所以，令 )()( kk dxf ??? ??
.)()( kTkk ddxf ??? ????
)(m i n)( kkkkk dxfdxf ?? ? ????
.0)()( ?????? kTkkkk ddxf ???
满足步长有一阶连续偏导数，若设 kxf ?)(
注：
。kkkTk dddd ??? ?? 11 0)(
所以，因为梯度法的搜索方向 )(1 kkkk dxfd ?????
锯齿现象
，其等值面近似数可以用二次函数近似在极小点附近，目标函
椭球面。
1x
*x
2x
3x
它只是。标函数的一种局部性质最速下降方向反映了目
快的方向。局部目标函数值下降最
注
?
的算法。最速下降法是线性收敛
三,共轭梯度法
1,共轭方向和共轭方向法
定义
共轭。关于和，则称若有 AddAdd T 2121 0?
ARddd nk 它们两两关于中一组非零向量，如果是设,,,21 ?
。共轭，即 kjijiAdd jTi,,2,1,,,0 ????
共轭方向。组共轭的，也称它们是一则称这组方向是关于 AA
注：
00 2121 ?????? dddId TT
21 dd ??
共轭是正交的推广。
，和中的两个非零向量的对称正定矩阵，对于是设 21 ddRnnA n?
是单位矩阵，则如果 A
共轭的非零个是阶对称正定矩阵，是设 AkdddnA k,,,21 ?
性无关。向量，则这个向量组线
.1定理
证明,使得设存在实数 k???,,,21 ?
,01 ???ki iid?
，则有上式两边同时左乘 Ad Tj
,01 ???ki iTji Add?
可化简为共轭的向量，所以上式个是因为 Akddd k,,,21 ?
.0?jTjj Add?
，是正定矩阵，所以而因为 0,0 ?? jTjj AddAd
所以 。kjj,,2,1,0 ????
线性无关。因此 kddd,,,21 ?
几何意义
设有二次函数
)()(21)( xxAxxxf T ???
对称正定矩阵，是其中 nnA ?是一个定点。x
的等值面则函数 )( xf cxxAxx T ??? )()(21
为中心的椭球面。是以 x
由于,0)()( ???? xxAxf
,0)(2 ??? AxfA 所以正定，因为
的极小点。是因此 )( xfx
x
,)(2 Axf ??而
点，是在某个等值面上的一设 )0(x
处的法向量为该等值面在点 )1(x
.)()( )1()1( xxAxf ???
o 1x
2x
x
)1(d
)0(x
中的一个方向，是 nRd )1(
。以最优步长搜索得到点沿着 )1()1()0( xdx
所在等值面的切向量。是点则 )1()1( xd
正交，与则 )( )1()1( xfd ?
,0)( )1()1( ?? xfd T即
,)1()2( xxd ??令
)1(x
所以,0)2()1( ?Add T
共轭。小点的向量关于向量与由这一点指向极即等值面上一点处的切 A
)2(d
.2定理,设有函数 cxbAxxxf TT ??? 21)(
共轭向量。一组是阶对称正定矩阵。是其中 AdddnA k )()2()1(,,,?
进行搜索，为初始点，依次沿以任意的 )()2()1()1(,,,kn dddRx ??
上的在是函数则得到点 kkk Bxxfxxxx ??? )1()1()1()3()2( )(,,,,?
极小点，其中
},|{ 1 )( RdxxB iki iik ??? ?? ??
是时，当，生成的子空间。特别地是由 )1()()2()1(,,,?? nk xnkddd ?
上的唯一极小点。在 nRxf )(
推论 有在上述定理条件下，必
。kidxf iTk,,2,1,0)( )()1( ???? ?
共轭方向法
对于极小化问题
:法为共轭方向法是正定矩阵，称下述算其中 A
,21)(m i n cxbAxxxf TT ???；共轭方向取定一组 )()2()1(,,,)1( ndddA ?
,,)2( )1()()1( ?kk xxx 确定点依次按照下式由任取初始点
??
???
???
???
)(m i n)( )()()()(
)()()1(
kkk
k
k
k
k
kk
dxfdxf
dxx
??
?
?
。满足直到某个 0)( )()( ?? kk xfx
注 至多经过求解上述极小化问题，可知，利用共轭方向法由定理 2
。次迭代必可得到最优解n
2,共轭梯度法
如何选取一组共轭方向？
:共轭梯度法e e v e sRF le tc h e r ?
代点向相结合，利用已知迭将共轭性和最速下降方基本思想：
进行搜索，求出共轭方向，并沿此方向处的梯度方向构造一组
函数的极小点。
以下分析算法的具体步骤。
cxbAxxxf TT ??? 21)(m i n
是常数。，是对称正定矩阵，其中 cRbARx nn ??,；，第一个搜索方向取为任取初始点 )()1( )1()1()1( xfdx ???
，令，若，设已求得点 )(0)()2( )1(1)1()1( ???? ???? kkkk xfgxfx
:)1( 按如下方式确定则下一个搜索方向 ?kd
)1()(1)1( kkkk dgd ???? ??令
共轭。关于和要求 Add kk )()1( ?
？如何确定 k?
，得）式两边同时左乘则在（ Ad Tk )(1
)()(1)()1()(0 kTkkkTkkTk dAdAgdAdd ????? ??
)2(
)()(
1
)(
kTk
k
Tk
k
dAd
gAd ???解得
:)3( 搜索步长的确定
，步长利用一维搜索确定最优和搜索方向已知迭代点 kkk dx ?,)()(
。即求解 )(m i n )()( kk dxf ?? ?
,)()( )()( kk dxf ??? ??记
，令 0)()( )()()( ????? kTkk ddxf ???
，即有 0])([ )()()( ??? kTkk dbdxA ?
，则有令 bAxxfg kkk ???? )()( )(
，0][ )()( ?? kTkk dAdg ?
)3()()(
)(
kTk
kTk
k Add
dg???解得
3定理 次算法在，对于正定二次函数 nmFRcxbAxxxf TT ???? 21)(
），下列关系成立（且对所有的一维搜索后即终止，并 mii ??1;1,,2,1,0)1( )()( ??? ijAdd jTi ?;1,,2,1,0)2( ??? ijgg jTi ?
。iTiiTi ggdg ??)()3(
注
共轭的。是可知搜索方向）由定理（ Addd m )()2()1(,,,31 ?
则构造的搜索必须取负梯度方向，否算法中第一个搜索方向)2(
方向不能保证共轭性。
）可知，的（由定理 33)3(,0|||| 2)( ????? iiTiiTi gggdg
处的下降方向。是迭代点所以 )()( ii xd
的计算公式可以简化。算法中，由定理 iFR ?3)4(
)()(
1
)(
iTi
i
Ti
i Add
gAd ???
)()(
)(1
iTi
iTi
Add
dAg ??
]/)([
]/)([
)()1()(
)()1(
1
i
iiTi
i
iiT
i
xxAd
xxAg
?
?
?
??
?
?
?
.)( )()( bxAxfg iii ?????
)(
)(
1
)(
11
ii
Ti
ii
T
ii
ggd
ggg
?
???
?
???
i
Ti
i
gd
g
)(
2||||
?
? ?
)4(|||| |||| 2
21
i
i
g
g ??
算法步骤：FR
。，令精度要求，任取初始点 1.1 )1( ?kx ?
为所求极小点；停止，若令 )1(1)1(1,||||,)(.2 xgxfg ????
。令，）计算利用公式（否则，令 )1(1)1()2(11)1( 3,dxxgd ?? ????
为所求极小点；停止，若令 )1(1)1(1,||||,)(.3 ???? ??? kkkk xgxfg ?
）计算。用公式（其中否则，令 4,)(1)1( kkkkk dgd ????? ??
。转，令）计算利用公式（ 3,3.4 )()()1( kkkkk dxx ?? ???
。令 1,?? kk
算法求解下述问题：用例 FR
22212)(m i n xxxf ??
。初始点取为 Tx )2,2()1( ?
解：
.)2,4()( 21 Txxxf ??
次迭代：第 1
,)4,8(1)1( Tgd ?????令
)1()1(
)1(1
1 Add
dg
T
T
???
,20 04),(21)(
2
121 ?
?
??
?
??
?
??
?
??
x
xxxxf?,
20
04 ?
?
??
?
??? A
而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
??
4
8
20
04
)4,8(
4
8
)4,8(
18
5?
)1(1)1()2( dxx ???所以
TT )4,8(185)2,2( ???? T)98,92( ??
次迭代：第 2
.)916,9 8(2 Tg ???
21
22
1 ||||
||||
g
g?? ?,
81
4
48
)916()9 8(
22
22
?
?
??
?
)1(12)2( dgd ?????
TT )4,8(814)916,98( ?????
T)4,1(8140 ??
)2()2(
)2(2
2 Add
dg
T
T
????
?
?
?
?
?
?
???
?
?
?
?
?
?
?
?
?
?
?
?
?
??
4
1
20
04
)4,1()
81
40
(
4
1
)
9
16
,
9
8
(
81
40
2209?
)2(2)2()3( dxx ????
TT )4,1(8140209)98,9 2( ?????
T)0,0(?
Tg )0,0(3 ??
即为所求极小点。)3(x?
3,用于一般函数的共轭梯度法
nRxts
xf
?..
)(m in
共轭梯度法进行修改：对用于正定二次函数的
确定。）计算，需由一维搜索不能利用公式（搜索步长 3)2( i?
。速下降方向，即第一个搜索方向仍取最 )()1( )1()1( xfd ???
算：其它搜索方向按下式计
,)( )()1()1( iiii dxfd ????? ??
。其中 2)(
2)1(
||)(||
||)(||
i
i
i xf
xf
?
?? ??
此时可采取一定能满足停止条件，算法在有限步迭代后不)3(
如下措施：
没有求成一轮搜索后，如果还次迭代为一轮，每次完以 n
新的初始点，的最后一个迭代点作为得极小点，则以上一轮
一轮搜索。一个搜索方向，开始下取最速下降方向作为第
注,如算采用其它形式的公式计在共轭梯度法中，也可 i?
。）共轭梯度法P RPgg ggg
iTi
iiTii ()( 11 ?? ???
1,无约束最优化问题
2,梯度法
3,共轭梯度法
一, 无约束最优化问题
无约束最优化问题
nRxts
xf
?..
)(m i n
有一阶连续偏导数。其中 )( xf
解析方法,利用函数的解析性质构造迭代公式使之收敛到最优解。
二, 梯度法（最速下降法）
迭代公式,kkkk dxx ???? 1
如何选择下降最快的方向？
)( kxf?
)( kxf?? 函数值下降最快的方向
函数值增加最快的方向
函数值下降的方向
kx
梯度法（最速下降法）：
也称为最速下降方向；搜索方向：,)(.1 kk xfd ???
。即满足取最优步长搜索步长 )(m i n)(,:.2 kkkkkk dxfdxf ??? ? ???
梯度法算法步骤：
。令允许误差给定初始点 1,0,.1 1 ??? kRx n ?;)(.2 kk xfd ???计算搜索方向
kkk xd ?? 否则，求最优步长为所求极值点；则停止计算，若,||||.3 ?
。使得 )(m i n)( kkkkk dxfdxf ?? ? ???
。转令令 2,1:,.4 1 ????? kkdxx kkkk ?
,)1,2(,3)(m i n:,12221 Txxxxf ??? 设初始点为用最速下降法求解例
。求迭代一次后的迭代点 2x
解：,)6,2()( 21 Txxxf ???
.)6,4()( 11 Txfd ???????
.)61,42(11 Tdx ??? ?????
，令 2211 )61(3)42()()( ????? ?????? dxf
)(m i n ???求解
0)61(36)42(8)( ??????? ????令 62131 ?? ?
Tdxx )31 8,3136(1112 ????? ?
收敛性
)(m i n)( kkkkk dxfdxf ?? ? ???
。则有 0)( ??? kTkkk ddxf ?
性质,
证明,所以，令 )()( kk dxf ??? ??
.)()( kTkk ddxf ??? ????
)(m i n)( kkkkk dxfdxf ?? ? ????
.0)()( ?????? kTkkkk ddxf ???
满足步长有一阶连续偏导数，若设 kxf ?)(
注：
。kkkTk dddd ??? ?? 11 0)(
所以，因为梯度法的搜索方向 )(1 kkkk dxfd ?????
锯齿现象
，其等值面近似数可以用二次函数近似在极小点附近，目标函
椭球面。
1x
*x
2x
3x
它只是。标函数的一种局部性质最速下降方向反映了目
快的方向。局部目标函数值下降最
注
?
的算法。最速下降法是线性收敛
三,共轭梯度法
1,共轭方向和共轭方向法
定义
共轭。关于和，则称若有 AddAdd T 2121 0?
ARddd nk 它们两两关于中一组非零向量，如果是设,,,21 ?
。共轭，即 kjijiAdd jTi,,2,1,,,0 ????
共轭方向。组共轭的，也称它们是一则称这组方向是关于 AA
注：
00 2121 ?????? dddId TT
21 dd ??
共轭是正交的推广。
，和中的两个非零向量的对称正定矩阵，对于是设 21 ddRnnA n?
是单位矩阵，则如果 A
共轭的非零个是阶对称正定矩阵，是设 AkdddnA k,,,21 ?
性无关。向量，则这个向量组线
.1定理
证明,使得设存在实数 k???,,,21 ?
,01 ???ki iid?
，则有上式两边同时左乘 Ad Tj
,01 ???ki iTji Add?
可化简为共轭的向量，所以上式个是因为 Akddd k,,,21 ?
.0?jTjj Add?
，是正定矩阵，所以而因为 0,0 ?? jTjj AddAd
所以 。kjj,,2,1,0 ????
线性无关。因此 kddd,,,21 ?
几何意义
设有二次函数
)()(21)( xxAxxxf T ???
对称正定矩阵，是其中 nnA ?是一个定点。x
的等值面则函数 )( xf cxxAxx T ??? )()(21
为中心的椭球面。是以 x
由于,0)()( ???? xxAxf
,0)(2 ??? AxfA 所以正定，因为
的极小点。是因此 )( xfx
x
,)(2 Axf ??而
点，是在某个等值面上的一设 )0(x
处的法向量为该等值面在点 )1(x
.)()( )1()1( xxAxf ???
o 1x
2x
x
)1(d
)0(x
中的一个方向，是 nRd )1(
。以最优步长搜索得到点沿着 )1()1()0( xdx
所在等值面的切向量。是点则 )1()1( xd
正交，与则 )( )1()1( xfd ?
,0)( )1()1( ?? xfd T即
,)1()2( xxd ??令
)1(x
所以,0)2()1( ?Add T
共轭。小点的向量关于向量与由这一点指向极即等值面上一点处的切 A
)2(d
.2定理,设有函数 cxbAxxxf TT ??? 21)(
共轭向量。一组是阶对称正定矩阵。是其中 AdddnA k )()2()1(,,,?
进行搜索，为初始点，依次沿以任意的 )()2()1()1(,,,kn dddRx ??
上的在是函数则得到点 kkk Bxxfxxxx ??? )1()1()1()3()2( )(,,,,?
极小点，其中
},|{ 1 )( RdxxB iki iik ??? ?? ??
是时，当，生成的子空间。特别地是由 )1()()2()1(,,,?? nk xnkddd ?
上的唯一极小点。在 nRxf )(
推论 有在上述定理条件下，必
。kidxf iTk,,2,1,0)( )()1( ???? ?
共轭方向法
对于极小化问题
:法为共轭方向法是正定矩阵，称下述算其中 A
,21)(m i n cxbAxxxf TT ???；共轭方向取定一组 )()2()1(,,,)1( ndddA ?
,,)2( )1()()1( ?kk xxx 确定点依次按照下式由任取初始点
??
???
???
???
)(m i n)( )()()()(
)()()1(
kkk
k
k
k
k
kk
dxfdxf
dxx
??
?
?
。满足直到某个 0)( )()( ?? kk xfx
注 至多经过求解上述极小化问题，可知，利用共轭方向法由定理 2
。次迭代必可得到最优解n
2,共轭梯度法
如何选取一组共轭方向？
:共轭梯度法e e v e sRF le tc h e r ?
代点向相结合，利用已知迭将共轭性和最速下降方基本思想：
进行搜索，求出共轭方向，并沿此方向处的梯度方向构造一组
函数的极小点。
以下分析算法的具体步骤。
cxbAxxxf TT ??? 21)(m i n
是常数。，是对称正定矩阵，其中 cRbARx nn ??,；，第一个搜索方向取为任取初始点 )()1( )1()1()1( xfdx ???
，令，若，设已求得点 )(0)()2( )1(1)1()1( ???? ???? kkkk xfgxfx
:)1( 按如下方式确定则下一个搜索方向 ?kd
)1()(1)1( kkkk dgd ???? ??令
共轭。关于和要求 Add kk )()1( ?
？如何确定 k?
，得）式两边同时左乘则在（ Ad Tk )(1
)()(1)()1()(0 kTkkkTkkTk dAdAgdAdd ????? ??
)2(
)()(
1
)(
kTk
k
Tk
k
dAd
gAd ???解得
:)3( 搜索步长的确定
，步长利用一维搜索确定最优和搜索方向已知迭代点 kkk dx ?,)()(
。即求解 )(m i n )()( kk dxf ?? ?
,)()( )()( kk dxf ??? ??记
，令 0)()( )()()( ????? kTkk ddxf ???
，即有 0])([ )()()( ??? kTkk dbdxA ?
，则有令 bAxxfg kkk ???? )()( )(
，0][ )()( ?? kTkk dAdg ?
)3()()(
)(
kTk
kTk
k Add
dg???解得
3定理 次算法在，对于正定二次函数 nmFRcxbAxxxf TT ???? 21)(
），下列关系成立（且对所有的一维搜索后即终止，并 mii ??1;1,,2,1,0)1( )()( ??? ijAdd jTi ?;1,,2,1,0)2( ??? ijgg jTi ?
。iTiiTi ggdg ??)()3(
注
共轭的。是可知搜索方向）由定理（ Addd m )()2()1(,,,31 ?
则构造的搜索必须取负梯度方向，否算法中第一个搜索方向)2(
方向不能保证共轭性。
）可知，的（由定理 33)3(,0|||| 2)( ????? iiTiiTi gggdg
处的下降方向。是迭代点所以 )()( ii xd
的计算公式可以简化。算法中，由定理 iFR ?3)4(
)()(
1
)(
iTi
i
Ti
i Add
gAd ???
)()(
)(1
iTi
iTi
Add
dAg ??
]/)([
]/)([
)()1()(
)()1(
1
i
iiTi
i
iiT
i
xxAd
xxAg
?
?
?
??
?
?
?
.)( )()( bxAxfg iii ?????
)(
)(
1
)(
11
ii
Ti
ii
T
ii
ggd
ggg
?
???
?
???
i
Ti
i
gd
g
)(
2||||
?
? ?
)4(|||| |||| 2
21
i
i
g
g ??
算法步骤：FR
。，令精度要求，任取初始点 1.1 )1( ?kx ?
为所求极小点；停止，若令 )1(1)1(1,||||,)(.2 xgxfg ????
。令，）计算利用公式（否则，令 )1(1)1()2(11)1( 3,dxxgd ?? ????
为所求极小点；停止，若令 )1(1)1(1,||||,)(.3 ???? ??? kkkk xgxfg ?
）计算。用公式（其中否则，令 4,)(1)1( kkkkk dgd ????? ??
。转，令）计算利用公式（ 3,3.4 )()()1( kkkkk dxx ?? ???
。令 1,?? kk
算法求解下述问题：用例 FR
22212)(m i n xxxf ??
。初始点取为 Tx )2,2()1( ?
解：
.)2,4()( 21 Txxxf ??
次迭代：第 1
,)4,8(1)1( Tgd ?????令
)1()1(
)1(1
1 Add
dg
T
T
???
,20 04),(21)(
2
121 ?
?
??
?
??
?
??
?
??
x
xxxxf?,
20
04 ?
?
??
?
??? A
而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
??
4
8
20
04
)4,8(
4
8
)4,8(
18
5?
)1(1)1()2( dxx ???所以
TT )4,8(185)2,2( ???? T)98,92( ??
次迭代：第 2
.)916,9 8(2 Tg ???
21
22
1 ||||
||||
g
g?? ?,
81
4
48
)916()9 8(
22
22
?
?
??
?
)1(12)2( dgd ?????
TT )4,8(814)916,98( ?????
T)4,1(8140 ??
)2()2(
)2(2
2 Add
dg
T
T
????
?
?
?
?
?
?
???
?
?
?
?
?
?
?
?
?
?
?
?
?
??
4
1
20
04
)4,1()
81
40
(
4
1
)
9
16
,
9
8
(
81
40
2209?
)2(2)2()3( dxx ????
TT )4,1(8140209)98,9 2( ?????
T)0,0(?
Tg )0,0(3 ??
即为所求极小点。)3(x?
3,用于一般函数的共轭梯度法
nRxts
xf
?..
)(m in
共轭梯度法进行修改：对用于正定二次函数的
确定。）计算，需由一维搜索不能利用公式（搜索步长 3)2( i?
。速下降方向，即第一个搜索方向仍取最 )()1( )1()1( xfd ???
算：其它搜索方向按下式计
,)( )()1()1( iiii dxfd ????? ??
。其中 2)(
2)1(
||)(||
||)(||
i
i
i xf
xf
?
?? ??
此时可采取一定能满足停止条件，算法在有限步迭代后不)3(
如下措施：
没有求成一轮搜索后，如果还次迭代为一轮，每次完以 n
新的初始点，的最后一个迭代点作为得极小点，则以上一轮
一轮搜索。一个搜索方向，开始下取最速下降方向作为第
注,如算采用其它形式的公式计在共轭梯度法中，也可 i?
。）共轭梯度法P RPgg ggg
iTi
iiTii ()( 11 ?? ???
