第四章无约束最优化的直接方法解析

若把顶点vh去掉，则剩下的n个顶点v1， v2 ，v3 …vn+1(不含Vh)
构成n-1维空间中的单纯形，按下面公式求其中心：
v0
1 n1
n
vi
i 1,i h
2 反射。
按如下公式通过v0反射vh:vr v0 (v0 vh ) 0为反射系数,常,取vr称 1 为vh的反射点。因vh是坏点，则一般 有f(vr)<f(vh)
收缩分以下两种情况
4.2.1 若f(vr) >=f(vh),即反射点比原来单纯形的坏点
还坏，则舍弃vr，对方向vh- v0进行收缩。如图d
计算公式为 vc v0 (vh v0 )
其中vc是vh的收缩点，而收缩常数常取为：
1 2
若f(vc)>f(vh)，即收缩点比原单纯形最坏点还坏，因此放弃vc 点，转5步进行棱长减半工作。否则以vc替换vh构成新单纯形， 转6。
2） 步长加速法。
3） 方向加速法（又称共轭方向法）。
只要目标函数连续，这些方法就可以使用。由于这些方 法无须计算目标函数的导数，因此又称为直接方法。但收敛 速度比上一章的方法都要慢。
4.1单纯形替换法
1 单纯形：Rn中的单纯形指具有n+1个顶点的多面体，若
各棱长彼此相等，则称为正规单纯形。如：在R2中，三角
vi v1 2 l 2
vi
vj
2
z
i
z(
j
2
)?
zi
2
z j
2 ziz j ziz j
l2 l2 pq pq n 1q2 pq pq n 1q2
vi v1 2
将值代入上式得： vi vj 2 l2，i j 由上可知上面确定的单纯形为正规单纯形。
正规单纯形是一种特殊的单纯形，还有一种特殊的单纯形取
p l ( n 1 n 1)
如:z(2)=[p,q … q]T.z(n+1)=[q,q … p]T.其中 n 2
q l ( n 1 1) n2
证明：当i=2,3…n+1时
vi
v1
2
z1
z
i
2
z1 ?
z i 2 p2 n 1 q2
将 p , q 代入上式有 当 i,j=2,3…n+1 时，
vl
vh e vl
5 减小棱长。将原单纯形的最好点保持不动，各棱长减 半，计算公式为
vi
1 2
vi
v l
, i l, i 1, 2, 3
n 1
ห้องสมุดไป่ตู้
6
终止原则。计算
f
1 n1 n1 i
fi , v*
1 n 1
n!
vi
i1
，
若
n1 fi
f
2
e则v*为极小点，终止；否则，转1。
i 1
例：min f x1, x2 4x152 x2 62
（如在R中，由图a知以Ve、Vi、Vl为顶点的新单纯形已向极小点 靠近了一步。）
否则，以反射点替换构成单纯形，转6步（如R中，由图b可知 以Vr、Vi、Vl为顶点的新单纯形向极小点靠近了一步）
vi
vz
v0
vh
vl
a
ve
vi
vr
z
v0
vh
vl b
4 收缩。
若f(vr)>f(vl)，即反射点并不比原单纯形的最好点好，
4.2.2 若f(vr)<f(vh)，则对向量vr--vo进行收缩（如图e），计
算公式为 vc vo (vr vo )
若f(vc)>f(vh),即收缩点vc比反射点vr还坏，则放弃收缩点vc，
转5进行棱长减半工作，否则以vc替换vh构成新单纯形，转6。
vr
vi
vr
vr
vi
vi
vl
vh c
vh
从而得到比vh更好的点,这时应按3进行伸延，否则进入 4.2进行收缩工作。
3 延伸
经过反射，若不仅有f(vr)< f(vh),且进一步有 f(vr)<f(vl)，则说明沿vr- vo方向还可以向前迈一步，因 此计算: ve= vo+r(vr -vo)
ve称为vh的延伸点，r>1是延伸系数，常取r=2,也可 用直线搜索技术确定r. 此时若有f(ve)< f(vh),则以ve替 换vh，而其余n个顶点不变, 构成新单纯形，转6.
则分下列两种情况处理：
4.1 若存在一个标点i，使得f(vr)<f(vi),即除最坏点vh 外，反射点vr比其他一个顶点好，因而可以用vr将vh替换 构成新的单纯形，转6步（如R2中，图c所示，以Vr、Vi、 Vl为顶点的新单纯形向极小点迈进了一步）
4.2 若对i=1,2,3--n+1(但 i h )均有f(vr)>=f(vi),则 要进 行收缩。
形就是单纯形，正三角形就是正规单纯形。（正三角形是
R2中周长一定包围面积最大的布点方式）
结论：
对于任意给定初始点z1和正数l，按如下公式取定的单纯形 是一个以为z 1顶点棱长为l的Rn中的正规单纯形：
v 1= z 1 , v i = z1+z(i) i=2,3,4…n+1
其中n 维向量z(i)=[q ~ q,pi-1,q … q]T
满意的极小点为止。
二 算法过程
单纯形替换法由两步构成：形成初始单纯形和迭代。而迭代
过程又包括四项操作：反射，延伸，收缩和减小棱长。
已知目标函数f(z)和终止限
1 设初始单纯形顶点的位置向量为v1， v2 ，v3 ,…vn+1.计算： fi=f(vi). i=1，2，3 …,n+1
fl=min{fi}.fh=max{fi},其中分别为此单纯形的最好和最坏顶 点。(取正规单纯形作为初始单纯形比取后一种形式好)
取初始点。为计算方便不取等边三角形为初始单纯形。
而取直角三角形为初始单纯形，其顶点为：
x0 8, 9T , x1 10,11T , x2 8,11T
相应函数值f0=45 , f1=125, f2=65
法：v1= z1,vi= z1 +lei-1.i= 2,3 … n+1,其中ei=[0 … 0,1,0 … 0]T 在R2中此特殊单纯形即为等腰直角三角形。
单纯形替换法的基本思想 就是按上面取特殊单纯形的方法
形成初始单纯形。然后从此出发，每次迭代都设法构造新的以替
代旧的，使新单纯形不断向目标函数的极小点靠近，直到搜索到
第四章 无约束最优化的
直接方法
本章仍讨论无约束最优化问题：min f (x) 在实际问题中 xRn
目标函数往往很复杂，从而导数表达式更加复杂，甚至难以 推导或不存在。这种情况下用上一章介绍的方法就不行了， 此时可用本章介绍的方法：
1） 由Spendy,Hext和Himsworth(1962)提出，经Nelden 和Mend(1965)作出改进的单纯形替换法。