第三章优化设计(06).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章,无约束问题的最优化方法,3.1,引言,3.2,一维搜索方法,3.3,坐标轮换法和,Poweel,法,3.4,梯度法和共轭梯度法,3.5,牛顿法和变尺度法,3.6,无约束优化设计方法小结,3.1,引言,一,.,目的：,求一组,n,维设计变量,X=x,1,x,2,x,n,T,使目标函数达到,min.f(x)XR,n,即求目标函数的最优解：最优点,x*,和最优值,f(x*),。,二,.,意义：,为有约束优化方法的研究提供了策略思想、概念基础和基本方法；,为有约束优化问题的间接解法提供了有效而方便的方法；,对于某些工程问题，进行分析后，便于提供解决的有效方法；,不可避免地还存在无约束优化的设计问题。,3.1,引言,三,.,内容：,一维搜索：求最优步长因子,(k),多维（变量）优化：确定搜索方向,S(k),黄金分割,插值法,坐标轮换法,共轭方向法,梯度法,共轭梯度法,牛顿法,DFP,变尺度法,3.2,一维搜索方法,一,.,一维搜索：,定义,:,在第,K,次迭代时，从已知点,X,(k),出发，沿给定方向求最优步长因子,(k),，使,f(X,(k),+,S,(k),),达到最小值的过程，称为一维搜索。,方法：,1.,解析法：,f(x,(k+1),)=min.f(x,(k),+,S,(k),),=f(x,(k),+,(k),S,(k),),步骤,:f(X,(k),+S,(k),),沿,S,(k),方向,x,(k),台劳展开；,取二次近似：,3.2,一维搜索方法,对,求导，令其为零。,2.,数值迭代法：,直接法,应用序列消去原理：,分数法、,黄金分割法,近似法,利用多项式函数逼近（曲线拟合）原理：,二次插值法,、三次插值法,求得最优步长因子,：,3.2,一维搜索方法,单峰区间：,在区间,1,，,3,内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点,*,，当任意一点,2,*,时，,f(,2,),f(*),，,说明：,单峰区间内，函数可以有不可微点，也可以是不连续函数；,f(x),0,1,3,0,f(x),3,1,f(),3,2,*,1,0,当,2,*,时，仍有,f(,2,),f(*),，则,*,是最优点，也即为最优步长因子,(k),。,2,确定的搜索区间必定是一个含有最优点,*,的单峰区间。,二、单峰区间确定,3.2,一维搜索方法,定步长搜索法,:,3.,加速步长搜索法,：,4.,外推法：,f 2=f(,1,+t,0,),1,f,1,3.2,一维搜索方法,三,.,黄金分割法,(0.618),：,1.,序列消去原理：,f(),3,(1),12,*,1,(1),0,3,(2),11,21,22,1,(2),1,(3),3,(3),3.2,一维搜索方法,2.,黄金分割与,0.618,：,b,d,古希腊建筑师认为：边长为,b,，,d,的矩形建筑物，若边长能符合以下条件，则最美观：,欧几里德几何称这种边长分割为黄金分割。,序列消去法中，为提高效率，减少计算量和存储量，希望,2026/5/26 周二,10,原函数,用三点二次插值多项式来逼近原函数。,一）基本思路,3.2,一维搜索方法,2026/5/26 周二,11,二）二次插值曲线的极小点,求出,a,、,b,后得,2,）求系数,a,和,b,1,）求驻点,插值多项式：,2026/5/26 周二,12,三）区间的缩短,x,4,=0.5(x,1,+x,2,),f,4,=f(x,4,),x,1,=x,4,f,1,=f,4,x,3,=x,2,f,3,=f,2,x,2,=x,4,f,2,=f,4,x,1,=x,p,f,1,=f,p,x,3,=x,2,f,3,=f,2,x,2,=x,p,f,2,=f,p,x,1,=x,2,f,1,=f,2,x,2,=x,p,f,2,=f,p,x,3,=x,p,f,3,=f,p,是,否,输出,二次插值法缩小区间流程图,输入,x,p,x,2,f,4,f,2,f,2,f,p,x,p,0,x*=x,p,f,*,=f,p,x,*,=x,2,f,*,=f,2,否,给定,x,1,、,x,3,、,否,否,是,结 束,是,是,是,本书认为是由于区间缩到很小时因计算机舍入误差引起，可取中间点输出。,2026/5/26 周二,15,)A=0,),这表明此时三个插值点共线。,3.2,一维搜索方法,2.,步骤,(,续,),：,3.,结果分析：,问题：若不满足精度，如何缩小区间，再拟合（分四种情况分析）？,3.2,一维搜索方法,与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。,4.,方法评价,:,3.3,坐标轮换法和,Poweel,法,一,.,坐标轮换法：,1.,基本思想：,2.,搜索方向与步长：,每次以一个变量坐标轴作为搜索方向，将,n,维的优化问题转化为一维搜索问题。例，第,k,轮迭代的第,i,次搜索，是固定除,x,i,外的,n-1,个变量，沿,x,i,变量坐标轴作一维搜索，求得极值点,x,i,(k),n,次搜索后获得极值点序列,x,1,(k),x,2,(k,）,x,n,(k),，若未收敛，则开始第,k+1,次迭代，直至收敛到最优点,x*,。,3.3,坐标轮换法和,Poweel,法,一,.,坐标轮换法：,3.,方法评价：,方法简单，容易实现。,当维数增加时，效率明显下降。,收敛慢，以振荡方式逼近最优点,。,受目标函数的性态影响很大。,如图,a),所示，二次就收敛到极值点；,如图,b),所示，多次迭代后逼近极值点；,如图,c),所示，目标函数等值线出现山脊（或称陡谷），若搜索到,A,点，再沿两个坐标轴，以,t,0,步长测试，目标函数值均上升，计算机判断,A,点为最优点。事实上发生错误。,3.3,坐标轮换法和,Poweel,法,二,.Poweel,法（,共轭方向法、方向加速法）：,1.,基本思想：,2.,共轭方向的定义：,若沿连接相邻两轮搜索末端的向量,S,方向搜索，收敛速度加快。,因为两条平行线,S,1,S,2,与同心椭圆族相切，两个切点的连线,S,直指中心。称,S,1,S,2,与,S,为共轭方向。,目的,：以共轭方向打破振荡，加速收敛。,3.3,坐标轮换法和,Poweel,法,3.,共轭方向的性质：,3.3,坐标轮换法和,Poweel,法,4.,步骤：,3.3,坐标轮换法和,Poweel,法,6.,方法评价：,计算步骤复杂,;,是二次收敛方法，收敛快。对非正定函数，也很有效,;,是比较稳定的方法。,5.,说明：,若是正定二次函数，,n,轮迭代后收敛于最优点,x*,。,若是非正定二次函数，则迭代次数增加。,若是,n,维问题，步骤相同。,搜索方向：第一轮迭代，沿初始方向组,S,i,(1),(i=1,2,n),的,n,个方向和共轭方向,S,(1),，搜索,n+1,次得极值点,x,n+1,(1),；第二轮迭代，沿方向组,S,i,(2),(i=1,2,n,；,im),的,n-1,个方向和共轭方向,S,(1),，构筑共轭方向,S,(2),搜索,n+1,次得极值点,x,n+1,(2),。其中，为保证搜索方向的线性无关，去除了,S,m,(2),方向。,在第,k,轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向,S,m,(k),。,去除的原则请自学。,3.4,梯度法和共轭梯度法,一,.,梯度法,（最速下降法）,：,1.,基本思想：,2.,搜索方向：,目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向作为搜索方向，期望很快找到最优点。,3.,步骤：,（略）,3.4,梯度法和共轭梯度法,4.,方法评价：,迭代过程简单，对初始点的选择，要求不高。,梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。,以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。,一,.,梯度法,（最速下降法）,：,3.4,梯度法和共轭梯度法,二,.,共轭梯度法,（旋转梯度法）,：,1.,基本思想,：,2.,共轭方向：,对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。,3.,共轭系数：,推导过程请自学。,(k),S,(k),3.4,梯度法和共轭梯度法,二,.,共轭梯度法,（旋转梯度法）,：,1.,基本思想,：,2.,共轭方向：,对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。,3.,共轭系数：,推导过程请自学。,(k),S,(k),3.4,梯度法和共轭梯度法,步骤：,5.,方法评价：,迭代程序简单，容易实现，存储量较小。,开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，收敛快。,3.5,牛顿法和变尺度法,一,.,牛顿法,（二阶梯度法）,：,1.,基本思想：,将,f(x),在,x,(k),点作台劳展开，取二次函数式,(x),作为近似函数,以,(x),的极小值点作为,f(x),的近似极小值点。,说明：,f(x),若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。,3.5,牛顿法和变尺度法,2.,修正牛顿法：,步骤：,（略）,4.,方法评价：,使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。,若初始点选得合适，牛顿法的收敛速度相当快。,牛顿法求逆矩阵的工作量大，计算量与存储量均随,n,2,上升。,一,.,牛顿法,（二阶梯度法）,：,3.5,牛顿法和变尺度法,二,.DEF,变尺度法,:,1.,变尺度的定义：,每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。,2.,基本思想：,发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。,3.5,牛顿法和变尺度法,3.,变尺度矩阵的构造：,原则：,使目标函数值有下降性，则变尺度矩阵应为实对称矩阵,（请证明）,；,使算法有二次收敛性，则,S,(k),(k=1,2,),应关于,H,(k),是共轭的；,构造变尺度矩阵的递推公式,：,4.,修正矩阵,:,3.5,牛顿法和变尺度法,步骤：,（略）,6.,方法评价：,DEF,变尺度法以逐次逼近的方法实现,H,-1,的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。,算法的第一步是梯度法，最速下降；接近,x*,时，又采用二次收敛的共轭方向，总的收敛速度较快。,H,(k),近似代表,x,(k),点的二阶导数，当其为零时，可判断,x,(k),为鞍点。,H,(k),的计算较复杂，存储量较大。,算法稳定性较差，由于计算机有舍入误差，容易使,H,(k),的正定性破坏，趋于奇异。,3.6,无约束优化设计方法小结,例：,解：,用,Poweel,法、共轭梯度法、牛顿法、变尺度,(DEF),法进行计算，并进行比较。,3.6,无约束优化设计方法小结,Poweel,法 共轭梯度法 牛顿法 变尺度,(DEF),法,迭代次数,搜索次数,搜索方向,收敛速度,存储量,适用维数,稳定性,2 2 1 2,6 2 1 2,共轭方向,零阶算法 一阶算法 二阶算法 超线性,较慢 二次收敛 收敛最快 二次收敛,小 中 最大 较大,存储量随,n,2,随,n,，,t,n20 n200,300,好 中 差 中下,