无约束优化方法.pptx

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

1、多维多维无约束优化问题是：求n维设计变量 使目标函数：各种多维无约束优化解法的区别：搜索方向的不同 分类：（1）直接解法-不使用导数信息，如坐标轮换不使用导数信息，如坐标轮换 法、法、PowellPowell法、随机搜索法、单纯形法等法、随机搜索法、单纯形法等（2）间接解法(解析法)-要使用导数，二阶有要使用导数，二阶有 梯梯度法、共轭梯度法、，二阶以上用牛顿法度法、共轭梯度法、，二阶以上用牛顿法搜索方向的构成问题是多维无约束优化方法的关键第1页/共67页多维无约束优化方法算法的基本过程是:从选定的某初始点x x(k)(k)出发，沿着以一定规律产生的搜索方向S S(k)(k),取适当的步长a

2、a(k)(k),逐次搜寻函数值下降的新迭代点x x(k+1)(k+1),使之逐步通近最优点x*x*。可以把初始点x x(k)(k)、搜索方向S S(k)(k)、迭代步长a a(k)(k)称为优化方法算法的三要素。其中以搜索方向S S(k)(k)更为突出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S S(k)(k)是研究优化方法的最根本的任务之一。第2页/共67页3.4.1 最速下降最速下降(梯度梯度)法法 函数的负梯度方向是函数值下降最快的方向 搜索方向S取该点的负梯度方向 (最速下降方向)，使函数值在该点附近的范围内

3、下降最快。为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有第3页/共67页 根据一元函数极值的必要条件和多元复合函数求导公式，得 在最速下降(梯度)法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。第4页/共67页第5页/共67页例3.43.41 1 求目标函数 的极小点。解 取初始点则初始点处函数值及梯度分别为沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件 第6页/共67页算

4、出一维搜索最佳步长 第一次迭代设计点位置和函数值 继续作下去，经1010次迭代后，得到最优解 第7页/共67页这一问题的目标函数f(x)的等值线为一簇椭圆。将上例中目标函数 引入变换 y1=x1,y2=5x2则函数f(x)f(x)变为：其等值线由椭圆变成一簇同心圆。仍从 即 出发进行最速下降法寻优。此时：沿负梯度方向进行一维搜索：第8页/共67页为一维搜索最佳步长，可由极值条件：由从而算得一步计算后设计点的位置及其目标函数：第9页/共67页经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。1 1第10页/共67页梯度法的特点梯度法的特点:（1）理论明确，程序简单

5、，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（4）梯度法的收敛速度 与目标函数的性质密切相 关。对于等值线(面)为同 心圆（球）的目标函数，一次搜索即可达到极小点。第11页/共67页3.4.2 牛顿法及其改进牛顿法及其改进 1 1、牛顿法、牛顿法 在在x xk k邻域内用一个二次函数邻域内用一个二次函数 来近似来近似代替原目标函数，并将代替原目标函数，并将 的极小点作为对目的极小点作为对目标函数标

6、函数 求优的下一个迭代点求优的下一个迭代点 。经多次迭代，使之。经多次迭代，使之逼近目标函数逼近目标函数 的极小点。的极小点。设 为 的极小点 第12页/共67页这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。例4 42 2 求目标函数 的极小点。解 取初始点第13页/共67页经过一次迭代即求得极小点 ，函数极小值 。从牛顿法迭代公式的推演中可以看到，迭代点的从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并位置是按照极值条件确定的，其中并未含有沿下降未含有沿下降方向方向搜寻的

7、概念。因此对于搜寻的概念。因此对于非二次函数非二次函数，如果采用，如果采用上述牛顿迭代公式，有时会使函数值上升。上述牛顿迭代公式，有时会使函数值上升。2 2、阻尼牛顿法、阻尼牛顿法 阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：第14页/共67页 阻尼牛顿法称序框图第15页/共67页 牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大。第16页/共67页一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法：第17页/共67页3.4.3 变尺度法变尺度法 变尺度法是在牛顿法的

8、思想上进行了重大改进的一类方法 1.基本思想基本思想 变量的尺度变换是放大或缩小各个坐标。通过尺变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。例如在用最速下降法求 的极小值时,需要进行10次迭代才能达到极小点 如作变换 y1=x1,y2=5x2把 的尺度放大5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。x2第18页/共67页消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快，但当迭代到最优点附近时收敛速度很慢；牛顿法收敛很快，对于二次函数只需迭代一

9、次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？能不能将两种算法的优点综合起来，扬长避短？第19页/共67页Ak 是需要构造nn的一个对称方阵，如Ak=I,则得到梯度法；则得到阻尼牛顿法；如 当矩阵Ak 不断地迭代而能很好地逼近 时，就可以不再需要计算二阶导数变尺度法的关键在于尺度矩阵Ak的产生。对于二次函数:第20页/共67页进行尺度变换在新的坐标系中，函数f(x)的二次项变为：目的：减少二次项的偏心如G是正定，则总存在矩阵Q，使得：用矩阵Q-1右乘等式两边，得：用矩阵

10、Q左乘等式两边，得：所以上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q来求得。第21页/共67页牛顿迭代公式：记：牛顿方向：迭代公式：A A 称为尺度变换矩阵第22页/共67页在例3.42中如取第23页/共67页求得：第24页/共67页2 2、构造尺度矩阵、构造尺度矩阵A Ak k从初始矩阵A0=I(单位矩阵)开始，通过对公式 中修正矩阵 的不断修正，在迭代中逐步逼近于 因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。1）DFP法（Davidon-Fletcher-Powell)式中。第25页/共67页2）BFGS算法(Broyden-Fletcher-Gold(Broyden-

11、Fletcher-Gold frob-Shannofrob-Shanno)DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。第26页/共67页第27页/共67页例3.4-3：用DFP算法求下列问题的极值：解：1）取初始点 ，为了按DFP法构造第一次搜寻方向S0，需计算初始点处的梯度取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为 第28页/共67页沿S0方向进行一维搜索，得为一维搜索最佳步长，应满足得:,2）再按DFP法构造点x1处的搜寻方向S1，需计算第29页/共67页代入校正公式=第30页/共67

12、页=第二次搜寻方向为再沿S1进行一维搜索，得第31页/共67页为一维搜索最佳步长，应满足,得3）判断x2是否为极值点梯度:海赛矩阵:第32页/共67页梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。第33页/共67页DFPDFP变尺度法的几点说明:(1)、在变尺度法中对A(k)矩阵是有要求的。因为对于极小化问题，为了使搜索方向 为下降方向，需要使搜索方向S(k)与负梯度方向的夹角为锐角，即 所以A(k)必须为正定矩阵第34页/共67页DFPDFP变尺度法的几点说明:(2)、对于对称正定矩阵A(k)和非零向量S(1)、S(2)S(n)(3)、每次迭代都能使目标函数值单调下降即为

13、算法的连续稳定性.为了提高实际计算中的稳定性，通常采用“重置”的方法，即在n次迭代后重新设置单位矩阵.第35页/共67页3.4.4 共轭方向法共轭方向法 1.1.共轭方向共轭方向 设G为nn阶实对称正定矩阵，如果有两个n维向量S0和S1满足 ，则称向量S0与S1 关于矩阵G共轭。当G为单位矩阵时，假设目标函数f(x)在极值点附近的二次近似函数为对二维情况任选取初始点x0沿某个下降方向S S0 0作一维搜索，得x1第36页/共67页0S0 x0 x1x*1 11S1 因为 是沿S0方向搜索的最佳步长，即在点x1处函数f（x）沿方向S0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有如

14、果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象。取下一次的迭代搜索方向S1直指极小点x*.S1第37页/共67页0S0 x0 x1x*1 11S1S1第38页/共67页如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行S0、S1两次直线搜索就可以求到极小点x*，即有那么这样的S1方向应该满足什么条件呢?对于前述的二次函数:有当 时 。x*是f(x)极小点，应满足极值必要条件，故有将等式两边同时左乘 得：第39页/共67页 就是使S1直指极小点x*，S1所必须满足的条件。两个向量S0和S1称为G的共轭向量，或称S0和S1对G是共轭方向。2.2.2.2.共轭方向的性质共轭方

15、向的性质共轭方向的性质共轭方向的性质性质1 1 若非零向量系S0,S1,S2,Sm-1是对G共轭，则这m个向量是线性无关的。性质2 2 在n维空间中互相共轭的非零向量的个数不超过n。性质3 3 从任意初始点出发，顺次沿n个G的共轭方向S0,S1,S2,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。第40页/共67页关键：新的共轭方向确定第41页/共67页3.3.共轭梯度法共轭梯度法共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。从xk出发，沿负梯度方向作一维搜索:设与Sk共轭的下一个方向Sk+1由Sk和点xk+1的负梯度的线形组合

16、构成，即：共轭条件：第42页/共67页则：解得：令为函数的泰勒二次展开式则上两式相减，并代入第43页/共67页将式与式两边相乘，并应用共轭条件得：因此第44页/共67页，已知初始点1,11,1T T例题 3.4-4 求下列问题的极值l解：1）第一次沿负梯度方向搜寻l计算初始点处的梯度为一维搜索最佳步长，应满足l迭代精度 。第45页/共67页得:2）第二次迭代：代入目标函数第46页/共67页得因收敛。由从而有：第47页/共67页3.4.5 鲍威尔方法鲍威尔方法鲍威尔（PowellPowell）法是直接利用函数值来构造共轭方向的一种方法 对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G 的

17、共轭方向1.1.1.1.共轭方向的生成共轭方向的生成共轭方向的生成共轭方向的生成jjk kkkSd dSjgg gk+1k+1xxk+1设xk,xk+1为从不同点出发，沿同一方向Sj j进行一维搜索而得到的两个极小点.第48页/共67页梯度和等值面相垂直的性质,Sj j和 xk,xk+1两点处的梯度gk,gk+1之间存在关系:另一方面，对于上述二次函数，其xk,xk+1两点处的梯度可表示为:因而有取这说明只要沿Sj j方向分别对函作两次一维搜索，得到两个极小点xk和xk+1 ，那么这两点的连线所给出的方向Sk k就是与Sj j一起对G共轭的方向。第49页/共67页2.2.基本算法基本算法二维情

18、况描述鲍威尔的基本算法:1 1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位 向 量 e1 1=1,0=1,0T T和e e2 2=0,1=0,1T T作 为 初 始搜索方向。2 2）从x0出发，顺次沿e1 1，e1 1作一维搜索，得 点，两点连线得一新方向S1 1x1x2x0o oe1e2d1d2x*1第50页/共67页用 S1代替e1 1形成两个线性无关向量S1,e2 2 ，作为下一轮迭代的搜索方向。再从 出发，沿S1作一维搜索得点 ，作为下一轮迭代的初始点。x1x2x0o oe1e2d1d2x*13 3）从出发 ，顺次沿e2 2,S1 作一维搜索，得到点 ，两点连线得一新方向:

19、沿S2作一维搜索得点x2.即是二维问题的极小点x*.方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。第51页/共67页 把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。上述基本算法

20、仅具有理论意义。第52页/共67页 因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时张不成n维空间，可能求不到极小点，所以上述基本算法有待改进。3.3.3.3.改进的算法改进的算法改进的算法改进的算法 在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。第53页/共67页为此，要解决两个关键问题：（1）Sk1是否较好？是

21、否应该进入新的方向组？即方向组是否进行更新？（2）如果应该更新方向组，Sk1不一定替换方向 ，而是有选择地替换某一方向 。令在k次循环中（）分别称为一轮迭代的始点、终点和反射点。第54页/共67页则在循环中函数下降最多的第m次迭代是记：相应的方向为 。为了构成共轭性好的方向组，须遵循下列准则：在k次循环中，若满足条件：和则选用新方向Sk，并在第k+1迭代中用Sk替换对应于 的方向 。否则，仍然用原方向组进行第k+1迭代。因此第55页/共67页 这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于n次函次，最多n次就可找到极小点，而对一般函

22、数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。第56页/共67页例3.4-5 3.4-5 用改进的鲍威尔法求目标函数的最优解。已知初始点1,11,1T T，迭代精度。解：（1 1）第1 1轮迭代计算，沿e1方向进行一维搜索得第57页/共67页以 为起点，沿第二坐标轴方向 e2 进行一维搜索得第58页/共67页确定此轮中的最大下降量及其相应方向 反射点及其函数值，检验PowellPowell条件第59页/共67页由于满足PowellPowell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。构成新的方向 沿 方向一维搜索得极小点和极小值，此点为下轮迭代初始

23、点。按点距准则检验终止条件 需进行第二轮迭代计算。第60页/共67页（2 2）第2 2轮迭代计算此轮基本方向组为e2，分别相当于 ，起始点为 。沿e2方向进行一维搜索得 以 为起点沿 方向一维搜索得确定此轮中函数值最大下降量及其相应方向 第61页/共67页反射点及其函数值检验Powell条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为 ，。构成新的方向沿 方向进行一维搜索得第62页/共67页检验终止条件（3 3）第3 3轮迭代计算此轮基本方向组为 ，起始点为 ，先后沿 ，方向，进行一维搜索，得，检验终止条件 故最优解 第63页/共67页 实际上，前两轮迭代的 ，为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。第64页/共67页表2 2 无约束优化方法搜索方向之间的相互联系搜索方向函数梯度的修正因子所用目标函数信息梯度法I I（单位阵）一阶导数牛顿法二阶导数共轭梯度法一阶导数变尺度法一阶导数，使（海赛矩阵的逆阵）第65页/共67页作业P145页3-13；3-16。第66页/共67页感谢您的观看。第67页/共67页