第2章-2.4.2无约束优化方法(白版)鲍威尔法课件.ppt

1、 2-1 2-1 最速下降法（梯度法）最速下降法（梯度法）2-2 2-2 牛顿类方法牛顿类方法2-3 2-3 变尺度法变尺度法2-4 2-4 共轭方向法共轭方向法 2-5 2-5 鲍威尔方法鲍威尔方法2-6 2-6 其它方法（如坐标轮换法、单纯形法）其它方法（如坐标轮换法、单纯形法） 第第1章所列举的机械优化设计问题，都是在一定的章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。化问题。工程问题大都如此。 （1）有些实际问题，其数学模型本身就是一个无约束）有些实际问题，其数学模型本身就是

2、一个无约束优化问题。优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定

3、才能求得极小点，这种方法有理论意义，阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。化方法发展的基础。 目前已研究出很多种无约束优化方法，它们的目前已研究出很多种无约束优化方法，它们的主要不同点在于主要不同点在于构造搜索方向构造搜索方向上的差别。上的差别。 min( )nfRxx（1）间接法）间接法要使用导数，如梯度法、（阻尼）要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。牛顿法、变尺度法、

4、共轭梯度法等。（2）直接法）直接法不使用导数信息，如坐标轮换法、不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。鲍威尔法单纯形法等。无约束优化问题是：无约束优化问题是：12Tnx xxx求求n维设计变量维设计变量( )minfx使目标函数使目标函数 1(0,1,2,)kkkkskxx搜索方向的构成问题乃是无约束优化方法的关键。搜索方向的构成问题乃是无约束优化方法的关键。 用直接法寻找极小点时，不必求函数的导数，只要计用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的算目标函数值。这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法

5、效率低。间接法除）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。还要计算其海赛矩阵。 1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx 基本思想基本思想：函数的负梯度方向是函数值在该点：函数的负梯度方向是函数值在该点下降最快的方向。将下降最快的方向。将n n维问题转化为一系列沿负梯度维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。搜索方向，故称最速下降法或梯

6、度法。 ( )fx 搜索方向搜索方向s取该点的负梯度方向取该点的负梯度方向 (最速下降方最速下降方向向) ，使函数值在该点附近的范围内下降最快，使函数值在该点附近的范围内下降最快 。 为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向 能够获能够获得最大的下降值，其步长因子得最大的下降值，其步长因子 应取一维搜索的最应取一维搜索的最佳步长。即有佳步长。即有()kf xk1()()min ()min ( )kkkkkkaaffaffa f xxxxx 根据一元函数极值的必要条件和多元复合根据一元函数极值的必要条件和多元复合函数求导公式，得函数求导公式，得 ( )()()0Tkkkkfff xx

7、x1()()0kTkffxx1()0kTkss 在最速下降法中，在最速下降法中，相邻两个迭代点上的函相邻两个迭代点上的函数梯度相互垂直。而搜数梯度相互垂直。而搜索方向就是负梯度方向，索方向就是负梯度方向，因此相邻两个搜索方向因此相邻两个搜索方向互相垂直。这就是说在互相垂直。这就是说在迭代点向函数极小点靠迭代点向函数极小点靠近的过程，走的是曲折近的过程，走的是曲折的路线。形成的路线。形成“之之”字字形的锯齿现象，而且越形的锯齿现象，而且越接近极小点锯齿越细。接近极小点锯齿越细。 图图2-2 最速下降法的搜索路径最速下降法的搜索路径方法特点方法特点（1 1）初始点可任选，每次迭代计算量小，存储）初

8、始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。然后慢慢逼近局部极小点。 （2 2）任意相邻两点的搜索方向是正交的，它的）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。小点时，步长变得很小，越走越慢。 00102()10424()50100 xfxfxxx沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有01000024

9、()2 100fxxx0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件 122()min (24 )25(2 100 )min ( )f x例例2-1 2-1 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点则初始点处函数值及梯度分别为则初始点处函数值及梯度分别为02,2Tx2212( )25fxxx00( )8(24)5 000(2 100)0 算出一维搜索最佳步长算出一维搜索最佳步长 06260.020 030 7231 252第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 0120241.919 8772 1000.307178 5

10、 10 x1()3.686164fx继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 00Tx()0fx 这个问题的目标函数的等值线为一簇椭圆这个问题的目标函数的等值线为一簇椭圆, ,迭代点从迭代点从 走的是一段锯齿形路线，见下图。走的是一段锯齿形路线，见下图。0 x将上例中目标函数将上例中目标函数 引入变换引入变换2212( )25fxxx221212(,)y yyy其等值线由椭圆变成一簇同心圆。其等值线由椭圆变成一簇同心圆。 仍从仍从 即即 出发进行最速下降法出发进行最速下降法寻优。此时：寻优。此时：02,2Tx02,10Ty00102()10424()220y

11、yyyy沿负梯度方向进行一维搜索：沿负梯度方向进行一维搜索：则函数则函数f(f(X X) )变为：变为：y1=x1, y2=5x21000000()242410201020yyy为一维搜索最佳步长，可由极值条件：为一维搜索最佳步长，可由极值条件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552从而算得一步计算后设计点的位置及其目标函数：从而算得一步计算后设计点的位置及其目标函数：010124010200()0 yy经变换后，只需一次迭代，就可找到最优解。经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：这是因为经过尺度变换：1

12、1225yxyx等值线由椭圆变成圆。等值线由椭圆变成圆。l（1）理论明确，程序简单，对初始点要求不严格。）理论明确，程序简单，对初始点要求不严格。l（2）对一般函数而言，梯度法的收敛速度并不快，因）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。为最速下降方向仅仅是指某点的一个局部性质。l（3）梯度法相邻两次搜索方向的正交性，决定了迭代）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈全过程的搜索路线呈锯齿锯齿状，在远离极小点时逼近速度状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。较快，而在接近极小点时逼近速度较慢。l（4）梯度法

13、的收敛速度与目标函数的性质密切相关。）梯度法的收敛速度与目标函数的性质密切相关。对于等值线对于等值线(面面)为同心圆（球）的目标函数，一次搜索为同心圆（球）的目标函数，一次搜索即可达到极小点。即可达到极小点。2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx设设 为为 的极小点的极小点 1kx( )x1()0kx( )x( )x( )f x1kx( )f x21()()()0kkkkffxxxx121()()(0,1,2,)kkkkffk xxxx这就是多元函数求极值的牛顿法迭代公式。这就是多元函数求极值的牛顿法迭代公式。 对于二次函数对于二次函数 ，海

14、赛矩阵海赛矩阵H H是一个常矩阵，其中是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。需一步就可找到极小点。 例例2-2 2-2 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx00 x()0fx 从牛顿法迭代公式的推演中可以看到，迭代点从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如

15、果采降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升用上述牛顿迭代公式，有时会使函数值上升 。阻尼牛顿法阻尼牛顿法 121()()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛顿方向进行一维搜索的最佳沿牛顿方向进行一维搜索的最佳步长，由下式求得：步长，由下式求得： 1()()min()kkkkkkkffsfsxxx经过一次迭代即求得极小点经过一次迭代即求得极小点函数极小值函数极小值 阻尼牛顿法程序框图方法特点方法特点 （1） 初始点应选在初始点应选在X*附近，有一定难度；附近，有一定难度； （2） 尽管每次迭代都不会是函数值上升，

16、但不能保证尽管每次迭代都不会是函数值上升，但不能保证每次下降每次下降 ； （3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；不能构造牛顿法方向； （4） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的计算量和存储量大。此外，对于二阶不可微的F(X)也也不适用。不适用。 虽然阻尼牛顿法有上述缺点，但在特定条件下它虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和具有收敛最快的优点，并为其他的算法提供了思路和理论依据。理论

17、依据。1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：梯度法与牛顿法：梯度法与牛顿法：1()kkkkkfxxAx DFP变尺度法首先有戴维顿（变尺度法首先有戴维顿（Davidon）与）与1959年提出，又于年提出，又于1963年由弗莱彻（年由弗莱彻（Fletcher）和鲍维尔加）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。以发展和完善，成为现代公认的较好的算法之一。 D

18、FP法是基于牛顿法的思想又作了重要改进。这法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。速度。 1. 基本思想基本思想 变量的尺度变换是放大或缩小各个坐标。通过尺变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。 例如在用最速下降法求例如在用最速下降法求 的极小的极小2212( )25fxxx值时值时 ,需要进行需要进行10次迭代才能达到极小点

19、次迭代才能达到极小点0,0Tx 如作变换如作变换 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍，则目标函数等值线由一簇倍，则目标函数等值线由一簇椭圆变成一簇同心圆。椭圆变成一簇同心圆。x2221212(,)y yyy 消除了函数的偏心，用最速下降法只需一次迭消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。代即可求得极小点。 梯度法构造简单，只用到一阶偏导数，计算量小，梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近快；其主要缺点是迭代点接近X*时，即使对二次正

20、时，即使对二次正定函数收敛也非常慢。定函数收敛也非常慢。 牛顿法收敛很快，对于二次函数只需迭代一次便牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？能不能将两种算法的优点综合起来，扬长避短？1()kkkkkfxxAxAk 是需要构造是需要构造nn的一个对称方阵的一个对称方阵 ，如如Ak=I, 则得到梯度法则得到

21、梯度法 ；21()kkf Ax 则得到阻尼牛顿法则得到阻尼牛顿法 ；如如当矩阵当矩阵Ak 不断地迭代而能很好地逼近不断地迭代而能很好地逼近 21()kfx时，就可以不再需要计算二阶导数。时，就可以不再需要计算二阶导数。 变尺度法的关键在于尺度矩阵变尺度法的关键在于尺度矩阵Ak的产生的产生 。对于二次函数对于二次函数:1( )2TTfxx Gxb xcxQx进行尺度变换进行尺度变换在新的坐标系中，函数在新的坐标系中，函数f(x)的二次项变为：的二次项变为：1122TTTx Gxx Q GQx目的：减少二次项的偏心目的：减少二次项的偏心如如G是正定，则总存在矩阵是正定，则总存在矩阵Q，使得：，使得

22、：TQ GQI 用矩阵用矩阵Q-1右乘等式两边，得：右乘等式两边，得：用矩阵用矩阵Q左乘等式两边，得：左乘等式两边，得：1TQ GQTQQ GI所以所以1TQQG上式说明：二次函数矩阵上式说明：二次函数矩阵G的逆阵，可以通过尺度变换的逆阵，可以通过尺度变换矩阵矩阵Q来求得。来求得。121()()(0,1,2,)kkkkkffkxxxx牛顿迭代公式：牛顿迭代公式：1()(0,1,2,)kkTkkQQfkxxx记：记：TAQQ搜索方向：搜索方向：1()(0,1,2,)kkksfk Ax迭代公式：迭代公式：1()(0,1,2,)kkkkkfkxxAxA A 称为变尺度矩阵称为变尺度矩阵2212( )

23、25fxxx在例在例2-2中中122121222011( )2505022Txfxxx xxxx Gx20050G如取如取102105 2Q11002010221050101005 25 2TQ GQI求得：求得：1111000222111000505 25 2TGQQ从初始矩阵从初始矩阵A0=I(单位矩阵单位矩阵)开始，通过对公式开始，通过对公式 1kkkAAA因此，一旦达到最优点附近，就可望达到牛顿法因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度的收敛速度。1）DFP法（法（Davidon-Fletcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111

24、()()kkkkkkkkff gggxxxxx式中式中中修正矩阵中修正矩阵 的不断修正，在迭代中逐步逼近于的不断修正，在迭代中逐步逼近于kA1()kGx。l DFP算法由于舍入误差和一维搜索不精确，有可算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不能导致构造矩阵的正定性遭到破坏，以至算法不稳定。稳定。BFGS算法对于维数较高问题具有更好的稳算法对于维数较高问题具有更好的稳定性。定性。 1 kkTkTkkkkkTkTkkTkkkkTkkTxxgAgAxxxgxgAgxxgA开始给定结束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx

25、*1kxx否是1kkkn11111()kkkkkkkkf gxgggxxx11kkk AAA01kxx0k kkk dA g是否221212112( ,)242f x xxxxx xl解：解： 1）取初始点）取初始点 ，为了按，为了按DFP法构造第法构造第一次搜寻方向一次搜寻方向d0，需计算初始点处的梯度，需计算初始点处的梯度01 1Tx01200212244()422xxfxxxgx取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I，则第一次，则第一次搜寻方向为搜寻方向为 00010440122 dA gl沿沿d0方向进行一维搜索，得方向进行一维搜索，得010000014141 2

26、12 xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足01002()min()min(40203)ffxxd得得:00.25120.5x,2）再按）再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向d1，需计算，需计算1121212241422xxxxxg010143224ggg0102110.510.5 xxx代入校正公式代入校正公式000000000000TTTTxxAggAAxggAg1310.5340.543310.53444=100AAA21191010.5912112550010.50.251216194152550100=第二次搜寻方向为第二次搜寻方向为111866

27、5 dA g再沿再沿d1进行一维搜索，得进行一维搜索，得12111182560.55xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足12112811()min()min(4)52ffxxd154242 x,得得3）判断判断x2是否为极值点是否为极值点梯度梯度: : 2122212240()420 xxfxx xx海赛矩阵海赛矩阵 :2222()24fx梯度为零向量梯度为零向量, ,海赛矩阵正定。可见点满足极值海赛矩阵正定。可见点满足极值充要条件，因此为极小点。充要条件，因此为极小点。 *242Txx*()8f xl1.共共轭方向：轭方向：l 设设G为为nn阶实对称正定矩阵，如果有两个

28、阶实对称正定矩阵，如果有两个n维向量维向量d0和和d1满足满足 ，则称向量，则称向量d0与与d1 关于矩阵关于矩阵G共共轭。轭。01()0TdGd当当G为单位矩阵时为单位矩阵时，01()0Tdd假设目标函数假设目标函数f(x) 在极值点附近的二次近似函数为在极值点附近的二次近似函数为1( )2TfTxx Gxb xc对二维情况对二维情况任选取初始点任选取初始点x0沿某个下降方向沿某个下降方向d d0 0作一维搜索，得作一维搜索，得x11000 xxd 因为因为 是沿是沿d0方向搜索的最佳步长，即在点方向搜索的最佳步长，即在点x1处函数处函数f（x）沿方向）沿方向d0的方向导数为零。考虑到点的方

29、向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有处方向导数与梯度之间的关系，故有01100()0Tff xxdd如果按最速下降法，选择负梯度方向如果按最速下降法，选择负梯度方向 为搜为搜索方向，则将发生锯齿现象索方向，则将发生锯齿现象 。1()fx 取下一次的迭代搜索方向取下一次的迭代搜索方向d1直指极小点直指极小点x* *。0d0 x0 x1x*1 11d11()fxd1l如果能够选定这样的搜索方向，那么对于二元二次如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行函数只需顺次进行d0、d1两次直线搜索就可以求到两次直线搜索就可以求到极小点极小点x* * ，即有，即有111

30、xxd那么这样的那么这样的d1方向应该满足什么条件呢方向应该满足什么条件呢 ? ?对于前述的二次函数对于前述的二次函数: :1( )2TfTxx Gxb xc当当 时，时，1xx10 x* *是是f( (x) )极小点，应满足极值必要条件，故有极小点，应满足极值必要条件，故有()0fxGxb111111()()()ff xG xdbxGd0将等式两边同时左乘将等式两边同时左乘 得得：0()Td01()0TdGd11()fxGxb有有01()0TdGd 就是使就是使d1直指极小点直指极小点x* * ， d1所必须满足的条件所必须满足的条件 。两个向量两个向量d0和和d1称为称为G的共轭向量，或称

31、的共轭向量，或称d0和和d1对对G是共轭方向。是共轭方向。 2.2.共轭方向的性质共轭方向的性质性质性质1 1 若非零向量系若非零向量系d0, ,d1, ,d2,dm-1是对是对G共轭，共轭，则这则这m个向量是线性无关的。个向量是线性无关的。性质性质2 2 在在n维空间中互相共轭的非零向量的个数维空间中互相共轭的非零向量的个数不超过不超过n。 性质性质3 3 从任意初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭方的共轭方向向d0, ,d1, , d2,进行一维搜索，最多经过进行一维搜索，最多经过n次迭代就次迭代就可以找到的二次函数可以找到的二次函数f( (x) )极小点。极小点。 0

32、21()( )0Tfdx d开始给定结束00,x d1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共轭方向关键：新的共关键：新的共轭方向轭方向确定确定 在无约束方法中许多算法都是以共轭方向在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方共轭方向的原理不同，可以形成不同的共轭方向法。向法。 l共轭梯度法是共轭方向法中的一种，该方法中共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度每一个共轭向量都是依赖于迭代点处的负梯度而

33、构造出来。而构造出来。l 从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索:1(0,1,2,)kkkkkxxd()kkf dx设与设与dk共共轭的下一个方向轭的下一个方向dk+1由由dk和点和点xk+1的负梯的负梯度的线形组合构成，即：度的线形组合构成，即：11()kkkkf dxd21()( )0kTkfdx d共轭条件：共轭条件：l则：则：21()( )()0kTkkkfff xxxd解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc为函数的泰勒二次展开式为函数的泰勒二次展开式()kkfxGxb则则11

34、()kkfxGxb上两式相减，并代入上两式相减，并代入1kkkkxxd1()()kkkkff Gdxx1()()kkkkff Gdxx将式将式11()kkkkf dxd与式与式两边相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：11()()()()0kkkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd2212112( )242fxxxx xx，已知初始点，已知初始点1,11,1T Tl解：解： 1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻

35、l计算初始点处的梯度计算初始点处的梯度0120212244()422xxfxxxx010000014141 212 xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足1002()min()min(40203)ffxxdl迭代精度迭代精度 。 0.001得得:00.25120.5x2）第二次迭代：）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5f dxd21122220.51.50.5 1.5xxd代入目标函数代入目标函数22( )(22 )2(0.5 1.5 )2(22 )(0.5 1.5 )4(22 )( )f x 得得1因因2()0fx收敛。

36、收敛。( )0 由由22240,()8,()20ff xxx从而有：从而有： 鲍威尔法是以共轭方向为基础的收敛较鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。快的直接法之一，是一种十分有效的算法。 1964年，鲍维尔提出这种算法，其基本思想年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。的实践中进行了改进。 1()2TfTxx G xbxc对函数：对

37、函数：基本思想基本思想：在不用导数的前提下，在迭代中逐次构造：在不用导数的前提下，在迭代中逐次构造G的共轭方向。的共轭方向。 1.1.共轭方向的生成共轭方向的生成jjkkkdd ddjgg gk+1xxk+1设设xk, , xk+1为从不同为从不同点出发，沿同一方向点出发，沿同一方向dj j进行一维搜索而到进行一维搜索而到的两个极小点。的两个极小点。 l梯度和等值面相垂直的性质梯度和等值面相垂直的性质, , dj j和和 xk, , xk+1两点两点处的梯度处的梯度gk, ,gk+1之间存在关系之间存在关系: :1()0,()0jTkjTkdgdg另一方面，对于上述二次函数，其另一方面，对于上

38、述二次函数，其xk, , xk+1两点处的两点处的梯度可表示为梯度可表示为: :11,kkkkgGxbgGxb因而有因而有11() ()()()0jTkkjTkkdggdG xx1kkkdxx取取这说明只要沿这说明只要沿dj j方向分别对函作两次一维搜索，方向分别对函作两次一维搜索，得到两个极小点得到两个极小点xk和和xk+1 ，那么这两点的连线所，那么这两点的连线所给出的方向给出的方向dk k就是与就是与dj j一起一起对对G共轭的方向。共轭的方向。l二维情况描述鲍威尔的基本算法二维情况描述鲍威尔的基本算法: : 1 1）任选一初始点）任选一初始点x0，再选两个线性无关的再选两个线性无关的向

39、量，如坐标轴单位向量，如坐标轴单位向量向量e1 1=1,0=1,0T T和和e e2 2=0,1=0,1T T作为初始作为初始搜索方向。搜索方向。2 2）从）从x0出发，顺次沿出发，顺次沿e1 1， e1 1作一维搜索，得作一维搜索，得 点，两点连线点，两点连线得一新方向得一新方向d1 10012,x x1002dxxx1x2x0oe1e2d1d2x*102x10 x11x12x01xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x21120dxx沿沿d2作一维搜索得点作一维搜索得点x2 。 即是二维问题的极即是二维问题的极小点小点x* 。方法的基本迭代格式包括共方法的

40、基本迭代格式包括共轭方向产生和方向替换两轭方向产生和方向替换两主要步骤。主要步骤。用用 d1代替代替e1 1形成两个线性无关向量形成两个线性无关向量d1 , ,e2 2 ，作为，作为下一轮迭代的搜索方向。再从下一轮迭代的搜索方向。再从 出发，沿出发，沿d1作一作一维搜索得点维搜索得点 ，作为下一轮迭代的初始点。，作为下一轮迭代的初始点。 02x10 x3 3）从）从 出发，依次出发，依次沿沿e2 2, ,d1 作一维搜索，作一维搜索，得到点得到点 ，两点连，两点连线得一新方向线得一新方向: :1112,xx10 xl把二维情况的基本算法扩展到把二维情况的基本算法扩展到n维，则鲍威尔基本维，则鲍

41、威尔基本算法的要点是：算法的要点是：l在每一轮迭代中总有一个始点（第一轮的始点是任在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和选的初始点）和n个线性独立的搜索方向。从始点个线性独立的搜索方向。从始点出发顺次沿出发顺次沿n个方向作一维搜索得一终点，由始点个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。和终点决定了一个新的搜索方向。l用这个方向替换原来用这个方向替换原来n个方向中的一个，于是形成个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，一个方向而将新方向排

42、在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。就形成算法的循环。 l因为在迭代中的因为在迭代中的n个搜索方向有时会变成线性相关个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成而不能形成共轭方向。这时组不成n维空间，可能维空间，可能求不到极小点，所以上述基本算法有待改进。求不到极小点，所以上述基本算法有待改进。 3.3.改进的算法改进的算法 在鲍威尔基本算法中，每一轮迭代都用连结在鲍威尔基本算法中，每一轮迭代都用连

43、结始点和终点所产生出的搜索方向去替换原向量组中始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的的第一个向量，而不管它的“好坏好坏”，这是产生向，这是产生向量组线性相关的原因所在。量组线性相关的原因所在。 在改进的算法中首先判断原向量组是否需要在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。个最坏的向量，以保证逐次生成共轭方向。l为此，要解决两个关键问题为此，要解决两个关键问题：l（

44、1）dk1是否较好？是否应该进入新的方向是否较好？是否应该进入新的方向组？即方向组是否进行更新？组？即方向组是否进行更新？l（2）如果应该更新方向组，）如果应该更新方向组， dk1不一定替换方不一定替换方向向 ，而是有选择地替换某一方向，而是有选择地替换某一方向 。1kdkmd令在令在k次循环中次循环中00231()()()kknknFfFfFfxxx01,kkknnx x x100()2kkkkkknnnnxxxxxx（）分别称为一轮迭代的始点、终点和反射点分别称为一轮迭代的始点、终点和反射点 。l则在循环中函数下降最多的第则在循环中函数下降最多的第m次迭代是次迭代是1(1,2, )iiif

45、fin ()(0,1,2, )kiiffinx记记：11maxmimmi nff 相应的方向为相应的方向为 。kmd为了构成共为了构成共轭性好的方向组，须遵循下列准轭性好的方向组，须遵循下列准则：则：在在k次循环中，次循环中，若满足条件：若满足条件：30FF和和202302(2)()mFFFFF2030.5()mFF则选用新方向则选用新方向dk，并在第并在第k+1迭代中用迭代中用dk替换对应于替换对应于 的方向的方向 。否则，仍然用原方向组进行第。否则，仍然用原方向组进行第k+1迭代。迭代。kmdm002,nFfFf因此因此l 这样重复迭代的结果，后面加进去的向量都彼此对这样重复迭代的结果，后

46、面加进去的向量都彼此对G共轭，经共轭，经n轮迭代即可得到一个由轮迭代即可得到一个由n个共轭方向所组成的方个共轭方向所组成的方向组。对于二次函数，最多经过向组。对于二次函数，最多经过n次就可找到极小点，而对次就可找到极小点，而对一般函数，往往要超过一般函数，往往要超过n次才能找到极小点（这里次才能找到极小点（这里“n”表表示设计空间的维数）。示设计空间的维数）。 l例例2-5 2-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数2212112( )242fxxxx xx解：（解：（1 1）第）第1 1轮迭代计算轮迭代计算， 0011 x0000()3Fff x沿沿e1方向进行一维搜索方向

47、进行一维搜索0201min()43fxe12得得00101 11132101 xxe011()7ff x0.001。l的最优解。已知初始点的最优解。已知初始点1,11,1T T，迭代精度，迭代精度以以 为起点，沿第二坐标轴方向为起点，沿第二坐标轴方向 e2 进行一维进行一维搜索搜索01x0212min()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x确定此轮中的最大下降量及其相应方向确定此轮中的最大下降量及其相应方向 0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 反射点及其函数值反射点及其函数值，

48、000320315221.512 xxx033()7Ff x检验检验PowellPowell条件条件202302(2)()1.25mFFFFF2030.5()32mFF3073FF 由于满足由于满足PowellPowell条件，则淘汰函数值下降量最条件，则淘汰函数值下降量最大的方向大的方向e1，下一轮的基本方向组为，下一轮的基本方向组为e2， 。03d构成新的方向构成新的方向 0003203121.510.5 dxx沿沿 方向一维搜索得极小点和极小值方向一维搜索得极小点和极小值03d13.81.7x1()7.9f x，此点为下轮迭代初始点。此点为下轮迭代初始点。 按点距准则检验终止条件按点距准

49、则检验终止条件 11220(3.8 1)(1.71)2.886xx需进行第二轮迭代机算。需进行第二轮迭代机算。l（2 2）第）第2 2轮迭代计算轮迭代计算此轮基本方向组为此轮基本方向组为e2， ，分别相当于，分别相当于 ， ，起始点为起始点为 。03d11d12d10 x1x沿沿e2方向进行一维搜索得方向进行一维搜索得 113.81.9x111()7.98ff x以以 为起点沿为起点沿 方向一维搜索得方向一维搜索得11x03d123.961.9x122()7.996ff x确定此轮中函数值最大下降量及其相应方向确定此轮中函数值最大下降量及其相应方向10.08 20.016 12max,0.08

50、m l反射点及其函数值反射点及其函数值1113203.963.84.12221.941.72.18xxx133()7.964Ff x检验检验Powell条件，淘汰函数值下降量最大的方条件，淘汰函数值下降量最大的方向向e2，下一轮的基本方向组应为，下一轮的基本方向组应为 ， 。 03d13d构成新的方向构成新的方向1113203.963.80.161.941.70.24dxx沿沿 方向进行一维搜索得方向进行一维搜索得13d242 x2()8f xl检验终止条件检验终止条件 22220(43.8)(2 1.7)0.36xx（3 3）第）第3 3轮迭代计算轮迭代计算此轮基本方向组为此轮基本方向组为