一 维 最 优 化
2,黄金分割法
3,进退法
4,抛物线搜索法
5,三次插值法
1,一维最优化问题
一, 一维最优化问题
下降迭代算法中最优步长的确定
)(m i n)( kkkkk dxfdxf ?? ? ???
.kx
kd
.
k?
一维最优化问题,)(m in xf
Rxts ?..
极值点的必要条件,0)(' ?xf
二, 黄金分割法（ 0.618法）
1,单峰函数
定义,设
)(xf
是区间 ],[ ba 上的一元函数,x 是 )(xf 在 ],[ ba
上的极小点，且对任意的,,],[,2121 xxbaxx ?? 有
（ a） 当 xx ?2 时,;)()( 21 xfxf ?
（ b） 当 时，xx ?1,)()( 21 xfxf ?
a
.,
b
.
x
.,
1x 2x
则称 是单峰函数。
)(xf
.
.
性质：通过计算区间 ],[ ba 内两个不同点的函数值，就可以
确定一个包含极小点的子区间。
定理 设 是区间 ],[ ba 上的一元函数,x 是 )(xf 在 ],[ ba
上的极小点。任取点
)(xf
,],[ badc ?? 则有
（ 1）如果 )()( dfcf ?,则 ;],[ bcx ?
（ 2）如果,)()( dfcf ? 则 。],[ dax ?
a
.,
b
.
x
.,
c d
2,黄金分割法
思想 通过选取试探点使包含极小点的区间不断缩短，
直到区间长度小到一定程度，此时区间上各点的函数
值均接近极小值。
下面推导黄金分割法的计算公式。
上单峰，在设 ],[)( 11 baxf ].,[ 11 bax ?极小点 假设进行
次迭代前第 k ],,[ kk bax ? ],,[,kkkk ba???取 规定,kk ?? ?
,)()( kk ff ?? 和计算 分两种情况：
,)()(.1 kk ff ?? ?若,1 kka ???则令 ;1 kk bb ??
,)()(.2 kk ff ?? ?若,1 kk aa ??则令,1 kkb ??
？与如何确定 kk ??
kkkk ab ??? ??.1
比率相同，即每次迭代区间长度缩短.2
)0()(11 ???? ?? ?? kkkk abab
)1(
)2(
）可得：）与（由式（ 21
??
?
???
????
)(
))(1(
kkkk
kkkk
aba
aba
??
?? )3(
)4(
件：要求其满足以下两个条
ka kbk? ku
？取值的确定?
通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次
迭代的一个迭代点重合，从而减少算法的计算量。
?
,)()()1( kk uffk ??次迭代时有设在第 则有
。],[],[ 11 kkkk uaba ???
,,1 11k ??? kuk ?次迭代时选取在第 ）有则由（ 4
)( 1111 ???? ??? kkkk abau ?
)(2 kkk aba ??? ?
。不必重新计算因此则，如果令 112,1 ?? ??? kkk uu ???
6 1 8.02 1512 ?????? ???
。次迭代时有若在第 )()()2( k kuffk ??同理可得。
算法步骤：
0.],,[.1 11 ??精度要求给定初始区间 ba
.1:?k令
),(382.0 1111 aba ????令 ),(618.0 1111 aba ????
).()( 11 ?? ff 与并计算
,.2 ??? kk ab若 停止,.2 kk abx ??且 否则，；时，转当 3)()( kk ff ?? ?,4)()( 时，转当 kk ff ?? ?
,.3 1 kka ???令,1 kk bb ??,1 kk ???
),(618.0 1111 ???? ??? kkkk aba? ),( 1?kf ?计算 。转 2
,.4 1 kk aa ??令,1 kkb ???,1 kk ?? ??
),(382.0 1111 ???? ??? kkkk aba? ),( 1?kf ?计算
,1,?? kk令
。转 2,1,?? kk令
黄金分割法的迭代效果：第 k次后迭代后所得区间长度为
初始区间长度的 。倍k)2 15( ?
其它的试探点算法,Fibonacci算法。
三．进退法
思想 从一点出发,按一定的步长,试图确定出函数值呈现“高 -低 - 高”
的三点。一个方向不成功，就退回来，再沿相反方向寻找。
进退法的计算步骤
,.1 )0( Rx ?给定初始点,00 ?h初始步长,0hh ?令,)0()1( xx ?
),( )1(xf计算,0?k并令
,.2 )1()4( hxx ??令 ),( )4(xf计算,1,?? kk令
),()(.3 )1()4( xfxf ?若,则转 4 5.否则，转
,.4 )1()2( xx ?令,4()1( xx ? ),()( )1()2( xfxf ? ),()( )4()1( xfxf ?
.2,2,转令 hh ?
如何确定包含极小点的一个区间？
,1.5 ?k若 ；则转 6,7否则，转
,:.6 hh ??令,)4()2( xx ? ),()( )4()2( xfxf ?,2转
,.7 )2((3 ) xx ?令,)1()2( xx ?,)4()1( xx ? 停止计算。
例：
)0(x
)1(x hxx ?? )1()4(
)2(x )1(x )4(x
)3(x )2(x )1(x
)0(x
)1(x )4(xhh ??:
)1(x )2(x)4(x
)3(x)2(x)1(x
。即为包含极小点的区间或区间 ],[],[ )1()3()3()1( xxxx
],[ )1()3( xx：极小点区间 ],[ )3()1( xx极小点区间：
四, 抛物线插值
思想 在极小点附近，用二次三项式 ),()( xfx 逼近目标函数?
处有相同的函数值，在三点与令 )3()2()1()()( xxxxfx ???
并假设 ).()(),()( )3()2()2()1( xfxfxfxf ??
)1(x )2(x )3(x
)(xf
)(x?
x
*x
,)( 2cxbxax ????设
)()( )1(2)1()1()1( xfcxbxax ?????
)()( )2(2)2()2()2( xfcxbxax ?????
)()( )3(2)3()3()3( xfcxbxax ?????
.)( cbx 和的系数近函数解上述方程组，可得逼 ?
的极小点，再求函数 )( x?令
cxbx 2)( ????,0?
解得 cbx 2??
如何计算函数?)(x?
。的极小点的估计值作为以 )( xfx
])()()()()()([2
)()()()()()(
)3()2()1()2()1()3()1()3()2(
)3()2()1()2()1()3()1()3()2( 222222
xfxxxfxxxfxx
xfxxxfxxxfxx
?????
??????
令
抛物线插值算法步骤：
,],[)1( )3()1( xx给定初始区间 ).()(),()( )3()2()2()1( xfxfxfxf ??设
。给定精度。。令 ?)1()0(1,xxk ??
。令。设 3,2,1,)()()()2( )()(2 ????? ixfxcxbxax ii?? 解出
。的极小点解出。系数 cbxxcba k 2)(,,)( ???
及其的函数值最小的三个点中选择和从 )(,,)3( )()3()2()1( xfxxxx k
。）转（。令。重新标记为左、右两点,21:,,)3()2()1( ?? kkxxx
）。否则转（，则算法停止若 3,|)()(| )1()( ??? ?kk xfxf
五, 三次插值法
思路：,0)()()( )1()2()1()2()1( ??? xfxxxxxf 且有，的函数值、在点已知
利用这两点的函数值的极小点。内存在（则区间 )(),.0)( )2()1()2( xfxxxf ??
在这两点有相同的函使它与项式和导数构造一个三次多 )(,)( xfx?
的极小点。的极小点近似并用逼近用数值和导数,)()(,)()( xfxxfx ??
)1(x )2(x
)(xf )(x?
*x
x
设 )1()()()()( )1(2)1(3)1( dxxcxxbxxax ????????
令
?
?
?
?
?
?
?
???
???
?
?
)()(
)()(
)()(
)()(
)2()2(
)1()1(
)2()2(
)1()1(
xfx
xfx
xfx
xfx
?
?
?
?
则有
?
?
?
?
?
?
?
??????
??
???????
?
)()(2)(3
)(
)()()()(
)(
)2()1()2(2)1()2(
)1(
)2()1()2(2)1()2(3)1()2(
)1(
xfcxxbxxa
xfc
xfdxxcxxbxxa
xfd
)2(
。从而确定函数，的值求解方程组得出系数 )(,,,xdcba ?
的方法：确定函数 )( x?
求解满足
??
?
???
??
0)(
0)(
x
x
?
? 的极小点
令 0)(2)(3)( )1(2)1( ??????? cxxbxxax? )3(
。bxxax 2)(6)( )1( ??????而
解方程（ 3），有两种情况：
解得时，当 0.1 ?a
)4(2)1( bcxx ???
由（ 2）可知
。)1()2()2()1(,0)(,0)( xxxfxfc ??????
。所以 0?b
的极小点。是即因此 )(,02)( xxbx ?? ????
。x
解得时，当 0.2 ?a
a
acbbxx
3
32)1( ????? )5(
acb
b
a
acbbax
32
2
3
36)(
2
2
???
?????????此时有
式中应取则在为使 )5(,0)( ??? x?
a
acbbxx
3
32)1( ?????
acbb
c
32 ??
?? )6(
式可知由时，而当 )6(0?a 式所以,)6(2)1( bcxx ???
一表达式。两种情况下极小点的统、是 21
极小点的计算公式：
令 )7()]()([3 )1()2( )1()2( xx xfxfs ???
)8()()( )2()1( xfxfst ?????
)9()()( )2()1(22 xfxftw ????
)10()2)()( )(1)(( )1()2( )2()1()2()1( wxfxf wtxfxxxx ???? ???????则有
算法步骤：
要求计算给定初始点,)(,)(,)(,)(,,.1 )2()1()2()1()2()1( xfxfxfxfxx ??
。满足条件,0)(,0)(,)2()1()1()2( ????? xfxfxx
。给定允许误差 0,0 ?? ??
。和、、计算、、、按照公式 xwts)10()9()8()7(.2
。否则，转；则停止计算，得到点，若 4||.3 )1()2( xxx ???
。停止计算，得到点，若。计算 xxfxfxf ???? |)(|)(,)(.4
。转。则令，若 2)()(,)()(,0)( )1()1()1( xfxfxfxfxxxf ???????
。转。则令，若 2)()(,)()(,0)( )2()2()2( xfxfxfxfxxxf ???????
述问题：用三次插值算法求解下例
20..
13)(m i n 3
??
???
xts
xxxf
。则有取初始点解,2,0 )2()1( ?? xx
,3)(,1)(,2 )2()1()1()2( ???? xfxfxx
。9)(,3)( )2()1( ????? xfxf 得由,33)( 2 ??? xxf
所以,3)]()([3
)1()2(
)1()2( ?
?
??
xx
xfxfs
,3)()( )2()1( ??????? xfxfst
6)()( )2()1(22 ????? xfxftw 。6?? w
。则 1)6239 6391(20 ??? ??????x
是极小点。，所以而 10)( ??? xxf
其它插值算法,有理插值。
收敛速度：三次插值算法的收敛阶为 2。
2,黄金分割法
3,进退法
4,抛物线搜索法
5,三次插值法
1,一维最优化问题
一, 一维最优化问题
下降迭代算法中最优步长的确定
)(m i n)( kkkkk dxfdxf ?? ? ???
.kx
kd
.
k?
一维最优化问题,)(m in xf
Rxts ?..
极值点的必要条件,0)(' ?xf
二, 黄金分割法（ 0.618法）
1,单峰函数
定义,设
)(xf
是区间 ],[ ba 上的一元函数,x 是 )(xf 在 ],[ ba
上的极小点，且对任意的,,],[,2121 xxbaxx ?? 有
（ a） 当 xx ?2 时,;)()( 21 xfxf ?
（ b） 当 时，xx ?1,)()( 21 xfxf ?
a
.,
b
.
x
.,
1x 2x
则称 是单峰函数。
)(xf
.
.
性质：通过计算区间 ],[ ba 内两个不同点的函数值，就可以
确定一个包含极小点的子区间。
定理 设 是区间 ],[ ba 上的一元函数,x 是 )(xf 在 ],[ ba
上的极小点。任取点
)(xf
,],[ badc ?? 则有
（ 1）如果 )()( dfcf ?,则 ;],[ bcx ?
（ 2）如果,)()( dfcf ? 则 。],[ dax ?
a
.,
b
.
x
.,
c d
2,黄金分割法
思想 通过选取试探点使包含极小点的区间不断缩短，
直到区间长度小到一定程度，此时区间上各点的函数
值均接近极小值。
下面推导黄金分割法的计算公式。
上单峰，在设 ],[)( 11 baxf ].,[ 11 bax ?极小点 假设进行
次迭代前第 k ],,[ kk bax ? ],,[,kkkk ba???取 规定,kk ?? ?
,)()( kk ff ?? 和计算 分两种情况：
,)()(.1 kk ff ?? ?若,1 kka ???则令 ;1 kk bb ??
,)()(.2 kk ff ?? ?若,1 kk aa ??则令,1 kkb ??
？与如何确定 kk ??
kkkk ab ??? ??.1
比率相同，即每次迭代区间长度缩短.2
)0()(11 ???? ?? ?? kkkk abab
)1(
)2(
）可得：）与（由式（ 21
??
?
???
????
)(
))(1(
kkkk
kkkk
aba
aba
??
?? )3(
)4(
件：要求其满足以下两个条
ka kbk? ku
？取值的确定?
通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次
迭代的一个迭代点重合，从而减少算法的计算量。
?
,)()()1( kk uffk ??次迭代时有设在第 则有
。],[],[ 11 kkkk uaba ???
,,1 11k ??? kuk ?次迭代时选取在第 ）有则由（ 4
)( 1111 ???? ??? kkkk abau ?
)(2 kkk aba ??? ?
。不必重新计算因此则，如果令 112,1 ?? ??? kkk uu ???
6 1 8.02 1512 ?????? ???
。次迭代时有若在第 )()()2( k kuffk ??同理可得。
算法步骤：
0.],,[.1 11 ??精度要求给定初始区间 ba
.1:?k令
),(382.0 1111 aba ????令 ),(618.0 1111 aba ????
).()( 11 ?? ff 与并计算
,.2 ??? kk ab若 停止,.2 kk abx ??且 否则，；时，转当 3)()( kk ff ?? ?,4)()( 时，转当 kk ff ?? ?
,.3 1 kka ???令,1 kk bb ??,1 kk ???
),(618.0 1111 ???? ??? kkkk aba? ),( 1?kf ?计算 。转 2
,.4 1 kk aa ??令,1 kkb ???,1 kk ?? ??
),(382.0 1111 ???? ??? kkkk aba? ),( 1?kf ?计算
,1,?? kk令
。转 2,1,?? kk令
黄金分割法的迭代效果：第 k次后迭代后所得区间长度为
初始区间长度的 。倍k)2 15( ?
其它的试探点算法,Fibonacci算法。
三．进退法
思想 从一点出发,按一定的步长,试图确定出函数值呈现“高 -低 - 高”
的三点。一个方向不成功，就退回来，再沿相反方向寻找。
进退法的计算步骤
,.1 )0( Rx ?给定初始点,00 ?h初始步长,0hh ?令,)0()1( xx ?
),( )1(xf计算,0?k并令
,.2 )1()4( hxx ??令 ),( )4(xf计算,1,?? kk令
),()(.3 )1()4( xfxf ?若,则转 4 5.否则，转
,.4 )1()2( xx ?令,4()1( xx ? ),()( )1()2( xfxf ? ),()( )4()1( xfxf ?
.2,2,转令 hh ?
如何确定包含极小点的一个区间？
,1.5 ?k若 ；则转 6,7否则，转
,:.6 hh ??令,)4()2( xx ? ),()( )4()2( xfxf ?,2转
,.7 )2((3 ) xx ?令,)1()2( xx ?,)4()1( xx ? 停止计算。
例：
)0(x
)1(x hxx ?? )1()4(
)2(x )1(x )4(x
)3(x )2(x )1(x
)0(x
)1(x )4(xhh ??:
)1(x )2(x)4(x
)3(x)2(x)1(x
。即为包含极小点的区间或区间 ],[],[ )1()3()3()1( xxxx
],[ )1()3( xx：极小点区间 ],[ )3()1( xx极小点区间：
四, 抛物线插值
思想 在极小点附近，用二次三项式 ),()( xfx 逼近目标函数?
处有相同的函数值，在三点与令 )3()2()1()()( xxxxfx ???
并假设 ).()(),()( )3()2()2()1( xfxfxfxf ??
)1(x )2(x )3(x
)(xf
)(x?
x
*x
,)( 2cxbxax ????设
)()( )1(2)1()1()1( xfcxbxax ?????
)()( )2(2)2()2()2( xfcxbxax ?????
)()( )3(2)3()3()3( xfcxbxax ?????
.)( cbx 和的系数近函数解上述方程组，可得逼 ?
的极小点，再求函数 )( x?令
cxbx 2)( ????,0?
解得 cbx 2??
如何计算函数?)(x?
。的极小点的估计值作为以 )( xfx
])()()()()()([2
)()()()()()(
)3()2()1()2()1()3()1()3()2(
)3()2()1()2()1()3()1()3()2( 222222
xfxxxfxxxfxx
xfxxxfxxxfxx
?????
??????
令
抛物线插值算法步骤：
,],[)1( )3()1( xx给定初始区间 ).()(),()( )3()2()2()1( xfxfxfxf ??设
。给定精度。。令 ?)1()0(1,xxk ??
。令。设 3,2,1,)()()()2( )()(2 ????? ixfxcxbxax ii?? 解出
。的极小点解出。系数 cbxxcba k 2)(,,)( ???
及其的函数值最小的三个点中选择和从 )(,,)3( )()3()2()1( xfxxxx k
。）转（。令。重新标记为左、右两点,21:,,)3()2()1( ?? kkxxx
）。否则转（，则算法停止若 3,|)()(| )1()( ??? ?kk xfxf
五, 三次插值法
思路：,0)()()( )1()2()1()2()1( ??? xfxxxxxf 且有，的函数值、在点已知
利用这两点的函数值的极小点。内存在（则区间 )(),.0)( )2()1()2( xfxxxf ??
在这两点有相同的函使它与项式和导数构造一个三次多 )(,)( xfx?
的极小点。的极小点近似并用逼近用数值和导数,)()(,)()( xfxxfx ??
)1(x )2(x
)(xf )(x?
*x
x
设 )1()()()()( )1(2)1(3)1( dxxcxxbxxax ????????
令
?
?
?
?
?
?
?
???
???
?
?
)()(
)()(
)()(
)()(
)2()2(
)1()1(
)2()2(
)1()1(
xfx
xfx
xfx
xfx
?
?
?
?
则有
?
?
?
?
?
?
?
??????
??
???????
?
)()(2)(3
)(
)()()()(
)(
)2()1()2(2)1()2(
)1(
)2()1()2(2)1()2(3)1()2(
)1(
xfcxxbxxa
xfc
xfdxxcxxbxxa
xfd
)2(
。从而确定函数，的值求解方程组得出系数 )(,,,xdcba ?
的方法：确定函数 )( x?
求解满足
??
?
???
??
0)(
0)(
x
x
?
? 的极小点
令 0)(2)(3)( )1(2)1( ??????? cxxbxxax? )3(
。bxxax 2)(6)( )1( ??????而
解方程（ 3），有两种情况：
解得时，当 0.1 ?a
)4(2)1( bcxx ???
由（ 2）可知
。)1()2()2()1(,0)(,0)( xxxfxfc ??????
。所以 0?b
的极小点。是即因此 )(,02)( xxbx ?? ????
。x
解得时，当 0.2 ?a
a
acbbxx
3
32)1( ????? )5(
acb
b
a
acbbax
32
2
3
36)(
2
2
???
?????????此时有
式中应取则在为使 )5(,0)( ??? x?
a
acbbxx
3
32)1( ?????
acbb
c
32 ??
?? )6(
式可知由时，而当 )6(0?a 式所以,)6(2)1( bcxx ???
一表达式。两种情况下极小点的统、是 21
极小点的计算公式：
令 )7()]()([3 )1()2( )1()2( xx xfxfs ???
)8()()( )2()1( xfxfst ?????
)9()()( )2()1(22 xfxftw ????
)10()2)()( )(1)(( )1()2( )2()1()2()1( wxfxf wtxfxxxx ???? ???????则有
算法步骤：
要求计算给定初始点,)(,)(,)(,)(,,.1 )2()1()2()1()2()1( xfxfxfxfxx ??
。满足条件,0)(,0)(,)2()1()1()2( ????? xfxfxx
。给定允许误差 0,0 ?? ??
。和、、计算、、、按照公式 xwts)10()9()8()7(.2
。否则，转；则停止计算，得到点，若 4||.3 )1()2( xxx ???
。停止计算，得到点，若。计算 xxfxfxf ???? |)(|)(,)(.4
。转。则令，若 2)()(,)()(,0)( )1()1()1( xfxfxfxfxxxf ???????
。转。则令，若 2)()(,)()(,0)( )2()2()2( xfxfxfxfxxxf ???????
述问题：用三次插值算法求解下例
20..
13)(m i n 3
??
???
xts
xxxf
。则有取初始点解,2,0 )2()1( ?? xx
,3)(,1)(,2 )2()1()1()2( ???? xfxfxx
。9)(,3)( )2()1( ????? xfxf 得由,33)( 2 ??? xxf
所以,3)]()([3
)1()2(
)1()2( ?
?
??
xx
xfxfs
,3)()( )2()1( ??????? xfxfst
6)()( )2()1(22 ????? xfxftw 。6?? w
。则 1)6239 6391(20 ??? ??????x
是极小点。，所以而 10)( ??? xxf
其它插值算法,有理插值。
收敛速度：三次插值算法的收敛阶为 2。
