常用无约束最优化方法ppt课件

第五章常用无约束最优化方法,内容5.1最速下降法5.2Newton法5.3修正Newton法5.4共轭方向法5.5共轭梯度法5.6变尺度法5.7坐标轮换法5.8单纯形法,引言,本章讨论多维无约束最优化问题:minf(X)它的求解是指,在Rn中找一点X*,使得对于任意的都有但大多数最优化方法只能求到局部最优点,即在Rn中找到一点X*,使得上述不等式在X*的某个领域中成立.这个矛盾对于实际问题一般容易解决.根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解.而在理论上这是个比较复杂的问题,本书不涉及.无约束优化方法是优化技术中极为重要和基本的内容之一.它不仅可直接求解无约束优化问题,而且很多约束优化问题也常转化为无约束优化问题,然后用无约束优化方法来求解.另,有些无约束优化方法只略加处理,即可求解约束优化问题.无约束优化理论发展较早,比较成熟,方法也很多,新的方法还在陆续出现.把这些方法归纳起来可以分成两大类:一类是仅用计算函数值所得到的信息来确定搜索方向,通常称它为直接搜索法,简称为直接法,另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向,这一类方法称为间接法(解析法).直接法不涉及导数、Hesse矩阵,适应性强,但收敛速度较慢;间接法收敛速度快,但需计算梯度,甚至需要计算Hesse矩阵.一般情况是,在可能求得目标函数导数时尽可能用间接方法;在不能求目标函数导数或根本不存在导数时就使用直接法.,其中,则点X*就是问题的全局最优点.,迭代终止准则(H准则),当第k次迭代点Xk与最优解X*充分靠近,即|Xk-X*|充分小时,Xk可作为最优解,这样可用|Xk-Xk+1|1作为迭代终止准则,此准则是不完全可靠的,因为,|Xk-Xk+1|充分小并不能保证|Xk-X*|充分小,这时函数值的差|f(Xk)-f(Xk+1)|很大,所以要增加条件:|fk-fk+1|1就比较可靠了,其中fk=f(Xk),fk+1=f(Xk+1)当fk的值或Xk分量的值与1相比很大时,上述准则就太严格了,即满足上述准则就要用很多计算.此时可用下列准则:当算法涉及到梯度时,可用下列准则:|f(Xk)|0置搜索方向依次为按下式求最优步长并进行迭代计算式中k为循环次数,k=1,2,.;i为该循环中一维搜索的序号,i=1,2,.,n,tk(i)为利用一维搜索求出的最优步长.如果i=n,即转(5);如果if(X3)这说明X1最差,X3最好,X2次差.为了寻找极小点,一般来说应向最差点的反对称方向进行搜索.以X4记为X2X3的中点在X1X4的延长线上取点X5,使称为X5为X1关于X4的反射点.,如图所示,X5-X4=X4-X1,算出X5的函数值f(X5),可能有下列情形:f(X5)f(X5),则扩张不利,舍去X6,以X5代替X1构新单纯形X2,X3,X5.f(X3)f(X5)f(X2).这说明搜索方向正确,无须扩张,以X5代替X1构成新的单纯形X2,X3,X5.f(X2)f(X5)f(X1).,这时应更多压缩,将新点压缩至X1X4之间,有注意,上两式只是X1和X5的差别.如f(X8)f(X1),则以X8代替X1构成新的单纯形X2,X3,X8.否则可以认为X1X4方向上所有点的函数值f(X)都大于f(X1)不能沿此方向搜索这时,可以以X3为中心进行缩边,使顶点X1和X2向X3移近一半距离如图所示,以此单纯形为基础再进行寻优.可见,不管如何,都可得到一新的单纯形,其中至少有一顶点的函数值比原单纯形为小.如此继续,直至满足终止准则.在n维情况下,一个单纯形含有n+1个顶点,计算工作量较大,但原理和上述二维情况相同.,得新单纯形X3,X9,X10.,二、单纯形法迭代步骤,已知设X为n维变量,目标函数为f(X),终止限为构造初始单纯形在n维空间中选初始点X0(离最优点越近越好),从X0出发,沿各坐标方向以步长t移动得n个顶点这样选择顶点可保证向量组否则,就会使搜索范围局限在较低维的空间内,可能找不到极小点.步长t的范围可取0.515.0,开始时常取t=1.52.0,接近最优点时要减小,例如取0.51.0.计算各顶点的函数值比较各函数值的大小,确定最好点最差点反射计算XH之外各点的“重心”求出反射点,线性无关.,当然,在各坐标方向可以走不同的距离.,次差点,当f(Xn+2)f(XL),扩张,令:如f(Xn+3)f(Xn+2),则以Xn+3代替XH形成一新单纯形.转(8).否则,以代Xn+2替XH构成新单纯形.转(8).无扩缩.当f(XL)f(Xn+2)f(XG),以代Xn+2替XH构成新单纯形.转(8).收缩.当f(XG)f(Xn+2)f(XH),收缩,令:以代Xn+4替XH构成新单纯形.转(8).缩边.当f(XH)f(Xn+2),先收缩,令:如f(Xn+5)f(XH),则以Xn+5代替XH形成一新单纯形.转(8).否则,将单纯形缩边,可将向量Xi-XL的长度缩小一半,即得新单纯形,转(8).终止检验,每次得新单纯形后,要做终止检验,如满足终止准则,则迭代停止,XL即为所求的近似解.否则,继续进行迭代.常用的终止准则是1和2为允许误差.,扩张.,或,单纯形法的流程如图,试用单纯形法求的极小值.解选X0=(8,9)T,并取X1=(10,11)T和X2=(8,11)T.这三点不共线,它们作为初始单纯形的顶点(如图所示).计算各顶点的函数值:X1为最差点,X0为最好点.以X3表示X0和X2的重心,则反射点,例5.6(P118),由于f(X4)f(X0),故需扩张.取=2,则因为f(X5)f(X4),故以X5代替X1,由X5,X0和X2构成新单纯形,然后进行下一个循环.该问题的最优解为X*=(5,6)T