数学规划法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,构造优化设计,南京航空航天大学,飞机设计技术研究所,第三章数学规划法,3.1,数学规划问题的分类及解法,I.,数学规划问题的一般提法是：,寻找一组设计变量变,X = X,1, X,2, X,3, X,n,T,使得,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),按目标函数和约束函数是否为线性，可分为：,对于线性规划问题，单纯形法十分有效,无约束非线性规划问题,不利用梯度的算法：0.618法、单纯形法、Powell法和随机搜索法,利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛顿法,有约束非线性规划问题,转化法：内罚函数法、外罚函数法,直接法：可行方向法、最正确矢量法、梯度投影法,序列近似规划法：序列二次规划方法、序列线性规划方法,III.,数学规划问题的求解,IV. 无约束优化问题的根本下降算法,原问题：,min,f ( x ),x = x,1, x,2, x,3, x,n,T,(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) = 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(x(k) Tf(x(k) P(k) 0,由于是正标量，所以：,Tf(x(k) P(k) 0,这说明搜索方向应该和目标函数负梯度方向夹角小于90，这样的方向称之为下山方向。,根本的下降算法：,令k=0,给定初始解x(0)；,*求搜索方向P(k),使Tf(x(k) P(k) 0,它意味最优化必要条件已经以足够的精度得到满足。,前后两次迭代所得的设计点之间的距离小于指定的小量,前后两次迭代目标函数值下降的相对值已经足够小,工程构造优化时常采用固定的迭代次数作为停顿迭代准那么,3.2,一维搜索方法,一维搜索方法是数学规划方法的一种根本方法，也是其它优化方法的一种中间手段,i. 0.618,法,0.618法的根本思想是通过取试探点和进展函数值比较，使包含极小点的搜索区间不断缩短，从而各点可以看作为极小点的近似。这类方法仅需计算函数值，用途广泛，尤其适用于非光滑函数形式。,ii.,插值法,插值法是一类重要的一维搜索方法。其根本思想是在搜索区间中不断用低次通常不超过三次多项式来近似目标函数，并逐渐用插值多项式的极小点来逼近一维搜索问题。当函数具体比较好的解析性质时，插值法比直接方法效果更好。,一点二次插值法牛顿法,二点二次插值法,I,二点二次插值法II割线法,不同搜索方法比较,连续性,收敛性,适用范围,0.618,法,0,阶,0.618,最优点在所选区间中,牛顿法,2,阶,2,靠近最优点,二点二次插值法,1,阶,1.618,靠近最优点,割线法,1,阶,1.618,靠近最优点,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(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,由此可见，最速下降法走的是“之字形,最速下降法是一阶线性收敛，收敛速度较慢。,最速下降法与变量长度有关，即与变量尺度关系很大。,最速下降法迭代过程简单，不受初始点位置限制。因此虽然该方法有收敛慢，依赖于变量的尺度等缺点，但这些缺点往往在最优点附近表现得才明显。,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法与变量尺度无关，如果函数本身为二次函数，那么只要一次迭代即求得最优解。但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)的选取不需要计算二阶导数矩阵和求逆，而又能逼近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. 概述,构造优化的一般数学规划表达式：,寻找一组设计变量 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 ( ) 0,这两个条件的几何意义是,:,目标函数梯度向量和约束条件梯度向量与方向向量之间的夹角均大于,90,0,.,根据上述要求,可以有三条路线来完成调参,:,1.,沿等重线,(,面,),侧移；,2.,沿约束边界侧移梯度投影法,( Gradient projection method ),；,3.,沿可用可行方向,P,侧移可行方向法,( Feasible directional method ),。,由此构成三种不同形式的可行方向法。,II. 最正确矢量法 Optimum vector method,交替使用两种行进方向,:,1.,当设计点不在约束边界上时,采用最速下降法,( Steepest descent method ),或最速上升法,( 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. 从约束边界点开场, 沿目标函数等值面(线)内向可行域中侧移, 使设计点离开约束边界进入可行域.,两种调参方向交替进展，直到最优点为止。,这是一种较早期的方法，迭代次数多，代价大，步长试凑，有太多的随意性。,III.,梯度投影法,Gradient projection method,Rosen 的梯度投影法适用于目标函数为非线性、约束条件为线性的构造优化设计。,一般构造优化设计问题，多取重量为目标函数，它是设计变量的线性函数，约束条件是应力、位移、稳定，均为设计变量的非线性函数。,如果引入倒数设计变量，并把约束条件经过显式线性近似处理，那么问题正好符合梯度投影法要求。,1. 给定初始设计, 进展构造分析;,2. 在倒数变量空间进展射线调参, 将设计点拉到约束边界上( 最临界约束边界);,射线调参：在优化设计调参过程中，按所有约束的最大约束比，将设计点一次性拉到所对应的优化边界上，这种调参路线正好是过设计点与坐标原点的连线，并与最临界的约束相交。,3. 在倒数变量空间, 将所有有效约束显式线性近似;,4. 用梯度投影法调参, 直到获得最优解为止.,i.,梯度投影法调参的具体过程,ii.,梯度投影法调参,(1),侧移向量的计算,由推广的,K - T,条件知，,d,向量沿约束曲面的切线方向。现约束条件变为超平面，,d,即在这个超平面内。,在倒数变量空间，有,G(Z) + d = -f(Z),G(Z),T,d = 0,由此得：,= - G(Z),T,G(Z),-1,G(Z),T,f(Z),d = -Pf(Z),P = I - G(Z)G(Z),T,G(Z),-1,G(Z),T,其中,P,为正交投影算子，即目标函数梯度投影到有效约束边界面上去，,梯度投影法由此而得名。,令调参向量,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() 进展一维搜索求 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,其中 P() En. 假设使上述条件更严格一点,令 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 为有效约束和约束公差 的平方函数,上述为典型的线性规划问题,可用单纯型法求解,.,步长 的选取:,(1) 一维寻查 ( 对无约束问题 );,(2) 计算最小截断距离 ( 对带约束的优化问题, 此法更适宜 )。,可行方向法所计算的子规划问题,不是求解问题本身,而是做一个子规划,求,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) 可以以一定的方式附加到原问题的目标函数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 ) X E n,s. t. g i (X) 0 i =1, m,用外点罚函数那么转化为下述无约束极小化问题,其中罚项，其含义为在g i (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. 内点法和外点法的比较,内点法,外点法,设计点一定要是可行内点，要控制设计点不能超过约束边界；,内点法只能处理不等式约束问题；,内点法求解的极小点序列总位于可行域内，但总不在约束边界上，对某些工程设计问题，可任选一个最优解作为较好的设计；,内点法尽管,F(x,r),和,f(x),的偏导数阶数相同，但靠近约束边界处并不连续。,设计点的运动轨迹位于可行域外，迭代中向可行域靠近，最后趋近最优点；,可以处理不等式约束，也可以处理等式约束；,其极小点序列大部分落在不可行域中，只有当某些约束满足时，可能到达约束边界上，但其中间解均是不可行的；,外点法有连续的一阶偏导数。,3.6,序列二次规划方法,考虑等式约束的优化问题,min f( X ) X, E,n,s. t.,g,j,(X) = 0 j =1, m,定义其,拉格朗奇函数为,根据,Kuhn-Tucker,定理，其稳定点的非线性方程组为：,其解用,Newton-Raphson,迭代方法求解：,其中：,上式可以进一步修改为：,上式又可以看成是一个下面二次规划的的,Kuhn-Tucker,条件，即：,假设该规划满足以下条件：,i约束函数g在Xk的Jacobi矩阵A(Xk)行满秩；,ii矩阵 在约束函数g的切空间上是正定的。,那么该规划有唯一的解 ，其存在一个新的向量 使得：,那么：,考虑一般形式的约束优化问题：,在给定点 之后，将约束函数线性化，并且对Lagrange函数进展二次多项式近似，得到如下形式的二次规划子问题：,步骤1：初始化,步骤2：计算改进方向,步骤3：收敛性检验,步骤4：确定罚因子,步骤5：步长选择,步骤6：改进迭代点并校正Hesse矩阵,算法终止,