机械优化设计第三章

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 一维搜索方法（续,对求导，令其为

3、零,2. 数值迭代法,直接法应用序列消去原理：分数法 黄金分割法 近似法利用多项式函数逼近（曲线拟合）原理： 二次插值法 三次插值法,求得最优步长因子,一、一维搜索定义,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,确定的搜索区间必定是一个含有最优点

4、*的单峰区间,3.2 一维搜索方法（续3,定步长搜索法,3. 加速步长搜索法,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 一维搜

5、索方法（续6,四. 二次插值法（抛物线法,1. 基本原理,步骤,3.2 一维搜索方法（续7,2. 步骤,3. 结果分析,问题：若不满足精度，如何缩小区间，再拟合,4. 方法评价,与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少,四. 二次插值法（抛物线法,3.3 坐标轮换法和 Powell 法,一. 坐标轮换法,1. 基本思想,2. 搜索方向与步长,每次以一个变量坐标轴作为搜索方向，将 n 维的优化问题转化为一维搜索问题。例，第 k 轮迭代的第 i 次搜索，是固定除 xi 外的 n-1 个变量，沿 xi 变量坐标轴作一维搜索，求得极值点 xi(k) n 次搜索后获得极值

6、点序列 x1(k), x2(k , xn(k)，若未收敛，则开始第 k+1 次迭代，直至收敛到最优点 x,3.3 坐标轮换法和 Poweel 法（续,一. 坐标轮换法,3. 方法评价,方法简单，容易实现。 当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点,受目标函数的性态影响很大。 如图 a) 所示，二次就收敛到极值点； 如图 b) 所示，多次迭代后逼近极值点,如图 c) 所示，目标函数等值线出现山脊（或称陡谷），若搜索到 A 点，再沿两个坐标轴，以t0步长测试，目标函数值均上升，计算机判断 A 点为最优点。事实上发生错误,3.3 坐标轮换法和 Powell 法（续2,二. Powe

7、ll法（共轭方向法、方向加速法,1. 基本思想,2. 共轭方向的定义,若沿连接相邻两轮搜索末端的向量 S 方向搜索，收敛速度加快,因为两条平行线 S1 , S2 与同心椭圆族相切，两个切点的连线 S 直指中心。 称 S1 , S2 与 S 为共轭方向。 目的：以共轭方向打破振荡，加速收敛,3.3 坐标轮换法和 Poweel 法（续3,3. 共轭方向的性质,二. Powell法（共轭方向法、方向加速法,3.3 坐标轮换法和 Poweel 法（续4,4. 步骤,3.3 坐标轮换法和 Poweel 法（续5,6. 方法评价,计算步骤复杂。 是二次收敛方法，收敛快。对非正定函数，也很有效。 是比较稳定

8、的方法,5. 说明,若是正定二次函数，n 轮迭代后收敛于最优点 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 轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向 S

9、m(k)。去除的原则请自学,二. Powell法（共轭方向法、方向加速法,3.4 梯度法和共轭梯度法,一. 梯度法（最速下降法,1. 基本思想,2. 搜索方向,目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向作为搜索方向，期望很快找到最优点,3. 步骤： （略,3.4 梯度法和共轭梯度法（续,4. 方法评价,迭代过程简单，对初始点的选择，要求不高。 梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。 以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径,一. 梯度

10、法（最速下降法,3.4 梯度法和共轭梯度法（续2,二. 共轭梯度法（旋转梯度法,1. 基本思想,2. 共轭方向,对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛,3. 共轭系数,推导过程请自学,3.4 梯度法和共轭梯度法（续3,步骤,5. 方法评价,迭代程序简单，容易实现，存储量较小。 开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，收敛快,二. 共轭梯度法（旋转梯度法,3.5 牛顿法和变尺度法,一. 牛顿法（二阶梯度法,1. 基本思想,将 f(x) 在 x(k) 点作台劳展开，取二次函数式(x) 作为近似函数,

11、以(x) 的极小值点作为 f(x) 的近似极小值点,说明,f(x) 若是正定二次函数，一般迭代一次即可；若是严重 非线 性函数，则可能不收敛，或收敛到鞍点,3.5 牛顿法和变尺度法 （续,2. 修正牛顿法,步骤： （略,4. 方法评价,使用牛顿法时，若目标函数是严重 非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。 若初始点选得合适，牛顿法的收敛速度相当快。 牛顿法求逆矩阵的工作量大，计算量与存储量均随 n 的平方上升,一. 牛顿法（二阶梯度法,3.5 牛顿法和变尺度法 （续2,二. DEF 变尺度法,1. 变尺度的定义,每

12、确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度,2. 基本思想,发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法,3.5 牛顿法和变尺度法 （续3,3. 变尺度矩阵的构造,原则： 使目标函数值有下降性，则变尺度矩阵应为实对称矩阵（请证明）； 使算法有二次收敛性，则 S(k) (k=1,2,)应关于 H(k) 是共轭的,构造变尺度矩阵的递推公式,4. 修正矩阵,二. DEF 变尺度法,3.5 牛顿法和变尺度法 （续4,步骤： （略,6. 方法评价,DEF变尺度法以逐次逼近的方法实现 H-1 的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。 算法的第一步是梯度法，最速下降；接近 x* 时，又采用二次收敛的共轭方向，总的收敛速度较快。 H(k) 近似代表 x(k) 点的二阶导数，当其为零时，可判断 x(k) 为鞍点。 H(k) 的计算较复杂，存储量较大。 算法稳定性较差，由于计算机有舍入误差，容易使 H (k) 的正定性破坏，趋于奇异,二. DEF 变尺度法,3.6 无约束优化设计方法小结,例,解,用 Powell法、共轭梯度法、牛顿法、变尺