工程最优化方法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,工程最优化技术,（,EOT,）,第五章 无约束非线性问题的解法,提纲,一,、,概述,二、直接搜索法,三、梯度法,四、本章总结,一、概述,要点提示,单纯形搜索法,基本思想,共轭方向法,基本定理,Powell,共轭方向法,基本思想,最速下降法,基本思想及特点,Newton,法,基本思想及特点,牛顿方向,Marquardt,法,基本思想,最小二乘问题,共轭梯度法,基本思想,拟,Newton,法,基本思想,学习的重要性：,1,、,直接用于无约束的实际问题；,2,、,其基本思想和逻辑结构可以推广到约束问题；,3,、,约束问题可以转化成无约束问题求解。,方法分类：,1,、间接法：,对简单问题，求解必要条件或充分条件；,2,、迭代算法：,零阶法：只需计算函数值,f(x),一阶法：需计算,f(x),二阶法：需计算,2,f(x),直接法,梯度法,二、直接搜索法,单纯形搜索法,共轭方向法,5.1,直接搜索法,优点：计算不太复杂；易于实施与快速调试；所需的准备时间较少,5.1.1,单纯形搜索法,1962,年由,Spendley,Hext,和,Himsworth,提出，,80,年代得到证明,在山谷最低处找到泉水！,（二）,单纯形法的基本思想,初始单纯形,搜索方向,与步长,比较单纯形,顶点的函数值,新近似点,新的单纯形,以,min f(x,1,x,2,),为例，说明迭代过程,x,2,x,1,P,H,P,L,f,H,f,G,f,L,P,F,P,R,反射,P,R,f,R,f,R,扩张失败,P,S,=P,R,新单纯形,P,G,P,L,P,S,P,S,P,E,P,S,P,R,压缩,P,S,f,S,0,，令,x,(i),=x,(0),+he,(i),(i=1,2,n),其中,e,(i),=(0,.,0,1,0,0),T,为单位坐标向量,第,i,个分量为,1,x,2,x,1,x,(0),x,(1),x,(2),h,h,(2),取初始步长,h0,，令,x,(i),=x,(0),+Z,(i),(i=1,2,n),其中,Z,(i),=(q,.,q,p,q,q),T,第,i,个分量为,p,x,2,x,1,x,(0),x,(1),x,(2),h,q,p,p,q,棱长为,h,的正规单纯形,（三）,单纯形搜索法的算法,给定一个最大迭代次数,K,M,，令迭代次数计数变量,K,0,1,、,给定初始点,x,(0),构造初始单纯形,2,、,计算函数值,f,i,=f(x,(i),),，,(i=0,1,2,n),，并比较大小，找出最差点,x,(H),，次差,点,x,(G),和最好点,x,(L),，即,3,、,按终止准则判断是否已达到精度要求，若已达到，停止计算，否则转,4,4,、,求反射点,x,(R),5,、,将,f,R,与,f,L,，,f,G,和,f,H,作比较,6,、,若,f,S,f,H,，压缩成功，令,x,(H),=x,(S),转向,2,否则，进行收缩。,几点说明：,1,、,关于初始步长,h,的选取（一般可取,0.5h15,）,(1),开始取,h,为,1.6,2,；,(2),进行到发现,f,H,f,L,已 很小，但尚未达到精度，这时取,x,(0),=x,(L),，,重新开始,，并取步长为：,当离精度要求已不远时，,h=0.5,1,；,当离精度要求还很远时，,h 2,。,2,、,终止准则,P109,3,、,扩张因子,r=1.2,2,例,5.1.1,用单纯形搜索法求解,min f(x)=60,10 x,1,4x,2,x,1,2,+x,2,2,x,1,x,2,设,x,(0),=0,0,T,e,(1),=1,0,T,e,(2),=0,1,T,取,h=2,=0.5,=2,=1,终止准则为,|(,f,H,f,L,)/f,L,|0,，,其中，,p,(i),0,i=0,1,n-1,则此向量系必线性无关。,推论：在,n,维空间中，互相共轭的非零向量的个数不超过,n,个。,定理,5.1.2,：,若,p,(0),p,(1),p,(n-1),是,n,个非零的,A,共轭向量，则二次目标函数,f(x)=c+b,T,x+1/2 x,T,Ax,的最优点,x,*,为,!,可得到非二次函数最优点的一个近似点；其中,A,其是目标函数的,Hesse,矩阵！,?,上式用于非二次目标函数，可否得到最优点？,定理,5.1.3:,设,A,为,n,阶对称正定矩阵，对于二次目标函数,:,f(x)=c+b,T,x+1/2 x,T,Ax,，,从任意初始点,x,(0),出发，逐次进行一维搜索，即,min,f,(x,(i),+t p,(i),)=,f,(x,(i),+t,i,p,(i),)i0,若搜索方向,p,(0),p,(1),p,(n-1),是非零的,A,共轭向量，则至多进行,n,次迭代必可得到极小点,x,*,，即,x,(i+1),=x,(i),+t,i,p,(i),其中,t,i,为最优步长因子，,i=0,1,n,1,x,*,=x,(k),0kn,上述搜索方法具有二次收敛性,?,对非二次函数，采用上述方法，,n,次迭代是否也可得到极小点？,?,如何简便地找出,n,个相互,A,共轭的向量？,定理,5.1.4:,假设,1.n,元函数,f(x)=c+b,T,x+1/2 x,T,Ax,中的矩阵,A,是对称正定的；,2.,向量,p,(0),p,(1),p,(m-1),(,mn,),是互相,A,共轭的；,3.x,(0),x,(1),是不同的任意两点，分别从,x,(0),x,(1),出发，依次沿,p,(0),p,(1),p,(m-1),作一维精确搜索，设最后一次一维搜索的极小,点分别为,x,(0)*,和,x,(1)*,那么，,则：向量,p=x,(0)*,x,(1)*,与,p,(0),p,(1),p,(m-1),互为,A,共轭。,已知前,m,个共轭方向，,就可以找到第,m+1,个共轭方向,定理,5.1.4:,已知前,m,个共轭方向，,就可以找到第,m+1,个共轭方向,p,(1),x,(0),x,(1),p,(0),p,(0),x,(0)*,x,(1)*,x,*,x,(0),x,(1),p,(0),p,(0),p,(1),p,(1),x,(0)*,x,(1)*,p,(2),x,*,（三）,Powell共,轭方向法的基本思想,表,5.1.1 Powell,共轭方向法的迭代过程,阶段起点,x,(k,0),n+1,次一维搜索过程,新共轭方向,一边搜索，,一边找共轭方向,每一阶段（行）都进行,n+1,次搜索，产生一个共轭方向；共,n,个阶段（列）,任意,n个线性无关的方向,二维空间中二次函数的,Powell,共轭方向,法示意,p,(0),p,(1),e,(2),e,(1),p,(0),=e,(1),p,(1),=e,(2),以,二次函数,f(x,1,x,2,),为例,x,(1,0),x,(1,1),x,(1,2),p,(1),x,(2,2),x,(2,0),x,(2,1),x,*,对于二次函数,x,*,即为极小点,（四）,Powell,方法的原始算法,开始,给定,x,(0),e,(1),e,(2),e,(n),及,否,x,(k),=x,(k,n),+,k,p,(n-1),其中,k,为最优步长,k=1,p,(i),=e,(i+1),i=0,1,n-1,j=0,x,(k,j),=x,(k-1),x,(k,j+1),=x,(k,j),+,j,p,(j),其中,j,为最优步长,j=j+1,j=n,满足精度,否,k=k+1,x,*,=x,(k+1),结束,是,是,p,(i),=p,(i+1),i=0,1,n-2,几点说明,1,、,迭代中逐次产生的是共轭方向，是较好的搜索方向，所以,Powell,法又称,方向加速法,；,2,、,原始算法具有重要的理论意义，但实际应用时有局限,因为只有在每次搜索均为一维完全精确搜索,的条件下，每个阶段产生的方向才是相互共轭,的方向。,但实际一维搜索都是近似的，产生的方向不,一定共轭，,有时甚至是线性相关的,，导致搜,索空间降维，这时将找不到真正的极小点。,p,(1),x,(0),x,(1),p,(0),p,(0),x,(0)*,x,(1)*,x,*,p,(1),对于一般非线性函数，,n个阶段迭代后一般得不到极小点,，,但由于,一组,共轭方向的个数只有n个,，,如果继续按上述方法迭代,，,产生的方向就不再是相互共轭方向了,，,收敛速度会变慢,。,（五）,原始算,法一种简便改进,重新开始,：,每进行,n,个阶段的迭代，或当收敛速度变慢时，以当前点为起点，,回到第一步重新开始；,（六）,改进的,Powell算法,1.,基本思想,:,克服搜索方向的线性相关问题；,?,如何判定方向组是“最相互共轭”的,?,在每个阶段产生新的方向,p,后,更换方向组的方法,不是一律去掉第一个方向,p,(0),而是有选择地去掉某个方向,p,(J),原则是,使新的方向组,“最相互共轭”；,定理,5.1.5,设,A,是,n,阶对称正定矩阵，方向组,p,(0),p,(1),p,(n-1),按下式意义是规范化的：,p,(i)T,A p,(i),=1,，,(,i=0,1,n-1),置,Q,p,(0),p,(1),p,(n-1),，则方向组,p,(0),p,(1),p,(n-1),相互,A,共轭的充要条件为：,行列式,|Q|,的值达到它的最大值。,改进,Powell,算法的理论基础,三、梯度法,最速下降法,Newton,法,Marquardt,法,最小二乘问题,共轭梯度法,拟,Newton,法,5.2,梯度法,直接搜索法收敛速度一般比较慢，需要计算大量的函数值。梯度反映了函数值变化的规律，充分利用梯度信息构造算法，能加速收敛。,使用函数的梯度（一阶导数）或,Hesse,矩阵（二阶导数）的优化算法称为梯度法,目标：,求出平稳点（满足,f(x,)=0,的,x,*,）。,由于,f(x,)=0,一般是非线性方程组，解析法往往行不通，所以梯度法通常也是逐次逼近的迭代法,假定：,f(x,),和,2,f(x,),连续存在,5.2.1,最速下降法,(Cauchy,法,),1847,年,Cauchy,提出。特点,是,直观易懂，但收敛速度慢,（一）,基本思想,x,(k+1),=x,(k),+t,k,p,(k),瞎子下山：,由于他看不到哪里是山谷，不可能沿直接指向山谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然后在新的位置上再用手杖寻找最陡方向，再下降一步。这就是最速下降法的形象比喻。,多变量最优化迭代解法的一般迭代公式,可用一维搜索技术解决,关键是如何确定搜索方向,p,(k),迭代公式,x,(k+1),=x,(k),t,k,f(x,(k),),x,(k),x,*,p,(k),=,f(x,(k),),x,(k+1),p,(k+1),=,f(x,(k+1),),？,（二）,算法,开始,给定,x,(0),M,1,2,令,k=0,计算,f(x,(k),),|f(x,(k),)|M,x,*,=x,(k),是,结束,是,一维搜索求,t,k,，精度为,2,否,x,(k+1),=x,(k),t,k,f(x,(k),),k=k+1,x,(k+1),p,(k),x,(k),f(x),等值面,f(x,(k+1),),（三）,最速下降法的搜索路径呈直角锯齿形,t,k,定理,5.2.1,设从点,x,(k),出发，沿方向,p,作一维搜索，,t,k,为最优步长因子，即,f(x,(k),+t,k,p)=min f(x,(k),+t p),则成立,f(x,(k),+t,k,p),T,p=0,即新点处的梯度与搜索方向垂直。,p,(k+1),x,(0),x,(1),x,(2),两维情形下最速下降法搜索路径,1,、优点：,计算简单，需记忆的容量小；,对初始点要求低，稳定性高；远离极小点时收敛快，常作为其它方法的第一步。,2,、缺点：,收敛速度较慢（线性或不高于线性）。原因是最速下降方向只有在该点附近有意义。,尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时，收敛更慢。,例,5.2.1,用最速下降法求函数,f(x,1,x,2,),x,1,2,+4x,2,2,的极小点，（迭代两次），,并验证相邻两个搜索方向是正交的。初始点取为,x,(0),=1,1,T,。,解：,梯度,f(x),2x,1,8x,2,T,。,1.,第一次迭代：,f(x,(0),),2,8,T,，,x,(1),=,x,(0),t,0,f(x,(0),),1,1,T,t,0,2,8,T,用一维搜索求,t,0,，对简单,f(x),，可用解析法求解：,设,0,(t),f(x,(1),),f(1,1,T,t2,8,T,),(1,2t),2,+4(1,8t),2,0,(t),520t,68,0 t,0,0.130769,x,(1),=0.738462,0.046152,T,2.,第二次迭代：,f(x,(1),),1.476924,0.369216,T,x,(2),=x,(1),t,1,f(x,(1),)=,0.738462,1.476924t,1,0.046152+0.369216t,1,1,(t),2.317625t+5.453173t,0 t,1,0.45005,x,(2),=0.110762,0.110767,T,f(x,(2),),0.221524,0.886136,T,3.,验证相邻两个搜索方向是正交的：,f(x,(0),),T,f(x,(1),)=2,8 1.476924,0.369216,T,=0.00012,0,f(x,(1),),T,f(x,(2),)=0.000001,0,5.2.2,Newton,法（二阶方法）,？,由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别好的方向，有没有更好的方向,?,（一）基本,Newton,法,取,f(x;x,(k),),的平稳点作为,f(x),最优点的一个近似点,f(x;x,(k),)=,f(x,(k),)+,2,f(x,(k),),x=0,x,x,(k),=,x=,2,f(x,(k),),1,f(x,(k),),x=,x,(k),+(,2,f(x,(k),),1,f(x,(k),),5.2.2,Newton,法（二阶方法）,Newton,迭代公式,x,(k+1),=,x,(k),2,f(x,(k),),1,f(x,(k),),x,(k),f(x,(k),),f(x;x,(k),),x,(k+1),或,x,(k+1),=,x,(k),H,(x,(k),),1,g,(x,(k),),H,(x,(k),),1,g,(x,(k),),!,当,f(x),是二次函数时，一次迭代就可达到平稳点,！,!,当,f(x),是单变量函数时，本方法即为,Newton-Raphson,法,！,结束,基本,Newton,法的算法,开始,给定,x,(0),令,k=0,计算,g,(k),=,f(x,(k),),x,*,=x,(k),是,p,(k),=,H,(x,(k),),1,g,(k),x,(k+1),=x,(k),+p,(k),k=k+1,否,计算,H,(x,(k),),|g,(k),|,例,5.2.2,用基本,Newton,法求函数,f(x,1,x,2,),8x,1,2,+4x,1,x,2,+5x,2,2,的极小点。初始点取为,x,(0),=10,10,T,。,解：,f(x),16x,1,+4x,2,4x,1,+10 x,2,T,2,f(x),H(x)=,16 4,4 10,H(x),1,=,10,4,4 16,1,144,x,(1),=,x,(0),H,(x,(0),),1,f(x,(0),),10,10,=,10,4,4 16,1,144,200,140,0,0,因为,f(x),是二次函数，所以一步迭代就达到平稳点，又因为,H,(x,(1),),是正定矩阵，所以,x,(1),是极小点。,说明：,1,、基本,Newton,法要求,Hesse,矩阵具有逆矩阵。,如果,H(x,(k),),是正定的，则,H(x,(k),),1,必存在，并且保证求得的平稳点是极小点。,然而“在迭代过程中要求,H(x,(k),),是正定的”这一条件不一定总能保证，只有当初始点合适时才能满足。一般在极小点附近的,Hesse,矩阵容易为正定的。,所以,基本,Newton,法在极小点附近才比较有效,。,2,、,Newton,法的搜索方向,H(x),1,f(x),不一定是下降方向。,因为若是下降方向，则应有,f(x),T,H(x),1,f(x)0,，但由于,H(x),1,不一定是正定的，所以上式不一定成立,3,、,Newton,法的最大优点是：当初始点选得合适时收敛很快，具有二阶收敛速度，是目前算法中最快的一种。,对初始点要求高，一般要求初始点离极小点较近，否则不收敛。有时即使是,收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。,4,、,H(x),1,f(x),称为,Newton,方向，是一个好方向，对二次函数直指平稳点。,（二）修正,Newton,法,?,怎样才能使,Newton,法成为一个下降算法,？,修正,1,：,迭代公式：,x,(k+1),=,x,(k),t,k,H,(x,(k),),1,f(x,(k),),沿,Newton,方向一维搜索得到的最优步长,保证了,f(x,(k+1),)f(x,(k),),，,且不必要求,H(x),为正定矩阵。,?,出现,(1)H(x,(k),),1,不存在；或,(2)t,k,=0,时怎么办,？,修正,2,：改用最速下降法，即,p,(k),=,f(x,(k),),修正,Newton,法,优点：收敛快，程序简单。前者更实用可靠。,缺点：要求计算,Hesse,矩阵及其逆矩阵，计算量大，尤其当维数,n,较大时。,最速下降法,优点：,对初始点要求不高，稳定性好；远离最优点时收敛较快。,缺点：,离最优点较近时收敛很慢。,牛顿法的优缺点刚好与最速下降法相反。,1963,年,Marquardt,提出将最速下降法与,Newton,法结合：,开始用最速下降法；,在接近最优点时用,Newton,法；,5.2.3,Marquart,法,在迭代公式,x,(k+1),=x,(k),+t,k,p,(k),中，取步长,t,k,1,，搜索方向为,p,(k),2,f(x,(k),),+,k,I,1,f(x,(k),),其中,k,同时起控制搜索方向和步长的作用，,I,为单位矩阵,(1),开始阶段取很大，如,0,=10,4,，,p,(0),2,f(x,(0),),+,0,I,1,f(x,(0),),f(x,(0),),1,0,(2),在迭代过程中，让,k,0,，,p,(k),2,f(x,(k),),1,f(x,(k),),（一）方法思想,最速下降法,Newton,法,具体在每一步是否缩小,k,，要通过检验目标函数值来决定：,若,f(x,(k+1),)f(x,(k),),，取,k+1,1,，重作第,k,步迭代。,（二）算法,开始,x,*,=x,(k),是,结束,p,(k),=,2,f(x,(k),),+,k,I,1,f(x,(k),),否,否,kM,是,|f(x,(k),)|,f(x,(k+1),)f(x,(k),),k+1,=0.5,k,k=k+1,是,否,k,=2,k,（三）评注,PP124,I,可推广为半正定矩阵,计算,f(x,(k),),给定,x,(0),M,，,令,k=0,，,0,=10,4,x,(k+1),=x,(k),+p,(k),5.2.4,非线性最小二乘问题,（一）最小二乘问题,在工程实际问题中，经常遇到一类特殊的求极小值问题，其目标函数具有平方和形式：,例,5.2.3,求解方程组,f,i,(x)=0,，（,i=1,2,m),的问题可化为求解下列优化问题,例,5.2.4,通过,m,组实验数据来建立物理量,y,与另外,l,个物理量,t,1,t,2,t,l,之间的函数关系：,y=Y(t,1,t,2,t,l,;x,1,x,2,x,n,),“,接近”的衡量标准常用平方和的形式,求解,min F(x),引入向量函数,f(x)=f,1,(x),f,2,(x),f,m,(x),T,最小二乘问题化为：,min F(x)=min f(x),T,f(x),=min|f(x)|,2,（二）最小二乘问题的求解,可直接用前面介绍的单纯形法、,Powell,共轭方向法、最速下降法、,Newton,法、,Marquardt,法求解,最小二乘法（,Gauss-Newton,法）,！,如用,Newton,法求解，则要求,F(x),的,Hesse,矩阵，是否可以不求,H(x),？,由于最小二乘问题目标函数形式的特殊性，可用计算一阶导数来代替二阶导数的计算：,F(x,(k),)=2J(x,(k),),T,f(x,(k),),Newton,方向：,p,(k),=,2,F(x,(k),),1,F(x,(k),),Jacobi,矩阵,:,J(x)=J,ij,(x),mn,J,ij,(x)=,2,F(x,(k),),2J(x,(k),),T,J(x,(k),),迭代公式：,x,(k+1),=x,(k),J(x,(k),),T,J(x,(k),),1,J(x,(k),),T,f(x,(k),),1:x,(k+1),=x,(k),J(x,(k),),T,J(x,(k),),1,J(x,(k),),T,f(x,(k),),修正,Gauss-Newton,迭代公式,t,k,?,如果在某次迭代中,J(x,(k),),T,J(x,(k),),变成奇异的，则,Gauss-Newton,法失效,!,2:,此时可直接取负梯度方向,J(x,(k),),T,f(x,(k),),为搜索方向,修正,Gauss-Newton,法的算法,:P127,5.2.5,共轭梯度法,由,Powell,共轭方向法可知，共轭方向是好方向，是否有比,Powell,共轭方向 法更简单的方法构建共轭方向？,（一）,Fletcher,Reeves,共轭梯度法的基本思想,任取初始点,x,(0),，然后沿着逐次迭代产生的共轭方向,p,(k),进行一维搜索：,x,(k+1),=x,(k),+t,k,p,(k),得到下一个迭代点。,构造共轭方向,p,(0),p,(n-1),的方法：,p,(0),=,f(x,(0),),p,(k+1),=,f(x,(k,1),)+,k,p,(k),p,(0),=,f(x,(0),),f(x,(1),),p,(1),=,f(x,(1),)+,0,p,(0),x,(0),x,(1),!,要使得,p,(0),p,(n-1),相互共轭，,显然,k,不能随便取 ！,记,g,(k),=,f(x,(k),),F,R,共轭梯度法的迭代公式：,x,(k+1),=x,(k),+t,k,p,(k),p,(k+1),=,g,(k),+,k,p,(k),k,=,|g,(k),|,2,|g,(k+1),|,2,p,(0),=,g,(0),以二次目标函数为模型，经推导得：,（详细看,P129,下半页的内容，注意,式,5.2.19,及,5.2.20,的推导）,几点说明,：,1,、“重新开始”的策略,原因同,Powell,共轭梯度法（误差、共轭梯度的个数）,2,、何时执行重新开始步骤？,见,PP131,（二）,F,R,法的算法,开始,给定,x,(0),|g,(k+1),|,否,k=0,，,p,(0),=,g,(0),x,*,=x,(0),是,结束,g,(0),=,f(x,(0),),|g,(0),|,x,(k+1),=x,(k),+t,k,p,(k),g,(k+1),=,f(x,(k+1),),其中,t,k,为最优步长,x,(0),=x,(k+1),g,(0),=g,(k+1),是,否,a,k,=,|g,(k+1),|,2,/,|g,(k),|,2,p,(k+1),=,g,(k),+,k,p,(k),k=k+1,x,*,=x,(k+1),是,结束,k=n,否,例,5.2.6,用,F,R,共轭梯度法解,:,min f(x),60,10 x,1,4x,2,+x,1,2,+x,2,2,x,1,x,2,;,初始点取为,x,(0),=0,0,T,。,解：,f(x),10,2x,1,x,2,4,2x,2,x,1,T,p,(0),g,(0),f(x,(0),),10,4,T,进行一维搜索，对简单,f(x),，可用解析法求解：,f(x,(1),)=,f(x,(0),t,p,(0),)=f(x)|,x=10t,4t,T,=60,116t+76t,2,f,(t),1520t,116,0 t,0,0.76315789,x,(1),=x,(0),+t,0,p,(0),=7.63157894,3.052631578,T,g,(1),f(x,(1),),2.21052631,5.52631579,T,a,0,=,|g,(1),|,2,/,|g,(0),|,2,=35.42659277/116,p,(1),=,g,(1),+,0,p,(0),=0.84349308,6.747922437,T,同理：,t,1,0.436781609,x,(2),=x,(1),+t,1,p,(1),=7.999999993,5.999999997,T,g,(2),f(x,(2),),0,0,T,所以，,x,*,=8,6,T,f,*,=8,（三）,其它的共轭梯度法（自学）,（四）,评注,1,、共轭梯度法的优点是不必计算,Hesse,矩阵及其逆矩阵，程序简单，对大规模问题很有吸引力。对一般函数为超线性收敛。,2,、收敛速度依赖于一维搜索的精确性及,Hesse,矩阵的特征。,5.2.6,拟,Newton,法（变尺度法）,优点是靠近极小点时收敛速度快；,缺点是要计算,Hesse,矩阵及其逆矩阵，计算量大；,?,有没有可能既保持,Newton,法快速的优点，又不计算,Hesse,矩阵及其逆矩阵,?,1959,年,Davidon,提出变尺度法；,1963,年经,Fletcher,和,Powell,改进，形成,DFP,法；,1970,年,Broyden-Fletcher-Goldfarb-Shanno,提出更稳定的,BFGS,变尺度法；,Newton,迭代公式,或,x,(k+1),=,x,(k),H,(x,(k),),1,g,(x,(k),),x,(k+1),=,x,(k),2,f(x,(k),),1,f(x,(k),),拟,Newton,法的基本思想,从形式上模仿；,但,H,(k),应满足：,(1),满足拟,Newton,条件：,x,(k+1),x,(k),=H,(k+1),f(x,(k+1),),f(x,(k),),(2),H,(k),为正定矩阵，这样,p,(k),为下降方向,(3),由,H,(k),出发计算,H,(k+1),应简便,:,(4),应使算法具有二次收敛性,校正矩阵,H,(k+1),H,(k),E,(k),x,(k+1),=,x,(k),H,(x,(k),),1,g,(x,(k),),x,(k+1),=,x,(k),H,(k),g,(x,(k),),H,(k),（三）,DFP,算法,p,(0),=,f(x,(0),),H,(0),=I,p,(k),=,H,(k),f(x,(k),),x,(k+1),=x,(k),+t,k,p,(k),H,(k+1),H,(k),s,(k),s,(k)T,s,(k)T,y,(k),H,(k),y,(k)T,y,(k)T,H,(k),y,(k)T,H,(k),y,(k),其中,y,(k),=g,(k+1),g,(k),s,(k),=x,(k+1),x,(k),1,、上述算法具有三个性质：,(1),校正公式的分母总大于零,校正公式总有物理意义；,(2),H,(k),都是正定的，所以每次迭代方向都是下降方向；,(3),对二次函数,f(x)=c+b,T,x+0.5x,T,Ax (A,正定,),，迭代得到的搜索方向,p,(0),p,(1),p,(k,1),相互,A,共轭，所以,DFP,是一种共轭方向法；且,H,(n),=A,1,，说明,H,(k),逐次逼近,A,1,；（尤其，,H,0,取,I,，共轭梯度法）,2,、,DFP,法的重新开始策略,由于计算的舍入误差及一维搜索精度不够，会破坏,H,(k),的正定性，导致算法失效。,（,1,）,一维搜索后，如果,f(x,(k+1),),f(x,(k),),，意味着,p,(k),不是下降方向，,H,(k),不是正 定矩阵，则重新开始，重置,H,(k),=I,；,（,2,）,每迭代,n+1,次后重新开始，令,x,(0),=x,(k+1),H,(0),=I,3,、,DFP,法的算法,开始,给定,x,(0),|g,(k+1),|,f,0,=,f(x,(0),),g,(0),=,f(x,(0),),x,(k+1),=x,(k),+t,k,p,(k),其中,t,k,为最优步长,f,k+1,=,f(x,(k+1),),g,(k+1),=,f(x,(k+1),),x,(0),=x,(k+1),f,0,=,f,k+1,g,(0),=g,(k+1),是,否,y,(k),=g,(k+1),g,(k),s,(k),=x,(k+1),x,(k),x,*,=x,(k+1),是,结束,k=n,否,f,k+1,f,k,否,是,H,(0),=I,，,p,(0),=,g,(0),k=0,p,(k+1),=,H,(k+1),g,(k+1),k=k+1,H,(k+1),H,(k),s,(k),s,(k)T,s,(k)T,y,(k),H,(k),y,(k)T,y,(k)T,H,(k),y,(k)T,H,(k),y,(k),四、本章总结,x,(k+1),=x,(k),+t,k,p,(k),多变量最优化迭代解法的一般迭代公式,最优步长,可用一维搜索技术解决,不同的搜索方向,p,(k),构成不同的算法,算法名称,搜索方向,p,(k),Powell,共轭方向法,共轭方向,最速下降法,p,(k),=,f(x,(k),),Newton,法,p,(k),=,2,f(x,(k),),1,f(x,(k),),Marquardt,法,p,(k),2,f(x,(k),),+,k,I,1,f(x,(k),),F-R,共轭梯度法,p,(0),=,f(x,(0),),p,(k+1),=,f(x,(k,1),)+,k,p,(k),DFP,法,（拟,Newton,法）,p,(0),=,f(x,(0),),p,(k),=,H,(k),f(x,(k),),5.4,方法的比较与选择,1,、间接法：,对简单问题，求解必要条件或充分条件；,2,、迭代算法：,零阶法：只需计算函数值,f(x),一阶法：需计算一阶导数,f(x),二阶法：需计算二阶导数,2,f(x),直接法,梯度法,从收敛速度考虑：梯度法快于直接法,Newton,法,拟,Newton,法,(,变尺度法,),共轭梯度法,Powell,共轭方向法,单纯形法,最速下降法,5.5,化工实例换热器系列的最优设计,300,T,3,100,物料,400,T,4,T,1,600,T,5,T,2,500,换热器,I,K,1,120,换热器,II,K,2,80,换热器,III,K,3,40,某化工厂欲利用本厂废热，采用三个换热器将某物料由,100,加热到,500,，其流程及有关数据如下图所示，问如何选取换热器的各个出口温度才能使换热器系列的总传热面积,F,最小？已知条件如下：,（,1,）所有物流,w,i,cp,i,10,5,，其中,w,是流体流量，,cp,为流体比热，,i,为流体序,号，,i,1,2,（,2,）三个换热器的总传热系数分别为,K,1,120,，,K,2,80,，,K,3,40,；,（,3,）换热器采用逆流换热方式，为简化起见，其换热温差采用算术平均,值，各数值已略去量纲。,300,T,3,100,物料,400,T,4,T,1,600,T,5,T,2,500,换热器,I,K,1,120,换热器,II,K,2,80,换热器,III,K,3,40,换热器,I,：,wcp,(,T,1,100),wcp,(300,T,3,),，,T,3,400,T,1,换热器,II,：,wcp,(,T,2,T,1,),wcp,(400,T,4,),，,T,4,400,T,2,T,1,换热器,III,：,wcp,(500,T,2,),wcp,(600,T,5,),，,T,5,100,T,2,换热器,I,：,换热器,II,：,换热器,III,：,1,、建立数学模型：,对三个换热器分别进行热量衡算：,300,T,3,100,物料,400,T,4,T,1,600,T,5,T,2,500,换热器,I,K,1,120,换热器,II,K,2,80,换热器,III,K,3,40,其中,三个换热器换热面积核算：,该问题的数学模型为：,2,、选择优化方法求解，结果,T,1,=182.0176;,T,2,=295.6012;,T,3,=217.9824;,T,4,=286.4164;,T,5,=395.6012,F,1,=579.3064;,F,2,=1360;,F,3,=5110;,F=,7049.2,作业：,PP452 7,（迭代,2,次）；,9(3),（迭代,2,次）,PP453 12(,迭代,3,次,),13,（用共轭梯度法）,二次函数（二次曲面）,二次函数（二次曲面）,