数学规划法ppt课件

1、.,结构优化设计,南京航空航天大学 飞机设计技术研究所,.,第三章数学规划法,.,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 ) - 约束条件,.,(1) 按约束的有无，可分为： 无约束最优化问题 有约束最优化问题 准无约束最优化问题,II. 数学规划问题的分类,.,线性规划

2、 非线性规划 如果目标函数与约束函数都是凸函数，则称为凸规划 如果目标函数是二次函数而约束函数是一次函数，则称为二次规划 如果设计变量只允许取整数，则称为整数规划 如果在目标函数和约束函数中包含具有随机性质的参数则称为随机规划,(2) 按目标函数和约束函数是否为线性，可分为：,.,对于线性规划问题，单纯形法十分有效 无约束非线性规划问题 不利用梯度的算法：0.618法、单纯形法、Powell法和随机搜索法 利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛顿法 有约束非线性规划问题 转化法：内罚函数法、外罚函数法 直接法：可行方向法、最佳矢量法、梯度投影法 序列近似规划法：序列二次规划方法、

3、序列线性规划方法,III. 数学规划问题的求解,.,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(k)，要求x(k+1)比x(k)更接近最优解。对于无约束优化问题，也就是要求目标函数有所下降，即 f(x(k+1) f(x(k),.,在数学规划中，一般迭代格式可以写成： x (k+1)

4、 = x (k)+ P(k) , - 步长( Step length )，正标量 P(k) - 方向向量( Directional vector ) 因此目标函数的下降要求可以改写成： f(x (k)+ P(k) )0 这说明搜索方向应该和目标函数负梯度方向夹角小于90，这样的方向称之为下山方向。,.,基本的下降算法： 令k=0,给定初始解x(0)； *求搜索方向P(k),使Tf(x(k) P(k) 0； *求搜索步长(k)，要求f(x (k)+ (k)P(k) )=min f(x (k)+ P(k) ) 修改x (k+1) = x(k)+ (k)P(k) 检查收敛原则，不满足时令k=k+1,

5、返回2)；满足则停机。,.,一维搜索确定步长,步长(k)的决定方式常常是使目标函数在x (k+1) 点上达到沿P(k)方向最小，即要求： 因此，如果定义一个一元函数(): ()=f(x (k)+ P(k) ) 决定(k)方法就是估计的极小值，即()至少近似满足： ()=0 这个方程是一个非线性方程，要用到一维搜索方法才能确定步长，因此一维搜索对于提高下降算法非常重要。,.,一维搜索算法,0.618法 Newton法 割线法 抛物线法 三次插值法,.,确定搜索方向的算法,最速下降法 Newton法 共轭梯度法 拟Newton法（变尺度法） Powell法,.,. 停止迭代准则,梯度的长度已经充分

6、小，即 f(x(k) , 0 它意味最优化必要条件已经以足够的精度得到满足。 前后两次迭代所得的设计点之间的距离小于指定的小量 前后两次迭代目标函数值下降的相对值已经足够小 工程结构优化时常采用固定的迭代次数作为停止迭代准则,.,3.2 一维搜索方法,一维搜索方法是数学规划方法的一种基本方法，也是其它优化方法的一种中间手段,.,i. 0.618法,0.618法的基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断缩短，从而各点可以看作为极小点的近似。这类方法仅需计算函数值，用途广泛，尤其适用于非光滑函数形式。,.,.,ii. 插值法,插值法是一类重要的一维搜索方法。其基本思想是在

7、搜索区间中不断用低次（通常不超过三次）多项式来近似目标函数，并逐渐用插值多项式的极小点来逼近一维搜索问题。当函数具体比较好的解析性质时，插值法比直接方法效果更好。,.,一点二次插值法（牛顿法）,.,二点二次插值法I,.,.,二点二次插值法II（割线法）,.,不同搜索方法比较,.,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)，停机，否则转下一步；

8、求P(k) = -f(x(k) ，求 (k)=min f(x (k)- f(x(k)； 调整设计x (k+1) x (k)- f(x(k)，回第(2)步。,.,讨论： 在前后两次迭代过程中，搜索方向是相互正交的，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 由此可见，最速下降法走的是“之”字形 最速下降法是一阶线性收敛，收敛速度较慢。 最速下降法与变量长度有关，即与变量尺度关系很大。 最速下降法迭代过程简单，不受初始点位置限制。因此虽然该方法

9、有收敛慢，依赖于变量的尺度等缺点，但这些缺点往往在最优点附近表现得才明显。,.,.,ii. Newton法,.,从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法与变量尺度无关，如果函数本身为二次函数，则只要一次

10、迭代即求得最优解。但Newton法对初始点要求较高，一定要在很靠近最优点附近选取最优点。同时Newton法要求二阶导数矩阵，工作量较大，且要求该矩阵的逆，这就要求2f(x(k)是非奇异的,.,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)的选取不需要计算二阶导数矩阵和

11、求逆，而又能逼近2f(x(k)-1 ，那么所确定的算法可能会类似于Newton法收敛很快。基于这种想法，发展了一种拟Newton法。 H(k)构造方法不同，有不同的拟Newton法，其中DFP算法就是这类算法中最为著名的。 拟Newton法保留了Newton法的快速收敛性，而又不直接求二阶导数，受到了人们欢迎。,.,H(k)的产生采用迭代法逐步构成 先给定H(0)，一般取单位矩阵，则 H(1)= H(0)+E(0), H(2)= H(1)+E(1), H(3)= H(2)+E(2), 对于DFP算法 对于BFGS算法,.,.,3.4 可行方向法,I. 概述 结构优化的一般数学规划表达式： 寻找

12、一组设计变量 X = ( X1 , X2, , Xn )T min f( X ) X E n s. t. g i (X) 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 ( )

13、 0,.,这两个条件的几何意义是: 目标函数梯度向量和约束条件梯度向量与方向向量之间的夹角均大于900. 根据上述要求, 可以有三条路线来完成调参: 1. 沿等重线(面)侧移； 2. 沿约束边界侧移梯度投影法( Gradient projection method )； 3. 沿可用可行方向 P 侧移可行方向法 ( Feasible directional method )。 由此构成三种不同形式的可行方向法。,.,II. 最佳矢量法 Optimum vector method,交替使用两种行进方向: 1. 当设计点不在约束边界上时, 采用最速下降法( Steepest descent met

14、hod )或最速上升法( Steepest ascent method ) . P ( ) = - f ( X ( ) ) or P ( ) = f ( X ( ) ) X ( +1) = X ( ) - f ( X ( ) ) - 最速下降 X ( +1) = X ( ) + f ( X ( ) ) - 最速上升 其中步长按 采用试凑法. = 2 0 ( 在可行域内) = (1/2) (+1) 0,.,2. 从约束边界点开始, 沿目标函数等值面(线)内向可行域中侧移, 使设计点离开约束边界进入可行域.,.,两种调参方向交替进行，直到最优点为止。 这是一种较早期的方法，迭代次数多，代价大，步长

15、试凑，有太多的随意性。,.,III. 梯度投影法 Gradient projection method,Rosen 的梯度投影法适用于目标函数为非线性、约束条件为线性的结构优化设计。 一般结构优化设计问题，多取重量为目标函数，它是设计变量的线性函数，约束条件是应力、位移、稳定，均为设计变量的非线性函数。 如果引入倒数设计变量，并把约束条件经过显式线性近似处理，则问题正好符合梯度投影法要求。,.,.,1. 给定初始设计, 进行结构分析; 2. 在倒数变量空间进行射线调参, 将设计点拉到约束边界上( 最临界约束边界); 射线调参：在优化设计调参过程中，按所有约束的最大约束比，将设计点一次性拉到所对

16、应的优化边界上，这种调参路线正好是过设计点与坐标原点的连线，并与最临界的约束相交。 3. 在倒数变量空间, 将所有有效约束显式线性近似; 4. 用梯度投影法调参, 直到获得最优解为止.,i. 梯度投影法调参的具体过程,.,ii. 梯度投影法调参,(1) 侧移向量的计算 由推广的K - T 条件知，d 向量沿约束曲面的切线方向。现约束条件变为超平面，d 即在这个超平面内。 在倒数变量空间，有 G(Z) + d = -f(Z) G(Z)Td = 0 由此得： = - G(Z)TG(Z)-1G(Z)Tf(Z) d = -Pf(Z) P = I - G(Z)G(Z)TG(Z)-1G(Z) T 其中P为

17、正交投影算子，即目标函数梯度投影到有效约束边界面上去，梯度投影法由此而得名。 令调参向量 p() = d = -Pf (Z),.,Z ( +1) = Z ( ) + P() 步长可以有两种方法确定: (1) 沿 P()( 即d )向量方向对 求一维搜索最小点。这种方法对无约束条件下比较有效； (2) 利用可行性条件求 。 按P() 行进到两条线性约束的交点时, 首先要计算出下一轮侧移向量, 并加以判断: 若 f ( Z (+1) )T P(+1) 0 可沿 P(+1) 进一步调参; 若 f ( Z (+1) )T P(+1) 0 则不能继续调参, 要用上一个设计点 Z () 沿 P() 进行一

18、维搜索求 Z*, 或者利用 f ( Z* )T P(+1) = 0, 其中令 Z* = Z () + (+1) P(+1) , 代入式中, 即可解得 (+1) .,(2) 步长的确定,.,.,.,.,(3) 收敛性判别,在最优点处的收敛条件 当 j* 0 , j = 1, NC 对所有有效约束 | d* | = 0,.,非线性约束下梯度投影法困难,.,IV. 可行方向法Feasible Directional Methods,是由G. Zoutendijk 方法发展而来的一种可行方向方法. f ( X () )T P() 0 g j ( x () )T P() 0, j = 1, NC 其中

19、P() En. 若使上述条件更严格一点, 令 E1 , 上式变为 f ( X () )T P() g j ( x () )T P() , j = 1, NC 0 取 | P() i | 1, 即 -1 P() i 1, i = 1, n,.,上述不等式的解可借助于求解下述线性子规划 min s. t. f ( X () )T P() + 0 g j ( x () )T P() + j , j = 1, NC | P() i | 1, i = 1, n,.,这里, 0, 若 = 0 迭代停止; 若 0 由此得一个下降的可行方向P() . 对推离因子( Pushoff factor ) j 的讨论

20、: (1) 它有效地把设计推离有效约束界面; (2) j = 0 , P() 倾向于有效约束, 最终与之相切; (3) j 1, 即j 足够大. P() 倾向于目标函数等值线; (4) 小的j 值将使目标函数值迅速减小, 但很容易到达同一约束边界, 即调参步子不可能大; (5) 大的 j 可使调参步子大, 但目标函数值减小缓慢; (6) j = 1, 对大多数问题可获得两方面都有利的效果. 这里取 j 为有效约束和约束公差 的平方函数,.,.,上述为典型的线性规划问题, 可用单纯型法求解.,.,步长 的选取: (1) 一维寻查 ( 对无约束问题 ); (2) 计算最小截断距离 ( 对带约束的优

21、化问题, 此法更合适 )。,可行方向法所计算的子规划问题, 不是求解问题本身, 而是做一个子规划, 求 P () !,.,.,.,.,.,.,.,.,.,3.5 序列无约束优化方法(SUMT),为了充分运用无约束优化方法来解决有约束的优化问题，一种重要的途径是把原有约束问题转化为无约束最优化问题来求解，这里的序列无约束优化方法便是其中的一种方法。,.,考虑结构优化的数学规划表达式： 寻找一组设计变量 X = ( X1 , X2, , Xn )T min f( X ) X E n s. t. g i (X) 0 i =1, m 其中的约束函数g i (X) 可以以一定的方式附加到原问题的目标函数

22、f( X )上，从而得到一系列的无约束优化问题： min F(x)=f(x)+罚项（或障碍项） 使它在转化过程中逐步做到满足原有约束条件并最终归结为原问题的同一最优解，这就是方法的实质。 罚项的意义：当设计变量不满足约束条件或靠近约束边界时，其数值变得很大，使目标函数F(x)与f(x)相差很远，即受到不满足约束条件的惩罚。,.,I. 内罚函数法,设原非线性规划问题为： 寻找，使得 min f( X ) X E n s. t. g i (X) 0 i =1, m 用内罚函数则转化为下述无约束极小化问题 内点法的一个显著特点是，设计点要始终落在可行域内，因此而得名内点法。,.,罚项具有下述性质： 当远离约束边界时，较小； 当靠近约束边界时，就变得很大，甚至趋于无穷。 由下图可知： 原规划最优点在x*，罚函数F(x)的最优解在罚函数等值线中心点，当较大时，该中心点离原规划x*较远，随着r的减少，中心点离x*的距离越来越近。 因此可以从一个单调下降的系数序列rk中 逐个选取系数rk,求得相应目标函数F(x,rk)的极小值及设计最优点x(K)的序列x(1), x(2) , x(K)则原规划的最优点x*对应于下述极限,.,.,II. 外罚函数法,设原非线性规划问题为： 寻找，使得 min f( X )