第5章 约束优化方法2(白版)ppt课件.ppt

第五章 有约束优化方法,5-1 引言5-2 随机方向法5-3 复合形法5-4 可行方向法 5-5 惩罚函数法5-6 序列二次规划法,5-1 引言,机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为,上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。 与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行域必是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，探索结果经常与初始点的选择有关。为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。,（1）直接法 直接法包括：网格法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。 （2）间接法 间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、广义乘子法、广义简约梯度法和约束变尺度法等。,根据求解方式的不同，约束优化设计问题可分为:直接解法、间接解法。,直接解法通常适用于仅含不等式约束的问题，思路是在m个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向 d 且以适当的步长 ，进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。,步长,可行搜索方向,可行搜索方向:当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。,间接解法的基本思路是按照一定的原则构造一个包含原目标函数和约束条件的新目标函数，即将原约束优化问题转化成为一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解。,5-2 随机方向法,基本思想：利用计算机产生的随机数所构成的随机方向进行搜索，产生的新点必须在可行域内，即满足直接法的特性。 随机方向法，是约束最优化问题的一种常用的直接求解方法。它和随机梯度法、GaussSeidel法等都属于约束随机法。,其基本原理如图所示，在约束可行域S内选取一个初始点X(0)，在不破坏约束的条件下以合适的步长a。沿X(0)点周围几个不同的方向（以某种形式产生的随机方向）进行若干次探索，并计算各方向上等距离（步长a。）点的函数值，找出其中的最小值f（X(l)）及点X(l)。若f（X(l)）f（X(0)），则继续沿方向（X(l)-X(0)）以适当的步长a向前跨步，得到新点X(1)，若f（X(1)）老f（X(l)），则将新的起点移至X(1) ，重复前面过程。否则应缩短步长a，直至取得约束好点。如此循环下去。当迭代的步长已经很小时，则表明已经逼近约束最优点。达到计算精度要求时，即可结束迭代计算。,图 约束随机方向探索法的基本原理,随机方向探索法的一般迭代计算公式为： X(k+1)=X(k)+aS(k) (k=0,1,2,) 式中a为步长，S(k) 为第k次迭代的随机探索方向。 因此，随机方向探索法的计算过程可归结为：,复合形法是求解约束非线性最优化问题的一种重要的直接方法。它来源于用于求解无约束非线性最优化问题的单纯形法，实际上是单纯形法在约束问题中的发展。 如前所述，在求解无约束问题的单纯形法中，不需计算目标函数的梯度，而是靠选取单纯形的顶点井比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。在用于求解约束问题的复合形法中，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。,5-3 复合形法,基本思想：在可行域中选取K个设计点 （n+1K2n）作为初始复合形的顶点。比较各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的中心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。 反复迭代计算，使复合形不断向最优点移动和收缩，直至收缩到复合形的顶点与形心非常接近，且满足迭代精度要求为止。,令：X(4)= X(0)+(X(0)-X(H),称X(4)为映射点，记为X(R)，为映射系数，通常取=1.3，可根据实际情况进行缩减。,取次好点和好点连线的中点为X(0)。,一般情况下，映射点的函数值比坏点的函数值要小，即F(X(R) F(X(H)。若满足可行域，则用X(R)代替X(H)构成新的复合形。如此反复迭代直到找到最优解。,在可行域内任选三个初始点X(1)、X(2)、X(3)，连接这三点形成一个三角形，此三角形称为初始复合形。计算各个顶点函数值F(X(1)、 F(X(2)、F(X(3)，找出最大值，记为坏点X(H)。最小值，记为最好点X(L)。在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。,在迭代过程中，按映射系数=1.3得到的映射点，不一定满足适用性和可行性，如出现此情况，将映射系数减半， 重新取得X(R)， 使它满足适用性和可行性。,一、初始复合形的构成 复合形的顶点K通常取n+1K2n个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，先产生K个随机点，然后再把非可行点逐一调入可行域内。1、产生K个随机点 xi= ai +i (bi - ai) i=1,2,.,ni为（0，1）区间内产生的均匀分布的随机数，需要n个随机数产生一个点X (1)。同样，产生其它的随机点X (2)、X (3)、X (K)。,2、将非可行点调入可行域 将产生的K个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有q个顶点X (1)、X (2)、X (q)是可行点，其它K-q个为非可行点。对X (q+1)，将其调入可行域的步骤是： （1）计算q个点集的中心X (s)； （2）将第q+1点朝着点X (s)的方向移动，按下式产生新的X (q+1)，即 X(q+1)= X(s)+0.5 (X(q+1)X(s),这个新点X(q+1)实际就是X(s)与原X(q+1)两点连线的中点，如图。若新的X(q+1)点仍为非可行点，按上式再产生X(q+1)，使它更向X(s)靠拢，最终使其成为可行点。,按照这个方法，同样使X (q+2)、X (q+3)、X (K)都变为可行点，这K个点就构成了初始复合形。,二、复合形法的迭代步骤（1）构造初始复合形；（2）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好点X(L)和坏点X(H)。,（3）计算坏点外的其余各顶点的中心点X(0)。,（4）计算映射点X(R),检查X(R)是否在可行域内。若X(R)为非可行点，将映射系数减半后再按上式改变映射点，直到X(R)进入可行域内为止。,（5）构造新的复合形 计算映射点的函数值F(X(R)，并与坏点的函数值F(X(H)比较，可能存在两种情况： 1）映射点优于坏点 F(X(R) F(X(H) 在此情况，用X(R)代替X(H)，构成新的复合形。,再转回本步骤的开始处，直到构成新的复合形。,2）映射点次于坏点 F(X(R) F(X(H) 这种情况由于映射点过远引起的，减半映射系数，若有F(X(R) F(X(H)，这又转化为第一种情况。,(6)判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即,2）各顶点与好点的函数值之差的平方和小于误差限，即,3）各顶点与好点函数值差的绝对值之和小于误差限，即,如果不满足终止迭代条件，则返回步骤2继续进行下一次迭代；否则，可将最后复合形的好点X(L)及其函数值F(X(L)作为最优解输出。,方法特点（1）复合形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。但复合形各顶点的选择和替换，不仅要满足目标函数值下降的要求，还应当满足所有的约束条件。 （2）复合形法适用于仅含不等式约束的问题。,可行方向是求解大型不等式约束优化问题的主要方法之一。 基本思想：这种方法的基本原理是在可行域内选择一个初始点 ，当确定了一个可行方向d和适当的步长后，按式:,5-4 可行方向法,进行迭代计算,迭代点既不超出可行域,又使目标函数的值有所下降。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。,可行方向法的搜索策略？,即：,图1-10,1.可行方向法的搜索策略,第一步迭代都是从可行的初始点 出发，沿点的负梯度 方向，将初始点移动到某一个约束面（只有一个起作用的约束时）上, 或约束面的交集（有几个起作用的约束时）上。,根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索。,1 新点在可行域内的情况,2 新点在可行域外的情况,3 沿线性约束面的搜索,4 沿非线性约束面的搜索,2.产生可行方向的条件,可行方向是指沿该方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。,可行方向应满足两个条件: (1)可行; (2)下降。,1）可行条件,方向的可行条件是指沿该方向作微小移动后，所得到的新点为可行点。,2）下降条件,方向的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。,满足可行和下降条件，即式:,位于约束曲面在点xk的切线和目标函数等值线在点xk的切线所围成的扇形区内，该扇形区称为可行下降方向区。,同时成立的方向称可行方向。,3.可行方向的产生方法,满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向。,（1）优选方向法,由条件：,求一个以搜索方向d为设计变量的约束优化问题,s.t.,各函数均为设计变量dk的线性函数，因此该式为一个（线性）规划问题。,当xk点目标函数的负梯度方向不满足可行条件时，可将 方向投影到约束面（或约束面的交集）上，得到投影向量 dk。,P投影算子，为nXn阶矩阵,G 起作用约束函数的梯度矩阵，nXJ阶矩阵；,（2）梯度投影法,4.步长的确定,确定的步长应使新的迭代点为可行点，且目标函数具有最大的下降量约束一维搜索。,1）取最优步长 从xk点出发，沿dk方向进行一维最优化搜索，取得最优步长，计算新点x的值 。,取到约束边界的最大步长 从xk点出发，沿dk方向进行一维最优化搜索，得到的新点x为不可行点。,改变步长，使新点x返回到约束面上来。使新点x恰好位于约束面上的步长称为最大步长 。,约束一维搜索：,与以前所讲过的一维搜索相比，约束一维搜索的特点在于：确定初始区间时，对产生的每一个探测点都进行可行性判断，如违反了某个或某些约束条件，就必须减少步长因子，以使新的探测点落在最近的一个约束曲面上或约束曲面的一个容许的区间 内。,0,x,1,x,2,x,k,d,k,x,k+1,g,2,(,x,)=0,g,1,(,x,)=0,a*,d,k,a,M,d,k,x,如得到的相邻三个探测点都是可行点，而且函数值呈“大小大”变化，则与前面一维搜索相同，两端点所决定的区间就是初始区间，接着缩小区间直到一维最小点。,如最后得到的探测点落在约束曲面的一个容限 之内，而且函数值比前一点的小，则该点就是一维极小点。,收敛条件,2）设计点xk满足库恩-塔克条件,1）设计点xk及约束允差 满足,例题5-1：用可行方向法求约束优化问题,解: (1)取初始点 ，则取作用约束集: Jk=1,(2)寻找最优方向，即解一个以可行方向为设计变量 的规划问题：,1,d1,d2,用图解法：最优方向：,(3)沿d0方向进行一维搜索,x1在约束边界g3(x)=0上: g3(x1)=0,(4) 第二次迭代，用梯度投影法确定可行方向,迭代点x的目标函数负梯度,不满足方向的可行条件，将 投影到约束边界g3(x)=0上。,投影算子：,由上式可求得：,本次迭代方向,D为沿约束边界g3(x)=0的方向，求最佳步长,求得：,g5(x)=0,6,8,x1,x2,g4(x)=0,g3(x)=0,g2(x)=0,g1(x)=0,x0,d0,（4）收敛判断：,由于,Jk=3， 5,代入KT条件：,基本思想：通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解，这类方法称为序列无约束最小化方法。简称为SUMT法。,5-5 惩罚函数法,将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。,构成一个新的目标函数，称为惩罚函数,从而有,惩罚项必须具有以下极限性质：,求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。按一定的法则改变罚因子r1 和r2的值，求得一序列的无约束最优解，不断地逼近原约束优化问题的最优解。,根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。这种方法是1968年由美国学者AVFiacco和GPMcormick提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。,内点法,这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化问题。,对于只具有不等式约束的优化问题：,转化后的惩罚函数形式为：,或：,rk是惩罚因子，它是一个由大到小且趋近于0的正数列，即:,由于内点法的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。由“障碍项”的函数形式可知，当迭代点靠近某一约束边界时，其值趋近于0，而“障碍项”的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“高墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。,罚因子的作用是：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很小的正值。,例5-2 用内点法求,的约束最优解。,解: 用内点法求解该问题时，首先构造内点惩罚函数:,用解析法求函数的极小值，运用极值条件：,联立求解得：,无约束极值点为,当,1） 初始点x0的选取,使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难.,2） 惩罚因子初值r0的选取,惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同的问题，都要经过多次试算，才能决定一个适当 r0,3) 惩罚因子的缩减系数c的选取,在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为 :,式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。,4) 收敛条件,算法步骤：1）选择可行域内初始点X(0);2）选取初始罚因子r(0)与罚因子降低系数c，并置K0；3）求min(x(K),r(K)解出最优点xK*；4）当K=0转步骤5），否则转步骤6）；5）KK+1，r(K+1)r(K)， xK+10 xK* ，并转步骤3）；6）按终止准则判别，若满足转步骤7），否则转步骤5）；7）输出最优解（X*，F*），停止计算。,2. 外点法,外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。,外点惩罚函数的形式为：,r是惩罚因子 ,外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项的形式可知，当迭代点x 不可行时，惩罚项的值大于0。,例5-3 用外点法求解下列有约束优化问题,解：惩罚函数为：,对上式求偏导，得,无约束目标函数极小化问题的最优解系列为：,当惩罚因子渐增时，由下表可看出收敛情况。,内点法和外点法的简单比较 内点法的特点： （1）始点必须为严格内点 （2）不适于具有等式约束的数学模型 （3）迭代过程中各个点均为可行设计方案 （4）一般收敛较慢 （5）初始罚因子要选择得当 （6）罚因子为递减，递减率c有01,3. 混合法,混合法是用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约束的优化问题。,混合惩罚函数的形式为：,r是惩罚因子 ,混合法具有内点法的特点，迭代过程在可行域之内进行，参数的选择同内点法。,惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方法结合使用。因此该方法也是应用较多的有约束优化方法。,5-6 序列二次规划法,序列二次规划法的基本原理是将原问题转化为一系列二次规划子问题。,对于,相对应的拉格朗日函数为：,在xk点作泰勒展开，取二次近似表达式,令 ,拉格朗日函数的一阶导数为,Hk用变尺度矩阵Bk来代替,将等式约束 函数在xk作泰勒展开，取线性近似式:,构成二次规划子问题,求解上述二次规划子问题，得到的d就是搜索方向 。沿搜索方向进行一维搜索确定步长 ，最终得到原问题的最优解。,对具有不等式约束的非线性规划问题：,构成二次规划子问题为:,求解时，在每次迭代中应对不等式约束进行判断，保留其中的起作用约束，除掉不起作用的约束，将起作用的约束纳入等式约束中。这样，其中不等式约束的子问题和只具有等式约束的子问题保持了一致。,蒙特卡洛优化方法（介绍）,对于约束优化问题，最理想的当然是得到严格意义上的真正全局最优解。然而，要做到这一点往往是不现实的，有的问题（例如非凸的非线性规划问题）至今在理论上还没有一种算法能保证得到全局最优解；有些问题（如凸规划）虽然从理论上讲可以得全局最优解，但是在实际计算中，也只能逼近最优解，且计算量往往很大，在实际工作中，人们往往希望只用较少的计算量就找到有较大概率保证的近似最优解，蒙特卡洛（Monte Carlo）优化方法就是达到这个目的的一种较为有效的方法。,一、原理与基本方法,在对大量的研究对象进行调查分析时，有两种基本方法，普查与随机抽样。 穷举法就是对所有研究对象进行普查，其优点是结论完全可靠，但工作量大，适用于规模较小的问题。而当问题的规模很大时，通常应采用随机抽样，对随机抽取的样本点进行研究，从样本点的性质来推断原问题全面的性质，这样处理的工作量相对较少，可操作性强，只要随机抽样得当，结论的可靠性可以得到保证。,蒙特卡洛优化方法就是根据随机抽样原理，利用计算机语言所提供的随机数函数 对约束优化问题的可行点进行随机抽样，经过对样本点的目标值过滤比较，找出全体样本点中目标值最优的点，并将该点视作原问题的最优解的一个近似点。 随机抽样的可信程度取决于样本点数量的大小。样本点越多，可信程度就越高。因此，能否迅速地取得大量样本点就成了决定蒙特卡洛优化方法是否有效的关键。,二、蒙特卡洛优化方法的基本步骤,（1）预置L为充分大的正数，确定选点个数M；（2）用随机数函数（或子程序）产生可行点X；（3）计算目标函数值F；（4）比较函数值：若FL，转（6）；否则，转（5）；（5）记录当前最优点的信息：L=F，X*=X；（6）若已选完M个可行点，输出X*和L；否则，转（2），寻找下一个可行点。,蒙特卡洛优化方法具有许多显著的优点，除了程序简单，计算量小之外，还有可能获得全局最优点。 蒙特卡洛优化方法除了可以独立寻求最优解外，往往还与其它算法相配合。许多算法对初始点都有不同的要求。一般而言，初始点离极小点越近（即初始点的函数值越好），则算法越有效。这时，可以先使用蒙特卡洛优化方法找到较好的初始点，然后再改用其它优化方法。另外，还有的算法（如可行方向法、内点法）对初始点的可行性有较高的要求，当问题约束条件很复杂时，很难凭人的直觉找到符合要求的点，这时，也可利用蒙特卡洛优化方法迅速找到需要的初始点。,