机械优化设计第九章

1、 坐标轮换法坐标轮换法例题分析例题分析一、共轭方向一、共轭方向二、二、PowellPowell基本算法基本算法三、三、 改进的改进的PowellPowell算法算法5 53 3 鲍威尔（鲍威尔（powellpowell) )法法1 1、明确共轭方向的几何及求优意义、明确共轭方向的几何及求优意义2 2、掌握、掌握PowellPowell基本算法的求优原理基本算法的求优原理3 3、注意比较、注意比较PowellPowell基本算法与改进的基本算法与改进的PowellPowell算法算法 的异同点的异同点5 53 3 鲍威尔（鲍威尔（powellpowell) )法法Powell法法直接利用目标函数

2、值来构造直接利用目标函数值来构造“共共轭轭 方向方向“，并以，并以“共轭方向共轭方向“为搜为搜索方索方 向的一种直接搜索法向的一种直接搜索法一、共轭方向一、共轭方向 共轭性与共轭方向 共轭性定义： 设设A A为为n nn n 阶实对称正定矩阵，若在阶实对称正定矩阵，若在R Rn n 中有中有两个非零的两个非零的n n维矢量维矢量02121ASSSST能满足：和则称矢量则称矢量2121SSASS与是共轭的，或称对于与共轭矢量的为)(A 共轭方向 ： 指共轭矢量的方向指共轭矢量的方向 推论： 若非零的若非零的n 维矢量组：维矢量组： 且其中任两个向量关于且其中任两个向量关于n 阶实对称正定矩阵阶实

3、对称正定矩阵 A共轭，即满足：共轭，即满足： 则称矢量组：则称矢量组：，”、“nkRSSS21),2 . 1,;( , 0kjijiASSjTi共轭”关于、“ASSSk21 对于同一对于同一“A”A”而言，而言， 不是唯一的，即：存不是唯一的，即：存在多于一对的向量在多于一对的向量 满足：满足：21SS 和021ASST21SS 和例 如： 3226620 , 3121ATSS、0626 ,18623 , 22 , 60 , 321SS AT463 , 0221SST、0469 , 6463 , 22 , 63 , 021SS AT 若有两个非零的若有两个非零的n维矢量维矢量 ,对于单位矩对于

4、单位矩 阵阵E 共轭，由共轭定义知：共轭，由共轭定义知： ，此时，二者，此时，二者 nRSS21、0)cos(222121SSSSSS02121SSSSTTE为一对为一对正交向量正交向量 正交是共轭的特例，共轭概念是正交概念正交是共轭的特例，共轭概念是正交概念的推广！的推广！共轭方向的几何意义正定二元二次函数：正定二元二次函数：CXBAXXXfTT21)(“实对称正定矩阵”)(,211222211211aaaaaaA2121bbBxxXC常数BAXxfxfXfXXf21)()(梯度的矩阵表达式：在点函数1l2l) 1 (X)2(Xf(x1,x2)=Ci)() 2(XfX1S)() 1 (Xf

5、连接两切连接两切点构成的矢量点构成的矢量：) 1 () 2(2XXS任一矢量方向设：1S共轭对与则：ASS 212S证明：）（）（：式式的梯度：和在点函数（）（）（）（）（*)()() 1 () 2() 2()() 1 ()()(2) 1)212)22) 11)2() 1 (SAXXAXfXfBAXXfBAXXfXXXf）（）（即：正交，必与矢量和又）（）（）（）（40)(30)()()(2111121XfXfSXfXfTTSS）可得：）代入式（将式（）式（）式（）（）（*(*)0)()(:34121XfXfTS021SS AT “对于正定二元二次函数，沿共轭方向一维共轭方向一维搜索搜索就可获

6、得最优点，且只需两步只需两步就可得到 推论： “对于正定n元二次函数，从任意初始点出 发，依次沿着依次沿着n个相互共轭的方向进行一个相互共轭的方向进行一 维搜索维搜索就可获得最优点共轭矢量的性质 设设A A为为n nn n 阶实对称正定矩阵，若非零的阶实对称正定矩阵，若非零的 n n 维矢维矢 量组：量组： 则，这组向量是线性无关的则，这组向量是线性无关的 ，”、“nkRSSS21是共轭的，对于A 在在n维空间中，互相共轭的非零向量的个数维空间中，互相共轭的非零向量的个数维数维数 n 设有：正定设有：正定n元二次函数：元二次函数： ，若有彼此，若有彼此A共轭的共轭的 n 个个 非零矢量非零矢量

7、 则对于求则对于求 的极的极CXBAXXXfTT21)(nTnRxxxXX,21,1210”、“nSSSS)(Xf小点的寻优问题，可从任一点小点的寻优问题，可从任一点 出发，依次沿出发，依次沿 方向做方向做 n 次次一维搜索，即可找到极小点（最多一维搜索，即可找到极小点（最多 n 次，与次，与次序无关）次序无关）)0(X”“iS 优化算法的二次收敛性 如果一个优化算法，能通过有限次迭代（如果一个优化算法，能通过有限次迭代（ 一维搜索），求出正定一维搜索），求出正定n元二次函数的理想极小元二次函数的理想极小 点的话，就称此算法点的话，就称此算法具有具有“二次收敛性二次收敛性 ” ”二、二、Pow

8、ell Powell 基本算法基本算法1、任选一个初始点、任选一个初始点X(0) ,再选二个线性无关的向量再选二个线性无关的向量 （如坐标轴单位向量：（如坐标轴单位向量：e1=1,0T， e2=0,1T ）作）作 为初始搜索方向为初始搜索方向Ox2x1)2(S) 1 (S1e2e)1(1X)1(2X)()2(3XX)0()1(0XX)1(3)2(0XX)2(1X)2(2X2、从 出发，依次沿 做一维 搜索，分别得极小点 。 )()0()1(0XX21ee 、)1(2)1(1XX、第一环：”“)()2(0)1(3)1(2)1(1)1(0XXXXX基本方向组：”“21;ee新生方向：) 1 (S)

9、1(0)1(2)1(XXS再沿 做“n+1”次一维搜索得到极小点)1(S)1(3X 新方向 ：)1(S3、从 出发，依次沿 做一 维搜索，分别得极小点 。 )()1(3)2(0XX)1(2Se 、)1(2)1(1XX、)2(0)2(2)2(XXS再沿 做“n+1”次一维搜索得到极小点)2(S)2(3X 新方向 ：)2(S第二环：”“)2(3)2(2)2(1)2(0XXXX基本方向组：”、“)1(2Se新生方向：)2(S XXASS)2(321: 共轭，故一轮的终点对与由于n维问题维问题“Powell算法算法”的要点：的要点： 在每一环迭代中，总有一个始点（第一环为任 选）和n 个线性独立的搜索

10、方向作为基本方向 组，从始点出发，依次沿基本方向组的n个方 向做一维搜索，得一终点 由始点和终点的连线构成一个新生方向，再沿 新生方向一维搜索，就完成了一环的迭代 二维目标函数完成二维目标函数完成“二环二环”的迭代过程称为一轮的迭代过程称为一轮 用新生方向替换基本方向组的一个方向，替换原 则是：去掉基本方向组第一个方向而将新方向排 在基本方向组的最后。每一环的始点均是上一环 的终点 n 维目标函数完成n环迭代的过程称为“一轮”,对 于n 维的正定二次函数，一轮的终点即为“最优 点” X 对于非二次函数，则仿上转入第二轮迭代（重置 单位坐标矢量系）直到某轮中的某环的始点和 终点之距满足精度要求为

11、止Powell基本算法的缺陷举例基本算法的缺陷举例 ： （三维问题）小点”“三个相应方向上的极（一维搜索）方向组”）”（线性无关的“基本“（初始点）)2()1()0()2()1()0()0(XXXSSSX)()()() !(KKKKSXX根据迭代公式：)2()2()1()1()0()0()0()2()2()1()1()1()2()2()2()3(SSSXSSXSXX) 2() 2() 1 () 1 () 0() 0() 0() 3() 3(SSSXXS新生方向：Ox1x2x3Ox1x2x3)0(S)1(S)2(S)3(S) 1 () 1 (S) 2(2)S)3(S)0(X)1 (X)2(X)3

12、(X)0(X0) 0 () 2() 2() 1 () 1 () 0() 3() 3() 0(0SSXXS ，若：上式表明：在下一环的基本方向组 中，就和 线性相关或接近线性相关（共面）”“)3()2()1(SSS)3(S）（、2)1(SSPowell基本算法的缺陷基本算法的缺陷 基本方向组中的 n个搜索方向有可能出现线性 相关或近似线性相关的情况,一旦出现这种情况 以后的搜索将在维数下降的空间内进行，使算 法收敛不到真正的最优点上，此即“退化现象”三、改进后的三、改进后的PowellPowell算法算法其基本特点1、与基本算法的相同之处： 在第一环中，从初始点 出发，沿 n维空间的 各个坐标方

13、向来进行一维搜索可得点 ，则 由 到 连线方向就构成了“新生方向”)1(0X)1(nX)1(nX)1(0X2、不同之处：在获取了新的方向后，Powell法则要在本环中已取 得的“n+1”个方向中，选取n个线性无关的、且共轭 程度尽可能高的方向作为下一环的“基本方向组”， 以避免“退化现象”出现同时成立和若：23122132113)(21)(2(fffffffffmm则下一环迭代采用这个新方向，并淘汰原来基本方向组中的第 个方向，而将新方向放在新的基本方向组中的最后)(kmS)(,)()1()1()1(2)1(1)()()(1)(1)(2)(1)()()(2)(1kknknkkkknkmkmkk

14、knkmkkSSSSSSSSSSSSSSS，新方向组：原方向组：否则：否则： 仍用原来的n个搜索方向作为下一环的“基本方向组”( )( )( )( )10230( )( )( )11()()(2)()()maxkkkknnkkkmiii nff Xff XffXXf Xf X )(1)()()()()1kmkmkmkmkmkmXXSnmSK（相对应的方向与最大下降量中，相邻两点函数值的向的一维搜索环中沿基本方向组各方 改进后的Powell法只是在第一轮的第一环内采用单 位坐标矢量系 作为基本方向组， 以后每轮开始时，就不必重置单位坐标矢量系， 只按上述产生新基本方向组的方式一环接一环的 继续进

15、行即可，随着逐环迭代的继续各环的基本 方向组将渐趋共轭)2 .1(niei“ Pwell 算法的迭代步骤和程序框图（自学）例：用Powell基本算法求：1 . 0,0 , 060104)(min)0(212212221精度：的最优解。始点：TXRXxxxxxxXf解：1、选初始点、确定首轮第一环的基本方向组10010 , 02) 1 (2) 1 (1)0() 1 (0ee1SSXXT2、沿 进行一维搜索得到极小点1e)1(1X0500100) 1 (1) 1 (1) 1 (1) 1 (1) 1 (0) 1 (1SXX35)(56010)(min)1(1)1(1)1(12)1(1)1(1XfXf

16、：采用一维优化方法求解) 1 (2) 1 (2) 1 (2) 1 (2) 1 (1) 1 (251005SXX3、再由 沿 进行一维搜索得到该方向上 的极小点) 1 (1X2) 1 (2eS) 1 (2X75.14)(5 . 4359)(min)1(2)1(2)1(22)1(2)1(2XfXf：采用一维优化方法求解5 . 45005 . 45)1(0)1(2)1(XXS7253.64725.7154155 .455 .451313)1(3)1()1(3)1(2)1(3)1(3)1(2)1(3)(.)(SXSXX)()(4、沿新方向 一维搜索得到极小点)1(S)1(3X1863.9)()1(3Xf5、再进行首轮第二环的迭代8.6.80367.8)(0026.60028.80367.8)(1277.69075.72087.8)(7326.54725.7