第五章约束优化方法PPT讲稿.ppt

《第五章约束优化方法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第五章约束优化方法PPT讲稿.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章约束优化方法第1页，共68页，编辑于2022年，星期三2概述概述约束优化问题约束优化问题最优解最优解最优值最优值最优点最优点约束最优解和无约束最优解无论是在数学模型上还是几何意义上约束最优解和无约束最优解无论是在数学模型上还是几何意义上均是不同的概念均是不同的概念第2页，共68页，编辑于2022年，星期三3等值线等值线族的中心无约束最优解解无约束最优解解：等值线的共同中心：等值线的共同中心.数学模型数学模型:第3页，共68页，编辑于2022年，星期三4数学模型数学模型:可行域可行域约束最优解约束最优解第4页，共68页，编辑于2022年，星期三5无约束最优点无约束最优点约束最优点约束最优点

2、第5页，共68页，编辑于2022年，星期三6约束优化问题的类型约束优化问题的类型 1.不等式约束优化问题不等式约束优化问题(IP型型)2.等式约束优化问题等式约束优化问题(EP型型)3.一般约束优化问题一般约束优化问题(GP型型)第6页，共68页，编辑于2022年，星期三7约束优化方法分类约束优化方法分类约束优化方法约束优化方法 约束约束约束约束坐标轮换法坐标轮换法坐标轮换法坐标轮换法直接法：直接法：约束随机方向法约束随机方向法约束随机方向法约束随机方向法 复合形法复合形法复合形法复合形法间接法：间接法：惩罚函数法惩罚函数法惩罚函数法惩罚函数法 直接法：直接法：设法使每一次迭代产生的新迭代点限

3、制在可行域内，设法使每一次迭代产生的新迭代点限制在可行域内，且一步一步的降低目标函数值，直至最后获得一个且一步一步的降低目标函数值，直至最后获得一个 可行域内的约束最优解。可行域内的约束最优解。间接法间接法：将约束优化问题通过一定形式的变换，转化为无约将约束优化问题通过一定形式的变换，转化为无约 束优化问题，然后采用约束优化方法进行求解。束优化问题，然后采用约束优化方法进行求解。第7页，共68页，编辑于2022年，星期三85.3.1 约束坐标轮换法约束坐标轮换法基本思想基本思想:与无约束坐标轮换法类似与无约束坐标轮换法类似,依此沿坐标轴依此沿坐标轴 方向寻优方向寻优,逐步逼近最优点。逐步逼近最

4、优点。第8页，共68页，编辑于2022年，星期三9任取一个初始点任取一个初始点 取初始步长取初始步长0 0沿沿e1方向方向检查检查可行性可行性:适用性适用性:检查检查.加速步长加速步长检查检查可行性可行性:适用性适用性:第9页，共68页，编辑于2022年，星期三10沿沿e2方向方向检查检查可行性可行性:适用性适用性:检查检查可行性可行性:适用性适用性:检查检查可行性可行性:适用性适用性:检查检查可行性可行性:适用性适用性:第10页，共68页，编辑于2022年，星期三11沿沿e1方向方向检查检查可行性可行性:适用性适用性:检查检查可行性可行性:适用性适用性:沿沿e2方向方向检查检查可行性可行性:

5、适用性适用性:检查检查.第11页，共68页，编辑于2022年，星期三12沿坐标轴方向找不到合适的点沿坐标轴方向找不到合适的点:缩减初始步长缩减初始步长 0 00.50.50 0 继续迭代继续迭代终止准则终止准则:0 0约束坐标轮换法与无约束坐约束坐标轮换法与无约束坐标轮换法的区别：标轮换法的区别：步长步长 无约束无约束:最优步长最优步长 约约 束束:加速步长加速步长 对每一个迭代点的检查对每一个迭代点的检查 无约束无约束:检查适用性检查适用性 约约 束束:检查适用性和可检查适用性和可行性行性 终止准则终止准则 无约束无约束:点距准则点距准则 约约 束束:步长准则步长准则第12页，共68页，编辑

6、于2022年，星期三13特点特点:约束坐标轮换法具有算法明了、约束坐标轮换法具有算法明了、迭代简单、便于设计者掌握运迭代简单、便于设计者掌握运用等优点。用等优点。但是，它的收敛速度较慢，对但是，它的收敛速度较慢，对于维数较高的优化问题于维数较高的优化问题(例如例如1010维以上维以上)很费机时。很费机时。另外，这种方法在某些情况下还另外，这种方法在某些情况下还会出现会出现“死点死点”的病态，导致的病态，导致输出输出伪最优点伪最优点。避免输出避免输出伪最优点伪最优点的办法的办法:1 1、输入不同的初始点、输入不同的初始点2 2、用不同的不长多次计算、用不同的不长多次计算第13页，共68页，编辑于

7、2022年，星期三14基基本本原原理理：典典型型的的“瞎瞎子子爬爬山山”式式的的数数值值选选代代解解法法。在在可可行行域域内内，任任选选初初始始点点 x x(0)(0)，以以给给定定的的步步长长 a=aa=a0 0 ，沿沿按按某某方方法法产产生生的的随随机机方方向向 S S(1)(1)取取探探索索点点 x x=x x(0)(0)+a a S S(1(1），若若该该点点同同时时符符合合下下降降性性（F(x)F(x F(x)F2 F3 X(H)X(L)坏点坏点 好点好点先求出除坏点外，其余各点先求出除坏点外，其余各点构成的图形的构成的图形的形心点形心点X0再求坏点再求坏点X(H)相对于相对于形心点

8、形心点X0的的映射点映射点 X(R)132X0X(R)第21页，共68页，编辑于2022年，星期三22步骤：步骤：第一步：第一步：初始复合形的构成初始复合形的构成 第二步：第二步：对复合形进行对复合形进行调优迭代计算调优迭代计算 形心点形心点X0 映射点映射点 X(R):反射系数，反射系数，一般开始是取一般开始是取=1.3132检查检查可行性可行性:适用性适用性:新复合形新复合形4点的映射点的映射复合形的收缩复合形的收缩第22页，共68页，编辑于2022年，星期三23二、初始复合形的构成二、初始复合形的构成 v方法一方法一:试凑法试凑法v方法二方法二:随机产生随机产生(1)(1)产生产生K个随

9、机点个随机点随机数随机数 (il，2，n)(2)(2)将非可行点调入可行域将非可行点调入可行域 1234第23页，共68页，编辑于2022年，星期三24终止条件终止条件:第24页，共68页，编辑于2022年，星期三25例例:用复合形法求解下例约束最优化问题，迭代精度取用复合形法求解下例约束最优化问题，迭代精度取 解：取复合形的顶点数解：取复合形的顶点数:(1)(1)获得初始复合形获得初始复合形:本例采用人为给定四个点本例采用人为给定四个点检验各点是否可行：将各点的坐标值代入以上三个约束方程，均满足约束要求，检验各点是否可行：将各点的坐标值代入以上三个约束方程，均满足约束要求，这四个点为可行点，

10、用作初始复合形的四个顶点这四个点为可行点，用作初始复合形的四个顶点 第25页，共68页，编辑于2022年，星期三26(2)(2)迭代计算获得新复合形迭代计算获得新复合形 计算复合形各顶点目标函数值，计算复合形各顶点目标函数值，定出最坏点定出最坏点 最好点最好点 计算除坏点外其余各顶点的中心计算除坏点外其余各顶点的中心 将将 代入诸约束条件均满足，可知代入诸约束条件均满足，可知 在可行城内。在可行城内。取取 ，求坏点，求坏点 的映射点的映射点 在可行域内在可行域内 第26页，共68页，编辑于2022年，星期三27计算计算 并与并与 比较：比较：用用 替换替换 ，亦即替换构成新的复合形：，亦即替换

11、构成新的复合形：比较各点目标函数值，定出最坏点比较各点目标函数值，定出最坏点:最好点最好点:（3 3）检验迭代终止条件）检验迭代终止条件 第27页，共68页，编辑于2022年，星期三28第28页，共68页，编辑于2022年，星期三29复合形法的复合形法的特点特点:对对目目标标函函数数及及约约束束函函数数无无特特殊殊要要求求，适适应应性性强强，计计算算量量一一般般，收收敛敛较较快快，适适用用中中小小型型问问题题。是是现现有有解解不不等等式式约约束束优优化问题的一种重要的直接法。化问题的一种重要的直接法。第29页，共68页，编辑于2022年，星期三305.3.5 惩罚函数法惩罚函数法将约束优化问题

12、通过一定形式的变换，转化为无约束优化问题，将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解然后采用约束优化方法进行求解转化必须满足条件：转化必须满足条件：1、不破坏原约束问题的约束条件，、不破坏原约束问题的约束条件，2、最优解必须归结到原约束问题的最优解上去。、最优解必须归结到原约束问题的最优解上去。约束优化问题的间接法有约束优化问题的间接法有:消元法、拉格朗日乘子法、消元法、拉格朗日乘子法、惩罚函数法等惩罚函数法等.第30页，共68页，编辑于2022年，星期三31min(x，r(k)，m(k)(5.56)xRn式中，式中，(x，r(k)，m(k)为为增广函

13、数，称增广函数，称为惩罚为惩罚函数，函数，简简称称罚罚函数函数 将一般将一般约约束束优优化化问题问题数学模型数学模型minF(x)xRn：gu(x)0，ul，2，phv(x)=0，v=1，2，q转化成为一个如下的转化成为一个如下的无约束无约束优化问题优化问题构造的新目标函数一般形式为构造的新目标函数一般形式为惩罚函数法惩罚函数法惩罚项惩罚项第31页，共68页，编辑于2022年，星期三32按照惩罚函数构成的形式不同，惩罚函数法又分为三种：按照惩罚函数构成的形式不同，惩罚函数法又分为三种：1、内点惩罚函数法、内点惩罚函数法2、外点惩罚函数法、外点惩罚函数法3、混合惩罚函数法、混合惩罚函数法第32页

14、，共68页，编辑于2022年，星期三33一、内点惩罚函数法一、内点惩罚函数法基本思想基本思想：将新目标函数定义于可行域内，序列迭代点在可：将新目标函数定义于可行域内，序列迭代点在可 行域内逐步逼近原目标函数约束边界上的最优点。行域内逐步逼近原目标函数约束边界上的最优点。将将约束约束优化问题：优化问题：minF(x)x :gu(x)0 (u=1 2 m)转化为转化为无约束无约束优化问题优化问题 其中：其中：r(1)r(2)r(3)r(k)0 是一个递减的正值数列：是一个递减的正值数列：r(k)Cr(k-1)，0C1 (k)=0 第33页，共68页，编辑于2022年，星期三34内点惩罚函数法的内点

15、惩罚函数法的思路思路:当当X由可行域内靠近任一约束边界时由可行域内靠近任一约束边界时,惩罚项值趋于无穷大惩罚项值趋于无穷大,所以它就所以它就像围墙一样阻止迭代点越出约束边界像围墙一样阻止迭代点越出约束边界.条件条件1：不破坏原约束问题的约束条件：不破坏原约束问题的约束条件第34页，共68页，编辑于2022年，星期三35min(x,r(k)=minF(x)+r(k)（1/gu(x)）条件条件2：最优解必须归结到原约束问题的最优解上去：最优解必须归结到原约束问题的最优解上去第35页，共68页，编辑于2022年，星期三36解：若用内点法求解此约束最优化问题，由式知惩罚函数为解：若用内点法求解此约束最

16、优化问题，由式知惩罚函数为将函数将函数 对对 求导，得求导，得:令令:解得解得 无约束极小值的点列为无约束极小值的点列为:例例:用内点法求解用内点法求解 的约束最优化问题。的约束最优化问题。无约束极小值点列相应的惩罚函数值为无约束极小值点列相应的惩罚函数值为 第36页，共68页，编辑于2022年，星期三37第37页，共68页，编辑于2022年，星期三38序列极小点都在可行域内序列极小点都在可行域内第38页，共68页，编辑于2022年，星期三39初始点初始点x(0)的确定的确定(1)(1)自定法自定法 :(2)(2)搜索法搜索法 先任取一个设计点先任取一个设计点x(k)；计算计算x(k)点的诸约

17、束函数值点的诸约束函数值gu(x(k)，u1，2，p 若：若：构造：构造：按照该数学模型解出的最优点按照该数学模型解出的最优点x x*，至少比原设计点，至少比原设计点x x(k)(k)多满足多满足一个约束条件一个约束条件 重复数次，直到所有的约束条件都得到满足，最终可取得在可行域重复数次，直到所有的约束条件都得到满足，最终可取得在可行域内部的初始点内部的初始点x x(0)(0)。第39页，共68页，编辑于2022年，星期三40 关于几个参数的选择关于几个参数的选择(1)初始罚因子初始罚因子r(0)的选取的选取一般可取初始罚因子一般可取初始罚因子r(0)150也有建议取：也有建议取：(2)递减系

18、数递减系数C的选择的选择 通常建议取通常建议取C0.10.5 第40页，共68页，编辑于2022年，星期三41内点惩罚函数法的特点内点惩罚函数法的特点:在给定一个可行初始方案后，能求出一系列逐步在给定一个可行初始方案后，能求出一系列逐步得到改进的可行的设计方案。得到改进的可行的设计方案。但但只适用于解不等式约束优化问题只适用于解不等式约束优化问题，且初始点须，且初始点须在可行域内。在可行域内。第41页，共68页，编辑于2022年，星期三42=已知约束优化问题已知约束优化问题:试写出内点罚函数试写出内点罚函数,并选出初始迭代点并选出初始迭代点.内点罚函数内点罚函数:例：例：第42页，共68页，编

19、辑于2022年，星期三43例：例：桁架设计问题：桁架设计问题：minF(x)=1.57xminF(x)=1.57x1 1 x=x x=x1 1 x x2 2 T T 第43页，共68页，编辑于2022年，星期三44设有不等式约束优化问题设有不等式约束优化问题：构造外点法惩罚函数的常见形式如下：构造外点法惩罚函数的常见形式如下：惩罚因子惩罚因子r(k)规定取正。且在优化过程中规定取正。且在优化过程中r(k)取为递增数列取为递增数列 r r(k)(k)=Cr=Cr(k-1)(k-1)，C1 则将保证则将保证 (k)=二、外点惩罚函数法二、外点惩罚函数法基本思想基本思想：将新目标函数定义于可行域外，

20、序列迭代点在可：将新目标函数定义于可行域外，序列迭代点在可 行域外逐步逼近原目标函数约束边界上的最优点。行域外逐步逼近原目标函数约束边界上的最优点。第44页，共68页，编辑于2022年，星期三45式中式中:外点惩罚函数法的外点惩罚函数法的思路思路：可行域内时可行域内时,新目标函数就是原目标函数新目标函数就是原目标函数,当当X X位于可行域外时位于可行域外时,惩惩罚项为正值罚项为正值,新目标函数值增大新目标函数值增大,就构成了对不满足约束条件时就构成了对不满足约束条件时的一种的一种”惩罚惩罚”.且离可行域越远且离可行域越远,惩罚就越严厉惩罚就越严厉.当当r(k）不够大时，罚不够大时，罚函数（新目

21、标函数）的极小值在可行域外，即函数（新目标函数）的极小值在可行域外，即惩罚不够，可加大惩罚不够，可加大r(k），随着，随着r(k）的增大，使新目标函数）的极的增大，使新目标函数）的极小点越来越逼近原目标函数极小点。小点越来越逼近原目标函数极小点。可行域外可行域外可行域内可行域内第45页，共68页，编辑于2022年，星期三46对于解不等式约束优化问题对于解不等式约束优化问题min F(x)xx R1 ：g1(x)=x10用外点法构造惩罚函数，具体用外点法构造惩罚函数，具体构造形式如下：构造形式如下：写成另一种形式写成另一种形式例例第46页，共68页，编辑于2022年，星期三47令令:解得解得 无

22、约束极小值的点列为无约束极小值的点列为:无约束极小值点列相应的惩罚函数值为无约束极小值点列相应的惩罚函数值为 求惩罚函数极小点求惩罚函数极小点:第47页，共68页，编辑于2022年，星期三48由此可由此可见见，当，当惩罚惩罚因子因子为为一一递递增正增正值值数列数列时时，其极，其极值值点点 离约束最优离约束最优点点 愈来愈近，愈来愈近，的差值与的差值与 愈来愈小。当愈来愈小。当 时，时，亦即逼近于真正的约束最优解。无约束极值亦即逼近于真正的约束最优解。无约束极值点列点列 随随 值递增从可行域外向最优点收敛。值递增从可行域外向最优点收敛。第48页，共68页，编辑于2022年，星期三49对几个问题的

23、讨论对几个问题的讨论(1)初初始始点点x(0)的的选选取取:外外点点法法的的初初始始点点x(0)可可以以任任选选，即即在在可可行行域域 与与非非可可行行域选取均可。域选取均可。(2)初始罚因子初始罚因子r(0)和递增系数和递增系数C的选取的选取(1)初初始始罚罚因因子子r(0)选选得得是是否否恰恰当当，对对算算法法的的成成败败和和计计算算速速度度仍仍有有着显著的影响。因此，选取时要谨慎。着显著的影响。因此，选取时要谨慎。(2)递增系数递增系数C的取值，一般影响不太显著，但也不宜取得过大。的取值，一般影响不太显著，但也不宜取得过大。(3)通常取通常取C510。(3)约束容差带约束容差带 用用外外

24、点点法法求求解解时时，由由于于罚罚函函数数的的无无约约束束最最优优点点列列是是从从可可行行域域外外部部向向约约束束最最优优点点逼逼近近的的，所所以以最最终终取取得得的的最最优优点点一一定定是是在在边边界界的的非非可可行行域域一一侧侧。严严格格地地说说，它它是是一一个个非非可可行行点点。这这对对某某些些工工程程问问题题可可能能是是不不允允许许的的。为为了了解解决决这这一一问问题题。可可在在约约束束边边界界的的可可行域一侧加一条容差带，如图行域一侧加一条容差带，如图5.21。(1)这就相当于将约束条件改为这就相当于将约束条件改为(2)gu(x)u0，u=1，2，p(3)(3)式中的式中的u是容差量

25、，一般可取是容差量，一般可取u=103104。第49页，共68页，编辑于2022年，星期三50约束容差带。约束容差带。第50页，共68页，编辑于2022年，星期三51外外点点法法不不但但可可以以解解不不等等式式约约束束优优化化问问题题，而而且且还还可可以以解解等等式式约约束束优优化化问问题题 用外点法求解二维等式约束优化问题：用外点法求解二维等式约束优化问题：按外点法的基本思想，构造惩罚函数按外点法的基本思想，构造惩罚函数第51页，共68页，编辑于2022年，星期三52 外点法的特点外点法的特点外点法既可解不等式约束优化问题，也能解等式约束优化问题，外点法既可解不等式约束优化问题，也能解等式约

26、束优化问题，且其初始点且其初始点x(0)可任选，即在可行域中或非可行域中均可。可任选，即在可行域中或非可行域中均可。其缺点是序列无约束最优点是一系列的非可行点，对于工程设计其缺点是序列无约束最优点是一系列的非可行点，对于工程设计 一般是不可取的。为使最终的迭代点能落入可行域，必须设置约一般是不可取的。为使最终的迭代点能落入可行域，必须设置约 束容差带。束容差带。第52页，共68页，编辑于2022年，星期三53例：已知约束优化问题例：已知约束优化问题:试写出外点罚函数试写出外点罚函数,并选出初始迭代点并选出初始迭代点.外点罚函数外点罚函数:第53页，共68页，编辑于2022年，星期三54三、混合

27、法三、混合法用罚函数法解决有等式约束和不等式约束的一般约束（用罚函数法解决有等式约束和不等式约束的一般约束（GP型）型）优化问题的方法，把它称为混合惩罚函数法，简称混合法。优化问题的方法，把它称为混合惩罚函数法，简称混合法。一般约束优化问题的数学模型一般约束优化问题的数学模型 minf(x)x :gu(x)0 (u=1 2 p)hv(x)=0 (v=1 2 q,qn)第54页，共68页，编辑于2022年，星期三55内点形式的混合型惩罚函数法内点形式的混合型惩罚函数法r(k)-递减递减m(k)-递增递增初始点必须是严格的内点初始点必须是严格的内点为了统一用一个内点法惩罚因子为了统一用一个内点法惩

28、罚因子,上式也可写成上式也可写成:不等式约束部分按内点法形式处理不等式约束部分按内点法形式处理 r(k)-递减递减第55页，共68页，编辑于2022年，星期三56r(k)-递增递增外点形式的混合型惩罚函数法外点形式的混合型惩罚函数法不等式约束部分按外点法形式处理不等式约束部分按外点法形式处理 第56页，共68页，编辑于2022年，星期三57如何判断优化结果的正确性如何判断优化结果的正确性:1、约束优化问题，最优点大多位于边界上。、约束优化问题，最优点大多位于边界上。2、输入不同的初始点多次计算。、输入不同的初始点多次计算。3、用不同的方法解。、用不同的方法解。作业：作业：1、了解各种方法的基本

29、思想和特点、了解各种方法的基本思想和特点2、P130 题题 2 3 7第57页，共68页，编辑于2022年，星期三58机械优化举例：机械优化举例：已知已知给给定定轨轨迹曲迹曲线线，其上个主要点的坐，其上个主要点的坐标见标见下表，并下表，并给给定定（该该机构主要机构主要传递传递运运动动，对动对动力特性要求不高）。力特性要求不高）。试设计试设计一曲柄一曲柄摇摇杆杆机构，使其机构，使其连连杆上点的杆上点的连连杆曲杆曲线线最佳逼近已知曲最佳逼近已知曲线线.第58页，共68页，编辑于2022年，星期三59123476.572970277.441895266.350774147.5287212112.45

30、223777.766826861.158327957.614655200300600900567827.440720811.79956234.87726798.8210749666.1235445 120085.00026891500110.6724041800137.0327072100910111222.954366843.408767463.216836973.7877577160.899848174.145809173.413915153.9461892400270030003300第59页，共68页，编辑于2022年，星期三60第60页，共68页，编辑于2022年，星期三61可以取：

31、可以取：5第61页，共68页，编辑于2022年，星期三621、对对于四杆机构，其各构件的于四杆机构，其各构件的长长度度应满应满足足:目标函数目标函数:设计变量设计变量:约束条件约束条件:2、对对于曲柄于曲柄摇摇杆机构，曲柄存在条件：杆机构，曲柄存在条件：为为各杆各杆长长的极限的极限值值。第62页，共68页，编辑于2022年，星期三63即：即：3、传动性能这个角度出发，要求从动件的最小传动角应大于或等于、传动性能这个角度出发，要求从动件的最小传动角应大于或等于 许用传动角：许用传动角：即：即：第63页，共68页，编辑于2022年，星期三64第64页，共68页，编辑于2022年，星期三65图6.9

32、 双级圆柱齿轮减速机希望在传递一定功率、转速和满足寿命要求下使两级齿轮具有希望在传递一定功率、转速和满足寿命要求下使两级齿轮具有最小的体积，以期减小减速机的整体体积和重量最小的体积，以期减小减速机的整体体积和重量 例例2：第65页，共68页，编辑于2022年，星期三66目标函数目标函数:约束条件约束条件:1、高速级接触强度条件：、高速级接触强度条件：高速级弯曲强度条件：高速级弯曲强度条件：第66页，共68页，编辑于2022年，星期三67 2、低速级接触强度条件：、低速级接触强度条件：低速级弯曲强度条件：低速级弯曲强度条件：合理分配传动比条件：合理分配传动比条件：避免结构干涉条件：避免结构干涉条件：aII-0.5da2S 第67页，共68页，编辑于2022年，星期三68参数选择范围约束条件：参数选择范围约束条件：设计变量：设计变量：整理后得数学模型：整理后得数学模型：P11-164第68页，共68页，编辑于2022年，星期三