常用无约束最优化方法ppt课件.ppt

第五章第五章 常用无约束优化方法常用无约束优化方法最速下降法最速下降法 Newton法法修正修正Newton法法共轭方向法共轭方向法 共轭梯度法共轭梯度法 变尺度法变尺度法 坐标轮换法坐标轮换法 单纯形法单纯形法第五章第五章 常用无约束优化方法常用无约束优化方法对于多维无约束最优化问题对于多维无约束最优化问题)(minXf（5.1） 成立点成立点 就是问题（就是问题（5.1）的）的全局最优点全局最优点但是，但是，大多数最优化方法只能求到局部最优点这个矛盾对大多数最优化方法只能求到局部最优点这个矛盾对于实际问题来讲一般容易解决，因为根据问题的实际于实际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解意义多半可以直接判定用优化方法求出的局部最优解是否为全局最优解但在理论上这是个比较复杂的问是否为全局最优解但在理论上这是个比较复杂的问题，本书不涉及题，本书不涉及 *X其中其中 这个问题的求解是指，在这个问题的求解是指，在 中找一中找一点，使得对于任意的点，使得对于任意的 都有都有1RRfn：nRnRX )()(*XfXf（5.2） 无约束优化方法是优化技术中极为重要无约束优化方法是优化技术中极为重要,它不仅可以直它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化也常将其转化为无约束优化问题，然后用无约束优化方法来求解同时，有些无约束优化方法只需略加处方法来求解同时，有些无约束优化方法只需略加处理，即可用于求解约束优化问题理，即可用于求解约束优化问题 第五章第五章 常用无约束优化方法常用无约束优化方法无约束优化理论发展较早，比较成熟，方法也很多，无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为定搜索方向，通常称它为直接搜索法直接搜索法，简称为，简称为直接法直接法，另一类需要计算函数的一阶或二阶导数值所得到的信另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为息来确定搜索方向，这一类方法称为间接法间接法（或（或解析解析法法）直接法不涉及导数和）直接法不涉及导数和Hesse矩阵，适应性强，但矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算计算梯度，甚至需要计算Hesse矩阵一般的经验是，矩阵一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法不存在导数的情况下，当然就应该使用直接法 第五章第五章 常用无约束优化方法常用无约束优化方法5.1 最速下降法最速下降法为求问题（为求问题（5.1）的最优解，按最优化算法的基本思想）的最优解，按最优化算法的基本思想是从一个给定的初始点是从一个给定的初始点 出发，通过基本迭代公式出发，通过基本迭代公式 ，按照特定的算法产生一串点列，按照特定的算法产生一串点列 ，如果点列收敛，则该点列的极限点为问题（如果点列收敛，则该点列的极限点为问题（5.1）的最）的最优解优解 0XkkkkPtXX1kX最速下降法基本原理最速下降法基本原理在基本迭代公式在基本迭代公式 中，每次迭代搜索方向中，每次迭代搜索方向 取为目标函数取为目标函数 的负梯度方向，即的负梯度方向，即 ，而，而每次迭代的步长每次迭代的步长 取为最优步长，由此所确定的算法取为最优步长，由此所确定的算法称为称为最速下降法最速下降法kkkkPtXX1kP)(Xf)(kkXfPkt在第二章中，我们曾经提到，对于函数，其函数在第二章中，我们曾经提到，对于函数，其函数值下降最快的方向是该函数的负梯度方向。值下降最快的方向是该函数的负梯度方向。 第五章第五章 常用无约束优化方法常用无约束优化方法对于问题（对于问题（5.1），假定我们已经迭），假定我们已经迭代了代了k次，获得了第次，获得了第k个迭代点个迭代点Xk现现在从在从Xk出发，可选择的下降方向很多出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该方向（即负梯度方向）进行搜索应该是有利的，至少在邻近的范围内是这是有利的，至少在邻近的范围内是这样因此，取搜索方向为样因此，取搜索方向为:)(kkXfP为了使目标函数在搜索方向上下降最多，沿为了使目标函数在搜索方向上下降最多，沿Pk进行一维进行一维搜索，由此得到第搜索，由此得到第k+1个迭代点，即个迭代点，即)(1kkkkXftXX其中步长其中步长tk因子由因子由 来确定。来确定。 )(min)(kktkkkXftXfXftXf记为记为 )(,(1kkkXfXlsX令令k=0,1,2,. ，就可以得到一个点列（初始点可任意选，就可以得到一个点列（初始点可任意选择）。当函数满足一定的条件时，择）。当函数满足一定的条件时， 该点列必收敛于函该点列必收敛于函数的极小点。数的极小点。 为书写方便，记为书写方便，记 故故 在不发生在不发生混淆时，再记混淆时，再记 )()(XfXg)()(kkXfXg)()(kkkXfXgg第五章第五章 常用无约束优化方法常用无约束优化方法迭代步骤迭代步骤 已知目标函数已知目标函数 及其梯度及其梯度，终止限，终止限 、 和和 )(Xf)(Xg123（1）选定初始点）选定初始点 ，计，计算算 ， ；置；置 0X)(00Xff)(00Xgg0k（2）作直线搜索：）作直线搜索： ),(1kkkgXlsX计算计算 )(11kkXff)(11kkXgg（3）用终止准则检测是否满足：）用终止准则检测是否满足：若满足，则打印最优解若满足，则打印最优解 , ,结束；否则，置结束；否则，置 ，转（，转（2） 1kX)(1kXf1 kk第五章第五章 常用无约束优化方法常用无约束优化方法将最速下降法应用于正定二次函数将最速下降法应用于正定二次函数 cXbAXXXfTT21)(（5.4） 可以推出显式迭代公式可以推出显式迭代公式设第设第k次迭代点为次迭代点为Xk，我们来求，我们来求Xk+1的表达式对式的表达式对式（5.4）关于）关于X求梯度，有求梯度，有 bAXXg)(（5.5） 因此，因此，bAXXggkkk)(（5.6） 现在从现在从Xk出发沿出发沿-gk作直线搜索以确定作直线搜索以确定Xk+1，于是，于是kkkkgtXX1(5.7) 其中其中tk是最优步长因子是最优步长因子 又因又因 0)(1kTkgXg，再结合式（再结合式（5.5）、（）、（5.6）、（）、（5.7）0)(kTkkkgbgtXA0kTkkkgAgtg或或可得可得 由此解出由此解出kTkkTkkAggggt 第五章第五章 常用无约束优化方法常用无约束优化方法代入式（代入式（5.7）中得到）中得到kkTkkTkkkgAggggXX1（5.8） 例例5.1 试用最速下降法求函数试用最速下降法求函数 的极小的极小点迭代两次，计算各迭代点的函数值，梯度及其模，点迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点并验证相邻两个搜索方向是正交的设初始点为为 2221214),(xxxxfTX 1, 1 0解解 与式（与式（5.4）比较，得）比较，得8002A梯度表达式是梯度表达式是212182),()(xxxxfXf由由 ，计算出，计算出 TX 11 0，5141)(220 xf82)(00Xfg24621. 8|0g第五章第五章 常用无约束优化方法常用无约束优化方法因为目标函数是二次的，可以使用式（因为目标函数是二次的，可以使用式（5.8），所以有），所以有04616. 073846. 08213077. 0110000001gAggggXXTT计算计算，55385. 004616. 0473846. 0)(221Xf，52237. 136923. 047692. 1)(111gXfg11076. 011076. 036923. 047692. 142500. 004616. 073846. 01111112gAggggXXTT，91335. 088008. 022152. 0)(06134. 0)(2221gXfgXf因为因为10210.00000.0000TTg gg g，说明相邻两个搜索方向是正交的说明相邻两个搜索方向是正交的 第五章第五章 常用无约束优化方法常用无约束优化方法有关说明有关说明 最速下降法的优点是算法简单，每最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢一个严重缺点就是收敛速度慢沿负梯度方向函数值下降很快的说法，容易使人们产生沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快特别是对于等值线（面）具有狭长深谷敛速度并不快特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象即从直观上看，在远继续下去就产生所谓的锯齿现象即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快次迭代行进距离缩短，因而收敛速度不快 第五章第五章 常用无约束优化方法常用无约束优化方法5.2 Newton法法如果目标函数在上具有连续的二阶偏导数，其如果目标函数在上具有连续的二阶偏导数，其Hesse矩矩阵正定并且可以表达成为显式（记阵正定并且可以表达成为显式（记 ，那么，那么可以使用下述的可以使用下述的Newton法这种方法一旦用好，收敛法这种方法一旦用好，收敛速度是很快的它是一维搜索速度是很快的它是一维搜索Newton切线法的推广切线法的推广 )()(2XfXG基本原理基本原理为寻求收敛速度快的算法为寻求收敛速度快的算法,在应用在应用基本迭代公式中基本迭代公式中 ，每轮迭代在迭代的起始点每轮迭代在迭代的起始点 处用处用一个适当的二次函数来近似该点一个适当的二次函数来近似该点处的目标函数，由此用点处的目标函数，由此用点 指向指向近似二次函数极小点的方向来构近似二次函数极小点的方向来构造搜索方向造搜索方向 . kkkkPtXX1kXkXkP第五章第五章 常用无约束优化方法常用无约束优化方法1RRfn：设最优化问题为设最优化问题为 )(minXf其中其中 二阶可导，二阶可导，Hesse矩阵矩阵 )(2Xf正定正定 不妨设经过不妨设经过 次迭代已获点次迭代已获点 ，现将，现将 在在 处处展成二阶泰勒公式，于是有展成二阶泰勒公式，于是有 kkXkXX )(Xf)()(21)()()()()(2kkTkkTkkXXXfXXXXXfXfXQXf显然显然 是二次函数，并且还是正定二次函数，所以是二次函数，并且还是正定二次函数，所以 是凸函数且存在唯一全局极小点为求此极小点，令是凸函数且存在唯一全局极小点为求此极小点，令)(XQ)(XQ0)()()(2kkkXXXfXfXQ即可解得即可解得)()(12kkkXfXfXX即即 )()(121kkkkXfXfXX（5.9） 对照基本迭代公式对照基本迭代公式,易知，式（易知，式（5.9）中的搜索方向）中的搜索方向)()(12kkkXfXfP步长因子步长因子 1kt第五章第五章 常用无约束优化方法常用无约束优化方法方向方向 是直指点是直指点 处近似二次函数处近似二次函数 的极小点的方向此时称此方向为从点的极小点的方向此时称此方向为从点 出发的出发的Newton方向方向从初始点开始，每一轮从当前迭代点出发，从初始点开始，每一轮从当前迭代点出发，沿沿Newton方向并取步长方向并取步长 的算法称为的算法称为Newton法法 )()(12kkkXfXfPkX)(XQkX1kt迭代步骤迭代步骤 已知目标函数已知目标函数 及其梯度及其梯度 ，Hesse矩阵矩阵 ，终，终止限止限 )(Xf)(Xg)(XG（1）选定初始点）选定初始点 ；计算；计算 ；置；置 0X)(),(0000XggXff0k（2）计算）计算 . )(2kkXfG（3）由方程）由方程 解出解出 kkkgPGkP（4）计算）计算 .，)(111kkkkkXffPXX)(11kkXgg（5）判别终止准则是否满足：若满足，则打印最优解）判别终止准则是否满足：若满足，则打印最优解 ， 结束；否则，置结束；否则，置 ，转（，转（2） 1kX1kf1kk第五章第五章 常用无约束优化方法常用无约束优化方法第五章第五章 常用无约束优化方法常用无约束优化方法例例5.2 试用试用Newton法求法求 的极小点，初的极小点，初始点取为始点取为 2221214)(xxxxf，TX 1, 1 0解解 梯度为梯度为 TxxXfXg82)()(21，Hesse矩阵为矩阵为8002)(XG其逆矩阵为其逆矩阵为125. 0005 . 0)(1XG由迭代公式（由迭代公式（5.9）得第）得第1 迭代点为迭代点为11000()()10.502000.125180XXG Xg X 由此由此 ，停止迭代得，停止迭代得 61100|)(|XfTXX001*，第五章第五章 常用无约束优化方法常用无约束优化方法对于目标函数是非二次函数的非约束最优化问题，一般对于目标函数是非二次函数的非约束最优化问题，一般来说，用来说，用Newton法通过有限轮迭代法通过有限轮迭代并不能并不能保证可求得保证可求得最优解但由于目标函数在最优解附近能近似于二次函最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用数，因此当先取接近于最优解的初始点使用Newton法法求解时，其收敛速度一般是较快的求解时，其收敛速度一般是较快的从例从例5.2我们看到，用我们看到，用Newton法求解，只经一轮迭代就法求解，只经一轮迭代就得到最优解这一结果并不是偶然的，因为从得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，方向的构造我们知道，对于正定二次函数，Newon方方向就是指向其极小点的方向因此，用向就是指向其极小点的方向因此，用Newton法解目法解目标函数为标函数为正定二次正定二次函数的函数的无约束无约束最优化问题，只需一最优化问题，只需一次迭代就可得最优解次迭代就可得最优解 事实上，可以证明在初始点离最优解不远的条件下，事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解法是二次收敛的但是当初始点选得离最优解太远时，太远时，Newton法并不一定是收敛的方法，甚至连其法并不一定是收敛的方法，甚至连其下降性也很难保证下降性也很难保证第五章第五章 常用无约束优化方法常用无约束优化方法有关说明有关说明 Newton法收敛速度非常快具有二次收敛的优点，但它存法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数上升，但仍不能保）尽管每次迭代不会使目标函数上升，但仍不能保证下降当证下降当Hesse矩阵非正定时，矩阵非正定时，Newton法的搜索将会法的搜索将会失败失败 （2）对初始点要求严格一般要求比较接近或有利于）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的接近极值点，而这在实际计算中是比较难办的 （3）在进行某次迭代时可能求不出搜索方向由于搜）在进行某次迭代时可能求不出搜索方向由于搜索方向为索方向为 ,若目标函数在若目标函数在 点点Hesse矩阵是奇异的，则矩阵是奇异的，则 不存在，因而不能不存在，因而不能构成构成newton方向，从而使迭代无法进行方向，从而使迭代无法进行)()(12kkkXfXfPkX12)(kXf（4）newton方向构造困难，计算相当复杂，除了求梯方向构造困难，计算相当复杂，除了求梯度以外还需计算度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存矩阵及其逆矩阵，占用机器内存相当大相当大 第五章第五章 常用无约束优化方法常用无约束优化方法5.3 拟拟Newton法法基本原理基本原理为了克服为了克服Newton法的缺点，人们保留选取法的缺点，人们保留选取Newton方向作方向作为搜索方向，摒弃其步长恒取为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优，而用一维搜索确定最优步长，由此产生的算法称为步长，由此产生的算法称为修正修正Newton法法（或（或阻力阻力Newton法法）迭代步骤迭代步骤 已知目标函数已知目标函数 及其梯度及其梯度 ，Hesse矩阵矩阵 ，终，终止限止限 )(Xf)(Xg)(XG（1）选取初始点）选取初始点 ，令，令 0X0k（2）计算）计算 若若 ，停止迭代输出，停止迭代输出，否则转（否则转（3） )()(kkXfXg|)(|kXf（3）构造）构造Newton方向计算方向计算 ，取，取121)()(kkXfXG)()(12kkkXfXfP（4）进行一维搜索求）进行一维搜索求 ，使得，使得 令令 ，转（，转（2） kt)(min)(0kktkkktPXfPtXf1,1kkPtXXkkkk第五章第五章 常用无约束优化方法常用无约束优化方法修正修正Newton法克服了法克服了Newton法的缺点特别法的缺点特别是，当迭代点接近于最是，当迭代点接近于最优解时，此法具有收敛优解时，此法具有收敛速度快的优点，对初始速度快的优点，对初始点的选择要求不严但点的选择要求不严但是，修正是，修正Newton法仍需法仍需要计算目标函数的要计算目标函数的Hesse矩阵和逆矩阵，所以计矩阵和逆矩阵，所以计算量和存贮量均很算量和存贮量均很大另外，当目标函数大另外，当目标函数的的Hesse矩阵在某点处出矩阵在某点处出现奇异时，迭代将无法现奇异时，迭代将无法进行，因此修正进行，因此修正Newton法仍有相当的局限性法仍有相当的局限性有关说明有关说明 第五章第五章 常用无约束优化方法常用无约束优化方法5.4 共轭方向法共轭方向法不同最优化方法，取决于基本迭代公式中确定搜索方不同最优化方法，取决于基本迭代公式中确定搜索方向的构造向的构造 最速下降法最速下降法， ，导致搜索路线出现锯齿状，导致搜索路线出现锯齿状，收敛速度降低；收敛速度降低； )(kkXfPNewton法法 ， ，收敛速度虽很快，收敛速度虽很快，但计算量很大，特别是还要求但计算量很大，特别是还要求Hesse矩阵正定，从而导矩阵正定，从而导致该算法对初始点选择要求过严致该算法对初始点选择要求过严 )()(12kkkXfXfP下面介绍下面介绍共轭方向法共轭方向法 ，该方法计算量小，收敛速度没，该方法计算量小，收敛速度没有有Newton法快，但比最速下降法快得多。法快，但比最速下降法快得多。 第五章第五章 常用无约束优化方法常用无约束优化方法基本原理基本原理 首先介绍共轭方向概念及其些性质首先介绍共轭方向概念及其些性质定义定义5.1 设设 是对称正定矩阵对于非零向量是对称正定矩阵对于非零向量 ，若有，若有 （5.10）则称则称 与与 相互相互 共轭或共轭或 正交的正交的 nnRAnRPP21，021APPT1P2PAA对于非零向量组对于非零向量组 ，若有，若有 ) 1210(niRPni，, 1, 2 , 1 , 0, 0jinjiAPPjTi（5.11） 则称则称 是是 共轭方向组或共轭方向组或 正交方向组，也正交方向组，也称它们是一组称它们是一组 的共轭方向的共轭方向 110nPPP， AAA若若 ，则式（，则式（5.10）和式（）和式（5.11）成为）成为 和和 由此可知，共轭概念是正交概念的推由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广广，共轭方向是正交方向的推广 nIA021PPT)(0jiPPjTi第五章第五章 常用无约束优化方法常用无约束优化方法定理定理5.1 设设 是正定矩阵，是正定矩阵， 是非零是非零向量若向量若 是一组是一组 共轭方向，则它们是线性共轭方向，则它们是线性无关的无关的nnRA) 110(niRPni， 110nPPP， A证明：设有一组实数证明：设有一组实数 ，使得，使得 110n，0111100nnPPP依次以依次以 左乘上式得到左乘上式得到) 110(niAPTi， 101100njjTijniAPP，（5.12）因为因为 是一组是一组 的共轭方向，故有的共轭方向，故有 110nPPP， AjinjiAPPjTi, 1, 2 , 1 , 0, 0又由于又由于A是正定矩阵，所以是正定矩阵，所以 对于，对于，有有 ），（1100niPi1100niAPPiTi，故故 1100nii，由此由此 是线性无关是线性无关 110nPPP， 第五章第五章 常用无约束优化方法常用无约束优化方法对于目标函数为二次函数的无约束优化问题对于目标函数为二次函数的无约束优化问题 cXbAXXXfTT21)(min（5.13） 有如下性质：有如下性质： 定理定理 5.2设设 是对称正定矩阵，是对称正定矩阵，是一组是一组 的共轭方向对于问题（的共轭方向对于问题（5.13），若从任意），若从任意点点 出发依次沿出发依次沿 进行一维搜索，则至进行一维搜索，则至多经过多经过 轮迭代，可得问题（轮迭代，可得问题（5.13）的最优解）的最优解 nnRAnnRPPP110， AnRX 0110nPPP， n证明证明 （略）（略）通常，我们把从任意点通常，我们把从任意点 出发，依次沿某组共轭出发，依次沿某组共轭方向进行一维搜索的求解最优化问题的方法，叫做方向进行一维搜索的求解最优化问题的方法，叫做共共轭方向法轭方向法 nRX 0第五章第五章 常用无约束优化方法常用无约束优化方法算法形成算法形成 为了直观起见，考虑形式为（为了直观起见，考虑形式为（5.13）的二元二次函数）的二元二次函数任选初始点任选初始点 ，从，从 出发沿某出发沿某个下降方向个下降方向 作一维搜索得到作一维搜索得到 0X0X0P1X根据一维搜索，显然有根据一维搜索，显然有 0)(01PXfT（5.20） 且向量且向量 所在的直线必与某条等值线（椭圆）相切于所在的直线必与某条等值线（椭圆）相切于 点点 0P1X下一次迭代，若按最速下降法选择负梯度方向作为搜索下一次迭代，若按最速下降法选择负梯度方向作为搜索方向，则将发生锯齿现象，为了克服这种现象，我们设方向，则将发生锯齿现象，为了克服这种现象，我们设想，若下一次迭代的搜索方向能直指极小点想，若下一次迭代的搜索方向能直指极小点 ，那么对，那么对于二元二次函数只须顺次进行两次直线搜索就可以求到于二元二次函数只须顺次进行两次直线搜索就可以求到极小点了极小点了这样的方向是否存在？若存在，应该满足什这样的方向是否存在？若存在，应该满足什么条件？怎样确定？么条件？怎样确定？ *X第五章第五章 常用无约束优化方法常用无约束优化方法因为因为 直接指极小点直接指极小点 ，所以可写成，所以可写成 1P*X111*PtXX（5.21） 其中其中 是最优步长因子，显然，当是最优步长因子，显然，当 时，时， 1t*1XX 01t对（对（5.13）中的函数求导数得）中的函数求导数得bAXXf)(（5.22） 因为因为 是极小点，所以有是极小点，所以有 *X0)(*bAXXf将式（将式（5.21）代入上式，并由式（）代入上式，并由式（5.22）可得）可得0)(111APtXf等式两边同时左乘等式两边同时左乘 ，并结合式（，并结合式（5.20）和）和 ，于是有于是有 TP001t010APPT（5.23） 这就是为这就是为 使直指极小点所必须满足的条件显然式使直指极小点所必须满足的条件显然式（5.23）中）中 和和 是是 的共轭向量的共轭向量 1P0P1PA第五章第五章 常用无约束优化方法常用无约束优化方法下面来求下面来求 的表达式，设的表达式，设 1P0011)(PXfP（5.24） 式式(5.24)两边同时左乘两边同时左乘 ，有，有 APT00)(0001010APPXfAPAPPTTT由此解出由此解出00100)(APPXfAPTT代回到式（代回到式（5.24），得），得0001011)()(PAPPXfAPXfPTT第五章第五章 常用无约束优化方法常用无约束优化方法一般地，在一般地，在n维空间中可以找出维空间中可以找出n个互相共轭的方向，个互相共轭的方向，对于对于n元正定二次函数，从任意初始点出发，顺次沿元正定二次函数，从任意初始点出发，顺次沿这这n个共轭方向最多作个共轭方向最多作n次直线搜索就可以求得目标函次直线搜索就可以求得目标函数的极小点这就是共轭方向法的算法形成的基本思数的极小点这就是共轭方向法的算法形成的基本思想想 对于对于n元正定二次目标函数，从任意初始点出发，如果元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那末这种算法称经过有限次迭代就能够求得极小点，那末这种算法称为具有二次终止性例如为具有二次终止性例如Newton法对于二次函数只须法对于二次函数只须经过一次迭代就可以求得极小点，因此是二次终止的；经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性共轭方向法（包括而最速下降法不具有二次终止性共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的一般来说，共轭梯度法，变尺度法等）是二次终止的一般来说，具有二次终止性的算法，在用于一般函数时，收敛速具有二次终止性的算法，在用于一般函数时，收敛速度较快度较快 第五章第五章 常用无约束优化方法常用无约束优化方法迭代步骤迭代步骤 已知具有正定矩阵已知具有正定矩阵 的二次目标的二次目标函数函数 和终止和终止限限 AcXbAXXXfTT21)(（1）选定初始点）选定初始点 和具有下降和具有下降的方向的方向 ，置，置 0X0P0k（2）作直线搜索）作直线搜索 ),(1kkkPXlsX（3）判别是否满足）判别是否满足 ：若满足，则打印若满足，则打印 ，结束；否，结束；否则转（则转（4） |)(|1kXf1kX（4）提供共轭方向）提供共轭方向 使得使得 1kPkjAPPkTj，21001（5） ，转（，转（2） 1 kk第五章第五章 常用无约束优化方法常用无约束优化方法5.5 共轭梯度法共轭梯度法如果在共轭方向法中初始的共轭向量如果在共轭方向法中初始的共轭向量 恰好取为初始点恰好取为初始点 处的负梯度处的负梯度 ，而以下各共轭方向，而以下各共轭方向 由第由第 迭代点迭代点 处的负梯度处的负梯度 与已经得到的共轭向量与已经得到的共轭向量 的线的线性组合来确定，那么就构成了一种具体的共轭方向性组合来确定，那么就构成了一种具体的共轭方向法因为每一个共轭向量都是依赖于迭代点处的负梯度法因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为而构造出来的，所以称为共轭梯度法共轭梯度法 0P0X)(00XfgkPkkXkg1kP基本原理基本原理 设从任意点设从任意点 出发，第一个搜索方向取为出发，第一个搜索方向取为 处的负梯处的负梯度方向度方向 . 0X0X00()Pf X 当搜索得到点当搜索得到点 后，设以下按后，设以下按 1kX11()0 12kkkkPf XPkn ， ， ，来产生搜索方向来产生搜索方向 第五章第五章 常用无约束优化方法常用无约束优化方法为了使选择为了使选择 所产生的所产生的 和和是是 共轭，以共轭，以 右乘上式的两边，于是有右乘上式的两边，于是有(0 12)kkn， ， ，1kP(0 12)kPkn， ， ，AkAPkTkkkTkkTkAPPAPXfAPP)(11因为因为 01kTkAPP故故 210)(1nkAPPAPXfkTkkTkk，这样，就可以生成这样，就可以生成n个方向：个方向： . 210)(, 210,)(),(11100nkAPPAPXfnkPXfPXfPkTkkTkkkkkk，（5.25） 第五章第五章 常用无约束优化方法常用无约束优化方法式（式（5.25）中含有问题（）中含有问题（5.13）的目标函数系数矩阵，）的目标函数系数矩阵，这对于目标函数是非二次函数的问题是不方便的通这对于目标函数是非二次函数的问题是不方便的通过简化，一般可以利用目标函数的梯度信息，来产生过简化，一般可以利用目标函数的梯度信息，来产生n个共轭方向个共轭方向0011212()()0 12|()|0 12|()|kkkkkkkPf XPf XPknf Xknf X ， ， ， ， ，由此得共轭梯度法由此得共轭梯度法第五章第五章 常用无约束优化方法常用无约束优化方法迭代步骤迭代步骤 已知目标函数已知目标函数 ，终止限，终止限 )(Xf0（1）选取初始点）选取初始点 ，给定终止限，给定终止限 0X0（2）求初始梯度计算）求初始梯度计算 ，若，若 ，停止迭，停止迭 代输出代输出 ，否则转（，否则转（3） )(0Xf|)(|0Xf0X（3）构造初始搜索方向取）构造初始搜索方向取 ，令，令 ，转（，转（4） )(00XfP0k（4）进行一维搜索求）进行一维搜索求 使得使得 kt)(min)(0kktkkktPXfPtXf令令 ，转（，转（5） kkkkPtXX1（5）求梯度向量计算）求梯度向量计算 ，若，若 ，停止迭代，停止迭代 输出输出 否则转（否则转（6） )(1kXf|)(|Xf1kX（6）检验迭代次数若）检验迭代次数若 ，令，令 ，转（，转（3），否），否 则转（则转（7） nk1kXX0（7）构造共轭方向取）构造共轭方向取 ， 212|()|()|kkkf Xf X11()kkkkPf XP 令令 ，转（，转（4） 1 kk第五章第五章 常用无约束优化方法常用无约束优化方法第五章第五章 常用无约束优化方法常用无约束优化方法例例5.3 用共轭梯度法求用共轭梯度法求222125)(minxxXf其中其中 ，选初始点为，选初始点为 12TXx x，601022，TX解解 1004)(00XfP0100000242421002100tXXt Ptt 22min(24 )25(2 100 ) min ( )ttt13.83975()0.15359f X( )500032100160dttdt令令 00.020037t 11.919880.00307X 21020|()|14.767320.001472|()|10016f Xf X 第五章第五章 常用无约束优化方法常用无约束优化方法1100()3.8397540.0014720.153591003.845650.00615Pf XP 则则 2111.919883.845650.003070.00615tXXt Pt故故 11()29.5799714.767300df Xt Ptdt令令 0.49923t 0000615. 084565. 349923. 000307. 091988. 11112PtXX 62100|)(|Xf由于由于 TXX0, 02* 第五章第五章 常用无约束优化方法常用无约束优化方法有关说明有关说明 实际上，可以把共轭梯度法看作是最速下降法的一实际上，可以把共轭梯度法看作是最速下降法的一种改进当种改进当 时，就变为最速下降法时，就变为最速下降法0k共轭梯度法由于不涉及矩阵，仅仅存储向量，因共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题而存储量小，适合于维数较高的优化问题另外，共轭梯度法不要求精确的直线搜索但是，另外，共轭梯度法不要求精确的直线搜索但是，不精确的直线搜索可能导致迭代出来的向量不再共不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能克服的办法是，重设初轭，从而降低方法的效能克服的办法是，重设初始点，即把经过始点，即把经过n次迭代得到的次迭代得到的Xn作为初始点重新作为初始点重新迭代迭代 第五章第五章 常用无约束优化方法常用无约束优化方法5.6 变尺度法变尺度法我们知道我们知道Newton法最突出的优点是收敛速度快，在这法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的因此，建议凡是一点上其它算法无法比拟的因此，建议凡是Hesse矩矩阵比较容易求出的问题尽可能使用阵比较容易求出的问题尽可能使用Newton法求解然法求解然而而Newton法还有一个严重缺陷，就是每次迭代都要计法还有一个严重缺陷，就是每次迭代都要计算目标函数的算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了较大时，计算量迅速增加，从而就抵消了Newton法的法的优点为此，人们开始寻找一种算法既可以保持优点为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可以摆脱关于法收敛速度快的优点，又可以摆脱关于Hesse矩矩阵的计算，这就是本节要给大家介绍的阵的计算，这就是本节要给大家介绍的变尺度算法变尺度算法 变尺度法是一种非常好的方法其中变尺度法是一种非常好的方法其中DFP算法算法和和BFGS算法算法，可以说直到目前为止是在不用，可以说直到目前为止是在不用Hesse矩阵的方法矩阵的方法中最好的算法中最好的算法 第五章第五章 常用无约束优化方法常用无约束优化方法一、变尺度法基本原理一、变尺度法基本原理 Newton法在基本迭代公式法在基本迭代公式 中，中， ， 。记。记kkkkPtXX11kt)()(12kkkXfXfP)()(2kkkkXfgXfG， 则则 ，21011kgGXXkkkk（5.26） 为了消除迭代公式为了消除迭代公式(5.26)中的中的Hesse逆矩阵逆矩阵 ,可用某种可用某种近似矩阵近似矩阵 来替换它，即构造一个矩阵序列来替换它，即构造一个矩阵序列去逼近去逼近Hesse逆矩阵序列逆矩阵序列 此时式（此时式（5.26）变为）变为1kG)(kkXHHkH1kGkkkkgHXX1为了取得更大的灵活性，我们考虑更一般的迭代公式为了取得更大的灵活性，我们考虑更一般的迭代公式kkkkkgHtXX1（5.27） 式（式（5.27）是一类更很广泛的迭代公式例如，当）是一类更很广泛的迭代公式例如，当 ，它变为最速下降法的迭代公式，它变为最速下降法的迭代公式 IHk第五章第五章 常用无约束优化方法常用无约束优化方法为使为使 与与 近似近似,并且有容易计算的特点，必须对附并且有容易计算的特点，必须对附加某些条件：加某些条件：kH1kG第一，为保证迭代公式具有下降性质，要求第一，为保证迭代公式具有下降性质，要求 中的每中的每一个矩阵都是对称正定的一个矩阵都是对称正定的 kH理由是，为使搜索方向理由是，为使搜索方向 是下降方向，只要是下降方向，只要kkkgHP0kkTkkTkgHgPg成立即可，即成立即可，即0kkTkgHg成立当成立当 对称正定时，此式必然成立，从而保证式对称正定时，此式必然成立，从而保证式（5.27）具有下降性质）具有下降性质 kH第二，要求第二，要求 之间的迭代具有简单形式而之间的迭代具有简单形式而 kHkkkEHH1（5.28） 是最简单的形式是最简