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