3 数学规划法.ppt

结构优化设计,南京航空航天大学飞机设计技术研究所,第三章数学规划法,3.1数学规划问题的分类及解法,I.数学规划问题的一般提法是：寻找一组设计变量变X=X1,X2,X3,XnT使得f(x)mins.t.gi(X)0i=1,2,mge(X)=0e=1,2,n其中,X-设计变量f(x)-目标函数gi(X)和ge(X)-约束条件,(1)按约束的有无，可分为：无约束最优化问题有约束最优化问题准无约束最优化问题,II.数学规划问题的分类,线性规划非线性规划如果目标函数与约束函数都是凸函数，则称为凸规划如果目标函数是二次函数而约束函数是一次函数，则称为二次规划如果设计变量只允许取整数，则称为整数规划如果在目标函数和约束函数中包含具有随机性质的参数则称为随机规划,(2)按目标函数和约束函数是否为线性，可分为：,对于线性规划问题，单纯形法十分有效无约束非线性规划问题不利用梯度的算法：0.618法、单纯形法、Powell法和随机搜索法利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛顿法有约束非线性规划问题转化法：内罚函数法、外罚函数法直接法：可行方向法、最佳矢量法、梯度投影法序列近似规划法：序列二次规划方法、序列线性规划方法,III.数学规划问题的求解,IV.无约束优化问题的基本下降算法,原问题：minf(x)x=x1,x2,x3,xnT(1)求解其最优化的必要条件：f(x*)=0(2)但是式(2)是一个非线性方程组，与求解原问题同样困难。在数学规划法中，是用迭代下降的算法找到极小值点。即先假定一个初始设计x(0),然后在第k次迭代(k=0,1,2,),用x(k+1)代替x(k)，要求x(k+1)比x(k)更接近最优解。对于无约束优化问题，也就是要求目标函数有所下降，即f(x(k+1)0则不能继续调参,要用上一个设计点Z()沿P()进行一维搜索求Z*,或者利用f(Z*)TP(+1)=0,其中令Z*=Z()+(+1)P(+1),代入式中,即可解得(+1).,(2)步长的确定,(3)收敛性判别,在最优点处的收敛条件当j*0,j=1,NC对所有有效约束|d*|=0,非线性约束下梯度投影法困难,IV.可行方向法FeasibleDirectionalMethods,是由G.Zoutendijk方法发展而来的一种可行方向方法.f(X()TP()0gj(x()TP()0,j=1,NC其中P()En.若使上述条件更严格一点,令E1,上式变为f(X()TP()gj(x()TP(),j=1,NC0由此得一个下降的可行方向P().对推离因子(Pushofffactor)j的讨论:(1)它有效地把设计推离有效约束界面;(2)j=0,P()倾向于有效约束,最终与之相切;(3)j1,即j足够大.P()倾向于目标函数等值线;(4)小的j值将使目标函数值迅速减小,但很容易到达同一约束边界,即调参步子不可能大;(5)大的j可使调参步子大,但目标函数值减小缓慢;(6)j=1,对大多数问题可获得两方面都有利的效果.这里取j为有效约束和约束公差的平方函数,上述为典型的线性规划问题,可用单纯型法求解.,步长的选取:(1)一维寻查(对无约束问题);(2)计算最小截断距离(对带约束的优化问题,此法更合适)。,可行方向法所计算的子规划问题,不是求解问题本身,而是做一个子规划,求P()!,3.5序列无约束优化方法(SUMT),为了充分运用无约束优化方法来解决有约束的优化问题，一种重要的途径是把原有约束问题转化为无约束最优化问题来求解，这里的序列无约束优化方法便是其中的一种方法。,考虑结构优化的数学规划表达式：寻找一组设计变量X=(X1,X2,Xn)Tminf(X)XEns.t.gi(X)0i=1,m其中的约束函数gi(X)可以以一定的方式附加到原问题的目标函数f(X)上，从而得到一系列的无约束优化问题：minF(x)=f(x)+罚项（或障碍项）使它在转化过程中逐步做到满足原有约束条件并最终归结为原问题的同一最优解，这就是方法的实质。罚项的意义：当设计变量不满足约束条件或靠近约束边界时，其数值变得很大，使目标函数F(x)与f(x)相差很远，即受到不满足约束条件的惩罚。,I.内罚函数法,设原非线性规划问题为：寻找，使得minf(X)XEns.t.gi(X)0i=1,m用内罚函数则转化为下述无约束极小化问题内点法的一个显著特点是，设计点要始终落在可行域内，因此而得名内点法。,罚项具有下述性质：当远离约束边界时，较小；当靠近约束边界时，就变得很大，甚至趋于无穷。由下图可知：原规划最优点在x*，罚函数F(x)的最优解在罚函数等值线中心点，当较大时，该中心点离原规划x*较远，随着r的减少，中心点离x*的距离越来越近。因此可以从一个单调下降的系数序列rk中逐个选取系数rk,求得相应目标函数F(x,rk)的极小值及设计最优点x(K)的序列x(1),x(2),x(K)则原规划的最优点x*对应于下述极限,II.外罚函数法,设原非线性规划问题为：寻找，使得minf(X)XEns.t.gi(X)0i=1,m用外点罚函数则转化为下述无约束极小化问题其中罚项，其含义为在gi(X)和之间挑选大者。随值增大，F(x)值也增大，即偏离f(x)越远，这可看成对于不满足约束条件的一种惩罚。,如图所示，原规划最优解在x*点，而罚函数F(x,M)的最优解在罚函数等值线中心x*处，两者有一定的距离。与内点法不同，x*在不可行域中，但处理问题的方式有相同之处。,因此可以从一个单调上升的系数序列Mk中逐个选取系数Mk,求得相应目标函数F(x,Mk)的极小值及设计最优点x(K)的序列x(1),x(2),x(K)，则原规划的最优点x*对应于下述极限,III.内点法和外点法的比较,3.6序列二次规划方法,考虑等式约束的优化问题minf(X)XEns.t.gj(X)=0j=1,m定义其拉格朗奇函数为,根据Kuhn-Tucker定理，其稳定点的非线性方程组为：,其解用Newton-Raphson迭代方法求解：,其中：,上式可以进一步修改为：,上式又可以看成是一个下面二次规划的的Kuhn-Tucker条件，即：,若该规划满足下列条件：i）约束函数g在Xk的Jacobi矩阵A(Xk)行满秩；ii）矩阵在约束函数g的切空间上是正定的。,那么该规划有唯一的解，其存在一个新的向量使得：,那么：