数学规划法在结构优化设计中应用.pptx

《数学规划法在结构优化设计中应用.pptx》由会员分享，可在线阅读，更多相关《数学规划法在结构优化设计中应用.pptx（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章数学规划法第1页/共73页3.1 数学规划问题的分类及解法I.数学规划问题的一般提法是：寻找一组设计变量变 X=X1,X2,X3,XnT 使得 f(x)min s.t.g i(X)0 i=1,2,m g e(X)=0 e=1,2,n 其中,X-设计变量 f(x)-目标函数 g i(X)和 g e(X)-约束条件第2页/共73页(1)按约束的有无，可分为：按约束的有无，可分为：无约束最优化问题无约束最优化问题有约束最优化问题有约束最优化问题准无约束最优化问题准无约束最优化问题II.数学规划问题的分类第3页/共73页线性规划非线性规划如果目标函数与约束函数都是凸函数，则称为凸规划如果目标函数

2、是二次函数而约束函数是一次函数，则称为二次规划如果设计变量只允许取整数，则称为整数规划如果在目标函数和约束函数中包含具有随机性质的参数则称为随机规划(2)按目标函数和约束函数是否为线性，可分为：第4页/共73页对于线性规划问题，单纯形法十分有效对于线性规划问题，单纯形法十分有效无约束非线性规划问题无约束非线性规划问题不利用梯度的算法：不利用梯度的算法：0.618法、单纯形法、法、单纯形法、Powell法和随机搜法和随机搜索法索法利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛顿法顿法有约束非线性规划问题有约束非线性规划问题转化法：内罚函数

3、法、外罚函数法转化法：内罚函数法、外罚函数法直接法：可行方向法、最佳矢量法、梯度投影法直接法：可行方向法、最佳矢量法、梯度投影法序列近似规划法：序列二次规划方法、序列线性规划方法序列近似规划法：序列二次规划方法、序列线性规划方法III.数学规划问题的求解第5页/共73页IV.无约束优化问题的基本下降算法原问题：min f(x)x=x1,x2,x3,xnT(1)求解其最优化的必要条件：f(x*)=0 (2)但是式(2)是一个非线性方程组，与求解原问题同样困难。在数学规划法中，是用迭代下降的算法找到极小值点。即先假定一个初始设计x(0),然后在第k次迭代(k=0,1,2,),用x(k+1)代替x(

4、k)，要求x(k+1)比x(k)更接近最优解。对于无约束优化问题，也就是要求目标函数有所下降，即 f(x(k+1)f(x(k)第6页/共73页在数学规划中，一般迭代格式可以写成：在数学规划中，一般迭代格式可以写成：x(k+1)=x(k)+P(k),-步长步长(Step length)，正标量，正标量 P(k)-方向向量方向向量(Directional vector)因此目标函数的下降要求可以改写成：因此目标函数的下降要求可以改写成：f(x(k)+P(k)f(x(k)如果函数如果函数f(x)在在x(k)是一次可微的，则对足够下小的是一次可微的，则对足够下小的 有：有：f(x(k)+P(k)-f(

5、x(k)Tf(x(k)P(k)0由于由于 是正标量，所以：是正标量，所以：Tf(x(k)P(k)0这说明搜索方向应该和目标函数负梯度方向夹角小于这说明搜索方向应该和目标函数负梯度方向夹角小于90，这样的方向称之为下山方向。，这样的方向称之为下山方向。第7页/共73页基本的下降算法：1)令k=0,给定初始解x(0)；2)*求搜索方向P(k),使Tf(x(k)P(k)0它意味最优化必要条件已经以足够的精度得到满足。前后两次迭代所得的设计点之间的距离小于指定的小量前后两次迭代目标函数值下降的相对值已经足够小工程结构优化时常采用固定的迭代次数作为停止迭代准则第12页/共73页3.2 一维搜索方法一维搜

6、索方法是数学规划方法的一种基本方法，也是其它优化方法的一种中间手段第13页/共73页i.0.618法0.618法的基本思想法的基本思想是通过取试探点和进是通过取试探点和进行函数值比较，使包行函数值比较，使包含极小点的搜索区间含极小点的搜索区间不断缩短，从而各点不断缩短，从而各点可以看作为极小点的可以看作为极小点的近似。这类方法仅需近似。这类方法仅需计算函数值，用途广计算函数值，用途广泛，尤其适用于非光泛，尤其适用于非光滑函数形式。滑函数形式。第14页/共73页第15页/共73页ii.插值法插值法是一类重要的一维搜索方法。其基本思想插值法是一类重要的一维搜索方法。其基本思想是在搜索区间中不断用低

7、次（通常不超过三次）是在搜索区间中不断用低次（通常不超过三次）多项式来近似目标函数，并逐渐用插值多项式的多项式来近似目标函数，并逐渐用插值多项式的极小点来逼近一维搜索问题。当函数具体比较好极小点来逼近一维搜索问题。当函数具体比较好的解析性质时，插值法比直接方法效果更好。的解析性质时，插值法比直接方法效果更好。第16页/共73页一点二次插值法（牛顿法）第17页/共73页二点二次插值法I第18页/共73页第19页/共73页二点二次插值法II（割线法）第20页/共73页不同搜索方法比较连续性连续性收敛性收敛性适用范围适用范围0.618法法0阶0.618最优点在所选最优点在所选最优点在所选最优点在所选

8、区间中区间中区间中区间中牛顿法牛顿法2阶2靠近最优点靠近最优点靠近最优点靠近最优点二点二次插值法二点二次插值法1阶1.618靠近最优点靠近最优点靠近最优点靠近最优点割线法割线法1阶1.618靠近最优点靠近最优点靠近最优点靠近最优点第21页/共73页3.3 确定搜索方向的算法i.最速下降法前面已经知道，目标函数沿负梯度方向下降最快，因此取负梯度方向为搜索方向，即：P(k)=-f(x(k)x(k+1)x(k)-f(x(k)基本算法：给定初始点x(0)，令k=0；计算f(x(k)若f(x(k)成立，则x*=x(k)，停机，否则转下一步；求P(k)=-f(x(k)，求 (k)=min f(x(k)-f

9、(x(k)；调整设计x(k+1)x(k)-f(x(k)，回第(2)步。第22页/共73页讨论：1)在前后两次迭代过程中，搜索方向是相互正交的，z这是因为在一维搜索中x(k+1)x(k)-(k)f(x(k)，而(k)是由()=0求得，即()=-f(x(k)-(k)f(x(k)f(x(k)=-f(x(k)f(x(k)=0 由此可见，最速下降法走的是“之”字形2)最速下降法是一阶线性收敛，收敛速度较慢。3)最速下降法与变量长度有关，即与变量尺度关系很大。4)最速下降法迭代过程简单，不受初始点位置限制。因此虽然该方法有收敛慢，依赖于变量的尺度等缺点，但这些缺点往往在最优点附近表现得才明显。第23页/共

10、73页第24页/共73页ii.Newton法第25页/共73页从Newton法迭代公式的推导过程可知，对任何二次函数，用Newton法求极小点，只需迭代一次（如果该二次函数有极小点存在的话）基本算法：给定初始点x(0)，令k=0；计算f(x(k)若f(x(k)成立，则x*=x(k)，停机，否则转下一步；求P(k)=-2f(x(k)-1f(x(k)；调整设计x(k+1)x(k)+P(k)，回第(2)步。Newton法为二阶收敛，收敛较快是它最大优点，另外Newton法与变量尺度无关，如果函数本身为二次函数，则只要一次迭代即求得最优解。但Newton法对初始点要求较高，一定要在很靠近最优点附近选取

11、最优点。同时Newton法要求二阶导数矩阵，工作量较大，且要求该矩阵的逆，这就要求2f(x(k)是非奇异的第26页/共73页iii.变尺度法无约束优化的迭代公式为：x(k+1)=x(k)+(k)H(k)P(k)对最速下降法H(k)=I，P(k)取负梯度，(k)用一维搜索对Newton法H(k)=2f(x(k)-1，P(k)取负梯度，(k)=1最速下降法收敛太慢，Newton法收敛最快，但要计算二阶导数并要求求逆，工作量大，有时还会碰到不可克服的困难。因此人们想若H(k)的选取不需要计算二阶导数矩阵和求逆，而又能逼近2f(x(k)-1，那么所确定的算法可能会类似于Newton法收敛很快。基于这种

12、想法，发展了一种拟Newton法。H(k)构造方法不同，有不同的拟Newton法，其中DFP算法就是这类算法中最为著名的。拟Newton法保留了Newton法的快速收敛性，而又不直接求二阶导数，受到了人们欢迎。第27页/共73页H(k)的产生采用迭代法逐步构成先给定H(0)，一般取单位矩阵，则H(1)=H(0)+E(0),H(2)=H(1)+E(1),H(3)=H(2)+E(2),对于DFP算法对于BFGS算法第28页/共73页第29页/共73页3.4 可行方向法I.概述结构优化的一般数学规划表达式：寻找一组设计变量 X=(X1,X2,Xn)T min f(X)X E n s.t.g i(X)

13、0 i=1,m 设计变量的迭代公式-X(+1)=X()+P()从 X()调参至 X(+1),要求设计点可行,并且目标函数还要下降,即满足可用可行性条件:1.满足可用性条件(Usability condition)f(X()T p()0 2.满足可行性条件(Feasibility condition)g i(X()+P()0或者 g i(X()T P()0 第30页/共73页 这两个条件的几何意义是这两个条件的几何意义是:目标函目标函数梯度向量和约束条件梯度向量与数梯度向量和约束条件梯度向量与方向向量之间的夹角均大于方向向量之间的夹角均大于900.根据上述要求根据上述要求,可以有三条路线来可以有

14、三条路线来完成调参完成调参:1.沿等重线沿等重线(面面)侧移；侧移；2.沿约束边界侧移梯度投影沿约束边界侧移梯度投影法法(Gradient projection method)；3.沿可用可行方向沿可用可行方向 P 侧移可侧移可行方向法行方向法(Feasible directional method)。由此构成三种不同形式的可行方向由此构成三种不同形式的可行方向法。法。第31页/共73页II.最佳矢量法 Optimum vector method交替使用两种行进方向:1.当设计点不在约束边界上时,采用最速下降法(Steepest descent method)或最速上升法(Steepest a

15、scent method).P()=-f(X()or P()=f(X()X(+1)=X()-f(X()-最速下降 X(+1)=X()+f(X()-最速上升 其中步长按 采用试凑法.=2 0(在可行域内)=(1/2)(+1)0 第32页/共73页2.从约束边界点开始,沿目标函数等值面(线)内向可行域中侧移,使设计点离开约束边界进入可行域.第33页/共73页两种调参方向交替进行，直到最优点为止。这是一种较早期的方法，迭代次数多，代价大，步长试凑，有太多的随意性。第34页/共73页III.梯度投影法 Gradient projection methodRosen 的梯度投影法适用于目标函数为非线性、

16、约束条件为线性的结构优化设计。一般结构优化设计问题，多取重量为目标函数，它是设计变量的线性函数，约束条件是应力、位移、稳定，均为设计变量的非线性函数。如果引入倒数设计变量，并把约束条件经过显式线性近似处理，则问题正好符合梯度投影法要求。第35页/共73页第36页/共73页1.给定初始设计,进行结构分析;2.在倒数变量空间进行射线调参,将设计点拉到约束边界上(最临界约束边界);射线调参：在优化设计调参过程中，按所有约束的最大约束比，将设计点一次性拉到所对应的优化边界上，这种调参路线正好是过设计点与坐标原点的连线，并与最临界的约束相交。3.在倒数变量空间,将所有有效约束显式线性近似;4.用梯度投影

17、法调参,直到获得最优解为止.i.梯度投影法调参的具体过程第37页/共73页ii.梯度投影法调参(1)侧移向量的计算由推广的K-T 条件知，d 向量沿约束曲面的切线方向。现约束条件变为超平面，d 即在这个超平面内。在倒数变量空间，有 G(Z)+d=-f(Z)G(Z)Td=0由此得：=-G(Z)T G(Z)-1 G(Z)T f(Z)d =-P f(Z)P =I -G(Z)G(Z)T G(Z)-1 G(Z)T其中P为正交投影算子，即目标函数梯度投影到有效约束边界面上去，梯度投影法由此而得名。令调参向量 p()=d=-P f(Z)第38页/共73页Z(+1)=Z()+P()步长可以有两种方法确定步长可

18、以有两种方法确定:(1)沿沿 P()(即即d)向量方向对向量方向对 求一维搜索最小点。求一维搜索最小点。这种方法对无约束条件下比较有效；这种方法对无约束条件下比较有效；(2)利用可行性条件求利用可行性条件求 。按按 P()行进到两条线性约束的交点时行进到两条线性约束的交点时,首先要计算出下首先要计算出下一轮侧移向量一轮侧移向量,并加以判断并加以判断:若若 f(Z(+1)T P(+1)0 可沿可沿 P(+1)进一步调参进一步调参;若若 f(Z(+1)T P(+1)0 则不能继续调参则不能继续调参,要用上一个要用上一个设计点设计点 Z()沿沿 P()进行一维搜索求进行一维搜索求 Z*,或者利用或者

19、利用 f(Z*)T P(+1)=0,其中令其中令 Z*=Z()+(+1)P(+1),代入式中代入式中,即可解得即可解得 (+1).(2)步长的确定第39页/共73页第40页/共73页第41页/共73页第42页/共73页(3)收敛性判别 在最优点处的收敛条件 当 j*0 ,j=1,NC 对所有有效约束|d*|=0 第43页/共73页非线性约束下梯度投影法困难第44页/共73页IV.可行方向法Feasible Directional Methods是由G.Zoutendijk 方法发展而来的一种可行方向方法.f(X()T P()0 g j(x()T P()0,j=1,NC 其中 P()En.若使上

20、述条件更严格一点,令 E1,上式变为 f(X()T P()g j(x()T P(),j=1,NC 0 由此得一个下降的可行方向P().对推离因子(Pushoff factor)j 的讨论:(1)它有效地把设计推离有效约束界面;(2)j =0,P()倾向于有效约束,最终与之相切;(3)j 1,即 j 足够大.P()倾向于目标函数等值线;(4)小的 j 值将使目标函数值迅速减小,但很容易到达同一约束边界,即调参步子不可能大;(5)大的 j 可使调参步子大,但目标函数值减小缓慢;(6)j =1,对大多数问题可获得两方面都有利的效果.这里取 j 为有效约束和约束公差 的平方函数第47页/共73页第48

21、页/共73页上述为典型的线性规划问题,可用单纯型法求解.第49页/共73页步长 的选取:(1)一维寻查(对无约束问题);(2)计算最小截断距离(对带约束的优化问题,此法更合适)。可行方向法所计算的子规划问题,不是求解问题本身,而是做一个子规划,求 P()!第50页/共73页第51页/共73页第52页/共73页第53页/共73页第54页/共73页第55页/共73页第56页/共73页第57页/共73页第58页/共73页3.5 序列无约束优化方法(SUMT)为了充分运用无约束优化方法来解决有约束的优化问题，一种重要的途径是把原有约束问题转化为无约束最优化问题来求解，这里的序列无约束优化方法便是其中的

22、一种方法。第59页/共73页考虑结构优化的数学规划表达式：寻找一组设计变量 X=(X1,X2,Xn)T min f(X)X E n s.t.g i(X)0 i=1,m 其中的约束函数g i(X)可以以一定的方式附加到原问题的目标函数f(X)上，从而得到一系列的无约束优化问题：min F(x)=f(x)+罚项（或障碍项）使它在转化过程中逐步做到满足原有约束条件并最终归结为原问题的同一最优解，这就是方法的实质。罚项的意义：当设计变量不满足约束条件或靠近约束边界时，其数值变得很大，使目标函数F(x)与f(x)相差很远，即受到不满足约束条件的惩罚。第60页/共73页I.内罚函数法设原非线性规划问题为：

23、寻找，使得 min f(X)X E n s.t.g i(X)0 i=1,m 用内罚函数则转化为下述无约束极小化问题内点法的一个显著特点是，设计点要始终落在可行域内，因此而得名内点法。第61页/共73页罚项具有下述性质：(1)当远离约束边界时，较小；(2)当靠近约束边界时，就变得很大，甚至趋于无穷。由下图可知：原规划最优点在x*，罚函数F(x)的最优解在罚函数等值线中心点，当较大时，该中心点离原规划x*较远，随着r的减少，中心点离x*的距离越来越近。因此可以从一个单调下降的系数序列rk中逐个选取系数rk,求得相应目标函数F(x,rk)的极小值及设计最优点x(K)的序列x(1),x(2),x(K)

24、则原规划的最优点x*对应于下述极限第62页/共73页第63页/共73页II.外罚函数法设原非线性规划问题为：寻找，使得 min f(X)X E n s.t.g i(X)0 i=1,m 用外点罚函数则转化为下述无约束极小化问题其中罚项，其含义为在g i(X)和之间挑选大者。随值增大，F(x)值也增大，即偏离f(x)越远，这可看成对于不满足约束条件的一种惩罚。第64页/共73页如图所示，原规划最优解在如图所示，原规划最优解在x*点，而罚函数点，而罚函数F(x,M)的最的最优解在罚函数等值线中心优解在罚函数等值线中心x*处，两者有一定的距离。与处，两者有一定的距离。与内点法不同，内点法不同，x*在不

25、可行域中，但处理问题的方式有相在不可行域中，但处理问题的方式有相同之处。同之处。第65页/共73页因此可以从一个单调上升的系数序列因此可以从一个单调上升的系数序列Mk中中逐个选取系数逐个选取系数Mk,求得相应目标函数求得相应目标函数F(x,Mk)的极小值的极小值及设计最优点及设计最优点x(K)的序列的序列x(1),x(2),x(K)，则原规划的，则原规划的最优点最优点x*对应于下述极限对应于下述极限第66页/共73页III.内点法和外点法的比较内点法外点法1)设计点一定要是可行内点，要控制设计点不能超过约束边界；2)内点法只能处理不等式约束问题；3)内点法求解的极小点序列总位于可行域内，但总不

26、在约束边界上，对某些工程设计问题，可任选一个最优解作为较好的设计；4)内点法尽管F(x,r)和f(x)的偏导数阶数相同，但靠近约束边界处并不连续。1)设计点的运动轨迹位于可行域外，迭代中向可行域靠近，最后趋近最优点；2)可以处理不等式约束，也可以处理等式约束；3)其极小点序列大部分落在不可行域中，只有当某些约束满足时，可能到达约束边界上，但其中间解均是不可行的；4)外点法有连续的一阶偏导数。第67页/共73页3.6 序列二次规划方法考虑等式约束的优化问题 min f(X)X E n s.t.g j(X)=0 j=1,m 定义其拉格朗奇函数为根据根据Kuhn-Tucker定理，其稳定点的非线性方

27、程组为：定理，其稳定点的非线性方程组为：第68页/共73页其解用Newton-Raphson迭代方法求解：其中：其中：上式可以进一步修改为：上式可以进一步修改为：第69页/共73页上式又可以看成是一个下面二次规划的的上式又可以看成是一个下面二次规划的的Kuhn-TuckerKuhn-Tucker条件，即：条件，即：若该规划满足下列条件：若该规划满足下列条件：i i）约束函数）约束函数g g在在X Xk k的的JacobiJacobi矩阵矩阵A(XA(Xk k)行满秩；行满秩；ii ii）矩阵）矩阵 在约束函数在约束函数g g的切空间上是正定的。的切空间上是正定的。那么该规划有唯一的解那么该规划

28、有唯一的解 ，其存在一个新的向量，其存在一个新的向量 使得：使得：那么：那么：第70页/共73页考虑一般形式的约束优化问题：考虑一般形式的约束优化问题：在给定点在给定点 之后，将约束函数线性化，并且对之后，将约束函数线性化，并且对LagrangeLagrange函数函数进行二次多项式近似，得到如下形式的二次规划子问题：进行二次多项式近似，得到如下形式的二次规划子问题：第71页/共73页步骤步骤1 1：初始化：初始化步骤步骤2 2：计算改进方向：计算改进方向步骤步骤3 3：收敛性检验：收敛性检验步骤步骤4 4：确定罚因子：确定罚因子步骤步骤5 5：步长选择：步长选择步骤步骤6 6：改进迭代点并校正：改进迭代点并校正HesseHesse矩阵矩阵算法终止算法终止第72页/共73页感谢您的观看！第73页/共73页