所有分类约束优化方法.pptx
《所有分类约束优化方法.pptx》由会员分享,可在线阅读,更多相关《所有分类约束优化方法.pptx(113页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、5-15-1约束最优解及其一阶必要条件约束最优解及其一阶必要条件机械优化设计中的问题,大多数属于约束优化设计问题,其数学模型为第1页/共113页实际工程中大部分问题的变量取值都有一定的限制,也就是属于有约束条件的寻优问题。与无约束问题不同,约束问题目标函数的最小值必须是满足约束条件,即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行域是一个凸集,目标函数是凸函数,其约束最优解就是全域最优解。否则,将由于所选择的初始点的不同,而探索到不同的局部最优解上。在这种情况下,探索结果经常与初始点的选择有关。(为了能得到全局最优解,在探索过程中最好能改变初始点,有时甚至要改换几次。)第2页
2、/共113页(1)直接法直接解法通常适用于仅含不等式约束的问题。思路:是在m个不等式约束条件所确定的可行域内,选择一个初始点,然后决定可行搜索方向sk且以适当的步长k,进行搜索,得到一个使目标函数值下降的可行的新点,即完成一次迭代。再以新点为起点,重复上述搜索过程,直至满足收敛条件。根据求解方式的不同,约束优化设计问题可分为根据求解方式的不同,约束优化设计问题可分为:直接解法、间接解法。直接解法、间接解法。第3页/共113页直接法主要包括:随机方向法、复合形法和可行直接法主要包括:随机方向法、复合形法和可行方向法。方向法。其迭代过程中,每一次的新迭代点X(K+1)都要经过可行性和适用性条件的检
3、验。可行性条件是指新迭代点X(K+1)必须在可行域内,即满足适用性条件是指新迭代点X(K+1)的目标函数值较前一点是下降的,即满足第4页/共113页特点:在可行域内进行;若可行域是凸集,目标函数是定义在凸集上的凸函数,则收敛到全局最优点;否则,结果与初始点有关。凸集凸集非凸集非凸集第5页/共113页(2)间接法)间接法目的:目的:将有约束优化问题转化为无约束优化问题将有约束优化问题转化为无约束优化问题方方法法:以以原原目目标标函函数数和和加加权权的的约约束束函函数数共共同同构构成成一一个个新新的的目目标标函函数数(x,r1,r2),成成为为无无约约束束优优化化问问题题。通通过过不不断断调调整整
4、加加权权因因子子,产产生生一一系系列列函函数数的的极极小小点点序序列列xk*(r1k,r2k)k=0,1,2,逐逐渐渐收收敛敛到到原原目目标标函数的约束最优解。函数的约束最优解。间间接接法法主主要要包包括括:内内点点罚罚函函数数法法、外外点点罚罚函函数数法法和和混合罚函数法、扩展内惩罚函数法。混合罚函数法、扩展内惩罚函数法。第6页/共113页 新目标函数:新目标函数:其中:其中:惩罚项:惩罚项:加权因子加权因子(惩罚因子惩罚因子):r1(k),r2(k)无约束优化问题:无约束优化问题:函数的极小点序列函数的极小点序列x(k)*(r1(k),r2(k)k=0,1,2其其收敛必须满足:收敛必须满足
5、:第7页/共113页5-2 5-2 随机方向法随机方向法基本思想:基本思想:随机产生初始点随机产生初始点X(0),随机产生搜索方向,随机产生搜索方向S(k),进行搜索。但要确保:进行搜索。但要确保:新迭代点在可行域中;新迭代点在可行域中;目标函数值的下降性。目标函数值的下降性。随机方向法,是约束最优化问题的一种常用的随机方向法,是约束最优化问题的一种常用的直接求解方法。直接求解方法。第8页/共113页一、随机方向的构成在计算机语言所适用的函数库中,都有一种随机函数,可以产生01之间的均匀分布的随机数,利用产生的随机数构成随机方向。若利用在(0,1)之间产生的随机数,i=1,2,n,构成单位矢量
6、S,方法如下。把随机数,转化为另一区间(-1,1)之间的随机数然后由随机数yi构成以下随机方向由于随机数由于随机数yi在区间(在区间(-1,1)内产生,所构成的随机方向)内产生,所构成的随机方向矢量矢量S一定是在超球面空间里均匀分布且模等于一定是在超球面空间里均匀分布且模等于1的单位矢量。的单位矢量。第9页/共113页如图5-1所示的二维问题。首先选定可行初始点X(0),利用随机函数构成随机方向S(1),按给定的初始步长h=h0沿S(1)方向取得试探点检查点X(1)的适用性和可行性,即检查二、随机方向法随机方向法图图5-1随机方向法随机方向法第10页/共113页直至达到某迭代点不能同时满足适用
7、性和可行性条件时停止,退回到前一点作为该方向搜索中的最终成功点,记作X(1)。进而,将X(1)作为新的始点X(0)X(1),再产生另一随机方向S(2),重复以上过程,得到沿S(2)方向的最终成功点X(2)。如此循环,点列X(1)、X(2)、必将逼近于约束最优点X*。若两者均满足,X作为新的起点,继续按上述迭代式在S(1)方向上取得新点。重复上述步骤,迭代点可沿S(1)方向前进。第11页/共113页(1)若在某个换向转折点处(如图中的X(1)点),沿某搜索方向的试探点目标函数值增大或越出可行域,则弃去该方向,再产生另一随机方向作试探。试探成功就前进,试探失败再重新产生新的随机方向。(2)当在某个
8、转折点处沿当在某个转折点处沿m个(预先限定的次数)个(预先限定的次数)随机方向试探均失败,如图中点随机方向试探均失败,如图中点X(2),则说明以此,则说明以此点为中心,点为中心,h0为半径的圆周上各点都不是适用、为半径的圆周上各点都不是适用、可行的。此时可将初始步长可行的。此时可将初始步长h0缩半后继续试探缩半后继续试探,直直到到f(k+1)f(k),且沿,且沿m个随机方向都试探失败时,则个随机方向都试探失败时,则最后一个成功点(如图中的最后一个成功点(如图中的X(3)点)就是到达预定点)就是到达预定精度要求的约束最优点,迭代即可结束。精度要求的约束最优点,迭代即可结束。第12页/共113页(
9、3)m是预先规定在某转折点处产生随机方向所允许的最大数目。对于性态不好的目标函数或可行域有狭长弯道的问题,m应取较大的值,以提高解题的成功率。约束随机方向法的搜索方向比较灵活,当预定的随机方向限定数m足够大时,无“病态”问题出现,一般都能求出最优点。第13页/共113页入口XX(0),aa0F0F(X)K=1 j0在(-1,1)区间产生随机数yiXX(0)+aSYgu(X)0FF(X)Fm?ae?KK+1X*X F*F出口a0.5aYYYYNNNNN图5-2随机方向法程序框图第14页/共113页三举例例:用约束随机方向法求解 解:人工选取一初始点X0=5,5T,初始点在可行域内。相应的目标函数
10、值为F(X0)=50。第一次迭代1)产生两个伪随机数,求出第一个随机方向。生成两个伪随机数第15页/共113页由此得第一个随机方向为:2)求第一个迭代点第一个迭代点表达式为:式中a为步长。第16页/共113页 将X1的表达式代入目标函数中,进行一维搜索,令目标函数对步长a的一阶导数为0,即可求出沿e1方向的最优步长。第一个迭代点为:第17页/共113页3)检验X1点是否满足约束条件 g(X1)=2*4.2+5.6=1 4 1 2,X1满足约束条件,是可行点。相应的目标函数值为:第二次迭代以X1为初始点,继续使用e1方向直到不满足可行性和适用性条件,再重新生成随机搜索方向e2。(以下过程略)目标
11、函数值下降目标函数值下降第18页/共113页 随机方向法方法评价:优点:1对目标函数无性态要求;2收敛快(当随机方向限定数m 足够大时);3不受维数影响,维数愈高,愈体现优点。缺点:1对于严重非线性函数,只能得近似解;2当m不够大时,解的近似程度大;3对于非凸函数,有可能收敛于局部解。第19页/共113页 复复合合形形法法是是求求解解约约束束非非线线性性最最优优化化问问题题的的一一种种重重要要的的直直接接方方法法。不不需需计计算算目目标标函函数数的的梯梯度度,而而是是靠靠选选取取复复合合形形的的顶顶点点井井比比较较各各顶顶点点处处目目标标函函数数值值的的大大小小,来来寻寻找找下下一一步步的的探
12、探索索方方向向的的。在在用用于于求求解解约约束束问问题题的的复复合合形形法法中中,复复合合形形各各顶顶点点的的选选择择和和替替换换,不不仅仅要要满满足足目目标标函函数值的下降,还应当满足所有的约束条件。数值的下降,还应当满足所有的约束条件。5-3 5-3 5-3 5-3 复合形法复合形法第20页/共113页 比较复合形各顶点目标函数值的大小,去掉目标函数值最大的顶点(称最坏点),以坏点以外其余各点的形心为映射中心,用坏点的映射点替换该点,构成新的复合形顶点。一、复合形法基本思想:在n维空间中,由n+1k2n个点组成的多(边)面体称为复合形。以新的复合形顶点,代替原复合形中的最坏点,组成新的复合
13、形,以不断的迭代,使新复合形逐渐逼近最优点。第21页/共113页例如:设有一约束优化问题的数学模型是该目标函数的等值线和可行域的几何图形如图5-3所示。用复合形法求该问题的约束最优解的过程如下:第22页/共113页第23页/共113页令:X(R)=X(S)+(X(S)-X(H)称X(R)为映射点,为映射系数,通常取=1.3,可根据实际情况进行缩减。取次好点和好点连线的中点为X(S)。一般情况下,映射点的函数值比坏点的函数值要小,即F(X(R)F(X(H)。若满足可行域,则用X(R)代替X(H)构成新的复合形。如此反复迭代直到找到最优解。在可行域内任选三个初始点X(1)、X(2)、X(3),连接
14、这三点形成一个三角形,此三角形称为初始复合形。计算各个顶点函数值F(X(1)、F(X(2)、F(X(3),找出最大值,记为坏点X(H)。最小值,记为最好点X(L)。在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。第24页/共113页二、初始复合形的构成复合形的顶点Kn+1个。对于维数较低的优化问题,由于顶点数目较少,可试凑几个可行点作为复合形的顶点。对于维数较高的问题,采用随机方法,先产生K个随机点,然后再把非可行点逐一调入可行域内。最终使K个随机点都成为可行点而构成初始复合形。复合形的产生可以:(1)人工选择初始复合形(2)随机产生初始复合形第25页/共113页xi=ai+i(bi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 所有 分类 约束 优化 方法
限制150内