《《最优化设计》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《最优化设计》PPT课件.ppt（44页珍藏版）》请在三一办公上搜索。
1、最优化设计/无约束优化方法,1,第四章 无 约 束 优 化 方 法,4-1 概述4-2 最速下降法4-3 牛顿型方法4-4 共轭方向及共轭方向法4-5 共轭梯度法4-6 变尺度法4-7 坐标轮换法4-8 鲍威尔法4-9 单形替换法,最优化设计/无约束优化方法,2,4-1 概 述,无约束优化方法只考虑搜索的适行性，结合罚函数法，也可解约束优化问题。目前，成熟可靠的优化算法中，无约束优化方法占多数，总体上无约束优化方法的有效性及实用性都优于约束优化方法。无约束优化方法可分为两大类：1)不求导数的直接法，主要有随机方法和直接搜索方法；2)求导数的间接法，按所求导数的最高阶数又可分为一阶方法和二阶方法
2、。二阶方法很少采用。图4-1为无约束极小化算法的粗框图。在1-4 中已给出了优化算法的一般搜索迭代公式 xk+1=xk+xk(115)xk+1=xk+kdk(116)注意，在搜索迭代中，由于一维搜索需增加大量计算，因此，并不是所有优化方法都采用一维搜索。,最优化设计/无约束优化方法,3,4-2 最速下降法(1),最速下降法以负梯度方向作为搜索方向并作一维搜索，因此又称为“梯度法”，属于求导数的间接法。它的基本思想早在1847年就已提出。尽管它本身不再被认为是一种有效的方法，但它是许多优化方法尤其是二次收敛方法的基础。各点的梯度一般各不相同，因此“最速下降方向”仅对某一点附近而言，它具有局部性质
3、。如图4-2所示，当作一维搜索时，搜索方向是与目标函数等值线相切的，而切点的梯度方向是与等值线正交的。因此，相邻两次搜索方向相互垂直，搜索路径呈严重的“之”字形，特别是目标函数接近二次型时更为明显。可以利用梯度矢量在极值点为零这一重要性质设立收敛准则 f(x*),最优化设计/无约束优化方法,4,4-2 最速下降法(2),或,数值微分 数值微分在优化中是一个非常重要的问题，对优化结果影响较大。具体作法是用 代替，其中,f=f f0式中，f0=f(x0)，是计算偏导数那点 x0 处的目标函数值；f=f(x)=f(x1,x2,xi+xi,xn)，是其它变量保持不变，xi 变化为 xi+xi 时的目标
4、函数值。,xi=0.001(ui li)ui 和 li 分别为变量 xi 的估计上限和下限。,最优化设计/无约束优化方法,5,4-2 最速下降法(3),例4-1(图4-3)求 f(x1,x2)=x12+25x22 的极小点。取初始点 x0=2 2T，则 f(x0)=104 f(x0)=4 100T 沿负梯度即-4-100T方向进行一维搜索，有 x1=x0 0 f(x0)=2 2T 04 100T=2 40 2 1000T 在x1点 f(x1,x2)=(2 40)2+25(2 1000)2=(0)令(0)=0，有 2(2 40)(-4)+50(2 1000)(-100)=-16+320 1000
5、0+5000000=5000320 10016=0 0=0.020030718 得到第一次迭代的结果：x1=2 40 2 1000T=1.919877-3.0718034-2T f(x1)=3.686164 经过十次迭代，得到最优解：x*=0 0T f(x*)=0,最优化设计/无约束优化方法,6,4-2 最速下降法(4),图4-3表示例4-1的搜索路径，目标函数等值线为椭圆。若进行代换 y1=x1 y2=5x2则 f(x1,x2)变为(y1,y2)，等值线为一族同心圆。因为圆上任一点的负梯度方向都指向圆心，因此沿负梯度方向经过一次一维搜索即可找到最优点。图4-5为最速下降法的程序框图。,最优化
6、设计/无约束优化方法,7,4-3 牛顿型方法(1),牛顿法是用目标函数二阶偏导数的间接方法，因类似于解非线性方程的牛顿法而得名，又叫“二阶导数法”、“拟线性法”。将目标函数泰勒展开，保留到二次项，原目标函数就转变为下列二次型函数：,f(xk)+2f(xk)(x*xk)=0 对于二次型函数，从理论上来说，牛顿法从任选初始点一步就能收敛到最优点。但对于目标函数不是二次型，或计算机截断误差的影响，往往需要多次迭代才能得到最优点。牛顿法的迭代公式为：xk+1=xk 2f(xk)-1f(xk)(k=0,1,2,),2f(xk)为f(x)在xk点处的海赛矩阵。,最优化设计/无约束优化方法,8,4-3 牛顿
7、型方法(2),为防止牛顿法收敛到极大点而不是极小点，可在迭代过程中作一维搜索，形成改进的牛顿法“阻尼牛顿法”，其程序框图见图4-6。牛顿法的最大缺点是需要计算海赛矩阵，并求其逆矩阵，计算量很大。例4-2 用牛顿法求 f(x1,x2)=x12+25x22 的极小点。取 x0=2 2T f(x0)=2x10 50 x20 T=4 100T,最优化设计/无约束优化方法,9,4-3 牛顿型方法(3),例4-2(续)因为f(x1,x2)是二次型函数，用牛顿迭代公式，一步就可达到最优点：,对照梯度法和牛顿法迭代公式，可以看出只相差一项海赛矩阵的逆矩阵。因此，牛顿法是对梯度法的进一步修正。事实上，梯度法是对
8、目标函数f(x)在点xk的一阶(线性)近似，而牛顿法是对f(x)在点xk 的二阶(二次)近似。,最优化设计/无约束优化方法,10,4-4 共轭方向及共轭方向法(1),共轭方向的概念 二次正定函数的一般形式为：,式中，G为 nn 阶对称正定矩阵，b=b1,b2,bnT 为常矢量，c为常数。对于矩阵 G，若存在两个 n 维非零矢量 d0 和 d1，使(d0)TGd1=0成立，则称d0和d1是G共轭方向(或G共轭矢量)。特别地，当G为单位矩阵时，(d0)Td1=0，则称d0 和d1是正交的。矢量正交是矢量共轭的特例。,最优化设计/无约束优化方法,11,4-4 共轭方向及共轭方向法(2),共轭方向的性
9、质二次收敛性：如n=2，二次函数的等值线为一同心椭圆族，它的极小点就是椭圆中心。该椭圆族有一重要性质，即两平行线与椭圆的两个切点的连线必过椭圆族的中心，且连线与平行线的方向是共轭的(见下图)。,最优化设计/无约束优化方法,12,4-4 共轭方向及共轭方向法(3),因此，从任一点出发，沿任意方向作一维搜索找到的极小点就是椭圆的切点，再沿共轭方向作一维搜索找到的极小点就是椭圆中心也就是目标函数的极小点。这说明，对二维二次正定目标函数只要沿共轭方向作两次一维搜索就可得到其极小点。推广到n维，若采用共轭方向作为搜索方向，任何一个具有极小值的n维二次正定目标函数，理论上最多只要n步就能达到极小点且与所用
10、搜索方向的次序无关。这种性质称为“二次收敛性”，利用这种性质的优化方法称为二次收敛方法。,最优化设计/无约束优化方法,13,4-4 共轭方向及共轭方向法(4),共轭方向法 共轭方向是一大类方法，包括共轭梯度法，Powell法等。总的框图见图4-8。其中一种产生共轭方向的方法为格拉姆斯密特(GramSchmidt)法。比较有效的共轭方向法都尽量避免计算海赛矩阵。例4-3 选三个坐标轴上的单位向量作为一组线性无关向量系,最优化设计/无约束优化方法,14,4-4 共轭方向及共轭方向法(5),例4-3(续1),最优化设计/无约束优化方法,15,4-4 共轭方向及共轭方向法(6),例4-3(续2),说明
11、 d0、d1、d2 对G 共轭。,最优化设计/无约束优化方法,16,4-5 共轭梯度法(1),gk=Gxk+b 前面已给出优化算法的搜索迭代公式：xk+1=xk+kdk 若进行一维搜索，k 则为最优步长因子。xk 和xk+1 两点负梯度方向的差为 gk+1 gk=G(xk+1 xk)=G(xk+kdk xk)=k Gdk 若dk+1 和 dk 是G 共轭方向，则(dk+1)TG dk=0 用(dk+1)T前乘(gk+1 gk)，有(dk+1)T(gk+1 gk)=k(dk+1)TGdk=0 即 dk+1与(gk+1 gk)正交。,共轭梯度法的共轭方向,最优化设计/无约束优化方法,17,4-5
12、共轭梯度法(2),上式表明：从xk 开始沿dk方向进行一维搜索，其终点 xk+1与始点xk 两点的梯度之差 gk+1 gk与dk 的共轭方向dk+1正交。因此，利用这个性质，不必计算矩阵G 即可求出共轭梯度法的共轭方向。共轭梯度法的几何说明,最优化设计/无约束优化方法,18,4-5 共轭梯度法(3),共轭梯度法的迭代公式 设从xk出发，沿dk=-gk 方向作一维搜索到 xk+1点，并算出xk+1点的梯度方向gk+1。由于gk+1 是沿等直面在该点的法线方向，而dk是沿等直面在该点的切线方向，故(dk)Tgk+1=0，即 gk+1Tgk=0，gk+1 与 gk 正交。为了在 gk+1 和 gk
13、构成的正交系中确定共轭方向dk+1，令 dk+1=-gk+1+k dk 即把共轭方向dk+1看成-gk+1与 dk的线性组合，k 为待定系数。要使dk+1与dk 共轭，就应使(dk+1)TGdk=0而(dk+1)TGdk=(-gk+1+kdk)TGdk=(-gk+1 kgk)TG(-gk)=gk+1TGgk+k gkTGgk=0,最优化设计/无约束优化方法,19,4-5 共轭梯度法(4),因此,前面已推导出 gk+1 gk=k Gdk，即 gk+1 gk=-kGgk或,代入上式得,最优化设计/无约束优化方法,20,4-5 共轭梯度法(5),因此,下一个搜索方向确定为,同样,可以证明按上述公式确
14、定的 dk+2与dk+1为共轭方向，依此类推而确定的 n个dk(k=0,1,2,n-1)方向为一组关于G的共轭向量系。上述结论也可由数学归纳法证明。最后，我们得到共轭梯度法的迭代公式为 x k+1=x k+k dk式中 dk=-gk+k-1 dk-1,在迭代中第一次搜索方向 d0 取 x0 的负梯度方向-g0。,最优化设计/无约束优化方法,21,4-5 共轭梯度法(6),与梯度法相比，由于修正项kdk 改进了收敛性，使搜索方向共轭，故能以较少的迭代次数收敛到最优点。由于计算梯度时很可能出现误差，使搜索方向不能完全保持共轭，同时目标函数也可能不是正定的二次函数，因此n次迭代后一般都不会达到精确的
15、极小点。可在每n次迭代后令 d0=dn=-gn作为下一轮迭代的第一次搜索方向，重新开始新一轮迭代。上述共轭梯度法又称Fletcher-Reeves共轭梯度法。而PRP(Polak-Ribiere-Poiyak)共轭梯度法按下式计算k-1：,最优化设计/无约束优化方法,22,4-5 共轭梯度法(7),共轭梯度法(Fletcher-Reeves)的算法 1)给定变量个数n，选取收敛精度和初始点x0，计算x0点的梯度 g0，取第一次搜索方向d0=-g0，令k=0。2)沿dk方向作一维搜索，得到 xk+1点，xk+1=xk+k dk。k k+1。,转2)继续进行迭代。,最优化设计/无约束优化方法,23
16、,4-5 共轭梯度法(8),例4-4 用共轭梯度法求f(x1,x2)=x12+2x22 4x1 2x1x2的极小点。取 x0=1 1T d0=-g0=-2x1 2x2 4 4x2 2x1x0=4-2T 沿 d0 进行一维搜索 x1=x0+0 d0=1 1T+04-2T=1+40 1 20T 在x1点 f(x1,x2)=(1+40)2+2(1-20)2 4(1+40)2(1+40)(1 20)令df/d0=0，有 8(1+40)8(1 20)16 2(2 160)=8+320 8+160 16 4+320=800 20=0 0=0.25 x1=2 0.5T g1=2x1 2x2 4 4x2 2x
17、1x1=-1-2T,最优化设计/无约束优化方法,24,4-5 共轭梯度法(9),例4-4(续)d1=-g1+0 d0=2 1.5T 沿d1 进行一维搜索 x2=x1+1d1=2 0.5T+12 1.5T=2+21 0.5+1.51T 在 x2点 f(x1,x2)=(2+21)2+2(0.5+1.51)2 4(2+21)2(2+21)(0.5+1.51)令 df/d1=0，有 4(2+21)+6(0.5+1.51)8 2(4+61)=8+81+3+91 8 8 121=51 5=0 1=1 x2=4 2T 因为 g2=0 0T，且在 x2 点处海赛矩阵正定，故 x2 为极小点。x*=x2=4 2
18、T f(x*)=-8,最优化设计/无约束优化方法,25,4-6 变尺度法(1),变尺度法又被称为“拟牛顿法”、“大步梯度法”、“共轭方向法”，其中最有名的是DFP算法。变尺度法是在牛顿法的基础上演变发展的，但它是一阶方法，不求二阶偏导数，而是用一个矩阵近似表示海赛矩阵的逆矩阵，然后在搜索迭代过程中不断修正这个矩阵，使它逐步逼近海赛矩阵的逆矩阵。一、尺度矩阵的概念 通过尺度变换可改进收敛性。对于一般二次函数,进行尺度变换 xQx，则二次项,若G正定，则总存在矩阵Q使 QTGQ=II 为单位矩阵。,最优化设计/无约束优化方法,26,4-6 变尺度法(2),用Q-1左乘等式两边，再用Q左乘等式两边，
19、得到 QQTG=I即 QQT=G-1令 H=QQTH 称为尺度矩阵，要求H 正定。则牛顿法迭代公式变为 xk+1=xk kHf(xk)(k=0,1,2,)二、变尺度矩阵的建立 用尺度矩阵逼近海赛矩阵的逆矩阵G-1，则构成一个尺度矩阵序列Hk。因此，尺度在不断变化，迭代公式为 xk+1=xk k Hk gk(k=0,1,2,)gk f(xk),最优化设计/无约束优化方法,27,4-6 变尺度法(3),对Hk的要求：1)Hk应对称正定。2)Hk之间的迭代应具有下列简单的形式：H k+1=H k+Ek Ek为nn 阶矩阵，称为校正矩阵。3)Hk必须满足拟牛顿条件 H k+1 yk=sk yk gk+
20、1 gk sk xk+1 xk三、变尺度法的一般步骤 图4-11为变尺度法的程序框图。,最优化设计/无约束优化方法,28,4-6 变尺度法(4),四、DFP算法 根据校正公式中Ek选取的不同，形成不同的变尺度法，其中最著名的为DFP算法。DFP算法中Ek取下列形式：Ek=k uk ukT+k vk vkT式中k、k 为待定常数，uk、vk 是n维待定向量，ukukT 和 vkvkT 都是对称、秩为1的n n 阶矩阵。取k、k、uk、vk，使它们满足：kuk ukTyk=sk k vk vkTyk=-Hk yk注意到uyk和vyk均为1 1阶矩阵即常量，可取 uk=sk vk=Hk yk定出,最
21、优化设计/无约束优化方法,29,4-6 变尺度法(5),因此，DFP算法校正公式为,例4-5 用DFP法求f(x1,x2)=x12+2x22 4x1 2x1x2的最优解。1)取x0=1 1T k=0 g0=-4 2T H0=I d0=-H0 g0=4-2T 沿d0进行一维搜索 x1=x0+0 d0=1+40 1 20T 令df/d0=0,得到 0=0.25，x1=2 0.5T 2)k=1 g1=-1-2T y0=g1 g0=3-4T s0=x1 x0=1-0.5T,最优化设计/无约束优化方法,30,4-6 变尺度法(6),d1=-H1 g1=0.84+0.76 0.38+0.82T=1.6 1
22、.2T x2=x1+1 d1=2+1.61 0.5+1.21T 令df/d1=0,得到 1=1.25，x2=4 2T 3)g2=0 0T,例4-5(续),(x2)T2f(x2)x2=4 0 4 2T=16 0 2f(x2)正定 x*=x2=4 2T f(x*)=-8,最优化设计/无约束优化方法,31,4-7 坐标轮换法(1),坐标轮换法属于不求导数的直接搜索法。它的基本思想是取x的n个坐标方向作为搜索方向，即从x0出发，第一次搜索沿x1坐标方向，第二次搜索沿x2坐标方向，第n次搜索沿xn坐标方向，第n+1次搜索沿x1坐标方向，依次类推。搜索不断沿坐标方向轮换进行，直到收敛条件被满足。坐标轮换法
23、一般不作一维搜索。坐标轮换法的算法如下：1)选取初始点x0(x0又称为初始基点)，初始步长xi，收敛精度i。一般初始步长可取为变量估计变动范围(uili)的1/100，收敛精度i可取为初始步长xi的1/100。令k=0。2)k k+1。进行一轮依次沿坐标方向的探查搜索。先给x1 一个增量x1，其它变量保持不变，得到一个试验点,最优化设计/无约束优化方法,32,4-7 坐标轮换法(2),检验 xs 的适行性。若f(xs)f(xk-1)，则xs 就作为下一个坐标方向搜索的起点；否则，从xk-1点沿反方向搜索,若两个方向的搜索都失败了，则停在原来的点不动。接着，以步长x2沿x2坐标方向搜索，直到 x
24、n为止。此轮探查搜索的终点称为基点 xBk。3)作模式移动(Pattern Move)到点xMk。模式移动的方向是从前一个基点xBk-1到当前基点xBk，移动量是两基点之间的距离，即,检验模式移动的适行性。若f(xMk)f(xBk)，则xMk就作为下一轮搜索的起点；否则，取消此次模式移动，xBk作为下一轮搜索的起点。,最优化设计/无约束优化方法,33,4-7 坐标轮换法(3),4)重复2)、3)的搜索模式移动的循环，直到各个坐标方向探查搜索都失败，仍停留在原基点不动为止。检验收敛准则 xiI 是否满足。若不满足，则将各变量步长xi(i=1,2,n)都减少一半，重新开始新一轮探查搜索；若满足，则
25、输出最优点x*=xBk。例 用坐标轮换法解 f(x)=x12+x226(x1+x2)+x3min.求经过一轮探查搜索和模式移动后的终点xM(1)。1)选取变量估计下限xl=0 0 0T，变量估计上限xu=10 10 10T，初始点x0=xB(0)=5 5 5T，初始步长x1=x2=x3=0.1，收敛精度1=2=3=0.001。求出 f0=f(x0)=-5 2)进行探查搜索。x1 方向：向正向搜索：xs=5.1 5 5T，f(xs)=-4.59（不适行）向反向搜索：xs=4.9 5 5T，f(xs)=-5.39（适行）,最优化设计/无约束优化方法,34,4-7 坐标轮换法(4),x2 方向：向正
26、向搜索：xs=4.9 5.1 5T，f(xs)=-4.98（不适行）向反向搜索：xs=4.9 4.9 5T，f(xs)=-5.78（适行）x3 方向：向正向搜索：xs=4.9 4.9 5.1T，f(xs)=-5.68（不适行）向反向搜索：xs=4.9 4.9 4.9T，f(xs)=-5.88（适行）因此，xB(1)=4.9 4.9 4.9T，f(xB(1)=-5.88。3)作模式移动 xM(1)=xB(1)+(xB(1)xB(0)=4.9 4.9 4.9T+(4.9 4.9 4.9T 5 5 5T)=4.9 4.9 4.9T+-0.1-0.1-0.1T=4.8 4.8 4.8T 由于f(xM(
27、1)=-6.72 f(xB(1)，因此模式移动满足适行性，点4.8 4.8 4.8T 作为下一轮探查搜索的起点。,最优化设计/无约束优化方法,35,4-7 坐标轮换法(5),坐标轮换法被认为是目前最成功的优化算法之一，至今仍被广泛应用着。国外有些专家曾以工程实际中实际提出的优化设计问题作为考题，对各种优化方法进行专门研究对比，坐标轮换法是名列前茅的算法之一。坐标轮换法的缺点是有时收敛较慢。由于其搜索方向是固定的，如果恰好遇到某些约束曲面的走向对它的搜索特别不利时，往往会在接近最优点之前，“粘”在约束边界上中止收敛而得到一个假最优点。针对这个缺点，已提出了一些改进措施。如:多选几个初始点进行多次
28、运行；选择较为“温和”的罚函数；搜索中止后，对最后一个点的邻近区域进行随机“扫靶”搜索，如能发现一个新的好点，则以此点作为起点开始一轮新的搜索；设法使搜索在遇到约束边界后改变固定的搜索方向，沿约束边界“爬行”等。,最优化设计/无约束优化方法,36,4-8 鲍威尔法(1),鲍威尔(Powell)法的搜索方向是共轭的，但不需要计算目标函数的导数，这是它的一大优点。一、共轭方向的生成,gk=Gxk+b gk+1=Gxk+1+b gk+1 gk=G(xk+1 xk)=Gdk 设xk、xk+1为沿同一方向dj进行一维搜索得到的两个极小点，因此dj和梯度方向正交(图4-15)，有(dj)T gk=0(dj
29、)T gk+1=0 根据共轭方向的定义(式4-11)，有(dj)T(gk+1 gk)=(dj)TG dk=0 因此，dj和dk是G共轭方向。,最优化设计/无约束优化方法,37,4-8 鲍威尔法(2),二、基本算法 图4-17为 Powell 法搜索过程。1)任选一初始点x0，确定收敛精度，选择坐标轴方向ei(i=1,2,.,n)为第一轮搜索方向，令k=0,xB(0)=x0。2)k k+1。从xB(k-1)出发，分别沿ei(i=1,2,.,n)作一维搜索，此轮搜索的终点为xB(k)。3)作模式移动。沿dk=xB(k)xB(k-1)作一维搜索，得到xk，作为下一轮搜索的起点。4)检验收敛准则。如满
30、足则输出当前点xk作为最优点。5)若未收敛，则重复2)、3)的一维搜索和模式移动，但每一轮一维搜索中都用上一轮模式移动方向代替原有的一个坐标轴方向。如第二轮搜索方向为e2,e3,en,d1，依次类推。,最优化设计/无约束优化方法,38,4-8 鲍威尔法(3),三、改进的算法 框图见图4-18。在每一轮搜索后，模式移动与坐标轮换法的相同而不作一维搜索。另外增加了Powell 判别条件，若满足判别式，则用模式移动方向替换目标函数值下降量最大的一个方向，以保证下一轮搜索方向组线性无关。例4-6 用Powell法求f(x1,x2)=10(x1+x2 5)2+(x1 x2)2 的极小值。选取x0(0)=
31、0 0T，F0=f0=250。第一轮搜索：1)沿e1=1 0T方向作一维搜索，得到 x1(0)=4.5455 0T,f1=22.727,1=f0 f1=227.273。2)沿e2=0 1T方向作一维搜索，得到x2(0)=4.5455 0.8264T,F2=f2=15.214,2=f1 f2=7.513,m=1=227.273。3)模式移动:x3(0)=2 x2(0)x0(0)=9.091 1.6528T F3=f(x3(0)=385.24,最优化设计/无约束优化方法,39,4-8 鲍威尔法(4),4)检验Powell 判别条件。因为 F3 F0，因此下一轮搜索方向仍用e1、e2方向。因为 F2
32、 F3，因此x2(0)作为下一轮搜索的起点。第二轮搜索：起点x0(1)=x2(0)=4.5455 0.8264T,F0=f0=15.214。1)沿e1=1 0T方向作一维搜索，得到x1(1)=3.8693 0.8264T,F1=f1=10.185,1=f0 f1=5.029。2)沿e2=0 1T方向作一维搜索，得到x2(1)=3.8693 1.3797T,F2=f2=6.818,2=f1 f2=3.367,m=1=5.029。3)模式移动:x3(1)=2 x2(1)x0(1)=3.1931 1.9330T F3=f(x3(1)=1.747 4)检验Powell 判别条件。因为 F3 F0 且(
33、F0 2F2+F3)(F0 F2 m)2 0.5m(F0 F3)2，故用模式移动方向 d3(1)=x2(1)x0(1)=-0.6762 0.5533T代替e1。沿d3(1)方向作一维搜索，得到下一轮搜索的起点：x0(2)=2.49995 2.5091T F0=f0=0.0008 若不满足收敛准则，则再进行第三轮搜索。,最优化设计/无约束优化方法,40,4-9 单形替换法(1),单形替换法又称单纯形(Simplex)法，属于直接搜索方法。一、基本原理 单纯形就是在n维空间中由n+1个顶点构成的形体。在优化搜索过程中要满足适行性，就要对目标函数的变化趋势有大概的估计，避免盲目选择搜索方向。可以根据
34、若干点的目标函数值大小的变化推测这种趋势，这些点可取为单纯形的顶点。单纯形的基本思想是利用单纯形的顶点构造有利的搜索方向和步长，用新的较好点取代原来较差的点，构成新的单纯形，不断向最优点逼近。假定在一个二维问题中，已求得不在一条直线上的三个点H、S、L，及它们的目标函数值fH、fS、fL，且fH fS fL。这三点构成一个单纯形三角形。如有更好点，则在最差点H的反对称方向可能性最大。,最优化设计/无约束优化方法,41,4-9 单形替换法(2),因此，取S和L两点的中点M，从H出发沿H和M的连线作模式移动到A点。然后舍弃H点，剩下的S、L和A又构成一个单纯形。推广到n维的情况，仍在单纯形的n+1
35、个顶点中取三个点。H为最差点，S为次差点、L为最好点，M为除H点外其它各点的中点(或称“重心”)，模式移动的方向仍在过H和M的连线上。二、计算步骤 1)建立初始单纯形。选择一个初始点x0，再依次改变其中一个变量的值，给变量一个事先确定的步长xj，得到另外n个点xi(i=1,2,.,n)。每个点由下两式确定：xj(1)=xj(0)+xj(j=i)xj(1)=xj(0)(j=1,2,.,n,j i)这n个点加上x0即作为初始单纯形的顶点。确定收敛精度。,最优化设计/无约束优化方法,42,4-9 单形替换法(3),2)计算单纯形各顶点的目标函数值，从中确定最差点H、次差点S、最好点L。,5)求反射点
36、A xi(A)=2xi(M)xi(H)(i=1,2,.,n)6)比较L,S,A 三点的目标函数值，有下列几种情况：1.当fLfA fS 时，以A点代H点构成新单纯形，转2)。2.当fA fL时，进行扩张，移动到点B。xi(B)=xi(A)+(xi(A)xi(M)(i=1,2,.,n),4)确定除H点以外，所有其它各点的中点M。M点由下式确定：,最优化设计/无约束优化方法,43,4-9 单形替换法(4),其中 为扩张因子，=1.22.0。如果fB fA，则以B点代替H点；否则以A点代替H点构成新单纯形，转2)。3.当fA fS时，进行收缩。若fA fH，取收缩点C xi(C)=xi(M)+(xi
37、(A)xi(M)(i=1,2,.,n)其中 为收缩因子，一般取为0.5。若fA fH，则用下式计算收缩点C xi(C)=xi(M)+(xi(H)xi(M)(i=1,2,.,n)计算点C的目标函数值fC。若fC fH，则以C点代替H点，构成新单纯形，转2)；否则，进行缩边。除点L不变外，其余各点的新位置K由下式确定：xi(K)=0.5(xi(K)xi(L)(i=1,2,.,n)构成一个缩边的新单纯形，转2)。,最优化设计/无约束优化方法,44,4-9 单形替换法(5),例4-7 用单形替换法求 f(x1,x2)=4(x1 5)2+(x2 6)2 的极小值。1)选初始点 x0=8 9T,=0.001,x1=x2=1,得到 x1=9 9T,x2=8 10T。2)f0=45,f1=73,f2=52,因此确定最差点 H=x1，次差点 S=x2、最好点L=x0。3)收敛准则不满足，转4)。4)确定除H点以外，所有其它各点的中点M。M=(L+S)=8 9.5T 5)求反射点A A=2M H=7 10T fA=32 6)比较 fA、fL、fS，因为fA fL，故进行扩张。取扩张因子=2，得到点B：B=M+2(A M)=8 9.5T+-2 1T=6 10.5T fB=24.25 因 fB fA，故以B点代替H点，构成一个新单纯形，转2)继续迭代。,
