第四章--无约束最优化直接方法

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

1、第四章无约束最优化直接方法无约束最优化直接方法只要求目标函数是连续的，求解过程中不需要计算目标函数的导数。1.单纯形替换法1)单纯形(1)定义:中的单纯形就是指具有个顶点的多面体。若各棱长相等，称为正规单纯形。(2)正规单纯形的构建：已知正规单纯形任一顶点和棱长。根据棱长构建数组，其中，正规单纯形的顶点坐标为：，，在二维情形下，该方法构建的单纯形为一等边三角形。(3)一般单纯形的构建已知单纯形任一顶点和正数。令则单纯形的顶点坐标为：，，在二维情形下，该方法构建的单纯形为一直角三角形。2)基本想法6选定一个初始点，根据上述方法形成初始单纯形，从这一单纯形出发，通过迭代设法构造新的单纯

2、形以替换原有的单纯形，使新单纯形不断向目标函数的极小点靠近，直到搜寻到极小点为止。3)算法已知目标函数，单纯形各顶点的位置，终止限。(1)计算，令，，于是和分别是单纯形的最好和最坏的顶点。把顶点去掉，则剩下的顶点构成维空间中的单纯形，其中心。(2)反射按如下公式通过反射，，其中，称为反射系数，通常取,称为的反射点。当时，转(3)，否则转(4)(3)延伸计算延伸点,,称为延伸系数。①如果，那么就用替换，构成新的单纯形,否则，那么就用替换，构成新的单纯形。②转(6)(4)收缩①存在一个标号，,。也就是说，除最坏点外，反射点至少比其余一个顶点好。此时以替换构成新的单纯形,转(6)。6②在

3、这种情况下，反射点比原单纯形所有的顶点还坏。说明反射方向错误，则舍弃不管，沿方向进行收缩。，其中是的收缩点，而是收缩系数。如果，则舍弃收缩点，转(5),减少原单纯形棱长，否则以替换构成新的单纯形,转(6)。③，且，但在这种情况下，反射点只比好，则沿方向进行收缩。如果，则舍弃收缩点，转(5),减少原单纯形棱长，否则以替换构成新的单纯形,转(6)。(5)减少棱长原单纯形的最好点保持不动，各棱长减半。此时可按下式计算各顶点坐标。，(6)终止准则计算，若成立，则就是所求的极小点，否则转(1)重新迭代。2.步长加速法步长加速法主要由交替进行的“探测搜索”和“模式移动”而组成。6探测搜索的出发

4、点称为参考点。探测搜索的目的就是在参考点的周围寻找比它更好的点，这样的点称为基点，从而确定一个有利的前进方向。这样的向量称为“模式”。模式移动就是将参考点在“模式”所确定的搜索方向上移动，得到新的参考点。通过有限次的“探索”，“移动”，迭代点将逐渐逼近极小点。探测搜索算法：已知：目标函数,步长向量,参考点。①计算;置，，基点与参考点重叠。②以次沿第坐标轴方向作如下搜索。，，其中是第坐标轴上的单位向量。Ⅰ.若，置，。Ⅱ.若而，置，Ⅲ.若且，则和都保持当前值不变。③若，探测搜索成功，否则探测搜索失败。步长加速算法：已知：目标函数，步长收缩系数的终止限。①选定初始点，初始步长向量。②置，

5、，步长收缩系数，步长收缩系数的改变系数(或0.1)③④在点以为步长向量作探测搜索(参考点与基点重叠)。6⑤若探测搜索不成功，转⑩。⑥作模式移动，当前参考点为，当前基点为，。⑦在点以为步长向量作探测搜索(参考点与基点不同)。⑧若(注意不是)，则模式移动成功，转⑥。⑨若(注意不是)，则称模式移动失败。将参考点置为，转④。⑩若，则就是极小点，否则置。3.方向加速法方向加速法又称为Powell方法，其本质上就是共轭方向法，只不过Powell方法可以不用导数，通过逐次迭代来构造共轭方向。定理1:假设：①元二次函数中是对称正定的；②是互为共轭的向量系，其中；③和是互异的任意两点。分别从和出发，

6、依次沿作直线搜索，设最后一次直线搜索的极小点分别是和，再设。于是，与互为共轭。证明：由前面的定理可知：，，于是有：又因为：代入上式得：6证毕。推论：和是其联线方向不与方向平行的两点。分别从这两点出发沿方向对进行直线搜索，设所得的极小点分别是和,则与共轭。1)Powell算法已知：目标函数，终止限。①选定初始点，置，，其中是第个坐标轴上的单位向量。②依次对对目标函数作直线搜索③对，置。④作直线搜索。⑤若，则就是所求的极小点，结束。⑥置，转②。在上面的步骤中，当终止条件不满足时，②-⑥步被重复执行，称②-⑥步为算法的一个阶段。考察第个阶段与第个阶段所做的直线搜索，可以发现，任一阶段均需

7、搜索次，除第一次搜索所采用的搜索方向不同外，其余次的搜索方向都是相同的，且相邻两次的搜索起点都不相同。因此，根据前面的定理可知，至多经过个阶段的迭代就可产生个共轭方向并可求到极小点。6