《第四章--无约束最优化直接方法》由会员分享，可在线阅读，更多相关《第四章--无约束最优化直接方法（7页珍藏版）》请在金锄头文库上搜索。
1、第四章 无约束最优化直接方法无约束最优化直接方法只要求目标函数是连续的，求解过程中不需要计算 目标函数的导数。1. 单纯形替换法1) 单纯形(1) 定义：Rn中的单纯形就是指具有n + 1个顶点的多面体。若各棱长相等， 称为正规单纯形。(2) 正规单纯形的构建：已知正规单纯形任一顶点x和棱长l。其中p=丄(n莓 + n -1)，nJ20根据棱长l构建数组zi二q, .q.,.ip1,q, . .q.,T q = (、n +1 -1)n J2正规单纯形的顶点坐标为：v二x ， v二x + zi， i = 2,.,n +110 i 0在二维情形下，该方法构建的单纯形为一等边三角形。(3) 一般单纯
2、形的构建已知单纯形任一顶点x和正数i。0令 e = 0,.,0,1,0,.,0ti则单纯形的顶点坐标为：v = x ， v = x + le ， i = 2,.,n +110 i 0i-1在二维情形下，该方法构建的单纯形为一直角三角形。2) 基本想法选定一个初始点，根据上述方法形成初始单纯形，从这一单纯形出发，通过迭代设法构造新的单纯形以替换原有的单纯形，使新单纯形不断向目标函数的极小点靠近，直到搜寻到极小点为止。3) 算法已知目标函数f(x)，单纯形各顶点的位置v ,v，,v ，终止限。1 2n+1(1)计算 f 二 f (v )， i 二 1,2,.,n +1ii令f = min f ，f
3、 = maxf ，于是v和v分别是单纯形的最好和最坏的顶点。11i n+11h 1i 0，称为反射系数，通 0h r 00 h常取Q = 1, v称为v的反射点。rh当f (v ) 1, Y称为延伸系数。e 0 r 0 如果f (v ) f (v )，那么就用v替换v，构成新的单纯形,否则，那么就用ve1ehr替换v，构成新的单纯形。h 转(4) 收缩 存在一个标号i，f (v ) f ( v )rh在这种情况下，反射点比原单纯形所有的顶点还坏。说明反射方向错误， 则舍弃v不管，沿V - V方向进行收缩。r h 0V = V +B (v - V )，其中V是V的收缩点，而p G (0,1)是收
4、缩系数。c 0 h 0 c h如果f (V )f (V )，则舍弃收缩点，转(5),减少原单纯形棱长，否则以V替c h c 换V构成新的单纯形，转。h f (v ) f (v )， i 二 1,2,., n +1 但 i 丰 hrhri在这种情况下，反射点只比V好，则沿V -V方向进行收缩。hr 0V 二 V + p (v V )c 0 r 0如果 f(V ) f(V )，则舍弃收缩点，转(5),减少原单纯形棱长，否则以 V 替c r c 换V构成新的单纯形，转。h(5) 减少棱长原单纯形的最好点V保持不动，各棱长减半。此时可按下式计算各顶点坐标。l1v =(v + v )， i = 1,2,
5、.,n +1i 2 i l(6) 终止准则计算f =丄刃f，V* =丄艺Vn +1in +1 i=1i=1若2( f f )2 e成立，则V *就是所求的极小点，否则转(1)重新迭代。ii=12. 步长加速法步长加速法主要由交替进行的“探测搜索”和“模式移动”而组成。 探测搜索的出发点称为参考点。探测搜索的目的就是在参考点的周围寻找比它更好的点，这样的点称为基点，从而确定一个有利的前进方向。这样的向量称为“模式”。模式移动就是将参考点在“模式”所确定的搜索方向上移动，得到新的参 考点。通过有限次的“探索”，“移动”，迭代点将逐渐逼近极小点。 探测搜索算法：已知：目标函数f (x)，步长向量s
6、= L , s，s 1，参考点r = r, r , r 1 1 2 n 1 2 n 计算f = f (r)；置f = f， b = r，基点与参考点重叠。rb r 以次沿第i = 1,2,., n坐标轴方向作如下搜索。f = f(b + se )， f = f(b-se )，其中e是第i坐标轴上的单位向量。1i i2i iiI 若 f f 而 f f且f f ,则b和f都保持当前值不变。1 b2 bb 若 f f ，探测搜索成功，否则探测搜索失败。br步长加速算法：已知：目标函数f (X)，步长收缩系数的终止限。 选定初始点 x ，初始步长向量 s 。00 置r = x ， b = x，步长收
7、缩系数c = 1，步长收缩系数的改变系数w = 0.5 (或0 0 00.1) s = cs0 在r点以s为步长向量作探测搜索(参考点与基点重叠)。 若探测搜索不成功，转。 作模式移动，当前参考点为r二2b-b，当前基点为b二b， f二f。000 b 在r点以s为步长向量作探测搜索（参考点与基点不同）。 若f f （注意不是f f （注意不是f f ），则称模式移动失败。将参考点置为b，转。b 0b r0 若c e，则r就是极小点，否则置 c = cw。3. 方向加速法方向加速法又称为 Powell 方法，其本质上就是共轭方向法，只不过 Powell 方法可以不用导数，通过逐次迭代来构造Q共轭
8、方向。定理 1:假设： n兀一次函数f （x） = 2xtQx + bTx + c中Q是对称正定的； p ,p p是互为Q共轭的向量系，其中 mn；0 1m -1 x和x是互异的任意两点。分别从x和x出发，依次沿p ,p，,p作直线1 2 1 2 0 1m -1搜索，设最后一次直线搜索的极小点分别是x*和x*，再设p = x* -x*。1 2 1 2于是，p与p ,p ,.,p互为Q共轭。0 1m -1证明：由前面的定理可知：pTVf (x*) = 0， j = 0,1,.,m一 1 j1于是有：pTVf(x*)=0， j =0,1,.,m-1 j2pT(Vf(x*)-Vf(x*) = 0j1
9、2代入上式得：又因为：Vf (x) = Qx + bpT(Vf(x*)-Vf(x*)= pTQ(x*-x*)= pTQp=0j12j 12j证毕。推论：x和x是其联线方向不与p方向平行的两点。分别从这两点出发沿p1 2 0 0 方向对f (x)二1 xtQx + bTx + c进行直线搜索，设所得的极小点分别是x*和x* ,则2 1 2x* - x* 与 p Q 共轭。1 2 01)Powell 算法已知：目标函数f (x) = 2xtQx + bTx + c，终止限e。选定初始点x，置p二e ，i二0,1,.,n-1，其中e是第i个坐标轴上的单位0ii+1i向量。依次对i二0,1,.,n-1
10、对目标函数作直线搜索x二ls(x ,p )i+1i i对 i = 0,1,., n - 2，置 p 二 p , p二x -x。作直线搜索x二ls( x , p )。n+1n n-18，则x就是所求的极小点，结束。n +1ii+1n-1n 0 若llx - xn+10 置x二x，转。0n+1在上面的步骤中，当终止条件不满足时，-步被重复执行，称-步 为算法的一个阶段。考察第i个阶段与第i+1个阶段所做的直线搜索，可以发现，任一阶段均需 搜索n +1次，除第一次搜索所采用的搜索方向不同外，其余n次的搜索方向都是 相同的，且相邻两次的搜索起点都不相同。因此，根据前面的定理可知，至多 经过n个阶段的迭代就可产生n个共轭方向并可求到极小点。
