第四章 2008修改--无约束最优化直接方法.ppt

1.用单纯形替换法求解min{x12+4x22}，取x=（2，2)T。初始单纯形取为正三角形，边长为1，迭代到坐标原点（即极小值点）含于单纯形为上，并用几何图示求解过程。 2.用步长加速法求解 min { 3 x12 -2x1x2+x22+4x1+3x2} 取x=(0,0 )T ，初始步长s1=s2=1 终止准则s1=s20.25 画出迭代过程路程 第四章 无约束最优化的直接方法 本章仍讨论无约束最优化问题： 在实际问题中 目标函数往往很复杂，从而导数表达式更加复杂，甚至难以 推导或不存在。这种情况下用上一章介绍的方法就不行了， 此时可用本章介绍的方法： 4.1单纯形替换法 证明：当i=2,3…n+1时 | |vi- v1 | |2=| |z1+z(i)- z1 | |2=| |z(i)| |2=p2+(n-1)q2 将p,q代入上式有| |vi- v1| | 2=l2 当i,j=2,3…n+1时， | | vi- vj | |2=| |z(i)-z(j) | |2 = | |z(i) | | 2 +| |z(j) | | 2 - 2z(i)Tz(j)=2l2-2[2pq+(n-1) q2] 将值代入上式得： | | vi- vj | | = l2 ,i j由上可知上面确定的单纯形为正规单纯形。 二 算法过程 1 设初始单纯形顶点的位置向量为v1， v2 ，v3 …vn+1.计算： fi=f(vi).i=1，2，3 …,n+1 fl=min{fi}.fh=max{fi},其中分别为此单纯形的最好和最坏顶点。(取正规单纯形作为初始单纯形比取后一种形式好) 若把顶点vh去掉，则剩下的n个顶点v1， v2 ，v3 …vn+1(不含Vh)构成n-1维空间中的单纯形，按下面公式求其中心： 从而得到比vh更好的点,这时应按3进行伸延，否则进入4.2进行收缩工作。 3 延伸 经过反射，若不仅有f(vr) f(vh),且进一步有f(vr)f(vl)，则说明沿vr- vo方向还可以向前迈一步，因此计算: ve= vo+r(vr -vo) ve称为vh的延伸点，r1是延伸系数，常取r=2,也可用直线有哪些信誉好的足球投注网站技术确定r. 此时若有f(ve) f(vh),则以ve替换vh，而其余n个顶点不变, 构成新单纯形，转6. （如在R中，由图a知以Ve、Vi、Vl为顶点的新单纯形已向极小点靠近了一步。） 否则，以反射点替换构成单纯形，转6步（如R中，由图b可知以Vr、Vi、Vl为顶点的新单纯形向极小点靠近了一步） 收缩分以下两种情况 4.2.1 若f(vr) =f(vh),即反射点比原来单纯形的坏点还坏，则舍弃vr，对方向vh- v0进行收缩。如图d 计算公式为 若f(vc)f(vh)，即收缩点比原单纯形最坏点还坏，因此放弃vc点，转5步进行棱长减半工作。否则以vc替换vh构成新单纯形，转6。 4.2.2 若f(vr)f(vh)，则对向量vr--vo进行收缩（如图e），计算公式为 若f(vc)f(vh),即收缩点vc比反射点vr还坏，则放弃收缩点vc，转5进行棱长减半工作，否则以vc替换vh构成新单纯形，转6。 5 减小棱长。将原单纯形的最好点保持不动，各棱长减半，计算公式为 先做反射运算（为方便，取 =1） 故以?3 =（4，6）代替?2。f(?3 )=4代替。转入下一 次迭代。如此迭代下去最后可得极小点（5，6）T。 下面以第一个坐标方向为例加以说明，取 ，先取试验点 ，若 ，则这一维探测完成。取 ，然后再对第二个分量探测。 作变步长的轴向探测移动，直到各轴向的探测成功之后出现了失败，此时停止探测，得探测的最后点取为 否则 不变， 转 5 若 转7； 若 转3。 若 则最优解 否则转8 转2。 若 转11 否则转12 若 转11 ，若 则转10 令 转2 解：取 初始方向 第一轮 例：用原始powell方法求解无约束问题： 再沿加速方向 进行直线有哪些信誉好的足球投注网站，即