第十九章 无约束最优化的直接方法

《第十九章 无约束最优化的直接方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十九章无约束最优化的直接方法本章仍讨论无约束最优化问题：在实际问题中目标函数往往很复杂，从而导数表达式更加复杂，甚至难以推导或不存在。这种情况下用上一章介绍的方法就不行了，此时可用本章介绍的方法：1）由Spendy,Hext和Himsworth(1962)提出，经Nelden和Mend(1965)作出改进的单纯形替换法。2）步长加速法。3）方向加速法（又称共轭方向法）。只要目标函数连续，这些方法就可以使用。由于这些方法无须计算目标函数的导数，因此又称为直接方法。但收敛速度比上一章的方法都要慢。19.1单纯形替换法定义19.1.1：单纯形：中的单纯形指具有n+1个顶点的多面

2、体，若各棱长彼此相等，则称为正规单纯形。如：在中，三角形就是单纯形，正三角形就是正规单纯形。（正三角形是中周长一定包围面积最大的布点方式）结论：设是某一单纯形的n+1个顶点向量,则：对于任意给定初始点z1和正数l，按如下公式取定的单纯形是一个以为z1顶点棱长为l的正规单纯形。。其中n维向量z(i)=，如:z(2)=，…，z(n-1)=，其中证明：当i=2,3…n+1时将p,q代入上式有当i,j=2,3…n+1时，将值代入上式得：,ij由上可知上面确定的单纯形为正规单纯形。正规单纯形是一种特殊的单纯形，还有一种特殊的单纯形取法：其中=在中此特殊单纯形即为等腰直角三角形。单纯形

3、替换法的基本思想就是按上面取特殊单纯形的方法形成初始单纯形。然后从此出发，每次迭代都设法构造新的以替代旧的，使新单纯形不断向目标函数的极小点靠近，直到搜索到满意的极小点为止。19.1.1算法过程单纯形替换法由两步构成：形成初始单纯形和迭代。而迭代过程又包括四项操作：反射，延伸，收缩和减小棱长。已知目标函数f(z)和终止限4271）设初始单纯形顶点的位置向量为.计算：,其中分别为此单纯形的最好和最坏顶点。(取正规单纯形作为初始单纯形比取后一种形式好)若把顶点去掉，则剩下的n个顶点(不含)构成n-1维空间中的单纯形，按下面公式求其中心：2）反射。按如下公式通过反射:,称为的反射

4、点。因是坏点，则一般有f()1是延伸系数，常取r=2,也可用直线搜索技术确定r.此时若有f()

5、若f()=f(),则要进行收缩。收缩分以下两种情况4.2.1若f()>=f(),即反射点比原来单纯形的坏点还坏，则舍弃，对方向-v0进行收缩。如图d计算公式为；其中是的收缩点，而收缩常数常取为：427若f()>f()，即收缩点比原单纯形最坏点还坏，因此放弃点，转5步进行棱长减半工

6、作。否则以替换构成新单纯形，转6。4.2.2若f()f(),即收缩点比反射点还坏，则放弃收缩点，转5进行棱长减半工作，否则以替换构成新单纯形，转6。图19.1.1c图19.1.1b图19.1.1e5）减小棱长。将原单纯形的最好点保持不动，各棱长减半，计算公式为6）终止原则。计算，若，则v*为极小点，终止；否则，转1例19.1.1解：取初始点。为计算方便不取等边三角形为初始单纯形，而取直角三角形为初始单纯形，其顶点为：相应函数值=45,=125,=65故其中心先做反射运算（为方便，取=1）因满足延伸条件

7、，进行延伸实验（延伸系数r=2）因延伸成功。取此时得三个顶点及函数值为下面开始第二次迭代427中心反射延伸故以=（4，6）代替。f()=4代替。转入下一次迭代。如此迭代下去最后可得极小点。19.2步长加速法19.2.1算法思路步长加速法是由Hooke和Jeeves1961年提出的，对于变量数目较少的无约束最优化问题，这是一种程序简单而又比较有效的方法。这个方法又两类移动所构成，一类是探测性移动，另一类是模式性移动；前者为了揭示函数变化规律，探测函数f(X)下降方向，后者是利用发现的函数变化规律循着有利方向（也可看作