无约束多维问题的优化方法

1、l为什么要研究为什么要研究多维多维无约束优化问题无约束优化问题 ? (1)、有些实际问题，其数学模型本身就是一个、有些实际问题，其数学模型本身就是一个多维多维无约束优化问题。无约束优化问题。 (2)、通过熟悉它的解法可以为研究、通过熟悉它的解法可以为研究多维多维约束优约束优化问题打下良好的基础。化问题打下良好的基础。 (3)、多维多维约束优化问题的求解可以通过一系列约束优化问题的求解可以通过一系列多维多维无约束优化方法来达到。所以无约束优化方法来达到。所以多维多维无约束优无约束优化问题的解法是优化设计方法的基本组成部分，化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。也是优化方法

2、的基础。 l多维多维无约束优化问题是：无约束优化问题是：l求求n维设计变量维设计变量l 使目标函数：使目标函数： l 12Tnx xxx( )minfxmin( )nfRxx各种多维无约束优化解法的区别：搜索方向的不同各种多维无约束优化解法的区别：搜索方向的不同 分类分类：（1）直接解法）直接解法-不使用导数信息，如坐标轮换不使用导数信息，如坐标轮换 法、法、PowellPowell法、随机搜索法、单纯形法等法、随机搜索法、单纯形法等（2）间接解法）间接解法(解析法解析法)-要使用导数，二阶有要使用导数，二阶有 梯梯度法、共轭梯度法、，二阶以上用牛顿法度法、共轭梯度法、，二阶以上用牛顿法1(0

3、,1,2,)kkkkSkxx搜索方向的构成问题是多维无约束优化方法的关键搜索方向的构成问题是多维无约束优化方法的关键l 从选定的某初始点从选定的某初始点x x(k)(k)出发，沿着以一定规律产生的出发，沿着以一定规律产生的搜索方向搜索方向S S(k)(k) , ,取适当的步长取适当的步长a a(k)(k) , ,逐次搜寻函数值下降逐次搜寻函数值下降的新迭代点的新迭代点x x(k+1)(k+1), ,使之逐步通近最优点使之逐步通近最优点x x* * 。l 可以把可以把初始点初始点x x(k)(k) 、搜索方向搜索方向S S(k)(k) 、迭代步长迭代步长a a(k)(k) 称称为优化方法算法的三

4、要素。其中以搜索方向为优化方法算法的三要素。其中以搜索方向S S(k)(k)更为突更为突出和重要，它从根本上决定若一个算法的成败、收敛速出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。率的快慢等。l 一个算法的搜索方向成为该优化方法的基本标志，分一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向析、确定搜索方向S S(k)(k)是研究优化方法的最根本的任务是研究优化方法的最根本的任务之一。之一。 坐标轮换法又称为坐标轮换法又称为“变量轮换法变量轮换法”，“交替法交替法”或或“降维法降维法”。是一种常用的降维方法。是一种不需要。是一种常用的降维方法。是一种不需要求函数导数

5、，直接探索目标函数最优解的方法。求函数导数，直接探索目标函数最优解的方法。l 每次仅对多元函数的一个变量沿其坐标轴进行每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小行第二轮探索，直到找到目标函数在全域上的最小点为止。以达到将一个多维的无约束最优化问题，点为止。以达到将一个多维的无约束最优化问题，转化为一系列的一维问题来求解的目的。转化为一系列的一维问题来求解的目的。一）基本思想一）基

6、本思想l根据上述原理，对于第根据上述原理，对于第k k轮探索，其迭代轮探索，其迭代计算公式为：计算公式为：l式中式中 步长步长l 探索方向探索方向 二）迭代公式二）迭代公式1iiiiXXeiie1,2,in61210.001.0.00.1TTTneee几何描述几何描述( (以二维问题为例）以二维问题为例）四）探索过程四）探索过程依次沿个依次沿个n n个正交坐标轴的方向搜索：个正交坐标轴的方向搜索：三）搜索方向三）搜索方向7五）步长取法五）步长取法1) 随机选择随机选择 值的方法值的方法 i 此方法每次选择值此方法每次选择值 时，需满足下式：时，需满足下式：由于这种方法是轮流沿由于这种方法是轮流

7、沿n个设计变量的坐标轴方向前个设计变量的坐标轴方向前进，所以此方法有时路程过于迂回曲折，因此它不进，所以此方法有时路程过于迂回曲折，因此它不是快速探索的方法。是快速探索的方法。i11iiiifXefX2)加速步长法加速步长法 此方法先规定沿此方法先规定沿 方向的初始实验步长方向的初始实验步长 ，确定步长确定步长 的正负，当沿坐标轴正方向探索能使的正负，当沿坐标轴正方向探索能使目标函数值减小时，则取正值，否则应取负值。目标函数值减小时，则取正值，否则应取负值。iSihi8 再取实验步长再取实验步长 的若干倍计算目标函数，即取步的若干倍计算目标函数，即取步长长 计算目标函数值计算目标函数值。若。若

8、 ，则加速步长，使其沿同一方向延，则加速步长，使其沿同一方向延伸，如若延伸至第伸，如若延伸至第 次时次时 ，则延伸至，则延伸至第第 次为止。当步长不宜延伸而宜缩小时，亦可缩小，次为止。当步长不宜延伸而宜缩小时，亦可缩小，也是一直到函数达到最小值为止。然后改变方向也是一直到函数达到最小值为止。然后改变方向 ，在新的方向上重复前述过程，直到函数值达到最小值为在新的方向上重复前述过程，直到函数值达到最小值为止，终止计算。止，终止计算。 ihiih1iiiiiffXfXS1iiffX1J 1iiffXJiS2022-5-59加速步长法流程图：加速步长法流程图：给定给定,0hX00Xff0; 1ki0J

9、 ihSXX0Xffi?0ffihtta iSXX0Xff ?iff ?0J1 JJtt2ffi XX0 iStXX201k Xff0 ihSXX0Xffi?0ffihh1 ii?Ni 0k0i0kfX ,得出得出TTFTFTTFFFT结束结束2022-5-5103)最优步长法最优步长法 最优步长法是利用一维探索方方，如黄金分割最优步长法是利用一维探索方方，如黄金分割法或二次插值法，来确定最优步长法或二次插值法，来确定最优步长 值值i 在第在第k轮探索的第轮探索的第i次迭代中其步长为：次迭代中其步长为：11m iniiiiifXSfXS2022-5-511 最优步长法流程图最优步长法流程图从从

10、 出发沿出发沿 方向进行一维搜索得方向进行一维搜索得 ：1iXieiiiiieXX1)(iXFF 1ini 给给定定,0nX0XXn1iiFFXXn结束结束10kkXXn1k是否否是例：例：试用坐标轮换法求目标函数试用坐标轮换法求目标函数的极小值，设初始点的极小值，设初始点 。2212121210460fXxxx xxx 00012,0,0TTXxx解解：采用坐标轮换法中的最优步长法。先使：采用坐标轮换法中的最优步长法。先使 保持不变，保持不变，故故 ，此时目标函数，此时目标函数 。对。对 用一维探索最优化方法中的二次插值法求优得用一维探索最优化方法中的二次插值法求优得 ， 。1x 0110

11、xx222460fXxx2x 122x 156fX 然后保持然后保持 不变，则不变，则 ，并且二次插值法对并且二次插值法对 进行探索，求得最优解为进行探索，求得最优解为 ，故故 。 1222xx2111256fXxx1x 216x 220fX 如此交替的固定一个变量，探索另一个变量的最优如此交替的固定一个变量，探索另一个变量的最优解，在第解，在第9 9轮计算中得轮计算中得 ， , , 。所得结果与目标函数的实际最小点。所得结果与目标函数的实际最小点 ，实际最小值，实际最小值 已十分接近已十分接近。 98.0007318fX 817.96875x 925.984375x*12,8,6TTXx x

12、*8fX六）算法特点六）算法特点如如:(:(1)1)等值线为椭圆等值线为椭圆, ,且长短轴分别平行于坐标轴时且长短轴分别平行于坐标轴时-高效高效1x2xo(2(2) )等值线为如图脊线时等值线为如图脊线时-无效无效1x2xo(3(3) )一般情况一般情况-低效低效1 1）编程简单，容易掌握；）编程简单，容易掌握；2 2）收敛速度通常较低（其有效性取决于目）收敛速度通常较低（其有效性取决于目标函数的性态），仅适于低维的情况。标函数的性态），仅适于低维的情况。 函数的函数的负梯度方向负梯度方向是函数值下降最快的方向是函数值下降最快的方向 搜索方向搜索方向S取该点的负梯度方向取该点的负梯度方向 (

13、(最速下降方最速下降方向向) ) ，使函数值在该点附近的范围内下降最快。，使函数值在该点附近的范围内下降最快。( )fx1(0,1,2,)kkkkSkxx1() (0,1,2,)kkkkafkxxx为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向 能够获得最大的下能够获得最大的下降值，其步长因子降值，其步长因子 应取一维搜索的最佳步长。即有应取一维搜索的最佳步长。即有()kfxk1()()min ()min ( )kkkkkkaaffaffa f xxxxxl 根据一元函数极值的必要条件和多元复合函根据一元函数极值的必要条件和多元复合函数求导公式，得数求导公式，得 ( )()()0Tkkk

14、kfff xxx1()()0kTkffxx1()0kTkSS 在最速下降在最速下降( (梯度梯度) )法中，相邻两个迭代点上的函数梯法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此度相互垂直。而搜索方向就是负梯度方向，因此相邻两个相邻两个搜索方向互相垂直搜索方向互相垂直。这就是说在迭代点向函数极小点靠近。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成的过程，走的是曲折的路线。形成“之之”字形的锯齿现象，字形的锯齿现象，而且而且越接近极小点锯齿越细越接近极小点锯齿越细。 开始给定结束0,x()kkf dx1:min()kkkkkkkfxxdxd1kkxx*

15、1kxx否是1kk0k 例：最速下降法求目标函数例：最速下降法求目标函数 极小点。极小点。解解 取初始点取初始点则初始点处函数值及梯度分别为则初始点处函数值及梯度分别为02,2Tx00102()10424()50100 xfxfxxx沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有01000024()2 100fxxx0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件 122()min (24 )25(2 100 )min ( )f x2212( )25fxxx00( )8(24)5 000(2 100)0 算出一维搜索最佳步长算出一维搜索最佳步长 0626

16、0.020 030 7231 252第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 00Tx()0fxl这一问题的目标函数这一问题的目标函数f(x)的等值线为一簇椭圆。的等值线为一簇椭圆。将上例中目标函数将上例中目标函数 引入变换引入变换 y1=x1, y2=5x2则函数则函数f(x)f(x)变为：变为：2212( )25fxxx221212(,)y yyy其等值线由椭圆变成一簇同心圆。其等值线由椭圆变成一簇同心

17、圆。02,2Tx 仍从仍从 即即 出发进行最速下降法出发进行最速下降法寻优。此时：寻优。此时：02,10Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索沿负梯度方向进行一维搜索：1000000()242410201020yyy为一维搜索最佳步长，可由极值条件：为一维搜索最佳步长，可由极值条件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552从而算得一步计算后设计点的位置及其目标函数：从而算得一步计算后设计点的位置及其目标函数：010124010200()0 yy经变换后，只需一次迭代，就可找到最优解。经变换后，只需

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

19、极小点时逼近速度较慢。较快，而在接近极小点时逼近速度较慢。l（4）梯度法的收敛速度梯度法的收敛速度 与目标函数的性质密切相与目标函数的性质密切相 关。对于等值线关。对于等值线(面面)为同为同 心圆（球）的目标函数，心圆（球）的目标函数， 一次搜索即可达到极小点。一次搜索即可达到极小点。( )x( )x( )f x1kx( )f x2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx设 为 的极小点 1kx( )x1()0kx21()()()0kkkkffxxxx121()()(0,1,2,)kkkkffk xxxx这就是多元函数求极值的这就是多元函数求极值

20、的牛顿法迭代公式牛顿法迭代公式。 对于二次函数对于二次函数 ，海赛矩阵是一个常矩阵，其中海赛矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。需一步就可找到极小点。例：例： 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点2212( )25fxxx02,2Tx102010102402()()121000050ff xxxxl经过一次迭代即求得极小点经过一次迭代即求得极小点 ，l函数极小值函数极小值 。00 x()0fx 从牛顿法迭代公式的推演中可以看到，迭代点从牛顿法迭代公式的推演中可以看到，迭代点的

21、位置是按照极值条件确定的，其中并的位置是按照极值条件确定的，其中并未含有沿下未含有沿下降方向降方向搜寻的概念。因此对于搜寻的概念。因此对于非二次函数非二次函数，如果采，如果采用上述牛顿迭代公式，有时会使函数值上升。用上述牛顿迭代公式，有时会使函数值上升。 121()()(0,1,2,)kkkkkkkkSffkxxxxxk阻尼因子阻尼因子 ，沿牛顿方向进行沿牛顿方向进行一维搜索的最佳步一维搜索的最佳步长长，由下式求得：，由下式求得： 1()()min()kkkkkkkffSfSxxx开始给定结束0,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1

22、kk0k 阻尼牛顿法称序框图l 牛顿法和阻尼牛顿法统称为牛顿型方法。牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是每次迭代都要计算函数这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量量很大。特别是矩阵求逆，当维数高时工作量更大更大 。 1(0,1,2,)kkkkSkxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法：

23、1()kkkkkfxxAx 变尺度法是在牛顿法的思想上进行了重大改进变尺度法是在牛顿法的思想上进行了重大改进的一类方法的一类方法 1. 基本思想基本思想 变量的尺度变换是放大或缩小各个坐标。通过尺变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。 2212( )25fxxx例如在用最速下降法求例如在用最速下降法求 的极小的极小值时值时 ,需要进行需要进行10次迭代才能达到极小点次迭代才能达到极小点0,0Tx 如作变换如作变换 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍，则目标函数等值线由一倍，则目标函数等值线

24、由一簇椭圆变成一簇同心圆。簇椭圆变成一簇同心圆。x2221212(,)y yyy消除了函数的偏心，用最速下降法只需一次迭消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。代即可求得极小点。 梯度法构造简单，只用到一阶偏导数，计梯度法构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快，但当迭代到最算量小，迭代初期收敛速度快，但当迭代到最优点附近时收敛速度很慢；优点附近时收敛速度很慢； 牛顿法收敛很快，对于二次函数只需迭代牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆代到最优

25、点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存阵，对维数较高的优化问题，其计算工作和存储量都太大。储量都太大。能不能将两种算法的优点综合起来，扬长避短？能不能将两种算法的优点综合起来，扬长避短？1()kkkkkfxxAxAk 是需要构造是需要构造nn的一个对称方阵的一个对称方阵 ，如如Ak=I, 则得到梯度法则得到梯度法 ；21()kkf Ax 则得到阻尼牛顿法则得到阻尼牛顿法 ；如如 当矩阵当矩阵Ak 不断地迭代而能很好地逼近不断地迭代而能很好地逼近 21()kfx时，就可以不再需要计算二阶导数时，就可以不再需要计算二阶导数变尺度法的关键在于尺度矩阵变尺度法的关键在

26、于尺度矩阵Ak的产生的产生 。对于二次函数对于二次函数:1( )2TTfxx Gxb xcxQx进行尺度变换进行尺度变换在新的坐标系中，函数在新的坐标系中，函数f(x)的二次项变为：的二次项变为：1122TTTx Gxx Q GQx目的：减少二次项的偏心目的：减少二次项的偏心如如G是正定，则总存在矩阵是正定，则总存在矩阵Q，使得：，使得：TQ GQI 用矩阵用矩阵Q-1右乘等式两边，得：右乘等式两边，得：用矩阵用矩阵Q左乘等式两边，得：左乘等式两边，得：1TQ GQTQQ GI所以所以1TQQG上式说明：二次函数矩阵上式说明：二次函数矩阵G的逆阵，可以通过尺度变换的逆阵，可以通过尺度变换矩阵矩

27、阵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( )25fxxx在例题在例题122121222011( )2505022Txfxxx xxxx Gx20050G如取如取102105 2Q11002010221050101005 25 2TQ GQI求得：1111000222111000505 25 2TGQQ

28、从初始矩阵从初始矩阵A0=I(单位矩阵单位矩阵)开始，通过对公式开始，通过对公式 1kkkAAA中修正矩阵中修正矩阵 的不断修正，在迭代中逐步逼近于的不断修正，在迭代中逐步逼近于 kA1()kGx因此，一旦达到最优点附近，就可望达到牛顿法因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度的收敛速度。1）DFP法（法（Davidon-Fletcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111()()kkkkkkkkff gggxxxxx式中式中。l DFP算法由于舍入误差和一维搜索不精确，有可算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破

29、坏，以至算法不能导致构造矩阵的正定性遭到破坏，以至算法不稳定。稳定。BFGS算法对于维数较高问题具有更好的稳算法对于维数较高问题具有更好的稳定性。定性。 1 kkTkTkkkkkTkTkkTkkkkTkkTxxgAgAxxxgxgAgxxgA开始给定结束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gxgggxxx11kkk AAA01kxx0k kkk dA g是否l解：解： 1）取初始点）取初始点 ，为了按，为了按DFP法构造法构造第一次搜寻方向第一次搜寻方向S0，需计算初始点处的梯度，需计算初始点处

30、的梯度221212112( ,)242f x xxxxx x01 1Tx01200212244()422xxfxxxgx取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I，则第一次，则第一次搜寻方向为搜寻方向为 00010440122S A gl沿沿S0方向进行一维搜索，得方向进行一维搜索，得010000014141 212S xx为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足01002()min()min(40203)ffSxx得得:00.25120.5x,2）再按）再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向S1，需计算，需计算1121212241422xxxxx

31、g010143224ggg0102110.510.5 xxx代入校正公式代入校正公式000000000000TTTTxxAggAAxggAg1310.5340.543310.53444=100AAA21191010.5912112550010.50.251216194152550100=第二次搜寻方向为第二次搜寻方向为1118665S A g再沿再沿S1进行一维搜索，得进行一维搜索，得12111182560.55Sxx为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足12112811()min()min(4)52ffSxx154242 x,得得3）判断判断x2是否为极值点是否为极值点梯度梯度

32、: : 2122212240420 xxxx xg海赛矩阵海赛矩阵 :2222()24fx梯度为零向量梯度为零向量, ,海赛矩阵正定。可见点满足极值海赛矩阵正定。可见点满足极值充要条件，因此为极小点。充要条件，因此为极小点。 *242Txx*()8f x(1)、在变尺度法中对、在变尺度法中对A(k)矩阵是有要求的。矩阵是有要求的。因为对于极小化问题，为了使搜索方向因为对于极小化问题，为了使搜索方向 为下降方向，需要使搜索方为下降方向，需要使搜索方向向S(k)与负梯度方向的夹角为与负梯度方向的夹角为锐角锐角，即，即 所以所以A(k)必须为正定矩阵必须为正定矩阵(2)、对于对称正定矩阵、对于对称正

33、定矩阵A(k)和非零向量和非零向量S(1)、 S(2) S(n)(3)、每次迭代都能使目标函数值单调下降即、每次迭代都能使目标函数值单调下降即为算法的为算法的连续稳定性连续稳定性. 为了提高实际计算中的稳定性，通常采为了提高实际计算中的稳定性，通常采用用“重置重置”的方法，即在的方法，即在n次迭代后重新设置次迭代后重新设置单位矩阵单位矩阵.l 设G为nn阶实对称正定矩阵，如果有两个n维向量S0和S1满足 ，则称向量S0与S1 关于矩阵G共轭。01()0TSS G当当G为单位矩阵时为单位矩阵时，01()0TSS 假设目标函数假设目标函数f(x) 在极值点附近的二次近似函数为在极值点附近的二次近似

34、函数为1( )2TfTxx Gxb xc对二维情况对二维情况任选取初始点任选取初始点x0沿某个下降方向沿某个下降方向S S0 0作一维搜索，得作一维搜索，得x11000Sxx0S0 x0 x1x*1 11S11()fx 因为因为 是沿是沿S0方向搜索的最佳步长，即在方向搜索的最佳步长，即在点点x1处函数处函数f（x）沿方向）沿方向S0的方向导数为零的方向导数为零。考虑到点。考虑到点x1处方向导数与梯度之间的关系，故有处方向导数与梯度之间的关系，故有01100()0TffSS xx1()fx如果按最速下降法，选择负梯度方向如果按最速下降法，选择负梯度方向 为搜为搜索方向，则将发生索方向，则将发生

35、锯齿锯齿现象现象 。 取下一次的迭代搜索方向取下一次的迭代搜索方向S1直指极小点直指极小点x* * .S10S0 x0 x1x*1 11S11()fxS1l如果能够选定这样的搜索方向，那么对于二元二次如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行函数只需顺次进行S0、S1两次直线搜索就可以求到两次直线搜索就可以求到极小点极小点x* * ，即有，即有111Sxx那么这样的那么这样的S1方向应该满足什么条件呢方向应该满足什么条件呢 ? ?对于前述的二次函数对于前述的二次函数: :有有11()fxGxb1( )2TfTxx Gxb xc当当 时时 。1xx10 x* *是是f( (x)

36、 )极小点，应满足极值必要条件，故有极小点，应满足极值必要条件，故有()0fxGxb1111111()()()fSfxSb xG xbxG0将等式两边同时左乘将等式两边同时左乘 得得：0()TS01()0TSS G01()0TSS G 就是使就是使S1直指极小点直指极小点x* * ， S1所必须满足的条件所必须满足的条件 。两个向量两个向量S0和和S1称为称为G的共轭向量，或称的共轭向量，或称S0和和S1对对G是共轭方向。是共轭方向。 性质性质1 1 若非零向量系若非零向量系S0, ,S1, ,S2,Sm-1是是对对G共轭共轭，则这则这m个向量是线性无关个向量是线性无关的。的。性质性质2 2

37、在在n维空间中维空间中互相共轭的非零向量的个数互相共轭的非零向量的个数不超过不超过n。 性质性质3 3 从任意初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭方的共轭方向向S0, ,S1, , S2,进行一维搜索，进行一维搜索，最多经过最多经过n次迭代次迭代就可以找到的就可以找到的二次二次函数函数f( (x) )极小点。极小点。 021()( )0TSfSx开始给定结束00,x d1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共轭方向关键：新的共轭方向确定l共轭梯度法是共轭方向法中的一种，该方法中共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向

38、量都是依赖于迭代点处的负梯度每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。而构造出来。l 从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索:1(0,1,2,)kkkkSkxx()kkSf x设与设与Sk共共轭的下一个方向轭的下一个方向Sk+1由由Sk和点和点xk+1的负的负梯度的线形组合构成，即：梯度的线形组合构成，即：11()kkkkSfS x21()( )0kTkSfSx共轭条件：共轭条件：l则：则：21()( )()0kTkkkfffS xxx解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc为

39、函数的泰勒二次展开式为函数的泰勒二次展开式()kkfxGxb则则11()kkfxGxb上两式相减，并代入上两式相减，并代入1kkkkSxx1()()kkkkSff Gxx11()kkkkSfS x1()()kkkkSff Gxx将式将式与式与式两边相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：11()()()()0kkkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此11()kkkkSfS x212()()kkkffxx1(0,1,2,)kkkkSkxx2212112( )242fxxxx xx，已知初始点，已知初始点1,11,1

40、T Tl解：解： 1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度0120212244()422xxfxxxx010000014141 212S xx为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足1002()min()min(40203)ffSxx0.001迭代精度迭代精度 。 得:00.25120.5x2）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5SfS x21122220.51.50.5 1.5Sxx代入目标函数22( )(22 )2(0.5 1.5 )2(22 )(0.5 1.5 )4(22 )(

41、)f x ( )0 得122240,()8,()20ff xxx因2()0fx收敛。由从而有：l鲍威尔（鲍威尔（PowellPowell）法是直接利用函数值来构造共轭方）法是直接利用函数值来构造共轭方向的一种方法向的一种方法 1( )2TfTxx Gxb xc对函数：对函数：基本思想：基本思想：在不用导数的前提下，在迭代中逐次构造在不用导数的前提下，在迭代中逐次构造G 的共轭方向的共轭方向jjk kkkSd dSjgg gk+1k+1xxk+1设设xk, , xk+1为从不为从不同点出发，沿同同点出发，沿同一方向一方向Sj j进行一进行一维搜索而得到的维搜索而得到的两个极小点两个极小点. .

42、l梯度和等值面相垂直的性质梯度和等值面相垂直的性质, , Sj j和和 xk, , xk+1两点两点处的梯度处的梯度gk, ,gk+1之间存在关系之间存在关系: :1()0,()0jTkjTkSSgg另一方面，对于上述二次函数，其另一方面，对于上述二次函数，其xk, , xk+1两点处两点处的梯度可表示为的梯度可表示为: :11,kkkkgGxbgGxb因而有因而有11() ()()()0jTkkjTkkSSggG xx1kkkSxx取取这说明只要沿这说明只要沿Sj j方向分别对函作两次一维搜索，方向分别对函作两次一维搜索，得到两个极小点得到两个极小点xk和和xk+1 ，那么这两点的，那么这两

43、点的连线连线所给出的方向所给出的方向Sk k就是与就是与Sj j一起对一起对G共轭共轭的方向。的方向。l二维情况描述鲍威尔的基本算法二维情况描述鲍威尔的基本算法: : 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 10012,xx11002S xxx1x2x0o oe1e2d1d

44、2x*102x10 x11x12x01x用用 S1代替代替e1 1形成两个线性无关向量形成两个线性无关向量S1 , ,e2 2 ，作为，作为下一轮迭代的搜索方向。再从下一轮迭代的搜索方向。再从 出发，沿出发，沿S1作一作一维搜索得点维搜索得点 ，作为下一轮迭代的初始点。，作为下一轮迭代的初始点。 x1x2x0o oe1e2d1d2x*102x10 x11x12x01x02x3 3）从出发）从出发 ，顺次，顺次沿沿e2 2, ,S1 作一维搜索，作一维搜索，得到点得到点 ，两点，两点连线得一新方向连线得一新方向: :1112,x x21120S xx沿沿S2作一维搜索得点作一维搜索得点x2 .

45、即是二维问题的极即是二维问题的极小点小点x* .方法的基本迭代格式包括共方法的基本迭代格式包括共轭方向产生和方轭方向产生和方向替换两主要步骤。向替换两主要步骤。10 x10 xl 把二维情况的基本算法扩展到把二维情况的基本算法扩展到n维，则鲍威维，则鲍威尔基本算法的要点是：尔基本算法的要点是：l 在每一轮迭代中总有一个始点（第一轮的在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和始点是任选的初始点）和n个线性独立的搜索个线性独立的搜索方向。从始点出发顺次沿方向。从始点出发顺次沿n个方向作一维搜索个方向作一维搜索得一终点，由得一终点，由始点和终点决定了一个新的搜索始点和终点决定了一个新

46、的搜索方向。方向。l 用这个方向替换原来用这个方向替换原来n个方向中的一个，于个方向中的一个，于是形成新的搜索方向组。替换的原则是是形成新的搜索方向组。替换的原则是去掉原去掉原方向组的第一个方向而将新方向排在原方向的方向组的第一个方向而将新方向排在原方向的最后最后。此外规定，从这一轮的搜索终点出发沿。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。为下一轮迭代的始点。这样就形成算法的循环。 上述基本算法仅具有理论意义上述基本算法仅具有理论意义 。l 因为在迭代中的因为在迭代中的n个搜索方

47、向有时会变成线个搜索方向有时会变成线性相关而不能形成共轭方向性相关而不能形成共轭方向。这时张不成。这时张不成n维维空间，可能求不到极小点，所以上述基本算法空间，可能求不到极小点，所以上述基本算法有待改进。有待改进。 在鲍威尔基本算法中，每一轮迭代都用连结在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的组中的第一个向量，而不管它的“好坏好坏”，这，这是产生向量组线性相关的原因所在。是产生向量组线性相关的原因所在。 在改进的算法中在改进的算法中首先判断原向量组是否需要替首先判断原向量组是否需要替换。换

48、。如果需要替换，还要如果需要替换，还要进一步判断原向量组进一步判断原向量组中哪个向量最坏，中哪个向量最坏，然后然后再用新产生的向量替换再用新产生的向量替换这个最坏的向量，这个最坏的向量，以保证逐次生成共轭方向。以保证逐次生成共轭方向。l为此，要解决两个关键问题为此，要解决两个关键问题：l（1）Sk1是否较好？是否应该进入新的方向是否较好？是否应该进入新的方向组？即方向组是否进行更新？组？即方向组是否进行更新？l（2）如果应该更新方向组，）如果应该更新方向组， Sk1不一定替换不一定替换方向方向 ，而是有选择地替换某一方向，而是有选择地替换某一方向 。1kSkmS令在令在k次循环中次循环中002

49、31()()()kknknFfFfFfxxx01,kkknnxxx100()2kkkkkknnnnxxxxxx（）分别称为一轮迭代的始点、终点和反射点分别称为一轮迭代的始点、终点和反射点 。l则在循环中函数下降最多的第则在循环中函数下降最多的第m次迭代是次迭代是()(0,1,2, )kiiffinx1(1,2, )iiiffin 记记：11maxmimmi nff 相应的方向为相应的方向为 。kmS为了构成共为了构成共轭性好的方向组，须遵循下列准轭性好的方向组，须遵循下列准则：则：在在k次循环中，若次循环中，若满足条件满足条件：30FF和和202302(2)()mFFFFF2030.5()mF

50、F则选用新方向则选用新方向Sk，并在第并在第k+1迭代中用迭代中用Sk替换对应于替换对应于 的方向的方向 。否则，仍然用原方向组进行第。否则，仍然用原方向组进行第k+1迭代。迭代。mkmS002,nFfFf因此因此l 这样重复迭代的结果，后面加进去的向量这样重复迭代的结果，后面加进去的向量都彼此对都彼此对G共轭，经共轭，经n轮迭代即可得到一个由轮迭代即可得到一个由n个共轭方向所组成的方向组。对于个共轭方向所组成的方向组。对于n次函次，次函次，最多最多n次就可找到极小点，而对一般函数，往次就可找到极小点，而对一般函数，往往要超过往要超过n次才能找到极小点（这里次才能找到极小点（这里“n”表示表示

51、设计空间的维数）。设计空间的维数）。 l例例3.4-5 3.4-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数l的最优解。已知初始点的最优解。已知初始点1,11,1T T，迭代精度，迭代精度2212112( )242fxxxx xx0.001。解：（解：（1 1）第）第1 1轮迭代计算轮迭代计算， 0011 x0000()3Fff x沿沿e1方向进行一维搜索方向进行一维搜索0201min()43fxe12得得00101 11132101 xxe011()7ff xl以以 为起点，沿第二坐标轴方向为起点，沿第二坐标轴方向 e2 进行一维进行一维搜索搜索01x0212min()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x确定此轮中的最大下降量及其相应方向确定此轮中的最大下降量及其相应方向 0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 反