优化设计-鲍威尔法

武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512§5.4.3鲍威尔法（Powell法）•两次平行搜索产生一个共轭方向，Powell法也是一种共轭方向法，能在有限步长内极小化一个二次函数，是直接搜索方法中使用效果最佳的一种方法。•对于维数n20的目标函数求最优化问题，此法可获得满意效果。武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512Ⅰ、鲍威尔法基本原理、迭代格式•原始的Powell法是沿着逐步产生的共轭方向进行一维搜索的。•现以二维二次目标函数为例来说明。如下图所示，选定初始点X0(1)，初始方向：S1(1)=e1=[1,0]TS2(1)=e2=[0,1]T武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512模式方向)1(0X)1(1S)1(1X2X)1(2S)1(S)1(2X)2(2X)2(0X)3(0X)2(1X)1(S)2(S1X0武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512初始点方向终点新方向第一循环)1(0X1e2e)1(2X)1(0)1(2)1(XXS第二循环][)1(3)2(0XX2e)1(S)2(2X)2(0)2(2)2(XXS)1(0X)1(1S)1(1X2X)1(2S)1(S)1(2X)2(2X)2(0X)3(0X)2(1X)1(S)2(S1XS(1)与S(2)之间的关系？武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•由图可知点X0(2)、X2(2)是先后两次沿S(1)方向一维搜索的极小点。•由共轭性质知：连接X0(2)，X2(2)构成的矢量S(2)与S(1)对H共轭。)1(0X)1(1S)1(1X2X)1(2S)1(S)1(2X)2(2X)2(0X)3(0X)2(1X)1(S)2(S1X武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•从理论上讲，二维二次正定函数经过这组共轭方向的一维搜索，迭代点已达到函数的极小点X*。•将此结构推广至n维二次正定函数，即依次沿n个（S(1)，S(2)，…，S(n)）共轭方向一维搜索就能达到极小点。武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512Ⅱ、鲍威尔法缺陷•当某一循环方向组中的矢量系出现线性相关的情况（退化、病态）时，搜索过程在降维的空间进行，致使计算不能收敛而失败。为了避免此种情况产生，提出了修正的Powell法。3e2e1e(1)4S(1)0X(1)1X(1)2X(1)3X3e2e1e(1)4S(1)0X(1)1X(1)3X(1)2X新一轮搜索方向新一轮搜索方向和原方向线性相关武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•为了避免鲍威尔法缺陷，提出了修正算法。Ⅲ、修正Powell法2X1X)0(kX)1(kX)1(nkX)(nkX)2(nkX1f2f3f)(nkS12映射点武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•和原始Powell法的主要区别在于：在构成第k+1次循环方向组时，不用淘汰前一循环中的第一个方向S1(k)的办法，而是计算函数值并根据是否满足条件计算：f1=f(Xk(0))f2=f(Xk(n))f3=f(Xk(n+2))2X1X)0(kX)1(kX)1(nkX)(nkX)2(nkX1f2f3f)(nkS12武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•找出前一轮迭代法中函数值下降最多的方向m及下降量△m，即：△m=max｛[f(Xk(i))－f(Xk(i+1))]（i=0,1,…,n-1）｝=f(Xk(m-1))－f(Xk(m))•可以证明：若f3f1(f1-2f2+f3)(f1-f2-△m)20.5△m(f1-f3)2同时成立武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•表明方向Sk(n)与原方向组成线性无关，可以用来替换对象△m所对应的方向Sk(m)。否则仍用原方向组进行第k+1轮搜索。2X1X)0(kX)1(kX)1(nkX)(nkX)2(nkX1f2f3f)(nkS12武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512•例：试用修正Powell法求f(X)=X12+2X22－4X1-2X1X2的最优解。X0=[1,1]T，收敛精度ε=0.001。思考：如采用原始Powell法，如何判别此题具有几次收敛性？修正Powell算法是否具有同样的收敛性？提示：先沿(e1,e2)进行搜索：e1=[1,0]T，e2=[0,1]T武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512110)1(0XX110111)1(1)1(1)1(1)1(1)1(0)1(1SXX0)()1(1)1(1ddf解:f1=f(X0(1）)=－3第一次循环：沿坐标轴方向e1进行一维搜索：•得则有2)1(1代入f(X)令f(X)=X12+2X22－4X1-2X1X2武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼51213)1(1X1013)1(2)1(2)1(2)1(1)1(2SXX5.13)1(2Xf(X1(1）)=－7以X1(1）为起点，沿坐标轴方向e2进行一维搜索：f(X2(1）)=－7.5•检验是否满足终止迭代条件代入f(X)并令得则有0)()1(2)1(2ddf21)1(2f(X)=X12+2X22－4X1-2X1X2武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼51206.2)15.1()13(22)1(0)1(2XX4,max21m7)()1(3xff13ff计算各个方向的函数下降量：△1=f(X0(1))－f(X1(1))=-3－(-7)=4△2=f(X1(1))－f(X2(1))=-7－(-7.5)=0.5映射点：条件：32)(225.1))(2(231221321fffffffmm满足。25115.1322)1(0)1(2)1(xxx武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512)1(S5.02115.13)1(0)1(2)1(xxS)1(S)1(3)1(3)1(3)1()1(3)1(2)1(35.05.1235.025.13Sxx0)()1(3)1(3ddf)1(3521017519)1(3x9.7)()1(3xf故沿新的搜索方向进行沿作一维搜索：代入f(X),令得=故有，武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512)1()2(0xx)1(2,Se1017519)2(0x9.7)()2(0xf,1019519)2(1x1)2(198.7)(fxf故以为新起点，沿（）方向一，沿方向进行一维搜索维搜索，进行第二次循环：)2(1x50972599)2(2x2)2(2996.7)(fxf以为起点沿方向进行搜索，得，2e)1(S武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512122)2(0)2(2288.0101750975191599xx08.01016.0208.0m50109251032)2(0)2(2)2(xxx13)2(964.7)(ffxf检验：继续进行迭代，计算：映射点：)2(2)3(0xx)1(2,Se条件不成立。进行继续迭代时取沿方向一维搜索进行第三循环，并得：50992599)3(1x9992.7)()3(11xff武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512988.19992.3)3(2x99984.7)()3(22xff0577.0)3(0)3(2xx036.2024.4)3(3x99856.7)()3(33xff13ff32ff5012254101751950972599)2(0)2(2)2(xxS,,基本情况同第二循环但更接近极极小点。由第二循环产生的新方向为：武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512)1(S)2(S)2(S24)2(x8)()2(xf8xf)(*24x*由于及为共轭方向，方向进行一维搜索得到即为目标函数的最优解：目标函数是二次函数，若沿武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512§5.5惩罚函数法将约束优化问题转化为无约束优化问题的一种解法。约束优化设计的数学模型一般可表示为：npvxhmuxgtsRxxfvun,,2,10)(,,2,10)(..)(min用类似于拉格朗日法的方法，可将上述问题中的不等式和等式约束函数经过加权转化，并和原目标函数构成新的目标函数，成为惩罚函数（简称罚函数）p1vvk2m1uuk1k2k1xhHrxgGrxfrrx)()()(),,(min)()()()(武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512为了使),,(min)(2)(1kkrrx最后能收敛到约束目标函数f(x)的最优解，其惩罚项必须具有下列性质：：muukkxgGr1)(10)]([limpuvkkxhHr1)(20)]([lim故：0)(),,(lim)()(2)(1kkkkxfrrxp1vvk2m1uuk1k2k1xhHrxgGrxfrrx)()()(),,(min)()()()(惩罚项罚因子武汉科技大学机械自动化学院现代设计方法冶金机械教研室吕勇[e-mail]教一楼512§5.5.1外点法形式：对于一般的约束优化问题pvvkmuukkxhrxgrxfrx12)(12)()()(0),(max)(),()(kr——罚因子，大于零的递增序列说明：（1）当约束条件0)(xgu时，设计点在可行域内，这个函数对原问题的惩罚为0，当0)(xgu时，设计点违反了约束，在目标函数中加入惩罚项2)(xgruk。约束违反的越多，惩罚越重。这样，用惩罚的方法迫使迭代点逐近可行域边界。罚因子，大于零