无约束最优化方法直接搜索法课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,无约束最优化方法,无约束最优化方法,无约束最优化方法,求解无约束最优化问题,min f(x),的数值迭代解法构成约束最优化方法的基础解法无约束最优化方法求解无约束最优化问题 min f(x)的数,求解无约束最优化问题的下降迭代解法具有统一的迭代格式，其基本问题是选择搜索方向和在这些搜索方向上进行一维搜索由于构成搜索方向的方式可以不同，从而形成了各种不同的无约束最优化方法求解无约束最优化问题的下降迭代解法具有统一的迭代格式，其基本,无约束优化的直接搜索法,各种无约束优化方法的区别就在于确定其搜索方向,S,(k),的方法不同，所以搜索方向的构成问题是无约束优化方法的关键根据构造搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类：,X,(k+1),=,X,(k),+,(k),S,(k),(,k=,0,1,2,),一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。

无约束优化的直接搜索法 各种无约束优化方法的区别,基本思想,坐标轮换法（变量轮换法、交替法、降维法）,将,n,维无约束优化问题转化为,n,个沿坐标轴方向,e,i,(i=1,2,n),的一维优化问题来求解，并记完成,n,次一维搜索为一轮若一轮搜索后未得到满足精度要求的最优点，则继续下一轮迭代搜索如此反复，直至得到满足精度要求的最优点为止在每一轮搜索中，每次迭代仅对,n,元函数的一个变量沿其坐标轴方向进行一维搜索，其余,n-1,个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿,n,个坐标轴方向的,n,次一维搜索基本思想 坐标轮换法（变量轮换法、交替法、降维法）,x,1,x,2,X,0,(1),X,1,(1),X,2,(1),取初始点,X,(0),=,X,0,(1),，,x,1,坐标轴方向的单位向量,S,1,(1),=e,1,=1 0,T,，,x,2,坐标轴方向的单位向量,S,2,(1),=e,2,=0 1,T,X,1,(1),=,X,0,(1),+,1,(1),S,1,(1),，,X,2,(1),=,X,1,(1),+,2,(1),S,2,(1),x1x2X0(1)X1(1)X2(1)取初始点,判断是否满足迭代收敛准则：,|,X,2,(1),X,0,(1),|,？,X,1,(1),=,X,0,(1),+,1,(1),e,1,(1),=,x,1,(0),x,2,(0),T,+,1,(1),1 0,T,X,2,(1),=,X,1,(1),+,2,(1),e,2,(1),=,x,1,(1),x,2,(1),T,+,2,(1),0 1,T,第一轮迭代搜索：,若满足，则输出最优解，否则，继续下一轮迭代搜索。

判断是否满足迭代收敛准则：,X,i,(,k,),=,X,i-1,(,k,),+,i,(,k,),e,i,(,k,),(k,迭代轮次，,i k,轮迭代的第,i,次一维搜索,i,(,k,),一维搜索求得的最优步长）,|,X,n,(k),X,0,(k),|,？,计算步骤与算法框图,1,）任选初始点,X,(0),=,X,0,(1),=,x,1,(0),x,2,(0),x,n,(0),T,，给定迭代收敛精度,，,i=1,，,k=1,2,）置,n,个坐标轴方向向量为单位向量，即,e,1,=1 0,0,T,，,e,2,=0 1 0,0,T,，,，,e,n,=0,0,1,T,Xi(k)=Xi-1(k)+i(k)ei(k)|,3,）按如下迭代计算公式进行迭代计算,X,i,(,k,),=,X,i-1,(,k,),+,i,(,k,),e,i,(,k,),(k,迭代轮次，,i k,轮迭代的第,i,次一维搜索,i=1,，,2,，,，,n,）,4,）判断是否满足迭代收敛准则,|,X,n,(k),X,0,(k),|,？,若满足，则输出最优解,:,X,*,=,X,n,(k),，,f,*,=,f,(,X,*,),否则，令,X,0,(k+1),=,X,n,(k),，,k,k+1,，返回,3,）。

3）按如下迭代计算公式进行迭代计算 Xi(k)=X,单纯形替换法,基本思想,通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的大致趋势，从而可以寻求使函数值下降的搜索方向在,n,维空间中，由,n+1,个不同点顺序相连，就可以构成一个具有,n+1,个顶点的多面体,称之为单纯形计算函数在这,n+1,个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的单纯形，并用之取代原来的单纯形如此下去，新单纯形不断地向目标函数的极小点靠近，直到搜索到极小点为止单纯形替换法 基本思想 通过计算出若,计算步骤,1,）构造初始单纯形,选初始点,X,0,，和步长,h,从,X,0,出发沿各坐标轴方向分别走步长,h,，得到,n,个顶点,X,i,(i=1,2,n),，与,X,0,构成初始单纯形X,0,x,2,x,1,X,1,X,2,计算步骤 1）构造初始单纯形X0 x2x1X1,2,）计算各顶点的函数值,f,i,=,f,(,X,i,)(i=0,1,2,n),3,）比较函数值大小，确定最好点,X,L,、最差点,X,H,和次差点,X,G,，即,:,f,L,=,f,(,X,L,)=min,f,i,:,i=0,1,2,n,f,H,=,f,(,X,H,)=max,f,i,:,i=0,1,2,n,f,G,=,f,(,X,G,)=max,f,i,:,i=0,1,2,n;i H,4,）检验是否满足迭代收敛条件,|(,f,H,f,L,)/,f,L,|,?,2）计算各顶点的函数值 3）比较函数值大,若满足，则结束迭代计算，并输出,X,*,=,X,L,和,f,*,=,f,L,否则，转下一步。

5,）计算除,X,H,点外的各点的“重心”,X,n+1,，即,X,n+1,=(,X,i,X,H,)/n,计算反射点：,X,n+2,=2,X,n+1,X,H,和,f,n+2,=,f,(,X,n+2,),当,f,L,f,n+2,f,G,时，以,X,n+2,代替,X,H,，,f,n+2,代,替,f,H,，构造新的单纯形，然后返回到,3,）若满足，则结束迭代计算，并输出 否则，转下一步X,0,x,2,x,1,X,1,X,2,X,H,X,L,X,G,X,n+1,X,n+2,6,）扩张：当,f,n+2,f,L,时，取,扩张点,X,n+3,，即,X,n+3,=,X,n+1,+,(,X,n+2,X,n+1,)(,=1.2,2.0,),并计算,f,n+3,=,f,(,X,n+3,),若,f,n+3,f,n+2,，则以,X,n+3,代替,X,H,，,f,n+3,代替,f,H,，构造一个新的单纯形；否则，以,X,n+2,代替,X,H,，,f,n+2,代替,f,H,，构造新的单纯形；然后返回到,3,）X,n+3,X0 x2x1X1X2XHXLXGXn+1Xn+2 6）扩,7,）收缩：当,f,n+2,f,G,时，则需收缩。

若,f,n+2,f,H,，则取,收缩点,X,n+4,：,X,n+4,=,X,n+1,+,(,X,n+2,X,n+1,),（,=0.5,）,f,n+4,=,f,(,X,n+4,),否则，以,X,H,代替上式中的,X,n+2,，计算,收敛点,X,n+4,：,X,n+4,=,X,n+1,+,(,X,H,X,n+1,),f,n+4,=,f,(,X,n+4,),7）收缩：当 fn+2 f G 时，则需收缩X,0,x,2,x,1,X,1,X,2,X,H,X,L,X,G,X,n+1,X,n+2,X,n+3,若,f,n+4,f,H,，则以,X,n+4,代替,X,H,，,f,n+4,代替,f,H,，形成新的单纯形，然后返回到,3,）；否则转下一步,8,）X,n+4,X,n+4,X0 x2x1X1X2XHXLXGXn+1Xn+2Xn+3,8,）缩边：将单纯形向,X,L,缩边，可以将各向量,(,X,i,X,L,)(i=0,1,2,n),的长度都缩小一半，即,X,i,=,X,L,+0.5,(,X,i,X,L,)=0.5,(,X,i,+X,L,),(i=0,1,2,n),形成新的单纯形，然后返回到,2,）8）缩边：将单纯形向XL缩边，可以将各向量,鲍威尔（,Powell,）法,基本思想,它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。

由于对于,n,维正定二次函数，共轭搜索方向具有,n,次收敛的特性，所以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于维数,n 20,的目标函数它是成功的鲍威尔法是在研究具有正定对称矩阵,H,的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在迭代过程中逐次构造关于,H,的共轭方向鲍威尔（Powell）法 基本思想,共轭方向的生成,设是,X,(k),和,X,(k+1),为从不同点出发，沿同一方向进行,一维搜索,而得到的两个极小点S,(j),S,(j),S,(k),X,(k),X,(k+1),f,(,X,(k),),f,(,X,(k+1),),S,(j),T,f,(,X,(k),)=0,S,(j),T,f,(,X,(k+1),)=0,共轭方向的生成 设是X(k)和,具有正定对称矩阵,H,的二次函数,f,(,X,)=0.5,X,T,H,X,+,B,T,X+C,在,X,(k),和,X,(k+1),两点处的梯度可以表示为,f,(,X,(k),)=,H,X,(k),+,B,（,1,）,f,(,X,(k+1),)=,H,X,(k+1,）,+,B,（,2,）,（,2,）（,1,）得,f,(,X,(k+1),),f,(,X,(k),)=,H,(,X,(k+1),X,(k),),（,3,）,（,3,）式两边同时左乘,S,(j),T,得,S,(j),T,f,(,X,(k+1),),f,(,X,(k),)=,S,(j),T,H,(,X,(k+1),X,(k),)=0,具有正定对称矩阵H的二次函数 f(X(k),即,S,(j),T,H,(,X,(k+1),X,(k),)=0,若取,S,(k),=,X,(k+1),X,(k),那么，,S,(k),和,S,(j),关于,H,共轭，即,S,(j),T,H,S,(k),=0,这说明：,沿,S,(j),方向分别对函数做两次一维搜索，得到两个极小点,X,(k),和,X,(k+1),，该两点的连线方向,S,(k),与,S,(j),是关于,H,共轭的方向。

即 S(j)T H(X,X,(k),x,1,x,2,X,*,S,(j),X,(k+1),S,(k),X(k)x1x2X*S(j)X(k+1)S(k),上述生成共轭方向的方法完全可以推广到,n,维优化问题中，即在,n,维空间中，按上述方法可以生成,n,个相互共轭的搜索方向鲍威尔法的基本原理和迭代过程,1,）采用坐标轮换法顺次沿,n,个坐标轴方向进行一维搜索，然后以初始点,X,(0),和终点,X,n,(1),构成一个,新的方向,S,(1),，并以此方向为搜索方向再作一维搜索得到极小点,X,n+1,(1),2,）取始点,X,0,(2),=,X,n+1,(1),，并,去掉,原搜索方向组中的,第一个方向,S,1,(1),=e,1,，而将第一轮构成的,新搜索方向,S,(1),作为,最末一个方向,，以此组成第二轮迭代的,n,个方向上述生成共轭方向的方法完全可以推广到n维优化,依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止根据这一原理构造的迭代算法称为,鲍威尔基本算法X,1,(1),X,*,S,1,(1),X,。