无约束最优化问题的直接方法
1,模式搜索法
2,Powell 算法
3,单纯形替换法
无约束最优化问题的直接方法
无约束最优化问题;)(m in xf
直接方法,算函数值的方法。不用计算导数，只需计
一, 模式搜索法 年）方法，（ 1 9 6 1J e e v e sH o o k e ?
基本思想,向交替实施两种搜索：轴算法从初始基点开始，
个坐标轴的方向进行，搜索依次沿搜索和模式搜索。轴向 n
。模式搜索则利于函数值下降的方向用来确定新的基点和有
数值下降更快。线方向进行，试图使函沿着相邻两个基点的连
.1
算法分析.2;)(m in xf问题
个坐标轴方向。表示令 nnje Tj,,2,1,)0,,0,1,0,,0( ??? ??
作为第一个基点。。任取初始点，加速因子给定初始步长 1x??
个基点。表示第以下用 jx j
方向搜索时个坐标轴表示沿第用在每一轮轴向搜索中,ii eiy
的出发点。
轴向搜索：
。令 11 xy ?
O 1e
2e
)1()1( yx ?
方向搜索：沿 1e
，则令如果 )()( 111 yfeyf ?? ?;112 eyy ???
，否则，如果 )()( 111 yfeyf ?? ?;112 eyy ???则令
。令否则,12 yy ?
)2(y
，进行搜索得到出发，仿上沿再从 322 yey
)3(y
O 1e
2e
)1()1( yx ? )2(y
)3(y
。到点依次进行搜索，直到得 1?ny)( 一轮轴向搜索结束。
模式搜索：
,)()( 11 xfyf n ??如果
。则令 12 ?? nyx
方向可能有利于函数12 xx ?
12 xx ?值下降，因此下一步沿
方向进行模式搜索。
即令 。)( 1221 xxxy ??? ?
)2(x?
)1(y
为起点进行新的，仍以则缩小步长如果 111,)()( xxfyf n ???
轴向搜索。 否则，进行模式搜索。
有效？如何判断模式搜索是否
。搜索，所得的点仍记为为起点进行下一轮轴向以 11 ?nyy
，令表明此次模式搜索成功如果,)()( 21 xfyf n ??
。13 ?? nyx 仿上继续进行迭代。
表明此次如果,)()( 21 xfyf n ??
进行下一轮轴向搜索。
，点模式搜索失败，返回基 2x
O 1e
2e
)1()1( yx ? )2(y
)3(y )2(x?
)1(y
)2(y
)3(y?
x
1x
2x
3x
4x
5x 6x
模式搜索法：
，缩减率，加速因子初始步长给定初始点 1,)1( 1 ?? ??nRx
。精度 0,)1,0( ?? ?? 。令 1,1,11 ??? jkxy
轴向搜索：)2(
）；（转则令如果 3,,)()( 1 jjjjjj eyyyfeyf ?? ???? ?
）；（转则令如果 3,,)()( 1 jjjjjj eyyyfeyf ?? ???? ?
。否则，令 jj yy ?? 1
。转则令，若 )2(,1:)3( ??? jjnj
。否则，转；转如果 )5()4(,)()( 1 kn xfyf ??
。令模式搜索,)(,)4( 11111 kkknk xxxyyx ???? ???? ?
）。转（令 2,1,1,??? jkk；停止，得到点如果 )(,)5( kx?? ?,,??? ?否则，令
。kkk xxxy ?? ? 11,
）。转（令 2,1,1,??? jkk
注 维搜索确定步长，中的固定步长改为用一将轴向搜索和模式搜索
算法仍然收敛。
用模式搜索法求解问题例,1
。2221)(m i n xxxf ??
,125.0,)1,1(1 ??? ?? 加速因子，初始步长取初始点 Tx缩减
。率 2.0??
:解 轮迭代：第 1
。则令 2)(,)1,1( 111 ??? yfxy T
,)(5625.2)( 111 yfeyf ??? ??
,)(5 6 2 5.1)( 111 yfeyf ??? ?
。Teyy )1,75.0(112 ???? ?
,)(125.2)( 222 yfeyf ??? ??
,)(1 2 5.1)( 222 yfeyf ??? ?
。Teyy )75.0,75.0(223 ???? ?
,)()( 13 xfyf ??
。令 32 yx ??
。取加速方向 Txxd )25.0,25.0(121 ?????
模式搜索：
。Tdxy )5.0,5.0(121 ??? ?
二, Powell 方法
基本思想：
调整搜索方向三个基本搜索、加速搜索和方法主要由 P o w e l l
个搜索方向的括从基点出发沿着已知部分组成。基本搜索包 n
个新基点。进行一维搜索，确定一 的两加速搜索是指沿着相邻
降更快。一维搜索，使函数值下个基点的连线方向进行 最后用基点
新的搜索方向组，个搜索方向之一，构成连线方向代替已知的 n
进行下一轮迭代。
原始 Powell 法步骤：
个线性无关的方向：给定初始点 nx,)1( 0 。),1()2,1()1,1(,,,nddd ?
。，令允许误差 10 ?? k?
出发，依次沿方向从令 )0,(1)0,(,)2( kkk xxx ??
),()2,()1,(,,,nkkk ddd ?进行搜索,即令
??
???
???
??
??
?
)(m i n)(,),()1,(),()1,(
),()1,(),(
jkjk
t
jk
j
jk
j
jk
j
jkjk
dtxfdtxft
dtxx
得到点 。),()2,()1,(,,,nkkk xxx ?
进行一维出发沿从令 )1,(),()0,(),()1,(,?? ?? nknkknknk dxxxd
。搜索得到点 kx
否则，令，停止，得到点若 ;||||)3( 1 kkk xxx ??? ?
。njdd jkjk,,2,1,)1,(),1( ??? ??
）。返回（令 2,1,?? kk
.2例 方法求解下述问题：用原始 P o w e l l
21221 )1()()(m i n ???? xxxxf
。初始搜索方向为初始点为 TTT ddx )1,0(,)0,1(,)1,2( )2,1()1,1(0 ???
解,第一轮迭代：
。令 0)0,1( xx ? 作一维搜索，即求解出发沿着方向从 )1,1()0,1( dx
.)(m i n )1,1()0,1( dtxft ?
TTT ttdtx )1,2()0,1()1,2()1,1()0,1( ??????
,)1()3()()( 22)1,1()0,1( ttdtxft ???????记
,0)1(2)3(2 ????? ttdtd ?令
。解得 21 ??t
。Tdtxx )1,0()1,1()0,1()1,1( ????
作一维搜索，即求解出发，沿着方向再从 )2,1()1,1( dx
.)(m i n )2,1()1,1( dtxft ?
，解得 12 ??t 。所以 Tdtxx )0,0()2,1(2)1,1()2,1( ???
。令方向 Txxd )1,2()0,1()2,1()3,1( ?????
求解,)(m i n )3,1()2,1( dtxft ?
。解得 1323 ??t
第二轮搜索：
,)132,134(1)0,2( Txx ??初始点
。所以 Tdtxx )132,134()3,1(3)2,1(1 ???
:搜索方向为
。TT dddd )1,2(,)1,0( )3,1()2,2()2,1()1,2( ??????
求解 。)(m i n )1,2()0,2( dtxf
t ?
。所以解得 Tdtxxt )13 4,134(,13 6 )1,2(1)0,2()1,2(1 ??????
求解 。)(m i n )2,2()1,2( dtxf
t ?
。所以解得 Tdtxxt )169 34,16988(,169 18 )2,2(2)1,2()2,2(2 ??????
。令方向 Txxd )169 60,16936()0,2()2,2()3,2( ????
求解 。)(m i n )3,2()2,2( dtxft ?
,493 ?t解得
。所以极小点为 Tdtxx )1,1()3,2(3)2,2(2 ????
0x
)1,1(x
1x
2x
)2,1(x
o
1x
)1,2(x
)2,2(x
2x
迭代过程
定理 对称正定矩阵。阶是，其中设 nAcxbAxxxf TT ??? 21)(
作一维搜索得极小出发沿方向。从和点任意取定方向 dxxxd 121,
dyyydxy 方向与则有作一维搜索得极小点出发沿方向从点 12221,,?
共轭。关于 A
的分析：对例 2
。第一轮搜索方向,TTT ddd )1,2(,)1,0(,)0,1( )3,1()2,1()1,1( ?????
。第二轮搜索方向：, TTT ddd )16960,16936(,)1,2(,)1,0( )3,2()22()1,2( ??????
搜索得极小点沿方向搜索得到极小点沿方向 )2,2()0,2(1)3,1(,dxxd ?
,)2,2(x 共轭。和方向所以由定理可知方向 )2,2()0,2()2,2()3,2( dxxd ??
的，因此必为极小点。是沿共轭方向搜索得到2x
定理 对称正定矩阵。阶是，其中设 nAcxbAxxxf TT ??? 21)(
法求解下述最优化问题用原始 P o w e ll
。)(m in xf
下一轮所确定的轮，且每一轮迭代后为若迭代已进行了 )( nmm ?
线性无关，则各轮迭代个搜索方向前 )(,,,),()2,()1,( mkdddn nkkk ??
共轭的向量组。成所产生的加速方向必构 A
注
法。算法是一种共轭方向算原始 P o w e l l.1
个搜索方向线性无关。的前算法不能保证各轮迭代原始 nP o w e l l.2
.3例 方法求解下述问题：用原始 P o w e l l
,)(m i n 2221 xxxf ??
。初始搜索方向为初始点为 TTT ddx )1,0(,)1,1(,)1,1( )2,1()1,1(0 ????
解,第一轮迭代：
。令 0)0,1( xx ?
.)(m i n )1,1()0,1( dtxft ?求解
。，所以解得 Tdtxxt )1,1(0 )1,1(1)0,1()1,1(1 ????
.)(m i n )2,1()1,1( dtxft ?求解
。，所以解得 Tdtxxt )0,1(1 )2,1(2)1,1()2,1(2 ?????
。令方向 Txxd )1,0()0,1()2,1()3,1( ????
.)(m i n )3,1()2,1( dtxft ?求解
。，所以解得 Tdtxxt )0,1(0 )3,1(3)2,1(13 ????
第二轮迭代：
搜索方向,。TT dddd )1,0(,)1,0( )3,1()2,2()2,1()1,2( ?????
，到的线性相关，以下迭代得和 )2()0,1()2,2()1,2( ?? kxdd Tk
。不能得到最优解 Tx )0,0(* ?
个搜索方向线性无关？如何确保各轮迭代的前问题,n
)0,(),()1,( knknk xxd ???
分析：)1(
)0,(),()1,( )( knknnk xdtx ??? ?
??
)0,(),()2,(2)1,(1)0,( knknkkk xdtdtdtx ?????? ?
),()2,(2)1,(1 nknkk dtdtdt ???? ?
因。搜索方向线性相关的原
的线性组合。，，，是则如果 ),()3,()2,()1,(1,0 nkkknk ddddt ???
个搜索方向线性相关。轮的则第令 nkdd ikik 1,)1,(),1( ?? ??
解决方法：)2(
但不一定是个搜索方向中的一个，换出原来的每次用 nd nk )1,( ?
第一个。
搜索方向？如何确定应换出哪一个
。个搜索方向是单位向量假设初始的 n
。令 )0,(),(
)0,(),(
)1,(
knk
knk
nk
xx
xxd
?
???
满足使其选择搜索方向,),( skd
,||m a x|| 1 inis tt ???
,|),,,,,,(d e t| ),()1,()1,()1,()1,( ????? nksknkskk ddddd ??且
。否则，令 nidd ikik,,2,1,),(),1( ????
次的搜索方向。构成第换出则用 1,),()1,( ?? kdd sknk
行列式的计算)3(
|),,,,,,d et (| ),()1,()1,()1,()1,(1 nksknkskkk ddddd ?? ???? ??
|),,,,,,d e t(| ),()1,()0,(),(
),()1,(
1)1,()1,( nksk
knk
nk
n
k
skk dd
xx
dtdtdd ??? ??
?
???
|),,,,,,d e t(||| ),()1,(),()1,()1,()0,(),( nkskskskkknk s dddddxx t ?? ????
kknk
s
xx
t ?
?? )0,(),(
||
方法：改进的 P o w e ll
个线性无关的方向：给定初始点 nx,)1( 0 。nied ii,,1,),0( ???
。，令允许误差 0,10 0 ???? k?
。令 kk xx ?)0,()2(
??
???
???
??
??
?
)(m i n)(,),()1,(),()1,(
),()1,(),(
jkjk
t
jk
j
jk
j
jk
j
jkjk
dtxfdtxft
dtxx
即个方向进行一维搜索，依次沿 n
令。令 )0,(),(
)0,(),(
)1,()3(
knk
knk
nk
xx
xxd
?
???
??
???
???
??
??
??
?
?
?
)(m i n)(,)1,(),()1,(1),(1
)1,(
1
),(1
nknk
t
nk
n
nk
n
nk
n
nkk
dtxfdtxft
dtxx
）。否则转（算法结束，令如果 5;,)4( 1*1 ?? ??? kkk xxxx ?
,0:,,,1,1)5( 0),0( ?????? kxxniednk nii 令。则令，若 ?）。转（ 2
。使得确定，若 inis ttsnk ????? 1m a x1
,)0,(),( ???? kknk s xx t如果 。则 nidd ikik,,1),(),1( ????
）。转（令 2,1 kk ??? ?；则令如果 1,,1,,),(),1()0,(),( ?????? ? siddxx t ikikkknk s ??
。nsidddd ikiknksk,,1,; )1,(),1()1,(),1( ????? ????
）。转（令 2,1:,)0,(),(1 ?????? ? kkxx t kknk sk
1,模式搜索法
2,Powell 算法
3,单纯形替换法
无约束最优化问题的直接方法
无约束最优化问题;)(m in xf
直接方法,算函数值的方法。不用计算导数，只需计
一, 模式搜索法 年）方法，（ 1 9 6 1J e e v e sH o o k e ?
基本思想,向交替实施两种搜索：轴算法从初始基点开始，
个坐标轴的方向进行，搜索依次沿搜索和模式搜索。轴向 n
。模式搜索则利于函数值下降的方向用来确定新的基点和有
数值下降更快。线方向进行，试图使函沿着相邻两个基点的连
.1
算法分析.2;)(m in xf问题
个坐标轴方向。表示令 nnje Tj,,2,1,)0,,0,1,0,,0( ??? ??
作为第一个基点。。任取初始点，加速因子给定初始步长 1x??
个基点。表示第以下用 jx j
方向搜索时个坐标轴表示沿第用在每一轮轴向搜索中,ii eiy
的出发点。
轴向搜索：
。令 11 xy ?
O 1e
2e
)1()1( yx ?
方向搜索：沿 1e
，则令如果 )()( 111 yfeyf ?? ?;112 eyy ???
，否则，如果 )()( 111 yfeyf ?? ?;112 eyy ???则令
。令否则,12 yy ?
)2(y
，进行搜索得到出发，仿上沿再从 322 yey
)3(y
O 1e
2e
)1()1( yx ? )2(y
)3(y
。到点依次进行搜索，直到得 1?ny)( 一轮轴向搜索结束。
模式搜索：
,)()( 11 xfyf n ??如果
。则令 12 ?? nyx
方向可能有利于函数12 xx ?
12 xx ?值下降，因此下一步沿
方向进行模式搜索。
即令 。)( 1221 xxxy ??? ?
)2(x?
)1(y
为起点进行新的，仍以则缩小步长如果 111,)()( xxfyf n ???
轴向搜索。 否则，进行模式搜索。
有效？如何判断模式搜索是否
。搜索，所得的点仍记为为起点进行下一轮轴向以 11 ?nyy
，令表明此次模式搜索成功如果,)()( 21 xfyf n ??
。13 ?? nyx 仿上继续进行迭代。
表明此次如果,)()( 21 xfyf n ??
进行下一轮轴向搜索。
，点模式搜索失败，返回基 2x
O 1e
2e
)1()1( yx ? )2(y
)3(y )2(x?
)1(y
)2(y
)3(y?
x
1x
2x
3x
4x
5x 6x
模式搜索法：
，缩减率，加速因子初始步长给定初始点 1,)1( 1 ?? ??nRx
。精度 0,)1,0( ?? ?? 。令 1,1,11 ??? jkxy
轴向搜索：)2(
）；（转则令如果 3,,)()( 1 jjjjjj eyyyfeyf ?? ???? ?
）；（转则令如果 3,,)()( 1 jjjjjj eyyyfeyf ?? ???? ?
。否则，令 jj yy ?? 1
。转则令，若 )2(,1:)3( ??? jjnj
。否则，转；转如果 )5()4(,)()( 1 kn xfyf ??
。令模式搜索,)(,)4( 11111 kkknk xxxyyx ???? ???? ?
）。转（令 2,1,1,??? jkk；停止，得到点如果 )(,)5( kx?? ?,,??? ?否则，令
。kkk xxxy ?? ? 11,
）。转（令 2,1,1,??? jkk
注 维搜索确定步长，中的固定步长改为用一将轴向搜索和模式搜索
算法仍然收敛。
用模式搜索法求解问题例,1
。2221)(m i n xxxf ??
,125.0,)1,1(1 ??? ?? 加速因子，初始步长取初始点 Tx缩减
。率 2.0??
:解 轮迭代：第 1
。则令 2)(,)1,1( 111 ??? yfxy T
,)(5625.2)( 111 yfeyf ??? ??
,)(5 6 2 5.1)( 111 yfeyf ??? ?
。Teyy )1,75.0(112 ???? ?
,)(125.2)( 222 yfeyf ??? ??
,)(1 2 5.1)( 222 yfeyf ??? ?
。Teyy )75.0,75.0(223 ???? ?
,)()( 13 xfyf ??
。令 32 yx ??
。取加速方向 Txxd )25.0,25.0(121 ?????
模式搜索：
。Tdxy )5.0,5.0(121 ??? ?
二, Powell 方法
基本思想：
调整搜索方向三个基本搜索、加速搜索和方法主要由 P o w e l l
个搜索方向的括从基点出发沿着已知部分组成。基本搜索包 n
个新基点。进行一维搜索，确定一 的两加速搜索是指沿着相邻
降更快。一维搜索，使函数值下个基点的连线方向进行 最后用基点
新的搜索方向组，个搜索方向之一，构成连线方向代替已知的 n
进行下一轮迭代。
原始 Powell 法步骤：
个线性无关的方向：给定初始点 nx,)1( 0 。),1()2,1()1,1(,,,nddd ?
。，令允许误差 10 ?? k?
出发，依次沿方向从令 )0,(1)0,(,)2( kkk xxx ??
),()2,()1,(,,,nkkk ddd ?进行搜索,即令
??
???
???
??
??
?
)(m i n)(,),()1,(),()1,(
),()1,(),(
jkjk
t
jk
j
jk
j
jk
j
jkjk
dtxfdtxft
dtxx
得到点 。),()2,()1,(,,,nkkk xxx ?
进行一维出发沿从令 )1,(),()0,(),()1,(,?? ?? nknkknknk dxxxd
。搜索得到点 kx
否则，令，停止，得到点若 ;||||)3( 1 kkk xxx ??? ?
。njdd jkjk,,2,1,)1,(),1( ??? ??
）。返回（令 2,1,?? kk
.2例 方法求解下述问题：用原始 P o w e l l
21221 )1()()(m i n ???? xxxxf
。初始搜索方向为初始点为 TTT ddx )1,0(,)0,1(,)1,2( )2,1()1,1(0 ???
解,第一轮迭代：
。令 0)0,1( xx ? 作一维搜索，即求解出发沿着方向从 )1,1()0,1( dx
.)(m i n )1,1()0,1( dtxft ?
TTT ttdtx )1,2()0,1()1,2()1,1()0,1( ??????
,)1()3()()( 22)1,1()0,1( ttdtxft ???????记
,0)1(2)3(2 ????? ttdtd ?令
。解得 21 ??t
。Tdtxx )1,0()1,1()0,1()1,1( ????
作一维搜索，即求解出发，沿着方向再从 )2,1()1,1( dx
.)(m i n )2,1()1,1( dtxft ?
，解得 12 ??t 。所以 Tdtxx )0,0()2,1(2)1,1()2,1( ???
。令方向 Txxd )1,2()0,1()2,1()3,1( ?????
求解,)(m i n )3,1()2,1( dtxft ?
。解得 1323 ??t
第二轮搜索：
,)132,134(1)0,2( Txx ??初始点
。所以 Tdtxx )132,134()3,1(3)2,1(1 ???
:搜索方向为
。TT dddd )1,2(,)1,0( )3,1()2,2()2,1()1,2( ??????
求解 。)(m i n )1,2()0,2( dtxf
t ?
。所以解得 Tdtxxt )13 4,134(,13 6 )1,2(1)0,2()1,2(1 ??????
求解 。)(m i n )2,2()1,2( dtxf
t ?
。所以解得 Tdtxxt )169 34,16988(,169 18 )2,2(2)1,2()2,2(2 ??????
。令方向 Txxd )169 60,16936()0,2()2,2()3,2( ????
求解 。)(m i n )3,2()2,2( dtxft ?
,493 ?t解得
。所以极小点为 Tdtxx )1,1()3,2(3)2,2(2 ????
0x
)1,1(x
1x
2x
)2,1(x
o
1x
)1,2(x
)2,2(x
2x
迭代过程
定理 对称正定矩阵。阶是，其中设 nAcxbAxxxf TT ??? 21)(
作一维搜索得极小出发沿方向。从和点任意取定方向 dxxxd 121,
dyyydxy 方向与则有作一维搜索得极小点出发沿方向从点 12221,,?
共轭。关于 A
的分析：对例 2
。第一轮搜索方向,TTT ddd )1,2(,)1,0(,)0,1( )3,1()2,1()1,1( ?????
。第二轮搜索方向：, TTT ddd )16960,16936(,)1,2(,)1,0( )3,2()22()1,2( ??????
搜索得极小点沿方向搜索得到极小点沿方向 )2,2()0,2(1)3,1(,dxxd ?
,)2,2(x 共轭。和方向所以由定理可知方向 )2,2()0,2()2,2()3,2( dxxd ??
的，因此必为极小点。是沿共轭方向搜索得到2x
定理 对称正定矩阵。阶是，其中设 nAcxbAxxxf TT ??? 21)(
法求解下述最优化问题用原始 P o w e ll
。)(m in xf
下一轮所确定的轮，且每一轮迭代后为若迭代已进行了 )( nmm ?
线性无关，则各轮迭代个搜索方向前 )(,,,),()2,()1,( mkdddn nkkk ??
共轭的向量组。成所产生的加速方向必构 A
注
法。算法是一种共轭方向算原始 P o w e l l.1
个搜索方向线性无关。的前算法不能保证各轮迭代原始 nP o w e l l.2
.3例 方法求解下述问题：用原始 P o w e l l
,)(m i n 2221 xxxf ??
。初始搜索方向为初始点为 TTT ddx )1,0(,)1,1(,)1,1( )2,1()1,1(0 ????
解,第一轮迭代：
。令 0)0,1( xx ?
.)(m i n )1,1()0,1( dtxft ?求解
。，所以解得 Tdtxxt )1,1(0 )1,1(1)0,1()1,1(1 ????
.)(m i n )2,1()1,1( dtxft ?求解
。，所以解得 Tdtxxt )0,1(1 )2,1(2)1,1()2,1(2 ?????
。令方向 Txxd )1,0()0,1()2,1()3,1( ????
.)(m i n )3,1()2,1( dtxft ?求解
。，所以解得 Tdtxxt )0,1(0 )3,1(3)2,1(13 ????
第二轮迭代：
搜索方向,。TT dddd )1,0(,)1,0( )3,1()2,2()2,1()1,2( ?????
，到的线性相关，以下迭代得和 )2()0,1()2,2()1,2( ?? kxdd Tk
。不能得到最优解 Tx )0,0(* ?
个搜索方向线性无关？如何确保各轮迭代的前问题,n
)0,(),()1,( knknk xxd ???
分析：)1(
)0,(),()1,( )( knknnk xdtx ??? ?
??
)0,(),()2,(2)1,(1)0,( knknkkk xdtdtdtx ?????? ?
),()2,(2)1,(1 nknkk dtdtdt ???? ?
因。搜索方向线性相关的原
的线性组合。，，，是则如果 ),()3,()2,()1,(1,0 nkkknk ddddt ???
个搜索方向线性相关。轮的则第令 nkdd ikik 1,)1,(),1( ?? ??
解决方法：)2(
但不一定是个搜索方向中的一个，换出原来的每次用 nd nk )1,( ?
第一个。
搜索方向？如何确定应换出哪一个
。个搜索方向是单位向量假设初始的 n
。令 )0,(),(
)0,(),(
)1,(
knk
knk
nk
xx
xxd
?
???
满足使其选择搜索方向,),( skd
,||m a x|| 1 inis tt ???
,|),,,,,,(d e t| ),()1,()1,()1,()1,( ????? nksknkskk ddddd ??且
。否则，令 nidd ikik,,2,1,),(),1( ????
次的搜索方向。构成第换出则用 1,),()1,( ?? kdd sknk
行列式的计算)3(
|),,,,,,d et (| ),()1,()1,()1,()1,(1 nksknkskkk ddddd ?? ???? ??
|),,,,,,d e t(| ),()1,()0,(),(
),()1,(
1)1,()1,( nksk
knk
nk
n
k
skk dd
xx
dtdtdd ??? ??
?
???
|),,,,,,d e t(||| ),()1,(),()1,()1,()0,(),( nkskskskkknk s dddddxx t ?? ????
kknk
s
xx
t ?
?? )0,(),(
||
方法：改进的 P o w e ll
个线性无关的方向：给定初始点 nx,)1( 0 。nied ii,,1,),0( ???
。，令允许误差 0,10 0 ???? k?
。令 kk xx ?)0,()2(
??
???
???
??
??
?
)(m i n)(,),()1,(),()1,(
),()1,(),(
jkjk
t
jk
j
jk
j
jk
j
jkjk
dtxfdtxft
dtxx
即个方向进行一维搜索，依次沿 n
令。令 )0,(),(
)0,(),(
)1,()3(
knk
knk
nk
xx
xxd
?
???
??
???
???
??
??
??
?
?
?
)(m i n)(,)1,(),()1,(1),(1
)1,(
1
),(1
nknk
t
nk
n
nk
n
nk
n
nkk
dtxfdtxft
dtxx
）。否则转（算法结束，令如果 5;,)4( 1*1 ?? ??? kkk xxxx ?
,0:,,,1,1)5( 0),0( ?????? kxxniednk nii 令。则令，若 ?）。转（ 2
。使得确定，若 inis ttsnk ????? 1m a x1
,)0,(),( ???? kknk s xx t如果 。则 nidd ikik,,1),(),1( ????
）。转（令 2,1 kk ??? ?；则令如果 1,,1,,),(),1()0,(),( ?????? ? siddxx t ikikkknk s ??
。nsidddd ikiknksk,,1,; )1,(),1()1,(),1( ????? ????
）。转（令 2,1:,)0,(),(1 ?????? ? kkxx t kknk sk
