单纯形替换法
1.单纯形替换法, Spendley,Hext 和 Himsworth
于 1962年提出 ;
Nelder 和 Mead 1965年改进
2,问 题,
)x(fm inn
Rx ?
上连续函数是 nR)x(f
)R(C)x(f n?即
集合迭代的思想。( 1 )
为单纯形这里 ),,i(S
SSSS
i
kk
?
??
21
110
?
????? ?
3.算法思想
下降迭代的思想。( 2 )
降。中顶点的目标函数值下使 iS
4,单纯形概念
例：
三角形:2R
(1)
四面体:3R
线段:1R 0V 1V
0V
0V 1V
1V
2V
2V
3V
,RV,,V,V nn ??10设,),,2,1(0 线性无关如果 njVV j ???
即记为单纯形
构成的的凸组合称为由则
,],,,[,
,,,,,,
10
1010
n
nn
VVVS
VVVVVV
?
??
?
],,,[ 10 nVVVS ??
为该单纯形的顶点。称 nV,,V,V ?10
（ 2）单纯形的定义
0},1,|{
00
??? ??
??
j
n
j
j
n
j
j
jVx ??? 其中
形：，有两种方式构造单纯和正数对于给定的点 ?0x
)eee(VVeVV
)ee(VVeVV
eVVeVV
xV
n
n
n
nn
?
????
????????
???????
??????
?
?
21
01
21
02
2
12
1
01
1
01
00
( 1 )
5.如何构造单纯形?
。构成一个单纯形则 ],,,[ 10 nVVVS ??
例 。（设 2
1,)1,0,10 ?? ?TV
则,)1,0,23()0,0,1(21)1,0,1(101 TTTeVV ????? ?
,)1,21,23()0,1,0(21)1,0,23(212 TTTeVV ????? ?
。TTTeVV )23,21,23()1,0,0(21)1,21,23(323 ????? ?
。构成一个单纯形则 ],,,[ 3210 VVVVS ?
6.单纯形替换法的几何解释
*x
0V 2V
1V
V
rV
eV
。给定单纯形 ],,,[ 10 nVVVS ??
,})(,,)(,)({m a x)( 10 nh VfVfVfVf ??设
。})(,,)(,)({m in)( 10 nl VfVfVfVf ??
延伸步：
:)()( lr VfVf ?如果
。一般取延伸系数延伸点 2:β,?β，V e,
，则令 )( VVVV re ??? ?
)(,hr VVVV ??? ?反射步
。一般取，反射系数，反射点 1:,???rV
。令 ?
?
?
hi
iV
nV
1
,,),()( 构成新的单纯形代替则用若 hele VVVfVf ?
构成新的单纯形。代替否则用,hr VV
0V 2V
1V
V rVcV
。：收缩系数，一般取收缩点，
，则令
有
2
1
:
)(
)()()(
?
???
????
??
?
c
rc
hri
V
VVVV
VfVfVfhi
:收缩步（情形一）
构成新的单纯形。代替则用若,),()( hchc VVVfVf ?
0V
2V
1V V rV
cV
:收缩步（情形二）
。：收缩系数，一般取收缩点，
，则令，若
2
1:
)()()(
?
????
??
?
c
hchr
V
VVVVVfVf
构成新的单纯形。代替则用若,),()( hchc VVVfVf ?
。
棱长减半步：
],,,[
n),1,,0(i
2
1
1
no
k
li
i
VVVS
VV
V
?
?
?
?
?
?
?
)()( hc VfVf ?如果
.s t ep)V(f)V(f
.s t ep)V(f)V(f
lr
lr
5
4
则转，如果
则转，如果
?
?
7.单纯形替换法的步骤
00][
1
10
0
????,k,,V,,VVS
,x).(S t e p
no,精度
构造初始单纯形给定初始点初始步
?
。
，
，计算（准备步）
nVV
VfVf
VfVfS t e p
hi
i
i
ni
l
i
ni
h
/
)(m i n)(
)(m ax)(.2
0
0
?
?
??
??
?
?
?
)::V(
)VV(VV).(s t ep
r
hr
1
3
???
????
一般取，反射系数，反射点
反射步
)V(
)VV(V)VV(VV).(s t ep
e
rhe
2一般取，延伸系数:延伸点:
4
???
????????
，
延伸步
.s t e pV,,V,VS,VV
)V(f)V(f)V(f)V(f
n
k
eh
rele
（判断步）转则
，如果
7],[:
)(
10
1 ???
??
?
.s t e pV,,V,VS,VV
)V(f)V(f)V(f)V(f
n
k
rh
rele
（判断步）转则
，如果
7],[:
)(
10
1 ???
??
?
则使得如果存在
收缩步
),V(f)V(fhi
).(s t e p
ir ??( 1 )
5
.s t e pV,,V,VS,VV nkrh 7],[,101 转??? ?
)
2
1
:(
)(
)()()(( 2 )
。：收缩系数，一般取收缩点，
，令
则，有如果
?
???
????
??
?
c
rc
hri
V
VVVV
VfVfVfhi
).(7],,,,[,:
)()(
10
1 判断步转则
，如果
s t e pVVVSVV
VfVf
n
k
ch
rc
???
?
?
.)(6)()( 棱长减半步转则，如果 s tepVfVf rc ?
。则，如果 )()()(( 3 ) VVVVVfVf hchr ???? ?
).(7],,,,[,:
)()(
10
1 判断步转则
，如果
s t e pVVVSVV
VfVf
n
k
ch
rc
???
?
?
.)(6)()( 棱长减半步转则，如果 s tepVfVf rc ?
。判断步转
棱长减半步
)7( S t e p],,,,[
n),1,,0i(2).(6
1
1
no
k
li
i
VVVS
VVVs t e p
?
?
?
???
?
,17 0?
?
? ?n
V
V).(s t e p
n
i
i
计算判断步
。得到
则算法结束，）（或者如果
1
,m a x
0*
0 1
?
??
????
?
?
?
? ??
n
V
Vx
VVVV
n
i
i
n
i
ji
ni
i ??
。准备步转
那么）（如果
)(2 S t e p1:],[
,
1
1
0 1
,kkV,,V,VS
VVma xVV
no
k
n
i
ji
ni
i
???
? ????
?
? ??
?
??