《《机械设计优化方法》PPT课件》由会员分享,可在线阅读,更多相关《《机械设计优化方法》PPT课件(53页珍藏版)》请在金锄头文库上搜索。
1、机械优化设计机械优化设计太原科技大学张学良第三章 一维优化方法 进退法确定初始搜索区间进退法确定初始搜索区间 欲求一元函数欲求一元函数f (x) 的极小点,首先必须的极小点,首先必须确定极小点所在的区间,然后再不断缩小此确定极小点所在的区间,然后再不断缩小此区间,从而求得其极小点的数值近似解。所区间,从而求得其极小点的数值近似解。所以,一维搜索包括两个内容:其一是确定包以,一维搜索包括两个内容:其一是确定包含有极小点的搜索区间,其二是缩短区间获含有极小点的搜索区间,其二是缩短区间获得极小点。得极小点。 一维搜索时,假设一元函数一维搜索时,假设一元函数 f (x) 具有具有凸性(单谷性),即在所
2、考虑区间具有唯一凸性(单谷性),即在所考虑区间具有唯一的极小点的极小点 x*。 进退法的基本思想:按照一定规则试进退法的基本思想:按照一定规则试算若干个点,比较其函数值的大小,直到算若干个点,比较其函数值的大小,直到找到按找到按“大大小小大大”变化的单谷区间为变化的单谷区间为止。止。xf (x)abx*大大小小大大f (x)xx1x2h02h0 x31. 选择一个适当选择一个适当的初始步长的初始步长 h=h0 。2.从从任任意意点点 x1 出出发发 , 以以 x1 和和3. x2 = x1 + h 为为两两个个试试算算点点,计计算算两两点点处处的的函数值。函数值。 f1 = f (x1 ) f
3、2 = f (x2 )3. 比较比较f1 和和 f2 的大小的大小 若若 f1 f2 , h 2h ,继续做前进计算,继续做前进计算 x3 = x2 + h = x2 + 2 h0 ,并计算,并计算f3 = f (x3 )f (x)xx1x2h02h0 x3若若 f1 f2 ,则则满满足足f1 f2 f3 ,对对于于前前进进计计算算,函函数数极极小小点点必必在在区区间间x1 , x3内内,令令 a = x1 , b = x3,初始搜索区间,初始搜索区间a, b确定。确定。 对于后退计算对于后退计算,函数极小点必在区间,函数极小点必在区间x3 , x1内,令内,令 a = x3 , b = x1
4、,初始搜索区间,初始搜索区间a, b确定。确定。 若若 f3 f2 ,对于,对于前进计算前进计算,函数极小点还,函数极小点还在在 x3 右右侧,放弃侧,放弃x1 , 作置换:作置换: x1 x2 , x2 x3 ,f1 f2 , f2 f3 h 2h, 再再 取取 新新 点点 x3 = x2 + h , 并并 求求 f3 = f (x3 ) ,返回,返回 4。 对于后退计算对于后退计算,函数极小点还在,函数极小点还在 x3 左左侧,侧,放弃放弃x1 , 作置换:作置换: x1 x2 , x2 x3 ,f1 f2 , f2 f3 h 2h, 再再 取取 新新 点点 x3 = x2 + h , 并
5、并 求求 f3 = f (x3 ) ,返回,返回 4。 黄金分割法黄金分割法 黄金分割法的基本原理黄金分割法的基本原理 在目标函数的初始搜索区间在目标函数的初始搜索区间a, b内任取内任取两点两点x1 、 x2 ,且,且 x1 x2 ,计算,计算 f1 = f (x1 ) , f2 = f (x2 )。 比较比较f1 和和 f2 的大小:的大小: 当当 f1 f2 时,时, 去掉去掉a , x1 ),保留,保留x1 ,b 区间缩短为区间缩短为x1 ,b 。作置换作置换 a x1 ,新区,新区间形成。间形成。 该方法的缺陷是:每次需要计算两个新点。该方法的缺陷是:每次需要计算两个新点。 要提高计
6、算效率,就得减少每次计算的点要提高计算效率,就得减少每次计算的点数,因此只能每次增加一个计算点,这就要求数,因此只能每次增加一个计算点,这就要求新区间与原区间满足一定的比例关系,所选的新区间与原区间满足一定的比例关系,所选的两个计算点在区间两个计算点在区间 a, b 内的位置应是对称内的位置应是对称的。的。ab1 设区间设区间 a, b的长度为的长度为1,即单位长度区间,即单位长度区间,在其上初取两对称点在其上初取两对称点 x1 、 x2 ,且满足,且满足 a x2 = X, a x1 = 1 - X 计算计算 f1 = f (x1 ) , f2 = f (x2 ),并比较,并比较 f1 和和
7、 f2 的大小。的大小。 当当 f1 f2 ,可以求得同样的值。,可以求得同样的值。 可见,新区间是原区间的。所以称为法或可见,新区间是原区间的。所以称为法或黄金分割法。黄金分割法。 黄金分割法的计算步骤及算法框图黄金分割法的计算步骤及算法框图 (略)(略) 举例:举例: 用黄金分割法求目标函数用黄金分割法求目标函数 f (x) = x2 - 5 x + 2 的最优解。的最优解。 二次插值法(抛物线法)二次插值法(抛物线法) 基本思想:在目标函数极小点所在区间基本思想:在目标函数极小点所在区间内,利用三个点的函数值构造一个二次插值内,利用三个点的函数值构造一个二次插值多项式多项式 (x) =
8、ax2 + b x + c 是来近似表达原目是来近似表达原目标函数标函数f (x),并用,并用 (x)的极小点的极小点x *近似代替近似代替f (x) 的最优点的最优点x* 。当这种近似代替不满足精。当这种近似代替不满足精度度f (x)f (x) x a b x1 x2 x3x* (x)x *要求时,按照一定规律缩短区间,并在新区要求时,按照一定规律缩短区间,并在新区间内重新构造三点二次插值多项式,再求其间内重新构造三点二次插值多项式,再求其极小点。如此反复,直到满足精度要求为止。极小点。如此反复,直到满足精度要求为止。 在目标函数极小点所在区间内取三点在目标函数极小点所在区间内取三点x1 =
9、a, x2 =(a+b)/2, x3 = b ,计算相应的目标,计算相应的目标函数值函数值f 1 、 f 2 、 f 3 ,则应有,则应有 (x1 ) = a x1 2 + b x1 + c = f 1 (x2 ) = a x2 2 + b x2 + c = f 2 (x3 ) = a x3 2 + b x3 + c = f 3 解该线性方程组,可以得到解该线性方程组,可以得到a 、b 、 c,并由此可以求得并由此可以求得 x * = ( x1 + x3 - d1 / d2 )/ 2 d1 = ( f3 f1 ) / ( x3 - x1 )d2 = ( f2 f1 ) / ( x2 - x1
10、)- d1 /(x2 x3 ) f = f (x * ) 检验收敛准则检验收敛准则 | x * - x2 | 1 ? 若满足若满足,以,以x *代替代替f (x) 的最优点的最优点x*,并,并输出输出x* = x * , f * = f (x* )。 若不满足若不满足,缩短区间后重复上述迭代计,缩短区间后重复上述迭代计算过程,直至满足要求为止。算过程,直至满足要求为止。 缩短区间分两种情况,即缩短区间分两种情况,即 1) x * x2 2) x * f 2 ; ii ) f f 2 ; ii ) f 3),通称等值面。在二维平面中),通称等值面。在二维平面中为等值线。若给定一系列目标函数的值,
11、将在为等值线。若给定一系列目标函数的值,将在设计空间得到一组等值面(线)族。设计空间得到一组等值面(线)族。目标函数的等值线(面)目标函数的等值线(面) f(X)=ax12+2bx1x2+cx22 a0 c0 ac-b20 一、最速下降方向一、最速下降方向负梯度方向负梯度方向 最速下降方向和共轭方向最速下降方向和共轭方向 函数的方向导数函数的方向导数X0X0+Xx1x2Sn元函数的方向导数元函数的方向导数: 与负梯度方向成锐角的方向为目标函数与负梯度方向成锐角的方向为目标函数值的下降方向,成钝角的方向为目标函值的下降方向,成钝角的方向为目标函数值的增加方向。数值的增加方向。 目标函数的梯度方向
12、是目标函数等值线目标函数的梯度方向是目标函数等值线(面)在同一点的法向矢量方向。(面)在同一点的法向矢量方向。 f(X(k)- f(X(k)X(k)t所以,目标函数在某一点的最速下降方向为所以,目标函数在某一点的最速下降方向为负梯度方向负梯度方向两个向量的共轭两个向量的共轭 设两个非零向量设两个非零向量S(0)、S(1)及对称正定矩阵及对称正定矩阵H,若满足,若满足二、共轭方向二、共轭方向则称则称S(0)、S(1)关于关于H共轭,或称共轭,或称S(0)与与S(1)为共轭方向。为共轭方向。 若若H为单位阵,即为单位阵,即H=I,则,则S(0)与与S(1)正交。正交。一组向量的共轭一组向量的共轭
13、设有一组非零向量设有一组非零向量S(0)、S(1) S(n-1)及对称正及对称正定矩阵定矩阵H,若满足,若满足则称它们关于则称它们关于H共轭,或称它们为一组共轭方向。共轭,或称它们为一组共轭方向。 若若H为单位阵,则称它们相互正交。为单位阵,则称它们相互正交。凸集凸集 一个点集(或区域),如果连接其中任一个点集(或区域),如果连接其中任意两点的线段都全部包含在该点集内,则意两点的线段都全部包含在该点集内,则称该点集为凸集。否则,称为非凸集。称该点集为凸集。否则,称为非凸集。 凸集、凸函数与凸规划凸集、凸函数与凸规划凸函数凸函数 设函数设函数f (X)定义域为凸集定义域为凸集G,X(1)、X(2
14、)为凸集为凸集G上的任意两点,若函数上的任意两点,若函数f (X)在线段在线段X(1)X(2)上的函数值总小于或等于用上的函数值总小于或等于用f (X(1)及及f (X(2)作线性内插所得的值,则称函数作线性内插所得的值,则称函数f (X)为凸集为凸集G上的凸函数,即满足上的凸函数,即满足 的函数的函数f (X)为凸函数。若同时去掉式中的等为凸函数。若同时去掉式中的等号,则称函数号,则称函数f (X)为严格凸函数。为严格凸函数。凸规划凸规划 对于约束优化问题对于约束优化问题 若函数若函数f (X)、gj(X)均为凸函数,则称此约束均为凸函数,则称此约束优化问题为凸规划。优化问题为凸规划。凸规划
15、的性质凸规划的性质 1)凸规划的可行域为凸集)凸规划的可行域为凸集 2)凸规划的任何局部最优解就是全局最)凸规划的任何局部最优解就是全局最优解优解 优化问题的几何解释优化问题的几何解释X*X*X*X*X*X*h1=0h2=0 优化方法的简单分类优化方法的简单分类 按有无约束分类按有无约束分类 无约束优化方法、约束优化方法无约束优化方法、约束优化方法 按按目标函数的维数分类目标函数的维数分类 一维优化方法、多维优化方法一维优化方法、多维优化方法 按目标函数的数目分类按目标函数的数目分类 单目标优化方法、多目标优化方法单目标优化方法、多目标优化方法 按求优途径的不同分类按求优途径的不同分类 直接法
16、、解析法(间接法)、实验法、直接法、解析法(间接法)、实验法、图解法图解法 迭代方法及其收敛准则迭代方法及其收敛准则 无论是直接法还是解析法,求优的无论是直接法还是解析法,求优的过程都是采用数值迭代法,且迭代公式过程都是采用数值迭代法,且迭代公式的形式一致。的形式一致。 迭代方法迭代方法 X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , ) 两个特性两个特性 1)下降性)下降性: f (X (k+1) f (X (1) f (X (k) f (X (k+1) f (X *) 确定步长确定步长 (k) 的方法的方法 1)定步长法)定步长法 取取 (k) = p (p为常数为常数) ,检验下列不等式,检验下列不等式 f (X (k) + (k) S(k) ) f (X (k) ? 若成立,则继续下一步迭代计算;若成立,则继续下一步迭代计算; 否则,取否则,取 (k) = p (0 1),再检验不),再检验不 等式等式 f (X (k) + (k) S(k) ) f (X (k) ? 直至满足为止。直至满足为止。 2)最优步长法)最优步长法 用一维寻优方法确定