第四章_常用无约束最优化方法

1、Company Logo4.3修正修正NewtonNewton法法共轭方向法共轭方向法共轭梯度法共轭梯度法变尺度法变尺度法坐标轮换法坐标轮换法第四章第四章 常用无约束最优化方法常用无约束最优化方法最速下降法最速下降法Newton Newton 法法单纯形法单纯形法Company Logo成立点成立点 就是问题（就是问题（4.14.1）的全局最优点但是，大多数）的全局最优点但是，大多数最优化方法只能求到局部最优点，即在最优化方法只能求到局部最优点，即在 中找到一点中找到一点 ，使得式（使得式（4.2)4.2

2、)在在 的某个领域中成立的某个领域中成立第四章第四章 常用无约束最优化法常用无约束最优化法 本章开始讨论多维无约束最优化问题本章开始讨论多维无约束最优化问题 （4.14.1）其中其中 这个问题的求解是指，在这个问题的求解是指，在 中找一中找一点点 ，使得对于任意的，使得对于任意的 都有都有 （4.24.2）)(minXf1RRfn：nR*XnRX )()(*XfXf*XnR*X*XCompany Logo 这个矛盾对于实际问题来讲一般容易解决，因为根据问题这个矛盾对于实际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解的实际意义多半可以直接判定用优化方法求

3、出的局部最优解是否为全局最优解但在理论上这是个比较复杂的问题，本是否为全局最优解但在理论上这是个比较复杂的问题，本书不涉及书不涉及 无约束优化方法是优化技术中极为重要和基本的内容之无约束优化方法是优化技术中极为重要和基本的内容之一它不仅可以直接用来求解无约束优化问题，而且很多约一它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解另外，有些无约束优化方法只需略加处理，优化方法来求解另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题即可用于求解约束优化问题Company

4、Logo 无约束优化理论发展较早，比较成熟，方法也很多，新的无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用一类是仅用计算函数值所得到的信息来确定搜索方向计算函数值所得到的信息来确定搜索方向，通常，通常称它为称它为直接搜索法直接搜索法，简称为，简称为直接法直接法，另一类需要，另一类需要计算函数的计算函数的一阶或二阶导数值所得到的信息来确定搜索方向一阶或二阶导数值所得到的信息来确定搜索方向，这一类方，这一类方法称为法称为间接法（或解析法间接法（或解析法）直接法不涉及）直接法不涉及导数和

5、导数和HesseHesse矩阵矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算但需计算梯度，甚至需要计算HesseHesse矩阵一般的经验是，在矩阵一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法况下，当然就应该使用直接法Company Logo 一、最速下降法基本原理一、最速下降法基本原理 在基本迭代公

6、式在基本迭代公式 中，每次迭代搜索中，每次迭代搜索 方向取为目标函数方向取为目标函数 的负梯度方向，即的负梯度方向，即 ，而每次迭代的步长而每次迭代的步长 取为最优步长，由此所确定的算法取为最优步长，由此所确定的算法称为最速下降法称为最速下降法 对于问题（对于问题（4.14.1）为了求其最优解，按最优化算法的基）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点本思想是从一个给定的初始点 出发，通过基本迭代公出发，通过基本迭代公式式 ，按照特定的算法产生一串，按照特定的算法产生一串点列点列 ，如果点列收敛，则该点列的极限点为问题，如果点列收敛，则该点列的极限点为问题（4.14.1）的最

7、优解）的最优解4.1 4.1 最速下降法最速下降法0XkkkkPtXX1kXkkkkPtXX1kP)(Xf)(kkXfPktCompany Logo 为了求解问题（为了求解问题（4.14.1），如图），如图4.14.1所示，假定我们已经迭所示，假定我们已经迭代了代了 次，获得了第次，获得了第 个迭代点个迭代点 现在从现在从 出发，可出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在向（即负梯度方向）进行搜索应该是有利的，至少在 邻邻近的范围内是这样因此，取搜索方向为近的范围内是这样因此，

8、取搜索方向为 kkkXkXkX)(kkXfP图图4.14.1Company Logo 为了使目标函数在搜索方向上获得最多的下降，沿为了使目标函数在搜索方向上获得最多的下降，沿 进行进行一维搜索，由此得到第一维搜索，由此得到第 个迭代点个迭代点 ，即，即 ， 其中步长因子其中步长因子 按下式确定按下式确定 ，也可记为也可记为 （4.34.3） 显然，令显然，令 就可以得到一个点列就可以得到一个点列 ，其中其中 是初始点，由计算者任意选定当是初始点，由计算者任意选定当 满足一定的条满足一定的条件时，由式（件时，由式（4.34.3）所产生的点列）所产生的点列 必收敛于必收敛于 的极小的极小点点 kP

9、1k1kX)(1kkkkXftXXkt)(min)(kktkkkXftXfXftXf)(,(1kkkXfXlsX, 2, 1, 0k210,XXX0X)(XfkX)(Xf*XCompany Logo 以后为书写方便，记以后为书写方便，记 因因此，此， 在不发生混淆时，在不发生混淆时，再记再记 )()(XfXg)()(kkXfXg)()(kkkXfXggCompany Logo 已知目标函数已知目标函数 及其梯度及其梯度 ，终止限，终止限 、 和和 （1 1）选定初始点）选定初始点 ，计算，计算 ， ； 置置 （2 2）作直线搜索：）作直线搜索： ；计算；计算 ， （3 3）用终止准则检测是否满

10、足：若满足，则打印最优）用终止准则检测是否满足：若满足，则打印最优解解 ， ，结束；否则，置，结束；否则，置 ，转，转（2 2）最速下降法算法流程如图最速下降法算法流程如图4.24.2所示所示 二、最速下降法迭代步骤二、最速下降法迭代步骤)(Xf)(Xg1230X)(00Xff)(00Xgg 0k),(1kkkgXlsX)(11kkXff)(11kkXgg1kX)(1kXf1kk，Company Logo开始结束选定X0YX ， fH准则满足)()(0000XggXff),(00gXlsX)()(XggXffggffXX000最速下降法算最速下降法算法流程如图所法流程如图所示示图图4.24.2

11、Company Logo 设第设第 次迭代点为次迭代点为 ，我们来求，我们来求 的表达式对式的表达式对式(4.4)(4.4)关于求关于求 梯度，有梯度，有 ，(4.5)(4.5)因此，因此， (4.6)(4.6)现在从现在从 出发沿出发沿 作直线搜索以确定作直线搜索以确定 ，于是，于是 ， (4.7)(4.7)其中其中 是最优步长因子是最优步长因子 将最速下降法应用于正定二次函数将最速下降法应用于正定二次函数 （4.44.4）可以推出显式迭代公式可以推出显式迭代公式cXbAXXXfTT21)(kkX1kXXbAXXg)(bAXXggkkk)(kXkg1kXkkkkgtXX1ktCompany

12、Logo 又因式（又因式（4.24.2），有），有 ，再利用式，再利用式（4.54.5），式（），式（4.64.6）和式（）和式（4.74.7）可得）可得或或 由此解出由此解出 ，代入式（代入式（4.74.7）中得到）中得到 . .（4.84.8）这就是最速下降法用于二次函数的显式迭代公式这就是最速下降法用于二次函数的显式迭代公式0)(1kTkgXg0)(kTkkkgbgtXA0kTkkkgAgtgkTkkTkkAggggtkkTkkTkkkgAggggXX1Company Logo例例4.1 试用最速下降法求函数试用最速下降法求函数 的极小点迭代两次，计算各迭代点的函数值，梯度及的极小点迭代

13、两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点其模，并验证相邻两个搜索方向是正交的设初始点为为 2221214),(xxxxfTX 1, 1 0Company Logo解解 与式（与式（4.44.4）比较，得）比较，得 ，梯度表达式是梯度表达式是 ，由由 ，计算出，计算出 ， ， 因为目标函数是二次的，可以使用式（因为目标函数是二次的，可以使用式（4.84.8），所以有），所以有 ，8002A212182),()(xxxxfXfTX 11 0，5141)(220 xf82)(00Xfg24621. 8|0g04616. 073846. 08213077. 011

14、0000001gAggggXXTTCompany Logo计算计算 因为因为 由此说明相邻两个搜索方向由此说明相邻两个搜索方向 与、与、 , 与与 是正交的是正交的，55385. 004616. 0473846. 0)(221Xf，52237. 136923. 047692. 1)(111gXfg11076. 011076. 036923. 047692. 142500. 004616. 073846. 01111112gAggggXXTT，91335. 088008. 022152. 0)(06134. 0)(2221gXfgXf10210.00000.0000TTgggg，11gP00gP

15、22gP11gPCompany Logo三、最速下降法有关说明三、最速下降法有关说明 最速下降法的优点是算法简单，每次迭代计算量小，占用内最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢小点，但它有一个严重缺点就是收敛速度慢 图图4.34.3沿负梯度方向函数值下降很快的说法，容易使人们产生沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索

16、时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快特敛速度应该很快，然而事实证明，梯度法的收敛速度并不快特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢慢Company Logo其原因是由于每次迭代后下一次搜索方向总是与其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象（如图生所谓的锯齿现象（如图4.34.3所示）即从直所示）即从直观上看，在远离极小点的地方每次迭代可能使观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在

17、接近极小点的目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快距离缩短，因而收敛速度不快图图4.34.3Company Logo4.2 Newton4.2 Newton法法 如果目标函数如果目标函数 在在 上具有连续的二阶偏导数，上具有连续的二阶偏导数，其其HesseHesse矩阵矩阵 正定并且可以表达成为显式（今后为正定并且可以表达成为显式（今后为了简便起见，记了简便起见，记 ，那么可以使用下述，那么可以使用下述的的NewtonNewton法这种方法一旦好用，收敛速度是很快法这种方法一旦好用，收敛

18、速度是很快的它是一维搜索的它是一维搜索NewtonNewton切线法的推广切线法的推广)(XfnR)(XG)()(2XfXG图图4.44.4Company Logo 下面具体讨论下面具体讨论NewtonNewton法法 设最优化问题为设最优化问题为 ，其中，其中 二阶可导，二阶可导，HesseHesse矩阵矩阵 正定正定不妨设经过不妨设经过 次迭代已获点次迭代已获点 ，现将，现将 在在 处展成处展成二阶泰勒公式，于是有二阶泰勒公式，于是有 一、一、NewtonNewton法基本原理法基本原理 为寻求收敛速度快的算法，我们考虑在应用基本迭代公式为寻求收敛速度快的算法，我们考虑在应用基本迭代公式

19、中，每轮迭代在迭代的起始点中，每轮迭代在迭代的起始点 处用一个适当的二次函数来近似处用一个适当的二次函数来近似该点处的目标函数，由此用点该点处的目标函数，由此用点 指向近似二次函数极小点的方向指向近似二次函数极小点的方向来构造搜索方向来构造搜索方向 （如图（如图4.44.4所示）所示）kkkkPtXX1kXkXkP)(minXf1RRfn：)(2XfkkX)(XfkXX Company Logo 显然显然 是二次函数，特别由假设知是二次函数，特别由假设知 还是正定二次函还是正定二次函数，所以数，所以 是凸函数且存在唯一全局极小点为求此极小点，是凸函数且存在唯一全局极小点为求此极小点，令令即可解

20、得即可解得 ，亦即亦即 .)()(21)()()()()(2kkTkkTkkXXXfXXXXXfXfXQXf)(XQ)(XQ)(XQ0)()()(2kkkXXXfXfXQ)()(12kkkXfXfXX，)()(121kkkkXfXfXX(4.9)Company Logo对照基本迭代公式对照基本迭代公式易知，式（易知，式（4.94.9）中的搜索方向）中的搜索方向 ，步长因子步长因子 换句话说从点换句话说从点 出发沿搜索方向出发沿搜索方向并取步长并取步长 即可得即可得 的极小点的极小点 因此，因此，是直指点是直指点 处近似二次函数处近似二次函数 的极小点的方向的极小点的方向kkkkPtXX1)()

21、(12kkkXfXfP1ktkX)()(12kkkXfXfP1kt)(XQ1kX)()(12kkkXfXfPkX)(XQCompany Logo此时称此时称为从点为从点 出发的出发的NewtonNewton方向从初始点开始，每一轮方向从初始点开始，每一轮从当前迭代点出发，沿从当前迭代点出发，沿NewtonNewton方向并取步长方向并取步长 的的算法称为算法称为NewtonNewton法法)()(12kkkXfXfPkX1ktCompany Logo二、二、NewtonNewton法迭代步骤法迭代步骤已知目标函数已知目标函数 及其梯度及其梯度 ，HesseHesse矩阵矩阵 ，终止限终止限 （

22、1 1）选定初始点）选定初始点 ；计算；计算 ；置置 （2 2）计算）计算 （3 3）由方程）由方程 解出解出 （4 4）计算）计算 （5 5）判别终止准则是否满足：若满足，则打印最优）判别终止准则是否满足：若满足，则打印最优解解 ， 结束；否则，置结束；否则，置 ，转（，转（2 2） NewtonNewton法的流程如图法的流程如图4.54.5所示所示)(Xf)(Xg)(XG0X)(),(0000XggXff0k)(2kkXfGkkkgPGkP，)(111kkkkkXffPXX)(11kkXgg1kX1kf1kkCompany Logo开始结束选定X0N求解方程H准则满足X , f)()(0

23、000XggXff)(0XGG 0gGP)()(0XggXffPXXggffXX000NewtonNewton法的流法的流程如图所示程如图所示图图4.54.5Company Logo解解 梯度为梯度为 ，HesseHesse矩阵为矩阵为 ，其逆矩阵为其逆矩阵为 由迭代公式（由迭代公式（4.134.13）得第）得第1 1 迭代点为迭代点为由于此时由于此时 ，停止迭代得，停止迭代得 ，因此，它就是极小点因此，它就是极小点 例例4.2 4.2 试用试用NewtonNewton法求法求 的的极小点，初始点取为极小点，初始点取为 2221214)(xxxxf，TX 1, 1 0TxxXfXg82)()(

24、21，8002)(XG125. 0005 . 0)(1XG11000()()10.502000.125180XXG Xg X 61100|)(|XfTXX 00 1*，Company Logou从上述例从上述例4.24.2我们看到，用我们看到，用NewtonNewton法求解，只经一轮迭法求解，只经一轮迭代就得到最优解代就得到最优解u这一结果并不是偶然的，因为从这一结果并不是偶然的，因为从NewtonNewton方向的构造我方向的构造我们知道，对于正定二次函数，们知道，对于正定二次函数，NewonNewon方向就是指向其极方向就是指向其极小点的方向小点的方向u因此，用因此，用NewtonNew

25、ton法解目标函数为正定二次函数的无约法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解束最优化问题，只需一次迭代就可得最优解Company Logou 对于目标函数是非二次函数的非约束最优化问题，一般地说，对于目标函数是非二次函数的非约束最优化问题，一般地说，用用NewtonNewton法通过有限轮迭代并不能保证可求得最优解但由于法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用最优解的初始点使用NewtonNewton法求解时，其收敛速度一般是快法求解

26、时，其收敛速度一般是快的的u 事实上，可以证明在初始点离最优解不远的条件下，事实上，可以证明在初始点离最优解不远的条件下，NewtonNewton法是二次收敛的但是当初始点选得离最优解太远时，法是二次收敛的但是当初始点选得离最优解太远时，NewtonNewton法并不一定是收敛的方法，甚至连其下降性也很难保证法并不一定是收敛的方法，甚至连其下降性也很难保证Company Logou NewtonNewton法收敛速度非常快具有二次收敛的优点，但它存在下法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：面四个严重的缺点：u（1 1）尽管每次迭代不会使目标函数）尽管每次迭代不会使目标

27、函数 上升，但仍不能保上升，但仍不能保证证 下降当下降当HesseHesse矩阵非正定时，矩阵非正定时，NewtonNewton法的搜索将会法的搜索将会失败失败u（2 2）对初始点要求严格一般要求比较接近或有利于接近极）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的值点，而这在实际计算中是比较难办的)(Xf)(XfCompany Logo（3 3）在进行某次迭代时可能求不出搜索方向由于搜索方）在进行某次迭代时可能求不出搜索方向由于搜索方向为向为若目标函数在若目标函数在 点点HesseHesse矩阵为奇异，则求不矩阵为奇异，则求不出出 ，因而不有构成牛顿方向，从

28、而使，因而不有构成牛顿方向，从而使迭代无法进行迭代无法进行（4 4）牛顿方向构造困难，计算相当复杂，除了求梯度以外）牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算还需计算HesseHesse矩阵及其逆矩阵，占用机器内存相当大矩阵及其逆矩阵，占用机器内存相当大)()(12kkkXfXfPkX12)(kXfCompany Logo4.3 4.3 修正修正NewtonNewton法法 为了克服为了克服NewtonNewton法的缺点，人们保留选法的缺点，人们保留选NewtonNewton方向作方向作为搜索方向，摒弃其步长恒取为搜索方向，摒弃其步长恒取1 1，而用一维搜索确定最优，而用一维搜索

29、确定最优步长，由此产生的算法称为修正步长，由此产生的算法称为修正NewtonNewton法（或阻力法（或阻力NewtonNewton法）法）Company Logo已知目标函数已知目标函数 及其梯度及其梯度 HesseHesse矩阵矩阵 终止限终止限 （1 1）选取初始点）选取初始点 令令（2 2）求梯度向量计算）求梯度向量计算 ，若若 ，停止迭代输出，停止迭代输出 否则，转（否则，转（3 3）（3 3）构造）构造NewtonNewton方向计算方向计算 ， 取取（4 4）进行一维搜索求）进行一维搜索求 ，使得，使得 令令 ，转（，转（2 2） 修正修正NewtonNewton法的流程如图法的

30、流程如图4.64.6所示所示)(Xf)(Xg)(XG0X0k)()(kkXfXg|)(|kXfkX121)()(kkXfXG)()(12kkkXfXfPkt)(min)(0kktkkktPXfPtXf1,1kkPtXXkkkk令Company Logok=0计算 求 使 计算开始结束选定YN0,0X()kf X()kf X21()kf X)()(12kkkXfXfPkt)(min)(0kktkkktPXfPtXf1,1kkPtXXkkkkkX修正修正NewtonNewton法的法的流程如图所示流程如图所示图图4.64.6Company Logo 修正修正NewtonNewton法克服了法克服了

31、NewtonNewton法的缺点特别是，当法的缺点特别是，当 迭代点接近于最优解时，此法具有收敛速度快的优点，迭代点接近于最优解时，此法具有收敛速度快的优点， 对初始点的选择要求不严对初始点的选择要求不严 但是，修正但是，修正NewtonNewton法仍需要计算目标函数的法仍需要计算目标函数的HesseHesse矩矩 阵和逆矩阵，所以求解的计算量和存贮量均很大阵和逆矩阵，所以求解的计算量和存贮量均很大. .另外，另外， 当目标函数的当目标函数的HesseHesse矩阵在某点处出现奇异时，迭代将矩阵在某点处出现奇异时，迭代将 无法进行，因此修正无法进行，因此修正NewtonNewton法仍有相当

32、的局限性法仍有相当的局限性Company Logou构成各种不同最优化方法，往往取决于如何从基本迭代公式构成各种不同最优化方法，往往取决于如何从基本迭代公式 中中 确定搜索方向确定搜索方向u在最速下降法中，由于取在最速下降法中，由于取 从而导致搜索路线从而导致搜索路线出现锯齿状，收敛速度降低；出现锯齿状，收敛速度降低；u而在而在NewtonNewton法中，由于选取法中，由于选取 收敛速度收敛速度虽很快，但计算量很大，特别是还要求虽很快，但计算量很大，特别是还要求HesseHesse矩阵正定，从而导矩阵正定，从而导致该算法对初始点选择要求过严致该算法对初始点选择要求过严u下面我们将给大家介绍一

33、种新的最优化方法，它的计算量小，收下面我们将给大家介绍一种新的最优化方法，它的计算量小，收敛速度没有敛速度没有NewtonNewton法快，但比最速下降法快得多的新算法，称为法快，但比最速下降法快得多的新算法，称为共轭方向法共轭方向法kkkkPtXX1kP)(kkXfP)()(12kkkXfXfPCompany Logo 首先介绍共轭方向概念及其些性质首先介绍共轭方向概念及其些性质 定义定义4.14.1 设设 是对称矩阵是对称矩阵, ,对于非零向量对于非零向量若有若有 (4.10),(4.10),则称则称 与与 相互相互 共轭或共轭或 正交正交的的 对于非零向量组对于非零向量组 , ,若有若有

34、 (4.11) (4.11)则称则称 是是 共轭方向组或共轭方向组或 正交方向组，也称正交方向组，也称 它们是一组它们是一组 的共轭方向的共轭方向nnRAnRPP21，021APPT1P2PAA) 1210(niRPni，, 1, 2 , 1 , 0, 0jinjiAPPjTi110nPPP， AAACompany Logo 在上述定义中若在上述定义中若 ( ( 阶单位矩阵阶单位矩阵) )，则式（，则式（4.104.10）和式（和式（4.114.11）成为）成为 和和 由此可知，共轭概念是正交概念的推广，共轭方向是正交方向由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广的推广定理定

35、理4.14.1 设设 是正定矩阵，是正定矩阵， 是非零向量若是非零向量若 是是 一组一组 共轭方向，则共轭方向，则它们是线性无关的它们是线性无关的nIAn021PPT)(0jiPPjTinnRA) 110(niRPni，110nPPP， ACompany Logo证明证明 设有一组实数设有一组实数 , ,使得使得 . .依次以依次以 左乘上式得到左乘上式得到 ,(4.12),(4.12)因为因为 是一组是一组 的共轭方向，故有的共轭方向，故有 又由于又由于A A是正定矩阵，所以对于是正定矩阵，所以对于 有有 把以上两式用于式（把以上两式用于式（4.124.12），便可推知），便可推知由此证明由

36、此证明 是线性无关是线性无关110n，0111100nnPPP) 110(niAPTi， 101100njjTijniAPP，110nPPP， AjinjiAPPjTi, 1, 2 , 1 , 0, 0），（1100niPi1100niAPPiTi，1100nii，110nPPP，Company Logo 考虑以二次函数为目标函数的无约束极小化问题考虑以二次函数为目标函数的无约束极小化问题 ,(4.13) ,(4.13)其中其中 是对称正定矩阵是对称正定矩阵 有如下定理：有如下定理： 定理定理4.24.2 设设 是对称正定矩阵，是对称正定矩阵， 是一组是一组 的共轭方向的共轭方向. .对于问题

37、（对于问题（4.134.13）, ,若从任意点若从任意点 出发依次沿出发依次沿 进行一维搜索，则至多经过进行一维搜索，则至多经过 轮迭代，可得问题（轮迭代，可得问题（4.134.13）的最优解）的最优解cXbAXXXfTT21)(minnnRA1RcRbn，nnRAnnRPPP110， AnRX 0110nPPP，nCompany Logo 证明证明 设从点设从点 出发依次按方向出发依次按方向 进行一维搜进行一维搜索产生的迭代点是索产生的迭代点是 , , 其中最优步长其中最优步长 是通过下式来确定是通过下式来确定又由又由 和式（和式（4.144.14）可推知）可推知即即利用式（利用式（4.16

38、4.16）有）有 0X110nPPP，kkkkPtXX1110nk， kt)(min)(min)(0ttPXfPtXfkktkkk110nk， bAXXf)(kkkkkkkkAPtbAXbPtXAbAXXf)()(111210)()(1nkAPtXfXfkkkk，(4.14)(4.14)(4.15)(4.15)(4.16)(4.16)，kjAPtXfAPtAPtXfXfkjiiijkkkkkk210)()()(1111Company Logo对上式右乘对上式右乘 可得可得因为因为 是是 共轭方向，故得共轭方向，故得 或或 . .另外，由式（另外，由式（4.154.15）可知）可知 jP，kjA

39、PPtPXfPXfkjijTiijTjjTk210)()(1) 1, 1, 0(niPiAjTjjjjTjjjTjjTkPAPtXfAPPtPXfPXf)()()(111()()01TTkjjjf XPf XP jk， ，1100| )(njtPXfdtdjttjj(4.17)(4.17)(4.18)(4.18)Company Logo因为因为所以由式（所以由式（4.184.18）有）有由式（由式（4.174.17）和上式，对于）和上式，对于 我们得到我们得到特别地，当特别地，当 时有时有 . .由于由于 是一组是一组 的共轭方向的共轭方向, ,由定理由定理4.14.1知它们知它们是线性无关的

40、是线性无关的, ,因而向量因而向量 可表示为这些向量的线性组合可表示为这些向量的线性组合 , ,其中其中 是实数是实数 . .jTjjttTjjttjjPXfPtPXftPXfdtdjj)(|)(| )(11()00 11Tjjf XPjn， ， ，0 11kn， ，1()00 1Tkjf XPjk， ， ，1 nk()00 11Tnjf XPjn， ， ，110nPPP， A)(nXf10)(njjjnPXfj0 11jn， ， ，(4.19)(4.19)Company Logo所以由式（所以由式（4.194.19）有）有 , ,即有即有 于是得于是得 , ,即即 是是 的驻点又因为的驻点又

41、因为 是对称正定，故是对称正定，故 是凸函是凸函数，因而数，因而 是问题（是问题（4.134.13）的最优解）的最优解这说明，至多经过这说明，至多经过 次迭代必可求得次迭代必可求得 (4.13)(4.13)的最优解的最优解. .10100)()()()(njnjjTnjjjTnnTnPXfPXfXfXf0|)(|2nXf0)(nXfnX)(XfA)(XfnXnCompany Logo 通常，我们把从任意点通常，我们把从任意点 出发出发, ,依次沿某组共轭方向进行依次沿某组共轭方向进行一维搜索的求解最优化问题的方法一维搜索的求解最优化问题的方法, ,叫做共轭方向法叫做共轭方向法 为了直观起见为了

42、直观起见, ,首先考虑二维情况现在我们把下降法用于形首先考虑二维情况现在我们把下降法用于形式为式为(4.13)(4.13)的二元二次函数的二元二次函数 任选初始点任选初始点 从从 出发沿某个下降方向出发沿某个下降方向 作一维搜索得作一维搜索得到到 ( (如图所示如图所示) )nRX 00X0X0P1X0XCompany Logo 由式（由式（4.24.2）知）知 而且向量而且向量 所在的直线必与某条等值线（椭圆）相切于所在的直线必与某条等值线（椭圆）相切于 点下一次迭代，如果按最速下降法选择负梯度方向为搜索方点下一次迭代，如果按最速下降法选择负梯度方向为搜索方向，那末将要发生锯齿现象向，那末将

43、要发生锯齿现象. . 为了克服这种现象，我们设想，下一次迭代的搜索方向将直为了克服这种现象，我们设想，下一次迭代的搜索方向将直指极小点指极小点 如果能够选定这样的搜索方向，那么对于二元如果能够选定这样的搜索方向，那么对于二元二次函数只须顺次进行两次直线搜索就可以求到极小点了二次函数只须顺次进行两次直线搜索就可以求到极小点了 下面来讨论这样的方向下面来讨论这样的方向 应该满足什么条件，怎样确定应该满足什么条件，怎样确定0)(01PXfT0P1X*X1P(4.20)(4.20)Company Logo 因为因为 直接指极小点直接指极小点 , ,所以可写成所以可写成 其中其中 是最优步长因子，显然，

44、当是最优步长因子，显然，当 时，时， . . 对（对（4.134.13）求导数，有）求导数，有 因为因为 是极小点，所以有是极小点，所以有 . .将式（将式（4.214.21）代入此式中，由（）代入此式中，由（4.224.22）可得）可得 . .等式两边同时左乘等式两边同时左乘 并注意到式并注意到式(4.20)(4.20)和和 , ,于是有于是有 1P*X111*PtXX1t*1XX 01tbAXXf)(*X0)(*bAXXf0)(111APtXfTP001t010APPT, (4.21), (4.21), (4.22), (4.22). (4.23). (4.23)Company Logo

45、这就是为使这就是为使 直指极小点所必须满足的条件显然直指极小点所必须满足的条件显然（4.234.23）中）中 和和 是是 的共轭向量由式（的共轭向量由式（4.204.20），不），不难给出难给出 的表达式设的表达式设 两边同时左乘两边同时左乘 ，有，有 . .由此解出由此解出 , , 代回到式代回到式 （4.244.24），得），得 . .1P0P1PA1P0011)(PXfPAPT00)(0001010APPXfAPAPPTTT00100)(APPXfAPTT0001011)()(PAPPXfAPXfPTT，(4.24)(4.24)Company Logo 一般地，在一般地，在 维空间中可以

46、找出维空间中可以找出 个互相共轭的方向，个互相共轭的方向，对于对于 元正定二次函数，从任意初始点出发，顺次沿这元正定二次函数，从任意初始点出发，顺次沿这 个个共轭方向最多作共轭方向最多作 次直线搜索就可以求得目标函数的极小次直线搜索就可以求得目标函数的极小点这就是共轭方向法的算法形成的基本思想点这就是共轭方向法的算法形成的基本思想nnnnnCompany Logo 对于对于 元正定二次目标函数，从任意初始点出发，如果元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那么这种算法称为具有二经过有限次迭代就能够求得极小点，那么这种算法称为具有二次终止性次终止性 例如例如Ne

47、wtonNewton法对于二次函数只须经过一次迭代就可以求得法对于二次函数只须经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性；极小点，因此是二次终止的；而最速下降法不具有二次终止性；共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的 一般来说，具有二次终止性的算法，在用于一般函数时，一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快收敛速度较快nCompany Logo 已知具有正定矩阵已知具有正定矩阵 的二次目标函数的二次目标函数 和终止限和终止限 （1 1）选定初始点）选定初始点 和具有下降的方

48、向和具有下降的方向 , ,置置 （2 2）作直线搜索）作直线搜索 . .（3 3）判别）判别 是否满足：若满足，则打印是否满足：若满足，则打印 , , 结束；否则转（结束；否则转（4 4）（4 4）提供共轭方向）提供共轭方向 使得使得 . .（5 5） ，转（，转（2 2）. . 共轭方向法的流程如图共轭方向法的流程如图4.74.7所示所示AcXbAXXXfTT21)(0X0P0k),(1kkkPXlsX|)(|1kXf1kX1kPkjAPPkTj，210011 kkCompany Logo )(1kXf k=0 提供共轭方向1kP使得 kjQPPkj, 1 ,0,01T ),(1kkskPX

49、lX 开始 停 1kX Y N k=k+1 选定,00PX 共轭方向法的流共轭方向法的流程如图所示程如图所示图图4.74.7Company Logo 上述算法针对二次目标函数，但也可用于一般的非二次函上述算法针对二次目标函数，但也可用于一般的非二次函数在求优过程中数在求优过程中 因舍入误差不能满足因舍入误差不能满足 时，可取时，可取 为新的初始点，再重复前面的过程为新的初始点，再重复前面的过程1kX0)(1kXf1kXCompany Logo5.5 5.5 共轭梯度法共轭梯度法 如果在共轭方向法中初始的共轭向量如果在共轭方向法中初始的共轭向量 恰好取为初始点恰好取为初始点 处的负梯度处的负梯度

50、 ，而以下各共轭方向，而以下各共轭方向 由第由第 迭代点迭代点 处的负梯度处的负梯度 与已经得到的共轭向与已经得到的共轭向量量 的线性组合来确定，那么就构成了一种具体的共轭方的线性组合来确定，那么就构成了一种具体的共轭方向法向法. . 因为一个共轭向量都是依赖于迭代点处的负梯度而构造出来因为一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法的，所以称为共轭梯度法0P0X)(00XfgkPkkXkg1kPCompany Logo设从任意点设从任意点 出发，第一个搜索方向取为出发，第一个搜索方向取为 处的负梯度方向处的负梯度方向 . .当搜索得到点当搜索得到点 后，设以下按后，

51、设以下按 来产生搜索方向来产生搜索方向为了使选择为了使选择 使所产生的使所产生的 和和 是是 的共轭，以的共轭，以 右乘上式的两边，于是有右乘上式的两边，于是有 . . 0X0X00()Pf X 1kX11()012kkk kPf XPkn， ，(0 12)kkn， ， ，1kP(012)kP kn， ，AkAPkTkkkTkkTkAPPAPXfAPP)(11Company Logo 因为要使因为要使 和和 是是 的共轭的共轭, , 应有应有 故由上式得故由上式得 综上所述，我们可以生成综上所述，我们可以生成 个个方向方向1kPkPA01kTkAPP210)(1nkAPPAPXfkTkkTkk

52、，n. 210)(, 210,)(),(11100nkAPPAPXfnkPXfPXfPkTkkTkkkkkk，(4.25)(4.25)Company Logo式（式（4.254.25）中含有问题（）中含有问题（4.134.13）的目标函数系数阵，这对于目标）的目标函数系数阵，这对于目标函数是非二次函数的问题是不方便的通过简化，一般地我函数是非二次函数的问题是不方便的通过简化，一般地我们可以利用目标函数的梯度信息，来产生们可以利用目标函数的梯度信息，来产生 个共轭方向个共轭方向由此得共轭梯度法算法由此得共轭梯度法算法n0011212()()012|()|012|()|kkk kkkkPf XPf

53、 XPknf Xknf X， ， ，Company Logo已知目标函数已知目标函数 ，终止限，终止限 （1 1）选取初始点）选取初始点 ，给定终止限，给定终止限 （2 2）求初始梯度计算）求初始梯度计算 ，若，若 ，停，停止迭代输出止迭代输出 ， 否则转（否则转（3 3）（3 3）构造初始搜索方向）构造初始搜索方向. .取取 , ,令令 , ,转转（4 4）（4 4）进行一维搜索求）进行一维搜索求 使得使得 , , 令令 ，转（，转（5 5） )(Xf00X0)(0Xf|)(|0Xf0X)(00XfP0kkt)(min)(0kktkkktPXfPtXfkkkkPtXX1Company Log

54、o（5 5）求梯度向量计算）求梯度向量计算 ，若，若 ，停止迭代输出停止迭代输出 否则转（否则转（6 6）. .（6 6）检验迭代次数若）检验迭代次数若 ，令，令 ，转（，转（3 3），）， 否则，转（否则，转（7 7）（7 7）构造共轭方向取）构造共轭方向取 , , 令令 ，转（，转（4 4）. .共轭梯度法的流程如图共轭梯度法的流程如图4.84.8所示所示)(1kXf|)(|Xf1kXnk1kXX0212|()|()|kkkf Xf X11()kkkkPf XP 1 kkCompany Logo结束求tk使计算开始X0选定YN构造初始搜索方向取计算Xk+1YNYN0,0X)(0Xf|)(|

55、0Xf00(),0Pf XkkkkkPtXX1)(1kXf|)(|Xfnk121112|()|,(),1|( )|kkkkk kkf XPf XP k kf X 取)(min)(0kktkkktPXfPtXf共轭梯度法的共轭梯度法的流程如图所示流程如图所示图图4.84.8Company Logo用共轭梯度法求用共轭梯度法求 ， 其中其中 ，选初始点，选初始点 . . 显然显然222125)(minxxXf12TXx x，6010 22，TX0001000002201104()100242421002100min(24 )25(2100 ) min( )( )5000321001600.0200

56、371.919883.83975()0.003070.15359PfXtXXt PtttttdttdttXfX 令则，2120|() |14.767320.001472|() |10016fXfXCompany Logo所以新的搜索方向所以新的搜索方向由此，有由此，有 , ,并且可推知并且可推知 , , . .因而得下一迭代点因而得下一迭代点由于由于 停止迭代输出所求得停止迭代输出所求得 . . 1100()3.8397540.0014720.153591003.845650.00615PfXP 2111.919883.845650.003070.00615tXXt Pt11()29.5799

57、714.767300df Xt Ptdt0.49923t 0000615. 084565. 349923. 000307. 091988. 11112PtXX62100|)(|XfTXX0, 02* Company Logo例例4.34.3的迭代的路径如图所示的迭代的路径如图所示Company Logo 实际上实际上, ,可以把共轭梯度法看作是最速下降法的一种改进可以把共轭梯度法看作是最速下降法的一种改进. .当当令令 时时, ,就变为最速下降法就变为最速下降法. . 共轭梯度法由于不涉及矩阵共轭梯度法由于不涉及矩阵, ,仅仅存储向量仅仅存储向量, ,因而存储量小因而存储量小, ,适适合于维数

58、较高的优化问题合于维数较高的优化问题 另外另外, ,共轭梯度法不要求精确的直线搜索共轭梯度法不要求精确的直线搜索. .但是但是, ,不精确的直线不精确的直线搜索可能导致迭代出来的向量不再共轭搜索可能导致迭代出来的向量不再共轭, ,从而降低方法的效能从而降低方法的效能. .克克服的办法是服的办法是: :重设初始点重设初始点, ,即把经过即把经过 次迭代得到的次迭代得到的 作为初始点重新迭代作为初始点重新迭代0k1n1nXCompany Logou 我们知道我们知道NewtonNewton法最突出的优点是收敛速度快法最突出的优点是收敛速度快, ,在这一点上其在这一点上其它算法无法比拟的它算法无法比

59、拟的. .因此因此, ,建议凡是建议凡是HesseHesse矩阵比较容易求出的问矩阵比较容易求出的问题尽可能使用题尽可能使用NewtonNewton法求解法求解. .u 然而然而NewtonNewton法还有一个严重缺陷法还有一个严重缺陷, ,就是每次迭代都要计算目标就是每次迭代都要计算目标函数的函数的HesseHesse矩阵和它的逆矩阵矩阵和它的逆矩阵, ,当问题的维数当问题的维数n n较大时较大时, ,计算量迅计算量迅速增加速增加, ,从而就抵消了从而就抵消了NewtonNewton法的优点法的优点Company Logou 为此，人们开始寻找一种算法既可以保持为此，人们开始寻找一种算法既

60、可以保持NewtonNewton法收敛速度快法收敛速度快的优点，又可以摆脱关于的优点，又可以摆脱关于HesseHesse矩阵的计算，这就是本节要给大矩阵的计算，这就是本节要给大家介绍的变尺度算法家介绍的变尺度算法u 变尺度法是一种非常好的方法其中变尺度法是一种非常好的方法其中DFPDFP算法和算法和BFGSBFGS算法，可算法，可以说直到目前为止在不用以说直到目前为止在不用HesseHesse矩阵的方法中是最好的算法矩阵的方法中是最好的算法Company Logo 在在NewtonNewton法中，由基本迭代格式法中，由基本迭代格式 , , 其中其中 , . , . 令令 , , 于是有于是有