结构优化设计理论及应用ppt课件

结构优化设计理论及应用(2),土木水电学院硕士研究生课程,1,第三章无约束优化问题,2,第三章无约束优化问题,无约束优化问题的极值条件,搜索方向问题是无约束优化方法的关键。,各种无约束优化方法的区别：确定搜索方向的方法不同。,3,第三章无约束优化问题,（P1）Minf(X)XEn,研究意义：许多约束问题可转变为无约束问题求解。通常一个算法总包括一维搜索，而一维搜索实质就是一个无约束问题。因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,搜索的基本思想是通过逐次循环，来求得问题的最优解或近似最优解。,4,第三章无约束优化问题,5,第三章无约束优化问题,6,第三章无约束优化问题,无约束优化问题的极值条件,搜索方向问题是无约束优化方法的关键。,迭代格式：,7,定义1：令dEn，d0X*D称d为D在X*点的一个可行方向，如果存在某个0使得：X*+dD，（0，）。,第三章无约束优化问题,定义2：令dEn，d0X*D称d为f在X*点的一个下降（改善）方向，如果存在某个0，使得：f(X*+d)0,如果Xk-Xk-1/Xk0为预先给定的容许误差，则当某搜索步长小于时，搜索停止，得到问题的近似解。,17,第三章无约束优化问题,二、Fibonacci（分数）法,考虑问题,若F(x)是定义在a，b上的下单峰函数（即函数在限定区间a，b上有唯一极小点xmin，而且在最优解xmin左侧，即在区间a，xmin上F(x)严格下降，在在最优解xmin右侧，即在区间xmin，b上F(x)严格上升）。,任取两点x1a，b，x2a，b，x1F(x2)，则保留区间x1，b，保留点为x2如果不断重复上述过程，缩短搜索区间，则必定能求得最优解xmin。为了能利用前一次所得到结果，取前一次保留点为一个比较点，因此，只需要在保留区间上取一个不同于保留点的新点作为另一个比较点即可。依据上述原则缩小区间，如此下去，最终总会求得xmin满足给定误差的近似解。,18,假定Fk为Fibonacci数列：F0=F1=1,Fk+2=Fk+1+FkFn=1,1,2,3,5,8,13,.Step0给定最终不确定区间长度l0，初始区间a1,b1,根据Fn(b1-a1)/l,确定n,计算u1=a1+(Fn-2/Fn)(b1-a1)v1=a1+(Fn-1/Fn)(b1-a1)令k=1,进入Step1,第三章无约束优化问题,二、Fibonacci（分数）法,19,第三章无约束优化问题,a1,f(a1),b1,f(b1),uk,vk,f(uk),f(vk),u1=a1+(Fn-2/Fn)(b1-a1),二、Fibonacci（分数）法,20,第三章无约束优化问题,a1,f(a1),b1,f(b1),uk,vk,f(uk),f(vk),v1=a1+(Fn-1/Fn)(b1-a1),二、Fibonacci（分数）法,21,Step1若f(uk)f(vk)转Step2若f(uk)f(vk)转Step3Step2令ak+1=uk和bk+1=bk，进一步令uk+1=vk和vk+1=ak+1+(Fn-k-1/Fn-k)(bk+1-ak+1)若k=n-2,转Step5否则估计f(vk+1)且转Step4,第三章无约束优化问题,二、Fibonacci（分数）法,22,Step3令ak+1=ak和bk+1=vk，进一步令vk+1=uk和uk+1=ak+1+(Fn-k-2/Fn-k)(bk+1-ak+1)若k=n-2,转Step5否则估计f(uk+1)且转Step4,第三章无约束优化问题,二、Fibonacci（分数）法,23,Step4令k+1k,转Step1Step5令un=un-1和vn=un-1+，若f(un)f(vn)令an=vn和bn=bn-1，否则若f(un)f(vn)令an=an-1和bn=un，停止，则最优解落在区间an,bn中。,第三章无约束优化问题,二、Fibonacci（分数）法,24,第三章无约束优化问题,三、0.618（黄金分割）法,0.618法又称为黄金分割法，与Fibonacci法一开始的差别只在最初两个试验点的选取上，对于问题,用Fibonacci法最初的两个点选取在,及,用0.618法最初的两个点选取在0.382与0.618处。对于0.618法而言，当初始点选定后，序列中其余各点的取法与Fibonacci法原则一样，即按在保留区间中与保留点对称的原则来确定。可以认为这两个方法的区别仅在于用不随n而变化的0.382与0.618代替随n而变化的Fn-1/Fn+1与Fn/Fn+1。,25,三、0.618（黄金分割）法,第三章无约束优化问题,Step0给定容许最终不确定区间长度为l0，初始区间a1,b1,令k=1,进入Step1Step1若bk-akf(vk),则令ak+1=uk和bk+1=bk否则令ak+1=ak和bk+1=vkStep3令k+1k,转Step1,29,一维情况下的牛顿迭代公式,第三章无约束优化问题,四、牛顿法,多维情况下的牛顿法与一维情况相似，它的基本思路是将高次函数近似简化为一次或二次函数。二次函数的极值点较易求得。,对于多元函数，在,处进行泰勒展开，得,30,第三章无约束优化问题,四、牛顿法,称H(xk)为海森矩阵,也可以理解为牛顿法中的搜索方向为,31,对牛顿法进行改进，提出“阻尼牛顿法”,第三章无约束优化问题,四、牛顿法,与一维情况相似，牛顿法要求有合适的初始点，如果初始点偏离极值点太远，迭代可能不收敛。,32,第三章无约束优化问题,四、牛顿法,33,第三章无约束优化问题,五、变尺度（拟牛顿）法,牛顿法收敛速度快，但要求计算二阶导数的逆，计算工作量大，而有些问题目标函数的二阶导数难以求得，因此，牛顿法的应用受到限制。为此，人们对这种算法作了种种改进，其中一种思想是用一个nn阶的对称矩阵A来来逐步逼近牛顿法中的H(x)-1,这种方法称为拟牛顿法(QuasiNewtonMethod)。由于矩阵A是由递推公式逐步产生的，所以这个方法又称为变尺度法(VariableMetricMethod)。不同的递推公式形成不同的变尺度法。如BFGS法、DFP法。,34,第三章无约束优化问题,五、变尺度（拟牛顿）法,35,第三章无约束优化问题,五、变尺度（拟牛顿）法,36,六、共轭方向及共轭方向法,第三章无约束优化问题,共轭方向法。搜索方向是共轭方向。对于二次函数总能通过n轮(n为设计变量的个数)有限次的迭代达到极小点，且不需计函数的二阶导数和求逆矩阵，是较为有效的优化方法之一。,共轭方向的概念,共轭方向的概念是在研究二次函数,时引出的。,设S(i)(i=1,2,3,n)为一组线性无关的非零向量。A为nn阶对称正定矩阵，若它们存在如下关系：,则称向量S(i)与向量S(j)对A共轭（或正交）。当A为单位矩阵时，S(i)与S(j)为通常意义的正交（或几何上互相垂直）。,37,第三章无约束优化问题,六、共轭方向及共轭方向法,以二元函数为例说明共轭个方向的意义，设有初始点X(0)，并给定方向S(0)，在方向S(0)上求极小点，即,式中0是未知的，但可以用如下方法求得。,在X(0)处将函数F(x)进行Taylor展开,令,代入上式并简化,由于0的取值是使X(1)为极小，上式一阶导数应为零。即,38,第三章无约束优化问题,六、共轭方向及共轭方向法,得,这样可以得到X(1)点，由于X(1)点不可能恰好是函数得极小点，可以再给定方向S(1)，使沿S(1)方向找到的极小点恰好是函数的极小点，令,可仿上得,这样可得X(2)点，也是函数F(x)的极小点，所以函数,在X(2)点处的梯度应为零，即,39,第三章无约束优化问题,六、共轭方向及共轭方向法,代入上式，得,即,将上式左边向量与S(0)作内积，得,由0的计算公式，上式第一项为,且1一般不为零，所以,40,第三章无约束优化问题,六、共轭方向及共轭方向法,上述公式说明给定的S(0)与S(1)对H共轭，即从X(0)出发，沿S(0)、S(1)进行一维搜索得到的X(2)点为函数的极小点。在实际问题中，目标函数在极小点附近呈现为二次函数性状。可以证明，当目标函数为二次式时，应用共轭方向法，经过n轮迭代，一定可以寻到最小点（这种性质称为二次收敛性）。,41,七、坐标轮换法,第三章无约束优化问题,坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。,它把多变量的优化问题轮流地转化成单变量的优化问题。,因此又称变量轮换法。,其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是从初始点X0出发，先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。这样依次进行直到所有n个变量坐标方向都进行过搜索，达到一个新的初始点X0Xn。如此重复直到新的初始点与前一初始点之间的差异收敛到搜索精度的要求为止。,42,第三章无约束优化问题,坐标轮换法,43,第三章无约束优化问题,八、单纯形法,前面讨论的搜索方法都需要对目标函数沿某一方向（坐标方向、梯度方向或共轭方向）进行一维搜索。单纯形法不需要对目标函数进行这样的一维搜索，而只需对若干选点处的目标函数进行计算，通过比较其计算结果来逐步缩小选点范围以求收敛到极值点。设优化问题为,单纯形的过程如下：（1）选择一个初始点，即,44,第三章无约束优化问题,单纯形法,（2）选择单纯形边长l，并取,如n2，l1，则,（3）形成单纯形，单纯形定点Xi的坐标为,如n2，l1，则,在二维空间中，单纯形是一个等边三角形；在三维空间中，单纯形是一个正四面体。,45,第三章无约束优化问题,单纯形法,包括初始点在内，单纯形的顶点共有n1个，即X0，X1，X2，Xn单纯形的顶点处的目标函数值也有n1个，即f0，f1，f2fn,在这n1个目标函数值中，将其中最优（最小）者标为fg，其中最劣（最大）者标为fb，相应的顶点坐标各为Xg和Xb。,（4）求除Xb之外其余各顶点的形心Xa的坐标，得,（5）将最劣点Xb反射到Xa的另一面的Xr处，而,46,第三章无约束优化问题,单纯形法,计算目标函数值frf（Xr），如果fbfrfg，则反射成功，以Xr代替Xb，并返回（4）。（6）如果frfb，则反射