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

第十九章 无约束最优化的直接方法本章仍讨论无约束最优化问题：在实际问题中目标函数往往很复杂，从而导数表达式更加复杂，甚至难以推导或不存在。这种情况下用上一章介绍的方法就不行了，此时可用本章介绍的方法：1） 由Spendy,Hext和Himsworth(1962)提出，经Nelden和Mend(1965)作出改进的单纯形替换法。2） 步长加速法。3） 方向加速法（又称共轭方向法）。只要目标函数连续，这些方法就可以使用。由于这些方法无须计算目标函数的导数，因此又称为直接方法。但收敛速度比上一章的方法都要慢。19.1单纯形替换法定义19.1.1：单纯形：中的单纯形指具有n+1个顶点的多面体，若各棱长彼此相等，则称为正规单纯形。如：在中，三角形就是单纯形，正三角形就是正规单纯形。（正三角形是中周长一定包围面积最大的布点方式）结论：设是某一单纯形的n+1个顶点向量, 则：对于任意给定初始点z1和正数l，按如下公式取定的单纯形是一个以为z1顶点棱长为l的正规单纯形。其中n 维向量z(i)= ，如:z(2)= ，z(n-1)=，其中证明：当i=2,3n+1时将p,q代入上式有当i,j=2,3n+1时， 将值代入上式得： ,ij由上可知上面确定的单纯形为正规单纯形。正规单纯形是一种特殊的单纯形，还有一种特殊的单纯形取法：其中=在中此特殊单纯形即为等腰直角三角形。单纯形替换法的基本思想就是按上面取特殊单纯形的方法形成初始单纯形。然后从此出发，每次迭代都设法构造新的以替代旧的，使新单纯形不断向目标函数的极小点靠近，直到搜索到满意的极小点为止。19.1.1 算法过程单纯形替换法由两步构成：形成初始单纯形和迭代。而迭代过程又包括四项操作：反射，延伸，收缩和减小棱长。已知目标函数f(z)和终止限1）设初始单纯形顶点的位置向量为.计算：,其中分别为此单纯形的最好和最坏顶点。(取正规单纯形作为初始单纯形比取后一种形式好) 若把顶点去掉，则剩下的n个顶点 (不含)构成n-1维空间中的单纯形，按下面公式求其中心：2）反射。按如下公式通过反射: , 称为的反射点。因是坏点，则一般 有f()f()，从而得到比更好的点,这时应按3进行伸延，否则进入3进行收缩工作。3）延伸。经过反射，若不仅有f()f(),且进一步有f()1是延伸系数，常取r=2,也可用直线搜索技术确定r.此时若有f() f(),则以替换，而其余n个顶点不变, 构成新单纯形，转4）收缩。（如在R中，由图a知以、为顶点的新单纯形已向极小点靠近了一步。）否则，以反射点替换构成单纯形，转6步（如R中，由图19.1.1 b可知以、为顶点的新单纯形向极小点靠近了一步） 图19.1.1a 图19.1.1b若f()f()，即反射点并不比原单纯形的最好点好，则分下列两种情况处理：4.1 若存在一个标点i，使得f()=f(),则要进 行收缩。收缩分以下两种情况4.2.1 若f() =f(),即反射点比原来单纯形的坏点还坏，则舍弃，对方向-v0进行收缩。如图d 计算公式为；其中是的收缩点，而收缩常数常取为：若f()f()，即收缩点比原单纯形最坏点还坏，因此放弃点，转5步进行棱长减半工作。否则以替换构成新单纯形，转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）因满足延伸条件，进行延伸实验（延伸系数r=2）因延伸成功。取此时得三个顶点及函数值为下面开始第二次迭代中心反射延伸故以=（4，6）代替。f( )=4代替。转入下一次迭代。如此迭代下去最后可得极小点。19.2 步长加速法19.2.1 算法思路步长加速法是由Hooke和Jeeves1961年提出的，对于变量数目较少的 无约束最优化问题，这是一种程序简单而又比较有效的方法。这个方法又两类移动所构成，一类是探测性移动，另一类是模式性移动；前者为了揭示函数变化规律，探测函数f (X)下降方向，后者是利用发现的函数变化规律循着有利方向（也可看作近似梯度方向）寻找较好的点，可看成一种加速。下面先对算法过程做一些说明，再给出算法过程。给定初始点和步长;（也可对不同坐标方向给出不同步长: ，以向量=() i=0,1,2,3 ,n 描述步长）。探测性移动：从迭代点出发，依次沿坐标方向找下降点，为标出点与坐标方向之间的关系，采用记号表示第k次迭代按坐标方向ei在探测性移动时得到的点。下面以第一个坐标方向为例加以说明，取，先取试验点 ，若，则这一维探测完成。取，然后再对第二个分量探测。若，则取试验点，若，则这一维探测完成。 取，然后再对第二个分量探测。若，也认为这一维探测完成，不过取，将步长缩小，为下一次再做这一维探测时用。也可以在做一维 探测时不改变步长。上述过程一般公式如下：其中上式对i=1，2，n 进行。求出若此则完成了探测性移动，再开始模式移动。若则再进行探测性移动。再进行探测性移动时，若步长： 时，则认为即为近似极小优点（这是因为而时，必将有很小接近于0）下面再看模式移动（Pattern Move）记从出发，沿方向，以步长求出新的试验点，即 然后再从出发进行一次探测性移动，得到点这时有： （如各分量减半）重新开始探测性移动。若充分小，则终止。 图19.2.1 图19.2.2 模式移动方向可以看作梯度方向的一个近似，因而本方法也可以看作是最速下降的一个近似。因此这个方法的收敛速度较慢。特别是在最优点附近，但当变量个数不变时，此方法可能是有用的。此方法也可以与其它方法结合使用，以便在最优化过程开始阶段找到一个较好的初始点。19.2.2 算法过程19.3 方向加速法方向加速法是Powell（1964）提出来的，因此又称为Powell方法。它是目前在无约束最优化的直接搜索方法中最有效的一个方法，本质上是一种共轨方向法，这可通过本方法与共轭方向法的对比及下面简单的讨论看出来，因此这个方法具有二次终法性。下面先看一个几何事实： 设f()是一个具有极小值点的二次函数，其导值线f()=c是一族椭圆，如图。这族椭圆的中心就是函数f()的极小值点。若从不同的初始点，出发， 沿同一方向P。进行一维搜索。求出极小值点是，那么连接这两个极小值点的直线必定通过极小值点。从而沿该直线方向（记为P1）搜索就可求得极小值点 图19.3.1这就是说，由 出发，依次沿方向求极小，便得到最优点。而我们在介绍共轭梯度法及共轭方向时，也具有这一性质。可以证明此种方向是共轭方向。对于n维情形。我们在第三章已经证明过有下边结论：定理19.3.1若（1）二次函数f(z)= 中的Q对称正定。（2）P0. Pm-1 是互为Q共轭的向量系，mn.（3）z1 ,z2是任意的两个不同点，则若分别从z 1 ,z 2 出发依次沿方向P。作直线搜索，最后得到直线搜索的极小点分别设为，设P=，那么P 与是互为Q 的共轭的下面我们看一个具体例子：例19.3.1 f()解：取沿方向求极小得点在从出发沿方向求极小，得点又从出发沿方向求极小，得点于是那么此方向应与P。方向共轭。事实上也是这样，因为：故：可见从不同起点沿同一方向进行直线搜索可以产生共轭方向。Powell方向正是基于这一思想而产生的。他的办法是沿着n个坐标方向依次求极小值，这样经过n次以后所得到的n个新方向就是相互共轭的。这是powell方法的原始方案，过程如下： 已知目标函数f(z).设定z。 其中若转，若 转若，则最优解终止。否则转沿作直线搜索，；转2但是，原始powell方法有一个主要的缺点，即这样更换方向所产生的n个向量有时可能是近似的线形相关的，从而使其真的极小点可能被漏掉。为克服这些缺点，powell自己将其方法做了某些改进，但改进后的方法一般不是二次终截的了，即对于n元二次函数f(z)求极小点即使n次迭代也不一定能找到极小点。但修正的powell方法能克服出现退化的情形，尽管收敛速度比原始的Powell方法慢些，但仍不失为无约束极小值直接优化方法中最有效的一个。其过程如下：已知f(z),取Z及n个初始搜索方向，不防取给定控制误差，较大的正数M。 其中 否则不变，转5若转7；若转3若则最优解；否则转8若转11；若则转10若转11；否则转12转2令转2例19.3.2 用原始powell方法求解无约束问题：解： 取初始方向 第一轮再沿加速方向进行直线搜索，即则则；完成一轮迭代第二轮，有两个搜索方向（线形相关） 这样原始powell法导出任一第k轮迭代点z始终停留在非最优点处，而原向量最优点为。可见原始powell方法失效。修正的目的在于保证线形无关。关于其证明过程从略，参见computer Journal,vol.7.p154162.1964由迭代过程可以看出：在某些时候一组n个方向不变，因此当n很大时，powell修正方案接近于轮换坐标法。因而收敛速度慢，根据经验，powell方法适应的范围大体上可限制在问题中的变量在20个以下，当然，目标函数值计算向量，计算机速度快时，问题维数也可以提高。例19.3.3 解：给定初始点， 则取故故因；因此又 因且故令，并从出发沿方向P求极小，得 ；完成一次迭代。 而且下一次迭代的两个搜索方向为： ，取分别沿向量19.4 Rosenbrok法 （旋转方向法）Rosenbrok在1960年提出一种直接最优化法。次法的每一轮迭代采用变步长的轴向移动。然后再利用轴向的旋转来产生一组新的方向作为下一轮迭代的轴向由于方法特点是在每一轮迭代之后要进行轴向的旋转，故而叫作旋转方向法，旋转方向的目的是为了加速收敛速度。前面Hook-Jeeues 模式搜索法中，轴向移动的步长在一定阶段保持不变，只在固定适当条件时才做缩减。事先给定一个步长增大系数和步长缩减系数，若从一个参考点出发沿平行与某轴向作探测成功时则下一次沿此方向探测的步长增加倍，若失败，则取原步长的倍。由到的迭代是这样建立的:先以作为参考点Y,反复地沿平行于作为轴向的n个正交单位方向；作变步长的轴向探测移动，直到各轴向的探测成功之后出现了失败，此时停止探测，得探测的最后点取为为提高求解效率，Rosenbork 法在完成一轮轴向探测后都接着进行各轴向的旋转，并得新建立的n个正交单位作为下一轮迭代的一组轴方向。下面考虑如何转轴，记：由于第k轮迭代中沿平行于每一轴向的各方向都移动过，因而，令利用gram-sckmidt正交化方法得方向组标准正交化为新的，作为下一轮迭代轴向，其计算公式为：Rosenboro步骤1）取初点，标准正交化向量组初始步长，增大函数，缩减函数，泛点限2）3）（轴向移动），对方向组从Y出发，反向平行于轴向的变步长探测移动：若： 例1