1、机械优化设计何军良何军良18:031机械优化设计2 0 1 6 年9 月上 海 海 事 大 学何军良0 0:上海海事大学上海海事大学Shanghai Maritime University 1909 2009 2004 1912 1958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目 录CONTENTS一维搜索方法无约束优化方法线性规划 约束优化方法 18:03 上海海事大学 1 9 0 9 2 0 0 9 2 0 0第四章 无约束优化方法 概述01 最速下降法 牛顿型方法 共轭方向与共轭方向法020304 坐标轮换法05 共轭梯度法 变尺度法 鲍威尔方法060708 单形替换法0
2、918:033第四章 无约束优化方法 概述0 1 最速下降法 18:03变尺度法也称拟牛顿法，它是基于牛顿法的思想而又作了重大改进的一类方法。我们所介绍的变尺度法是由 Davidon 于1959年提出又经 Fletcher 和 Powell 加以发展和完善的一种变尺度法，故称为DFP变尺度法。4.7 变尺度法1()kkkkXXf X)()(121kkkkkXfXfXX能否克服各自的缺点，综合发挥其优点？2)阻尼牛顿法1)梯度法*简单，开始时目标函数值下降较快，但越来越慢。*目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。（1）问题提出4变尺度法也称拟牛顿法，它是基于牛顿法的思想而又
3、作了重大改进的18:034.7 变尺度法（2）基本思想n 变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。n 这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。n 尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。例如在用最速下降法求 极小值时,需要进行10次迭代才能达到极小点。221212(,)25f(1)()()1kkkkkxxaG g(1)()()kkkkxxag梯度法:牛顿法:(1)()()kkkkkxxaA g54.7 变尺度法（2）基本思想 变量的尺度变换是放大或缩18:034.7 变尺度法（2
4、）基本思想xxQ进行尺度变换在新的坐标系中，函数f(x)的二次项变为：1122x GxxG xTTTQQ目的：减少二次项的偏心如G是正定，则总存在矩阵Q，使得：GITQQ 对于二次函数:1()2TTfxx Gxb xc64.7 变尺度法（2）基本思想进行尺度变换在新的坐标系中18:034.7 变尺度法（2）基本思想 用矩阵Q-1右乘等式两边，得：用矩阵Q左乘等式两边，得：1GTQQGITQQ所以1GTQQ上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵 来求得。TAQQ74.7 变尺度法（2）基本思想 用矩阵Q-1 右乘等式两边18:03(3)变尺度法的搜索方向:S(k)=-Ak gk，称
5、为拟牛顿方向。(1)Ak为构造的 n n 阶对称矩阵，它随迭代点的位置变化而变化，对梯度起到改变尺度的作用，又称为变尺度矩阵。n 若Ak=I，上式为梯度法的迭代公式n 若Ak=Hk-1，上式为阻尼牛顿法的迭代公式(1)()()kkkkkxxaA g（3）迭代公式4.7 变尺度法(2)当矩阵Ak 不断地迭代而能很好地逼近 时，就可以不再需要计算二阶导数。21()kfx变尺度法的关键在于尺度矩阵Ak的产生。8(3)变尺度法的搜索方向:S(k)=-A k g k 18:03 拟牛顿方向 S(k)=-Ak gk 必须具有下降性、收敛性和计算的简便性。n 下降性要求变尺度矩阵为对阵正定矩阵；n 收敛性要
6、求变尺度矩阵逐渐逼近Hk-1，满足拟牛顿条件；n 简便性希望变尺度矩阵有如下递推形式：Ak+1=Ak+Ak（4）变尺度矩阵的产生4.7 变尺度法9 拟牛顿方向 S(k)=-A k g k 必须具有下18:03下降性：要求S(k)与-gk之间的夹角小于90o，即：-S(k)T gk0将拟牛顿方向带入上式，得：-S(k)T gk=Ak gkTgk=gkTAk gk 0所以只要 Ak 为对阵正定矩阵，S(k)就是下降方向。（4）变尺度矩阵的产生4.7 变尺度法10下降性：要求S(k)与-g k 之间的夹角小于9 0 o，即：18:03变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序列选取
7、初始矩阵A0，并以梯度方向快速收敛，通常取单位矩阵E 作为初始矩阵，即A0=E。而后的矩阵均是在前一构造矩阵的基础上校正得到，令推广到一般的k+1次构造矩阵 Ak，k=1，2，A1=A0+A0Ak+1=Ak+Ak矩阵序列的矩阵序列的基本迭代式基本迭代式 Ak 称为校正矩阵（4）变尺度矩阵的产生4.7 变尺度法简便性：11变尺度矩阵是随迭代过程的推进而逐次改变的，因而它是一种矩阵序18:03n 构造矩阵Ak+1应该满足一个重要条件拟牛顿条件n变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，主要目的之一就是为了避免计算二阶偏导数和逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向，因此，
8、拟牛顿条件是关于海赛矩阵和梯度之间的关系。（5）拟牛顿条件4.7 变尺度法12构造矩阵A k+1 应该满足一个重要条件拟牛顿条件变尺度法采用18:03设F(x)为一般形式 n 阶的目标函数，并具有连续的一、二阶偏导。在点 x(k)处的二次泰勒近似展开xHxxgxFxFkTTkk21)()()(该近似二次函数的梯度为：xHgxFkk)(式中 ，若令 ，则有)(kxxx)1(kxx)()()1(1kkkkkxxHgg)(11)()1(kkkkkggHxx（5）拟牛顿条件4.7 变尺度法13设F(x)为一般形式 n 阶的目标函数，并具有连续的一、二18:03上式中，x(k+1)x(k)称之为位移矢量
9、，并简化书写:(1)()kkkxx 而gk+1-gk 是前后迭代点的梯度矢量差，简化书写：kkkggy1由以上三式得：1kkkHy海赛矩阵与梯度间的关系式（5）拟牛顿条件4.7 变尺度法14上式中，x(k+1)x(k)称之为位移矢量，并简化书写18:03按照变尺度法产生构造矩阵的递推思想，期望能够借助前一次迭代的某些结果来计算下一个构造矩阵，因此可以根据上式，用第 k+1 次构造矩阵 Ak+1 近似代替 Hk-1，则kkkyA1上式即产生构造矩阵 Ak+1 应满足的一个重要条件，通常称为拟牛顿条件或拟牛顿方程（5）拟牛顿条件4.7 变尺度法15按照变尺度法产生构造矩阵的递推思想，期望能够借助前
10、一次迭代的18:03（6）变尺度矩阵的构造4.7 变尺度法拟牛顿条件 可写成 kkkkAAy或 (1)kkkkkA yA y DFP算法中的校正矩阵 Ak取为下列形式：(2)TTkkkkkkkAu uv v待定系数保证 Ak对称kkkyA116（6）变尺度矩阵的构造4.7 变尺度法拟牛顿条件 18:03（6）变尺度矩阵的构造4.7 变尺度法将(2)代入(1):TTkkkkkkkkkkku u yv v yA y两边对比得:,Tkkkkku u yTkkkkkkv v yA y 取,kkkkkuvA y1kTkky1kTkkky A y 则：TTkkkkkkkTTkkkkkA y y AAyy
11、A y 回代到(2)得:DFP变尺度法的迭代式为：11kkkkkTTkkkkkkkkTTkkkkkXXAfXA y y AAAyy A y 17（6）变尺度矩阵的构造4.7 变尺度法将(2)代入(1)18:03由上式可以看出，构造矩阵Ak+1的确定取决于第 k 次迭代中的下列信息：上次的构造矩阵：Ak迭代点的位移矢量：迭代点的梯度增量：)()1(kkkxxkkkggy1因此，不必作二阶导数矩阵及其求逆的计算（6）变尺度矩阵的构造4.7 变尺度法18由上式可以看出，构造矩阵A k+1 的确定取决于第 k 次迭代中18:03n DFP算法的收敛速度介于梯度法和牛顿法之间。n DFP法具有二次收敛性
12、(搜索方向的共轭性)。对于二次函数 F(x)，DFP法所构成的搜索方向序列S(0),S(1),S(2),为一组关于海赛矩阵H共轭的矢量，即DFP法属于共轭方向法，具有二次收敛性。在任何情况下，这种方法对于二次目标函数都将在n步内搜索到目标函数的最优点，而且最后的构造矩阵 An 必等于海赛矩阵H。（7）DFP变尺度算法的特点4.7 变尺度法19 D F P 算法的收敛速度介于梯度法和牛顿法之间。D F P 法具有18:03（7）DFP变尺度算法的特点4.7 变尺度法n 关于算法的稳定性，数值计算稳定性较差。1.算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。2.构造矩阵正定性从理论上肯定
13、了DFP法的稳定性，但实际上，由于每次迭代的一维搜索只能具有一定的精确度，且存在机器运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏；3.为了提高实际计算中的稳定性，一方面应对一维搜索提出较高的精度要求，另一方面，当发生破坏正定性时，将构造矩阵重置为单位矩阵E重新开始，通常采用的简单办法是在 n 次迭代后重置单位矩阵20（7）D F P 变尺度算法的特点4.7 变尺度法关于算法的稳18:031.任取初始点 x(0)给出迭代精度.计算初始点精度 及其模 。若 转步骤，否则进行下一步2.置k0，取 AkE3.计算迭代方向 ，沿S(k)方向做一维搜索求优化步长 a(k)，使)()0(0 xFg0g
14、0gkkkgAS)()(min)()()()()()(kkkkkSxFSxF确定下一个迭代点)()()()1(kkkkSxx（8）DFP变尺度算法的计算步骤4.7 变尺度法21任取初始点 x(0)给出迭代精度.计算初始点精度 18:034.计算x(k+1)的梯度gk+1及其模 ，若 则转步骤，否则转下一步1kg1kg5.计算位移矢量 和梯度矢量)()1(kkkxxkkkggy1kky按DFP公式计算构造矩阵kkTkTkTkkkkTkTkkkkyAyAyyAyAA16.置kk+1。若kn(n为优化问题的维数)返回步骤，否则返回步骤7.输出最优解（x*，F*），终止计算（8）DFP变尺度算法的计算
15、步骤4.7 变尺度法22计算x(k+1)的梯度g k+1 及其模 18:03DFP算法流程图,n,x)0(输入：）（计算：）（）（00)0(xFgIA0k)()()()1()()()()()()()()(minkkkkkkkkkkkSxxSxFgAS)()1()1(kkxFgk=n？)1()1()1()()1()()()()1()()1(kkkkkTkTkTTkkkkgASNMAAyAyyANyMggyxx)1()0(kxx入口入口出口出口*)(*)1(xFFxxk?)1(kg+-+-23D F P 算法流程图k=n？入口出口+-+-2 318:03解：1）取初始点 ，为了按DFP法构造第一次
16、搜寻方向d0，需计算初始点处的梯度221212112(,)242f x xxxxx x01 1Tx0120212244()422xxxxfxx取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为 0001044()0122dAxf 例:用DFP算法求下列问题的极值：24（9）DFP算例4.7 变尺度法解：1）取初始点 ，为了按D F18:03010000014141212 xxd一维搜索最佳步长应满足1002000()min()min(40203)ffxxd得:00.25120.5x2）再按DFP法构造点x1处的搜寻方向d1，需计算1121212241()422xxxxfxx 沿d0方向进行
17、一维搜索，得（9）DFP算例4.7 变尺度法25一维搜索最佳步长应满足得:2）再按D F P 法构造点x 1 处的搜寻18:03010143224ggg0102110.510.5 xxx代入校正公式000000000000TTTTxxAggAAxggAg1310.5340.543310.53444=（9）DFP算例4.7 变尺度法26代入校正公式=（9）D F P 算例4.7 变尺度法2 618:03100 AAA21191010.5912112550010.50.251216194152550100=第二次搜寻方向为1118665 dA g再沿d1进行一维搜索，得12111182560.55
18、xxd（9）DFP算例4.7 变尺度法27=第二次搜寻方向为再沿d 1 进行一维搜索，得（9）D F P 算例18:03为一维搜索最佳步长，应满足12112111811()min()min(4)52ffxxd154242 x,得3）判断x2是否为极值点梯度:2122212240()420 xxxxfxx 海赛矩阵:2222()24fx（9）DFP算例4.7 变尺度法梯度为零向量,海赛矩阵正定。可见满足极值充要条件，因此为极小点。28为一维搜索最佳步长，应满足,得3）判断x 2 是否为极值点梯度:18:03例:用DFP变尺度法求目标函数的最优解。已知初始点 ，迭代精度=0.012221)6()5
19、(4)(xxxFTx98)0(解：第一次迭代：624)6(2)5(8)()9,8(21)0(0 xxxFg3.240g62400)0(gAS(0)(1)(0)(0)(0)0(0)8248249696xxS （9）DFP算例4.7 变尺度法29例:用D F P 变尺度法求目标函数的最优解。已知初始点 18:03式中最优步长应用一维搜索方法在计算机上求解。为了说明问题，又因为此例目标函数简单，所以用解析法来求：22)1()669(5)248(4)()(fxF为求极小，将上式对求导，并令f()=013077.0)0(得：21538.886152.4)1(x于是：43076.410784.0)()1(
20、1xFg56716.41g（9）DFP算例4.7 变尺度法30式中最优步长应用一维搜索方法在计算机上求解。为了说明问题，又18:03第二次迭代：确定x(1)点的拟牛顿方向S(1)78462.013848.3)0()1(0 xx56924.110784.25010ggy按DFP公式计算构造矩阵0000000000001yAyAyyAyAATTTTT（9）DFP算例4.7 变尺度法31第二次迭代：确定x(1)点的拟牛顿方向S(1)按D F P 公式计18:03将数据代入得003801.1031487.0031487.012697.01A则拟牛顿方向为48248.428017.011)1(gAS沿
21、S(1)方向进行一维搜索求最优点x(2)求一维搜索步长4942.0)1(（9）DFP算例4.7 变尺度法32将数据代入得则拟牛顿方向为沿 S(1)方向进行一维搜索求最18:0300014.699998.4*)2(xx00028.000016.0)()2(2xFg00032.02g则：迭代即可结束，输出优化解00014.699998.4)2(x8101.2*)(*xFF（9）DFP算例4.7 变尺度法33则：迭代即可结束，输出优化解（9）D F P 算例4.7 变尺18:03讨论：该题的理论最优点是 。按DFP搜索方向为共轭的性质，本题为二元二次函数在两次迭代后即达到最优点，本题计算结果稍有误差
22、，这是由于一维搜索的不精确性产生的。Tx65*若在已知A1的基础上，再用DFP公式递推下一次的构造矩阵，可计算得5000.0001250.02A而计算目标函数海赛矩阵的逆阵有2008H2100811H12 HA（9）DFP算例4.7 变尺度法34讨论：该题的理论最优点是 18:03DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年，Broyden、Fletcher、Goldstein、Shanno等人提出一种更稳定的算法，称为BFGS算法。其校正公式为：11TTTTTTkkkkkkkkkkkkkkkkkTTTkkkkkkky A yA y
23、y AAAy AA yyyy A y（9）BFGS变尺度法4.7 变尺度法35D F P 算法由于舍入误差和一维搜索的不精确，有可能导致A k 奇异18:0336（1）概述4.8 鲍威尔方法基本思想：基于坐标轮换法，不用求导数，在迭代中逐次产生共轭搜索方向。收敛效果：对于正定（有极小值）二次函数，经过n轮迭代后求得极小点；对于非二次函数，一般也具有较高的收敛速度。Powell法是求解无约束优化问题的最好方法。将其与惩罚函数法结合，可以处理有约束优化问题。3 6（1）概述4.8 鲍威尔方法基本思想：基于坐标轮换法18:030Tjkdg 10Tjkdg 为两个极小点 1,kkxx1()0Tjkkd
24、gg根据梯度与等值面之间关系可知（2）共轭方向的生成4.8 鲍威尔方法37 为两个极小点 根据梯度与等18:03对于二次函数，两点处的梯度可表示为1,kkxxkkgGxb11kkgGxb11()kkkkggG xx1()0Tjkkdgg代入到公式：（2）共轭方向的生成4.8 鲍威尔方法38对于二次函数，两点处的梯度可表示为18:0311()()0TTjjkkkkdggdG xx结论：从不同的点出发沿某一方向分别对函数作两次一维搜索，得到两个极小点，那么这两个极小点的连线方向与该方向对G共轭（2）共轭方向的生成4.8 鲍威尔方法39结论：从不同的点出发沿某一方向分别对函数作两次一维搜索，得到18
25、:03（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程（二维）1）任选一初始点x0，再选两个线性无关的向量，如 坐 标 轴 单 位 向 量e1=1,0T和e2=0,1T作为初始搜索方向。x1x2x0oe1e2d1d2x*102x10 x11x12x01x40（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程18:03（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程（二维）2）从x0出发，顺次沿e1，e2作一维搜索，得 点，两点连线得一新方向d10012,xx1002dxxx1x2x0oe1e2d1d2x*102x10 x11x12x01x41（3）基本算法4.8 鲍威尔方
26、法鲍威尔基本算法的搜索过程18:03（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程（二维）21120dxx用 d1代替e1形成两个线性无关向量d1,e2，作为下一轮迭代的搜索方向。再从 出发，沿d1作一维搜索得点 ，作为下一轮迭代的初始点。02x10 x3）从 出发，e2,d1 作一维搜索，得到点 ，两点连线得一新方向:1112,xx10 xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x从 沿d2作一维搜索得点x2。即是二维问题的极小点 x*。12x42（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程18:03（3）基本算法4.8 鲍威尔方法鲍威尔基
27、本算法的搜索过程（二维）方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。43（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程18:03（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程（三维）441.第一轮基本方向组取单位坐标矢量系e1、e2、e3、en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向。2.再沿新生方向作一维搜索，完成第一轮的迭代。以后每轮的基本方向组是将上轮的第一个方向淘汰，上轮的新生方向补入本轮的最后而构成：d2k,d3k,dnk ,dk（3）基本算法4.8 鲍威尔方法鲍威尔基本算法的搜索过程18:03（4）基本算法示例4.8 鲍威尔方法45
28、（4）基本算法示例4.8 鲍威尔方法4 518:03（4）基本算法示例4.8 鲍威尔方法46（4）基本算法示例4.8 鲍威尔方法4 618:03（4）基本算法示例4.8 鲍威尔方法47（4）基本算法示例4.8 鲍威尔方法4 718:03（4）基本算法示例4.8 鲍威尔方法48（4）基本算法示例4.8 鲍威尔方法4 818:03（4）基本算法示例4.8 鲍威尔方法49（4）基本算法示例4.8 鲍威尔方法4 918:03（4）基本算法示例4.8 鲍威尔方法50（4）基本算法示例4.8 鲍威尔方法5 018:03（4）基本算法示例4.8 鲍威尔方法51（4）基本算法示例4.8 鲍威尔方法5 118:
29、03（4）基本算法示例4.8 鲍威尔方法52（4）基本算法示例4.8 鲍威尔方法5 218:03（4）基本算法示例4.8 鲍威尔方法53（4）基本算法示例4.8 鲍威尔方法5 318:03（4）基本算法示例4.8 鲍威尔方法54（4）基本算法示例4.8 鲍威尔方法5 418:03 可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况。如第k轮中，产生新的方向：dk=xnk-x0k=1kd1k+2kd2k+nkdnk 式中，d1k、d2k、dnk为第k轮基本方向组矢量，1k、2k、nk为各方向的最优步长。若在第k轮的优化搜索过程中出现 1k=0，则方向dk表示为d2k、d3k、dnk的线性组
30、合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。（5）基本算法缺陷4.8 鲍威尔方法55 可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情18:03鲍威尔基本算法的退化x1x2x3 1=0 2e2 3e3S1如图所示为一个三维优化问题的示例，设第一轮中 1=0，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。e2e3S1（5）基本算法缺陷4.8 鲍威尔方法56鲍威尔基本算法的退化x 1 x 2 x 3 1=0 2 e 2 3 e 3 S 118:03（5）基本算法缺陷4.8 鲍威尔方法57（5）基本
31、算法缺陷4.8 鲍威尔方法5 718:03（5）基本算法缺陷4.8 鲍威尔方法58（5）基本算法缺陷4.8 鲍威尔方法5 818:03（5）基本算法缺陷4.8 鲍威尔方法59（5）基本算法缺陷4.8 鲍威尔方法5 918:03（5）基本算法缺陷4.8 鲍威尔方法60（5）基本算法缺陷4.8 鲍威尔方法6 018:03（5）基本算法缺陷4.8 鲍威尔方法61（5）基本算法缺陷4.8 鲍威尔方法6 118:03（5）基本算法缺陷4.8 鲍威尔方法62（5）基本算法缺陷4.8 鲍威尔方法6 218:03（5）基本算法缺陷4.8 鲍威尔方法63（5）基本算法缺陷4.8 鲍威尔方法6 318:03（5）
32、基本算法缺陷4.8 鲍威尔方法64（5）基本算法缺陷4.8 鲍威尔方法6 418:03（5）基本算法缺陷4.8 鲍威尔方法65（5）基本算法缺陷4.8 鲍威尔方法6 518:03（5）基本算法缺陷4.8 鲍威尔方法66（5）基本算法缺陷4.8 鲍威尔方法6 618:0367（6）修正算法4.8 鲍威尔方法*根据Powell条件判定是否需换方向；如需换向，则换掉函数值下降量最大的方向。选取n个线性无关且尽可能共轭的方向作为下一轮搜索的方向组。做法：形成新的搜索方向组时，不是固定的去掉前一次搜索方向组中的第一个方向，而是首先根据Powell条件，判断原方向组是否需要替换，若需要，则进一步判断原方向
33、组中哪个方向最坏，并以前一轮新生成的搜索方向替换本轮中的这个最坏方向。6 7（6）修正算法4.8 鲍威尔方法*根据P o w e l18:0368（6）修正算法4.8 鲍威尔方法方向组的构造在第k轮的搜索中，x0k 为初始点，搜索方向为d1k、d2k、dnk，产生的新方向为dk，此方向的极小点为xk。沿dk方向移动得到点 xn+1k=2xnk-x0k，称之为x0k对xnk的反射点。计算x0k、x1k、xnk、xk、xn+1k 各点的函数值，记作：F0=F(x0k)F2=F(xnk)F3=F(xn+1k)=F(xm-1k)-F(xmk)是第k轮方向组中，依次沿各方向搜索函数下降值11maxmim
34、mi nFF 6 8（6）修正算法4.8 鲍威尔方法方向组的构造在第k 轮18:03鲍威尔算法的方向淘汰1knxkxknxknd0kx1kmxkmx3kd2kx1kx1kd2kdkd(F3)(F2)(F0)反射点反射点函数最大下降量函数最大下降量m始点始点终点终点（6）修正算法4.8 鲍威尔方法69鲍威尔算法的方向淘汰(F 3)(F 2)(F 0)反射点函数最大下18:03为了构造第k+1轮基本方向组，采用如下判别式：按照以下两种情况处理：1)上式中至少一个不等式不成立，则第k+1轮的基本方向仍用老方向组d1k、d2k、dnk。k+1轮的初始点取 x0k+1=xnk F2F0，不满足判别条件，
35、因而下轮迭代应继续使用原来的搜索方向e1,e202X10X因为F2 F 0，不满足判别条件，因18:038012d2）再沿方向进行一维搜索，得：2其中为一维搜索最佳步长，应满足：得：所以，取沿搜索的函数值增量的最大者 终点12x的反射点和函数值为：2212211128264.08693.3108264.08693.3dXX1852.101718.1211minmin22221221112dXfXff5533.023797.18693.312X818.62122XffF367.3818.6185.10212ff1211,dd029.5max121m9330.11931.32101213XXX74
36、7.1133XfF（8）算例4.8 鲍威尔方法8 0 2）再沿方向进行一维搜索，得：其中为一维搜索最佳步长，应18:03813）Powell条件判断：满足 230220320035.02FFFFFFFFFmm用新方向13d替换111ed ，下轮搜索方向为13,2 de 5533.06762.0101213XXd下轮起始点 为从 出发，沿 搜索的极小点：20X12X13d33313312205533.03797.16762.08693.35533.06762.03797.18693.3dXX其中3为一维搜索最佳步长，应满足8181.6734.66627.1minmin03231331220dXf
37、Xff得：0257.235059.24995.220X0008.00200XffF已足够接近极值点2.5 2.5T。（8）算例4.8 鲍威尔方法8 1 3）P o w e l l 条件判断：满足 用新方向替换，下轮搜索18:0382单形替换法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法，属于直接法之一。（1）基本原理4.9 单型替换法现以求二元函数的极小点为例，说明单形替换法形成原理.设二元函数 在 平面上取不在同一条 直线上的三个点 ,和 ，并以它们为顶点构成一单纯 形三角形。算出各顶
38、点的函数值 ，比较其大小，现假定比较后有这说明点 最差，点 最好，点 次差。为了寻找极小点，一般来说应向最差点的反对称方向进行搜索)()(21xxfXf，21xx 1X2X3X)(1Xf)(2Xf)(3Xf)(1Xf)()(32XfXf1X2X3X8 2 单形替换法是利用对简单几何图形各顶点的目标函数值作相互比18:0383（1）基本原理4.9 单型替换法以 记为 的中点（如图所示），在 的延长线上取点 ，使 称为 是 关于 的反射点。算出 的函数值 ，可能出现以下几种情形：4X32XX41XX5X1414452)(XXXXXX5X1X4X5X)(5Xf8 3（1）基本原理4.9 单型替换法以
39、 记为18:03 (1)这说明搜索方向正确，可进一步扩大效果，继续沿 向前搜索，也就是向前扩张。这时取 其中 为扩张因子，一般取 。如果 ，说明扩张有利，就可以 点 代替 点 构成新的单纯形 。如果 ，说明扩张不利，舍去点 ，仍以点 代替 构成新的单纯形 。)()(35XfXf51XX)(1446XXXX0.22.1)()(56XfXf6X1X,632XXX)()(56XfXf6X5X1X532XXX，（1）基本原理4.9 单型替换法84 (1)（1）基本原理4.9 单型替换18:03(2)这说明搜索方向正确，但无须扩张，以 代替 构成新的单纯形 。(3)这表示 点走得太远，应缩回一些。若以
40、表示压缩因子，则有 常取为0.5。以 代替 构成新的单纯形)()()(253XfXfXf5X1X532XXX，)()()(152XfXfXf5X)(4547XXXX7X1X,732XXX（1）基本原理4.9 单型替换法85(2)（1）基本原理4.9 单型替换法8 518:03(4)这时应压缩更多一些，将新点压缩至 之间，令（1）基本原理4.9 单型替换法86)()(15XfXf1X4X)()(4141448XXXXXXX如果)()(18XfXf则以 代替 构成新的单纯形8X1X,832XXX41XX否则认为 方向上的所有点的函数值 都大于 ，不能沿此方向搜索。)(Xf)(1Xf这时，可以以 为
41、中心进行缩边，使顶点 和 向 移近一半距离，得新单纯形 .以此单纯形为基础再进行寻优。3X1X2X3X,1093XXX(4)（1）基本原理4.9 单型替换法8 6 如果则以 18:03（2）比较各顶点Xi的函数值，挑出其中的最优点，记为XL；最劣点，记XH；次差点，记为Xw；（3）求反射中心21nnXX和反射点)(1 112)(01HnnnnHiiinXXaXXXnX其中，a0，通常取a=1；（1）令,2,1,100niiXXXniheXX构造单纯形；输出XL，为原问题近似极小点；否则，转（2）。(扩张时=2)构造新单纯形；5.0（4）根据不同情况，分别进行扩张，收缩或缩边，其中收缩因子112
42、1max )()(LiniLiXXXfXf（5）如果满足（2）计算步骤4.9 单型替换法87（2）比较各顶点X i 的函数值，挑出其中的最优点，记为X L；最18:03试用单型替换求 的极小值.选 ,并取 和 这三点不在一条直线上，用它们作为初始单纯形的顶点 （如图所示）2221)6()5(4)(xxXfTX9,80TX)11,10(1TX)11,8(2（3）算例4.9 单型替换法88 例 试用单型替换求 18:03 然后计算各顶点的函数值：可知 为最差点，为最好点。以 表示 和 的重心，则反射点65)(,125)(,45)(210XfXfXf1X0X3X0X2X308108108119111
43、111102niHiXXXn 43181062210119XXX 224()4(65)(96)13f X（3）算例4.9 单型替换法89 然后计算各顶点的函数值：（3）算例4.9 单型替18:03由于 ，故需扩张。取 ，则因为 ，故以 代替 ，由 ，和 构成新单纯形，然后进行下一个循环。该问题的最优解为 。经32次循环，可把目标函数减小到 。)()(04XfXf2534386842()2109108XXXX 8)68()54(4)(225Xf)()(45XfXf5X1X5X0X2XTX65*，)(Xf6101（3）算例4.9 单型替换法90由于 18:034.10 无约束优化方法总结（1）无约
44、束优化问题的评价准则 为了比较各种优化方法的特性，必须建立合理的评价准则。无约束优化方法评价准则主要包括以下几个方面：1、可靠性。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好。2、有效性。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数。3、简便性。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。914.1 0 无约束优化方法总结（1）无约束优化问题的评价准18:034.10 无约束优化方法总结（2）无约束优化
45、方法的评价结论可靠性：牛顿法较差，因为它对目标函数要求太高，解题成功率较低。有效性：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性。简便性：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。1、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。2、对于二次性较强的目标函数，使用牛顿法效果好。3、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。4、综合而言，鲍威尔法和变尺度法（DFP）具有较好的性能。924.1 0 无约束优化
46、方法总结（2）无约束优化方法的评价结18:034.10 无约束优化方法总结（3）无约束优化方法的联系1kkkd Ggkkkd Q g111kTkkkTkdgQIgg1kG搜 索 方 向函数梯度修正因子所用目标函数信息梯 度 法I（单位阵）一阶导数牛 顿 法二阶导数共轭梯度法一阶导数 变尺度法一阶导数kkkd A g11kkk AAA方 法kkd g鲍威尔法1kkkdxx函数值 零阶方法单形替换法 零阶方法函数值 最差点和最好点与次好点中点的连线934.1 0 无约束优化方法总结（3）无约束优化方法的联系搜18:03作业1.试用Newton法求 的极小点，初始点取为 。2221214)(xxxxf，01,1TX 2.用DFP算法求 ，取 2212min(4)xx01,1TX 3.试用鲍威尔修正算法求目标函数的最优解。已知 初始点 ，迭代精度=0.0012112221242)(xxxxxxF01,1TX 4.用共轭梯度法求 ，其中 ，选初始点 。222125)(minxxXf12TXx x，6010 22，TX94作业1.试用N e wt o n 法求
