lbc-第4章无约束问题的最优化方法.ppt

第四章无约束问题的最优化方法,4.1引言4.2梯度法4.3牛顿法4.4坐标轮换法4.5Poweel法4.6无约束优化设计方法小结,4.1引言,一.定义：,求一组n维设计变量X=x1,x2,xnT,使目标函数达到min.f(x)XRn对X没有任何限制即求目标函数的最优解：最优点x*和最优值f(x*)。,条件：,对于无约束优化问题的求解，就是把求极值的问题变成求解方程,即求X使其满足:,二.基本思想：,从给定的初始点X0出发，沿着搜索方向d进行搜索，寻找k使函数下降到新的点，故形成以下迭代算法：,f(Xk+1)f(Xk),三.内容：,一类是使用导数的方法，也就是根据目标函数的梯度（一阶导数）有时还要根据Hesse矩阵（即二阶导数）所提供的信息而构造出来的方法，就称为梯度方法。如：最速下降法，Newton法，共扼梯度法和变尺度法。另一类是不使用导数的方法，统称为直接方法。如:坐标轮换法,Powell法和单形替换法前者收敛速度快，但计算复杂（一阶，二阶导数）后者不用导数，适应性强，但收敛速度慢。因此再可以求得目标函数导数信息时，尽可能用另一方法，而若求目标函数导数很困难，或者根本不存在导数时，就用后一种方法,无约束最优化可以分为两大类：,四.意义：,为有约束优化方法的研究提供了策略思想、概念基础和基本方法；为有约束优化问题的间接解法提供了有效而方便的方法；对于某些工程问题，进行分析后，便于提供解决的有效方法；不可避免地还存在无约束优化的设计问题。,4.2梯度法(最速下降法),1.基本思想：,目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向作为搜索方向，期望很快找到最优点。,最速下降法是求多元函数极值的最古老的数值算法，它直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。其缺点是收敛速度较慢。,从某点X出发，其搜索方向d取该点的负梯度方向（最速下降方向），使函数值在该点附近的范围内下降最快，故形成以下迭代算法：,=,2.搜索方向：,为了使目标函数沿负梯度方向下降最快，应使步长因子应取一维搜索的最佳步长。即有：,根据一元函数极值的必要条件和多元复合函数求导公式，得：,负梯度向量,=,由此可知：相邻两个迭代点上的函数梯度相互垂直；相邻两个搜索方向互相垂直；形成“之”字形的锯齿现象。,说明：,3.程序设计：,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例1：求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去，经10次迭代后，得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线。,4.方法评价：,迭代过程简单，对初始点的选择，要求不高。梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。,4.3牛顿法,1.基本思想：,将f(x)在x(k)点作台劳展开，取二次函数式(x)作为近似函数,以(x)的极小值点作为f(x)的近似极小值点。,说明：,f(x)若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。,2.牛顿法：,例1：求目标函数的极小点。,经过一次迭代即求得极小点,函数极小值,解取初始点,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。,阻尼牛顿法,阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得:,阻尼牛顿法程序框图,3.程序设计：,4.方法评价：,使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。若初始点选得合适，牛顿法的收敛速度相当快。牛顿法求逆矩阵的工作量大，计算量与存储量均随n2上升。,一般迭代式：,梯度法：,牛顿法：,阻尼牛顿法：,5.梯度法与牛顿法区别：,4.4坐标轮换法,1.基本思想：,2.搜索方向与步长：,每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi(k)n次搜索后获得极值点序列x1(k),x2(k）,xn(k)，若未收敛，则开始第k+1次迭代，直至收敛到最优点x*。,3.步骤：,(,),(,),(,),(,),(,),(,),迭代。,若不满足，则作下一轮,。,则,若满足,是否满足收敛条件：,每轮迭代结束时，检验,。,的极值点,一维搜索，分别求得,方向作两次,，分别沿,令,第二轮迭代：,),(,n,0,n,2,2,2,1,),1,(,2,2,0,*,=,-,=,k,k,k,x,x,x,x,x,x,x,f,x,x,e,(,),(,),(,),(,),(,),(,),。,的极值点,分别求得,作两次一维搜索，,两个坐标轴方向,，依次沿,，令,选初始点,第一轮迭代：,1,2,1,1,1,2,1,1,),0,(,1,0,),0,(,x,x,x,f,d,d,x,x,x,=,(,),(,),2,2,2,1,d,d,4.程序设计：,5.方法特点：,方法简单，容易实现。不需要求函数导数的直接探索目标函数最优解的方法当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。,受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴，以t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。,4.5Powell法,一。基本Powell法:,1.基本思想：,若沿连接相邻两轮搜索末端的向量S方向搜索，收敛速度加快。,因为两条平行线S1,S1与同心椭圆族相切，两个切点的连线S直指中心。称S1与S为共轭方向。目的：以共轭方向打破振荡，加速收敛。,2.共轭方向的定义：,3.共轭方向的性质：,4.步骤：,把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：1）在每轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。2）始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。3）用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新的方向排在原方向的最后。4）此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点，这样就形成算法的循环。,二、改进的算法在鲍威尔法中，每一轮迭代都用连续始点和终点所产生出的搜索方向去替换原方向组中的第一个向量，而不管它的“好坏”，有时会产生n个向量组线性相关而不能形成共轭方向。因此在改进法中首先判断原向量组是否需要替换。如需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证