约束问题的最优化方法.ppt

《约束问题的最优化方法.ppt》由会员分享，可在线阅读，更多相关《约束问题的最优化方法.ppt（45页珍藏版）》请在三一办公上搜索。

1、根据约束条件类型的不同可以分为三种，其数学模型分别如下：1、不等式约束优化问题（IP型）,无约束优化方法是优化方法中最基本最核心的部分。但是，在工程实际中，优化问题大都是属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。,2、等式约束优化问题（EP型）,3、一般约束优化问题（GP型）,直接解法：随机方向搜索法、复合形法、可行方向法 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法,约束优化问题解法分类：约束优化方法按求解原理的不同可以分为直接法和间接法两类。,二.直接解法：,基本思想：合理选择初始点，确定搜索方向，以迭代公式 x

2、(k+1)=x(k)+(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。,基本要点：选取初始点、确定搜索方向及适当步长。搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。可行性：迭代点必须在约束条件所限制的可行域内，即满足 gu(x)0,u=1,2,p,适用性：当前迭代点的目标函数值较前一点是下降的，即满足 F(xk+1)F(xk),适用范围：只能求解不等式约束优化问题的最优解。,特点：在可行域内进行；若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。,收敛条件：边界点的收敛条件应该符合 K-T 条件；内点的收敛条件为：,目的：将有约

3、束优化问题转化为无约束优化问题来解决。前提：一不能破坏约束问题的约束条件，二使它归结到原约束问题的同一最优解上去。惩罚函数法：通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。惩罚函数法是一种使用很广泛、很有效的间接解法。基本思想：以原目标函数和加权的约束函数共同构成一个新的目标函数(x,r1,r2)，将约束优化问题转化为无约束优化问题。通过不断调整加权因子，产生一系列函数的极小点序列 x(k)*(r1(k),r2(k)k=0,1,2，逐渐收敛到原目标函数的约束最优解。,三.间接解法：,新目标函数：,加权因子（即惩罚因子）：r1,r2,无约束优化问题：,函数的

4、极小点序列 x(k)*(r1(k),r2(k)k=0,1,2 其收敛必须满足：,其中 和 称为加权转化项，并根据它们在惩罚函数中的作用，分别称为障碍项和惩罚项。障碍项：当迭代点在可行域内时，在迭代过程中阻止迭代点越出边界。惩罚项：当迭代点在非可行域或不满足不等式约束条件时，在迭代过程之中迫使迭代点逼近约束边界或等式约束曲面。,分类：根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。这种方法是1968年由美国学者AVFiacco和GPMcormick提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。,适用范围：求解等

5、式约束优化问题和一般约束优化问题。,4.2 内点惩罚函数法（障碍函数法）,一.基本思想：,内点法将新目标函数(x,r)构筑在可行域 D 内，随着惩罚因子 r(k)的不断递减，生成一系列新目标函数(xk,r(k)，在可行域内逐步迭代，产生的极值点 xk*(r(k)序列从可行域内部趋向原目标函数的约束最优点 x*。内点法只能用来求解具有不等式约束的优化问题。,二.惩罚函数的形式：,其中：惩罚（加权）因子 降低系数 c：0 c 1,例：用内点法求,的约束最优解。,解:首先构造内点惩罚函数:,用解析法求函数的极小值，运用极值条件：,联立求解得：,时不满足约束条件,应舍去。,无约束极值点为：,当,内点法

6、的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。,三.步骤：,选取合适的初始点 x(0)，以及 r(0)、c、计算精度 1、2，令 k=0；,2.构造惩罚（新目标）函数；,3.调用无约束优化方法，求新目标函数的最优解 xk*和(xk,r(k)；,4.判断是否收敛：运用终止准则,若均满足，停止迭代，有约束优化问题的最优点为 x*=xk*；若有一个准则不满足，则令 并转入第 3 步，继续计算。,四.几个参数的选择：,2.惩罚因子初始值 r(0)的选择：,1.初始点 x(0)的选择：,要求：在可行域内；不要离约束边界太近。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而

7、变得畸形，使求解无约束优化问题发生困难.,方法：人工估算，需要校核可行性；计算机随机产生，也需校核可行性。,惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。对于不同的问题，都要经过多次试算，才能决定一个适当 r0。,3.降低系数 c 的选择：,在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为:,式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。,4.收敛条件：,五.方法评价：,用于目

8、标函数比较复杂，或在可行域外无定义的场合下：由于优化过程是在可行域内逐步改进设计方案，故在解决工程问题时，只要满足工程要求，即使未达最优解，接近的过程解也是可行的；初始点和序列极值点均需严格满足所有约束条件；不能解决等式约束问题。,六.举例：盖板问题,b,h,ts,tf,设计一个箱形截面的盖板。已知：长度 l0=600cm，宽度 b=60cm，侧板厚度 ts=0.5cm，翼板厚度为 tf(cm)，高度为 h(cm)，承受最大的单位载荷 q=0.01Mpa。,要求：在满足强度、刚度和稳定性等条件下，设计一个最轻结构。,优化方法：选用内点惩罚法，惩罚函数形式为：,调用 Powell 法求序列无约束

9、优化极值，以逐渐逼近原问题的极值点。,设计分析：（略）,数学模型：,4.求解过程分析：,4.3 外点惩罚函数法(衰减函数法）,一.基本思想：,外点法将新目标函数(x,r)构筑在可行域 D 外，随着惩罚因子 r(k)的不断递增，生成一系列新目标函数(xk,r(k)，在可行域外逐步迭代，产生的极值点 xk*(r(k)序列从可行域外部趋向原目标函数的约束最优点 x*。,4,外点法可以用来求解含不等式和等式约束的优化问题。,二.惩罚函数的形式：,外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。,例：用外点法求解下列有约束优化问题,解：惩罚函数为：,对上式求偏导，得

10、,无约束目标函数极小化问题的最优解系列为：,当惩罚因子渐增时，由下表可看出收敛情况。,三.参数选择：,1.r(0)的选择:r(0)过大，会使惩罚函数的等值线变形或偏心，求极值困难。r(0)过小，迭代次数太多。,2.x(0)的选择：基本上可以在可行域内外，任意选择。,3.递增系数r 的选择：通常选择 5 10，可根据具体题目，进行试算调整。,四.步骤：,2.构造惩罚（新目标）函数，调用无约束优化方法，求新目标函数 的最优解 xk*和(xk,r(k)；,3.,4.判断是否收敛：运用终止准则,若均满足，停止迭代，有约束优化问题的最优点为 x*=xk*；若有一个准则不满足，则令 并转入第 2 步，继续

11、计算。,1.选择合适的初始点x(0)，并选择 r(0),a,1,2,0，令 k=0；,五.方法评价：,初始点原则上可任意选择;能解决等式约束问题;由于优化过程是在可行域外进行，故在解决工程问题时，过程解均不可行。,内点法:（1）始点必须为严格内点；（2）不适于具有等式约束的数学模型；（3）迭代过程中各个点均为可行设计方案；（4）一般收敛较慢；（5）初始罚因子要选择得当；（6）罚因子为递减，递减率c有01；,内点法和外点法的对比,4.4 混合惩罚函数法,一.基本思想：,采用内点法和外点法相结合的混合惩罚函数法，用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约束的优化问题

12、。,二.惩罚函数的形式：,一般既包括障碍项，也包括衰减项。,4.5 随机方向搜索法,一.基本思想：,随机产生初始点，随机产生搜索方向 S(k)，进行搜索。但要确保：新迭代点在可行域中；目标函数值的下降性。,随机方向探索法的一般迭代计算公式为：X(k+1)=X(k)+aS(k)(k=0,1,2,)式中a为步长，S(k)为第k次迭代的随机探索方向。因此，随机方向探索法的计算过程可归结为：,三.随机产生初始点：,估计设计变量的上、下限：xil x i xiu，i=1,2,n；在区间0,1中产生伪随机数列 ri，xi(0)=xil+ri(xiu-xil)；判断是否 gu(xi(0)0；若满足，则 x(

13、0)=xi(0)若不满足，则转向。,二.随机数的产生：,1.伪随机数：用数学模型，从计算机（的随机数发生器）中产生的随机数。,随机数的特性 有较好的概率统计特性 抽样的随机性；分布的均匀性；前后数之间的独立性；周期性长。,四.随机产生搜索方向：,x(0),x(m),x(1),x(2),x(j),x(l),H(0),五.步骤：,均是，转判2,X(k+1),六.方法评价：,优点：,对目标函数无性态要求；收敛快（当m足够大时）；不受维数影响，维数愈高，愈体现优点。,缺点：,对于严重非线性函数，只能得近似解；当m不够大时，解的近似程度大；对于非凸函数，有可能收敛于局部解。,4.6 复合形法,复合形法是

14、求解约束非线性最优化问题的一种重要的直接方法。它来源于用于求解无约束非线性最优化问题的单纯形法，实际上是单纯形法在约束问题中的发展。在求解无约束问题的单纯形法中，不需计算目标函数的梯度，而是靠选取单纯形的顶点井比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。在用于求解约束问题的复合形法中，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。,一.单纯形法：,定义：,基本思想：,以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，这样不断地迭代，单纯形逐渐逼近最优点。,以二维空间中的映射法为例：,X(1)=X(H),X(2),X(3

15、),X(S),X(R)=X(4),X(5),X(6),在 n 维空间中，由n+1个点组成的图形称单纯形。,X*,二.复合形法：,定义：在 n 维空间中，由 kn+1 个点组成的多面体称为复合形。,基本思想：,说明：,单纯形是无约束优化方法，而复合形可用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。,在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形就向

16、最优点移动一步，直至逼近最优点。,三.迭代方法：,1.映射法：,例：二维空间中，k=4，复合形是四面体 x(1)x(2)x(3)x(4)，计算得：f(x(1)f(x(2)f(x(3)f(x(4),确定最坏点 x(H)=x(4)，次坏点 x(G)=x(3)，最好点 x(L)=x(1)。x(S)为除x(H)以外，各点的几何中心。,搜索方向：沿 x(H)x(S)的方向。步长因子（映射系数）：1，建议先取1.3。映射迭代公式：x(R)=x(S)+(x(S)x(H)若求得的 x(R)在可行域内，且 f(x(R)f(x(H)，则以x(R)代替x(H)组成新复合形，再进行下以轮迭代。,2.变形法一 扩张法：

17、,变形法二 收缩法：,四.初始复合形的形成：,人工选择初始复合形：对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。随机产生初始复合形：对于维数较高的问题，采用随机方法，先产生K个随机点，然后再把非可行点逐一调入可行域内。,复合形的顶点K通常取n+1K2n个。,、产生K个随机点:,将非可行点调入可行域 判断产生的K个随机点是否在可行域内，重新排列，将可行点依次排在前面，如有q个顶点X(1)、X(2)、X(q)是可行点，其它K-q个为非可行点。对X(q+1)，将其调入可行域的步骤是：（1）计算q个点集的中心X(s)；（2）将第q+1点朝着点X(s)的方向移动，按下式产生

18、新的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个点就构成了初始复合形。,若可行域是非凸集，可能失败，需减小上、下界再进行。,五.步骤：,六.方法评价：,在用直接法解决约束优化问题时，复合形法是一种效果较好的方法。这种方法不需要计算目标函数的导数，也不进行一维搜索，因此对目标函数和约束函数无特殊要求，适用范围广，编程简单

19、。但是收敛速度较慢，不能用于解决具有等式约束的优化问题。,建议：初始取1.3。n+1 k 2n，当 n 5 时，k取值接近 2n；当 n 5 时，k 的取值可小些。,4.7 可行方向法,一.基本思想：,在第 k+1 次迭代时，从 x(k)点出发，寻找一个可行的搜索方向和合适的步长因子，从而得到一个可行、目标函数值下降的新点 x(k+1)，再以此点出发，寻找新点，直至满足收敛条件，得到最优点 x*。,(k)的选择原则：,使新点 x(k+1)在可行域内。,S(k)的选择原则：,必须是可行方向，即必须与所有适时约束的梯度方向成钝角。必须是目标函数值下降的方向，即必须与目标函数的负梯度方向成锐角。,同

20、时满足以上两个条件的方向，称为适用可行方向。,二.搜索策略：,可根据目标函数和约束函数的不同性态，选择不同的搜索策略。,边界反弹法：第一次搜索为负梯度方向，终止于边界。以后各次搜索方向均为适用可行方向，以最大步长从一个边界反弹到另一个边界，直至满足 K-T 条件。,最优步长法：第一次搜索为负梯度方向，终止于边界。第二次搜索沿适用可行方向作一维搜索以最优步长因子求得最优点。反复以上两步，直至得到最优点x*。,贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。若适时约束面是切面，每次搜索到约束面的交集时，移至另一个约束面，直至收敛到最优点。若可行域是凸集，约束面是非线性时，从x(k)点沿切线（面）方向s(k)搜索，会进入非可行域。,