《结构优化设计理论及应用.ppt》由会员分享，可在线阅读，更多相关《结构优化设计理论及应用.ppt（49页珍藏版）》请在金锄头文库上搜索。
1、结构优化设计理论及应用(2),土木水电学院硕士研究生课程,第三章 无约束优化问题,第三章 无约束优化问题,无约束优化问题的极值条件,搜索方向问题是无约束优化方法的关键。,各种无约束优化方法的区别：确定搜索方向的方法不同。,第三章 无约束优化问题,（P1） Min f(X) X En,研究意义： 许多约束问题可转变为无约束问题求解。 通常一个算法总包括一维搜索，而一维搜索实质就是一个无约束问题。 因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,搜索的基本思想是通过逐次循环，来求得问题的最优解或近似最优解。,第三章 无约束优化问题,第三章 无约束优化问题,第三章 无约
2、束优化问题,无约束优化问题的极值条件,搜索方向问题是无约束优化方法的关键。,迭代格式：,定义1：令d En ，d 0 X* D 称d为D在X* 点的一个可行方向，如果存在某个0使得： X* + d D ， （0， ）。,第三章 无约束优化问题,定义2：令d En ，d 0 X* D 称d为f在X* 点的一个下降（改善）方向，如果存在某个0，使得：f( X* + d) f ( X* )， （0， ）。,定义3：称d为可行下降方向，如果它既是可行又是下降的方向。,无约束优化算法中有直接法和解析法两种，直接法以“成功失败”法、Fibonacci法和0.618法为典型代表；解析法以牛顿法、变尺度法及共
3、轭方向法为典型代表。,搜索法的算法步骤： Step0 取初始点X0 ，寻找改善方向d0 Step1 取沿改善方向d0所跨过步长为0 （保持可行改善）求X1= X0+ 0 d0 Step2 对Xk-1,寻找改善方向dk-1 及f(x)，沿改善方向dk-1所下降最多的步长为k-1 ,求 Xk= Xk-1+ k-1 dk-1,第三章 无约束优化问题,第三章 无约束优化问题,下降最多的步长指求k-1 满足 Min f( Xk-1+ k-1 dk-1 ) Step3 对0,如果 Xk- Xk-1 / Xk = 则停算， Xk即为近似最优解。 否则，k +1 k,转Step2,第三章 无约束优化问题,第三
4、章 无约束优化问题,最速下降法（梯度法）,优化设计追求目标函数值最小，若搜索方向取该点的负梯度 方向，使函数值在该点附近的范围内下降最快。,按此规律不断走步，形成以下迭代算法：,以负梯度方向为搜索方向，所以称最速下降法或梯度法。,搜索方向确定为负梯度方向，还需确定步长因子,即求一维搜索的最佳步长，即有,第三章 无约束优化问题,由此可知，在最速下降法中，相邻两个迭代点上的函数 梯度相互垂直。而搜索方向就是负梯度方向，因此相邻 两个搜索方向互相垂直。,第三章 无约束优化问题,第三章 无约束优化问题,一、成功失败法,若问题,令,易见,因此，不失一般性，可考虑F(x)是在整个E1上的无条件极值问题，即
5、,第三章 无约束优化问题,一、成功失败法,所谓成功失败法，就是先从某个初始点x0出发，利用目标函数F(x)的信息，在E1上来回仔细搜索，以期求得 的最优解。若从x0起，以h为步长搜索一次，目标函数值下降，即,则称搜索成功。下次就以x0 h为起点，以2 h为步长进行加大步长搜索，称之为大步前进。若从x0起，以h为步长搜索一次，目标函数值不下降，即,则称搜索失败。下次搜索仍以x0为起点，即退回到起始搜索点，并以h/4为步长，即改变搜索方向和缩短步长，称之为小步后退。 由上述分析可知，每次搜索时，步长都要改变，若0为预先给定的容许误差，则当某搜索步长小于时，搜索停止，得到问题的近似解。,第三章 无约
6、束优化问题,二、Fibonacci（分数）法,考虑问题,若F(x)是定义在a，b上的下单峰函数（即函数在限定区间a，b上有唯一极小点xmin，而且在最优解xmin左侧，即在区间a ，xmin 上F(x)严格下降，在在最优解xmin右侧，即在区间xmin ，b 上F(x)严格上升）。,任取两点x1 a，b， x2 a，b， x1 F(x2)，则保留区间x1， b，保留点为x2 如果不断重复上述过程，缩短搜索区间，则必定能求得最优解xmin。为了能利用前一次所得到结果，取前一次保留点为一个比较点，因此，只需要在保留区间上取一个不同于保留点的新点作为另一个比较点即可。依据上述原则缩小区间，如此下去，
7、最终总会求得xmin满足给定误差的近似解。,假定Fk为Fibonacci数列： F0=F1=1,Fk+2=Fk+1+Fk Fn = 1,1,2,3,5,8,13,. Step0 给定最终不确定区间长度l 0，初始区间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（分数）法,第三章 无约束优化问题,a1,f(a1),b1,f(b1),uk,vk,f(uk),f(vk),u1=a1+ (Fn-2/ Fn) (
8、b1-a1),二、Fibonacci（分数）法,第三章 无约束优化问题,a1,f(a1),b1,f(b1),uk,vk,f(uk),f(vk),v1=a1+ (Fn-1/ Fn) (b1-a1),二、Fibonacci（分数）法,Step1 若 f(uk)f(vk) 转Step2 若 f(uk)f(vk) 转Step3 Step2 令 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,第三章 无约束优化问题,二、F
9、ibonacci（分数）法,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（分数）法,Step4 令k+1k,转Step1 Step5 令 un = un-1 和 vn= un-1+ ， 若 f(un) f(vn) 令an = vn和bn= bn-1， 否则 若 f(un) f(vn) 令an = an-1 和bn= un， 停止，则最优解落在区间a
10、n,bn 中。,第三章 无约束优化问题,二、Fibonacci（分数）法,第三章 无约束优化问题,三、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。,三、0.
11、618（黄金分割）法,第三章 无约束优化问题,Step0 给定容许最终不确定区间长度为l 0，初始区间a1,b1 ,令k=1,进入Step1 Step1 若 bk- akl,则停算,极小点x* ak,bk 否则计算 f 在 uk=ak+0.382(bk-ak) vk=ak+0.618(bk-ak) 的值。,第三章 无约束优化问题,三、0.618（黄金分割）法,a1,f(a1),b1,f(b1),uk,vk,f(uk),f(vk),uk=ak+0.382(bk-ak),第三章 无约束优化问题,三、0.618（黄金分割）法,f(a1),f(b1),f(uk),f(vk),uk=ak+0.618(b
12、k-ak),第三章 无约束优化问题,三、0.618（黄金分割）法,Step2 若f(uk)f(vk),则令 ak+1 = uk和bk+1= bk 否则令 ak+1 = ak和bk+1= vk Step3 令k+1 k,转Step1,一维情况下的牛顿迭代公式,第三章 无约束优化问题,四、牛顿法,多维情况下的牛顿法与一维情况相似，它的基本思路是将高次函数近似简化为一次或二次函数。二次函数的极值点较易求得。,对于多元函数，在,处进行泰勒展开，得,第三章 无约束优化问题,四、牛顿法,称H(xk)为海森矩阵,也可以理解为牛顿法中的搜索方向为,对牛顿法进行改进，提出“阻尼牛顿法”,第三章 无约束优化问题,
13、四、牛顿法,与一维情况相似，牛顿法要求有合适的初始点，如果初始点偏离极值点太远，迭代可能不收敛。,第三章 无约束优化问题,四、牛顿法,第三章 无约束优化问题,五、变尺度（拟牛顿）法,牛顿法收敛速度快，但要求计算二阶导数的逆，计算工作量大，而有些问题目标函数的二阶导数难以求得，因此，牛顿法的应用受到限制。为此，人们对这种算法作了种种改进，其中一种思想是用一个nn阶的对称矩阵A来来逐步逼近牛顿法中的H(x)-1,这种方法称为拟牛顿法(Quasi Newton Method)。由于矩阵A是由递推公式逐步产生的，所以这个方法又称为变尺度法(Variable Metric Method)。不同的递推公式
14、形成不同的变尺度法。如BFGS法、DFP法。,第三章 无约束优化问题,五、变尺度（拟牛顿）法,第三章 无约束优化问题,五、变尺度（拟牛顿）法,六、共轭方向及共轭方向法,第三章 无约束优化问题,共轭方向法。搜索方向是共轭方向。对于二次函数总能通过 n轮(n为设计变量的个数)有限次的迭代达到极小点，且不需计 函数的二阶导数和求逆矩阵，是较为有效的优化方法之一。,共轭方向的概念,共轭方向的概念是在研究二次函数,时引出的。,设S(i)(i=1,2,3,n)为一组线性无关的非零向量。A为nn阶对称正定矩阵，若它们存在如下关系：,则称向量S(i)与向量S(j) 对A共轭（或正交）。当A为单位矩阵时，S(i
15、)与S(j)为通常意义的正交（或几何上互相垂直）。,第三章 无约束优化问题,六、共轭方向及共轭方向法,以二元函数为例说明共轭个方向的意义，设有初始点X(0)，并给定方向S(0)，在方向S(0)上求极小点，即,式中0是未知的，但可以用如下方法求得。,在X(0)处将函数F(x)进行Taylor展开,令,代入上式并简化,由于0的取值是使X(1)为极小，上式一阶导数应为零。即,第三章 无约束优化问题,六、共轭方向及共轭方向法,得,这样可以得到X(1)点，由于X(1)点不可能恰好是函数得极小点，可以再给定方向S(1)，使沿S(1)方向找到的极小点恰好是函数的极小点，令,可仿上得,这样可得X(2)点，也是
16、函数F(x)的极小点，所以函数,在X(2)点处的梯度应为零，即,第三章 无约束优化问题,六、共轭方向及共轭方向法,代入上式，得,即,将上式左边向量与S(0)作内积，得,由0的计算公式，上式第一项为,且1一般不为零，所以,第三章 无约束优化问题,六、共轭方向及共轭方向法,上述公式说明给定的S(0)与S(1)对H共轭，即从X(0)出发，沿S(0) 、 S(1)进行一维搜索得到的X(2)点为函数的极小点。在实际问题中，目标函数在极小点附近呈现为二次函数性状。 可以证明，当目标函数为二次式时，应用共轭方向法，经过n轮迭代，一定可以寻到最小点（这种性质称为二次收敛性）。,七、坐标轮换法,第三章 无约束优化问题,坐标轮换法是每次搜索只允许一个变量变化，其余变量保持 不变，即沿坐标方向轮流进行搜索的寻优方法。,它把多变量的优化问题轮流地转化成单变量的优化问题。,因此又称
