第5章 无约束优化方法

《第5章 无约束优化方法》由会员分享，可在线阅读，更多相关《第5章 无约束优化方法（94页珍藏版）》请在装配图网上搜索。

1、 5-1 5-1 最速下降法（梯度法）最速下降法（梯度法）5-2 5-2 牛顿类方法牛顿类方法5-3 5-3 变尺度法变尺度法5-4 5-4 共轭方向法共轭方向法 5-5 5-5 鲍威尔方法鲍威尔方法5-6 5-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 在最速下降法中，在最速下降法中，相邻两个迭代点上的函相邻两个迭代点上的函数梯度相互垂直。而搜数梯度相互垂直。而搜索方向就是负梯度方向，索方向就是负梯度方向，因此相邻两个搜索方向因此相邻两个搜索方向互相垂直。这就是说在互相垂直。这就是说在迭代点向函数极小点靠迭代点向函数极小点靠近的过程，走的是曲折近的过程，走的是曲折的路线。形成的路线。形成“之之”字字形的锯齿现象，而且越形的锯齿现象，而且越接近极小点锯齿越细。接近极小点锯齿越细。 图图5-2 最速下降法的搜索路径最速下降法的搜索路径方法特点方法特点（1 1）初始点可任选，每次迭代计算量小，存储）初

8、始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。然后慢慢逼近局部极小点。 （2 2）任意相邻两点的搜索方向是正交的，它的）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。小点时，步长变得很小，越走越慢。 开始给定结束0,x()kkf dx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k s sk k00

9、102()10424()50100 xfxfxxx沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有01000024()2 100fxxx0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件 122()min (24 )25(2 100 )min ( )f x例例5-1 5-1 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点则初始点处函数值及梯度分别为则初始点处函数值及梯度分别为02,2Tx2212( )25fxxx00( )8(24)5 000(2 100)0 算出一维搜索最佳步长算出一维搜索最佳步长 06260.020 030 7231 2

10、52第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 00Tx()0fx 这个问题的目标函数的等值线为一簇椭圆这个问题的目标函数的等值线为一簇椭圆, ,迭代点从迭代点从 走的是一段锯齿形路线，见图走的是一段锯齿形路线，见图5-3。0 x1 1图图5-3将上例中目标函数将上例中目标函数 引入变换引入变换2212( )25fxxx221212(,)y yyy其等值线由椭圆变成一簇同心圆。其等值线由椭圆变成一簇同心圆。

11、仍从仍从 即即 出发进行最速下降法出发进行最速下降法寻优。此时：寻优。此时：02,2Tx02,10Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索：沿负梯度方向进行一维搜索：则函数则函数f(f(X X) )变为：变为：y1=x1, y2=5x21000000()242410201020yyy为一维搜索最佳步长，可由极值条件：为一维搜索最佳步长，可由极值条件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552从而算得一步计算后设计点的位置及其目标函数：从而算得一步计算后设计点的位置及其目标函数：010124010200

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

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

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

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

16、,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 阻尼牛顿法程序框图方法特点方法特点 （1） 初始点应选在初始点应选在X*附近，有一定难度；附近，有一定难度； （2） 尽管每次迭代都不会是函数值上升，但不能保证尽管每次迭代都不会是函数值上升，但不能保证每次下降每次下降 ； （3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；不能构造牛顿法方向； （4） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的

17、计算量和存储量大。此外，对于二阶不可微的F(X)也也不适用。不适用。 虽然阻尼牛顿法有上述缺点，但在特定条件下它虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和具有收敛最快的优点，并为其他的算法提供了思路和理论依据。理论依据。1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：梯度法与牛顿法：梯度法与牛顿法：1()kkkkkfxxAx DFP变

18、尺度法首先有戴维顿（变尺度法首先有戴维顿（Davidon）与）与1959年提出，又于年提出，又于1963年由弗莱彻（年由弗莱彻（Fletcher）和鲍维尔加）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。以发展和完善，成为现代公认的较好的算法之一。 DFP法是基于牛顿法的思想又作了重要改进。这法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。速度。 1. 基本思想基本思想 变量的尺度变换是放大或缩小各个坐标。通

19、过尺变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。 例如在用最速下降法求例如在用最速下降法求 的极小的极小2212( )25fxxx值时值时 ,需要进行需要进行10次迭代才能达到极小点次迭代才能达到极小点0,0Tx 如作变换如作变换 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍，则目标函数等值线由一簇倍，则目标函数等值线由一簇椭圆变成一簇同心圆。椭圆变成一簇同心圆。x2221212(,)y yyy 消除了函数的偏心，用最速下降法只需一次迭消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。代即可求得极

20、小点。 梯度法构造简单，只用到一阶偏导数，计算量小，梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近快；其主要缺点是迭代点接近X*时，即使对二次正时，即使对二次正定函数收敛也非常慢。定函数收敛也非常慢。 牛顿法收敛很快，对于二次函数只需迭代一次便牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算

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

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

23、迭代公式：牛顿迭代公式：1()(0,1,2,)kkTkkQQfkxxx记：记：TAQQ搜索方向：搜索方向：1()(0,1,2,)kkksfk Ax迭代公式：迭代公式：1()(0,1,2,)kkkkkfkxxAxA A 称为变尺度矩阵称为变尺度矩阵2212( )25fxxx在例在例5-2中中122121222011( )2505022Txfxxx xxxx Gx20050G如取如取102105 2Q11002010221050101005 25 2TQ GQI求得：求得：1111000222111000505 25 2TGQQ从初始矩阵从初始矩阵A0=I(单位矩阵单位矩阵)开始，通过对公式开始，

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

25、FGS算法对于维数较高问题具有更好的稳算法对于维数较高问题具有更好的稳定性。定性。 1 kkTkTkkkkkTkTkkTkkkkTkkTxxgAgAxxxgxgAgxxgA开始给定结束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gxgggxxx11kkk AAA01kxx0k kkk dA g是否221212112( ,)242f x xxxxx xl解：解： 1）取初始点）取初始点 ，为了按，为了按DFP法构造第法构造第一次搜寻方向一次搜寻方向d0，需计算初始点处的梯度，需计算初始点处的梯度01 1T

26、x01200212244()422xxfxxxgx取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I，则第一次，则第一次搜寻方向为搜寻方向为 00010440122 dA gl沿沿d0方向进行一维搜索，得方向进行一维搜索，得010000014141 212 xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足01002()min()min(40203)ffxxd得得:00.25120.5x,2）再按）再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向d1，需计算，需计算1121212241422xxxxxg010143224ggg0102110.510.5 xxx代入校正公

27、式代入校正公式000000000000TTTTxxAggAAxggAg1310.5340.543310.53444=100AAA21191010.5912112550010.50.251216194152550100=第二次搜寻方向为第二次搜寻方向为1118665 dA g再沿再沿d1进行一维搜索，得进行一维搜索，得12111182560.55xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足12112811()min()min(4)52ffxxd154242 x,得得3）判断判断x2是否为极值点是否为极值点梯度梯度: : 2122212240()420 xxfxx xx海赛矩阵海赛矩

28、阵 :2222()24fx梯度为零向量梯度为零向量, ,海赛矩阵正定。可见点满足极值海赛矩阵正定。可见点满足极值充要条件，因此为极小点。充要条件，因此为极小点。 *242Txx*()8f xl1.共共轭方向：轭方向：l 设设G为为nn阶实对称正定矩阵，如果有两个阶实对称正定矩阵，如果有两个n维向量维向量d0和和d1满足满足 ，则称向量，则称向量d0与与d1 关于矩阵关于矩阵G共共轭。轭。01()0TdGd当当G为单位矩阵时为单位矩阵时，01()0Tdd假设目标函数假设目标函数f(x) 在极值点附近的二次近似函数为在极值点附近的二次近似函数为1( )2TfTxx Gxb xc对二维情况对二维情况

29、任选取初始点任选取初始点x0沿某个下降方向沿某个下降方向d d0 0作一维搜索，得作一维搜索，得x11000 xxd 因为因为 是沿是沿d0方向搜索的最佳步长，即在点方向搜索的最佳步长，即在点x1处函数处函数f（x）沿方向）沿方向d0的方向导数为零。考虑到点的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有处方向导数与梯度之间的关系，故有01100()0Tff xxdd如果按最速下降法，选择负梯度方向如果按最速下降法，选择负梯度方向 为搜为搜索方向，则将发生锯齿现象索方向，则将发生锯齿现象 。1()fx 取下一次的迭代搜索方向取下一次的迭代搜索方向d1直指极小点直指极小点x* *。0

30、d0 x0 x1x*1 11d11()fxd1l如果能够选定这样的搜索方向，那么对于二元二次如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行函数只需顺次进行d0、d1两次直线搜索就可以求到两次直线搜索就可以求到极小点极小点x* * ，即有，即有111xxd那么这样的那么这样的d1方向应该满足什么条件呢方向应该满足什么条件呢 ? ?对于前述的二次函数对于前述的二次函数: :1( )2TfTxx Gxb xc当当 时，时，1xx10 x* *是是f( (x) )极小点，应满足极值必要条件，故有极小点，应满足极值必要条件，故有()0fxGxb111111()()()ff xG xdbxG

31、d0将等式两边同时左乘将等式两边同时左乘 得得：0()Td01()0TdGd11()fxGxb有有01()0TdGd 就是使就是使d1直指极小点直指极小点x* * ， d1所必须满足的条件所必须满足的条件 。两个向量两个向量d0和和d1称为称为G的共轭向量，或称的共轭向量，或称d0和和d1对对G是共轭方向。是共轭方向。 2.2.共轭方向的性质共轭方向的性质性质性质1 1 若非零向量系若非零向量系d0, ,d1, ,d2,dm-1是对是对G共轭，共轭，则这则这m个向量是线性无关的。个向量是线性无关的。性质性质2 2 在在n维空间中互相共轭的非零向量的个数维空间中互相共轭的非零向量的个数不超过不超

32、过n。 性质性质3 3 从任意初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭方的共轭方向向d0, ,d1, , d2,进行一维搜索，最多经过进行一维搜索，最多经过n次迭代就次迭代就可以找到的二次函数可以找到的二次函数f( (x) )极小点。极小点。 021()( )0Tfdx d开始给定结束00,x d1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共轭方向关键：新的共关键：新的共轭方向轭方向确定确定 在无约束方法中许多算法都是以共轭方向在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造作为搜索方向，它们具有许多特点。根据

33、构造共轭方向的原理不同，可以形成不同的共轭方共轭方向的原理不同，可以形成不同的共轭方向法。向法。 l共轭梯度法是共轭方向法中的一种，该方法中共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。而构造出来。l 从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索:1(0,1,2,)kkkkkxxd()kkf dx设与设与dk共共轭的下一个方向轭的下一个方向dk+1由由dk和点和点xk+1的负梯的负梯度的线形组合构成，即：度的线形组合构成，即：11()kkkkf dxd21()( )0kTkfdx d共轭条

34、件：共轭条件：l则：则：21()( )()0kTkkkfff xxxd解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc为函数的泰勒二次展开式为函数的泰勒二次展开式()kkfxGxb则则11()kkfxGxb上两式相减，并代入上两式相减，并代入1kkkkxxd1()()kkkkff Gdxx1()()kkkkff Gdxx将式将式11()kkkkf dxd与式与式两边相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：11()()()()0kkkkkffff xxxx21112()()()()()()kkTkkkTkkff

35、ffffxxxxxx因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd2212112( )242fxxxx xx，已知初始点，已知初始点1,11,1T Tl解：解： 1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度0120212244()422xxfxxxx010000014141 212 xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足1002()min()min(40203)ffxxdl迭代精度迭代精度 。 0.001得得:00.25120.5x2）第二次迭代：）第二次迭代：21200()50.

36、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收敛。收敛。( )0 由由22240,()8,()20ff xxx从而有：从而有： 鲍威尔法是以共轭方向为基础的收敛较鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。快的直接法之一，是一种十分有效的算法。 1964年，鲍维尔提出这种算法，其基本思想年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共是

37、直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。的实践中进行了改进。 1()2TfTxx G xbxc对函数：对函数：基本思想基本思想：在不用导数的前提下，在迭代中逐次构造：在不用导数的前提下，在迭代中逐次构造G的共轭方向。的共轭方向。 1.1.共轭方向的生成共轭方向的生成jjkkkdd ddjgg gk+1xxk+1设设xk, , xk+1为从不同为从不同点出发，沿同一方向点出发，沿同一方向dj j进行一维搜索而到进行一维搜索而到的两个极小点。

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

39、两点的连线所，那么这两点的连线所给出的方向给出的方向dk k就是与就是与dj 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作一维搜索，得作一维搜索，得 点，两点连线点，两点连线得一新方向得一新方向d1 10012,x x1002dxxx1x2x0oe1

40、e2d1d2x*102x10 x11x12x01xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x21120dxx沿沿d2作一维搜索得点作一维搜索得点x2 。 即是二维问题的极即是二维问题的极小点小点x* 。方法的基本迭代格式包括共方法的基本迭代格式包括共轭方向产生和方向替换两轭方向产生和方向替换两主要步骤。主要步骤。用用 d1代替代替e1 1形成两个线性无关向量形成两个线性无关向量d1 , ,e2 2 ，作为，作为下一轮迭代的搜索方向。再下一轮迭代的搜索方向。再 从出发，沿从出发，沿d1作一作一维搜索得点维搜索得点 ，作为下一轮迭代的初始点。，作为下一轮迭代的初始点。

41、 02x10 x3 3）从出发）从出发 ，顺次，顺次沿沿e2 2, ,d1 作一维搜索，作一维搜索，得到点得到点 ，两点连，两点连线得一新方向线得一新方向: :1112,xx10 xl 把二维情况的基本算法扩展到把二维情况的基本算法扩展到n维，则鲍威尔维，则鲍威尔基本算法的要点是：基本算法的要点是：l 在每一轮迭代中总有一个始点（第一轮的始点在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和是任选的初始点）和n个线性独立的搜索方向。个线性独立的搜索方向。从始点出发顺次沿从始点出发顺次沿n个方向作一维搜索得一终点，个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。由始点和终点

42、决定了一个新的搜索方向。l 用这个方向替换原来用这个方向替换原来n个方向中的一个，于是个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。代的始点。这样就形成算法的循环。 l 因为在迭代中的因为在迭代中的n个搜索方向有时会变成线性个搜索方向有时会变成线性相关而不能

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

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

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

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

47、。表示设计空间的维数）。 l例例5-5 5-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数2212112( )242fxxxx xx解：（解：（1 1）第）第1 1轮迭代计算轮迭代计算， 0011 x0000()3Fff x沿沿e1方向进行一维搜索方向进行一维搜索0201min()43fxe12得得00101 11132101 xxe011()7ff x0.001。l的最优解。已知初始点的最优解。已知初始点1,11,1T T，迭代精度，迭代精度以以 为起点，沿第二坐标轴方向为起点，沿第二坐标轴方向 e2 进行一维进行一维搜索搜索01x0212min()227fxe20.5得得0021

48、213030.5111.5 xxe022()7.5ff x确定此轮中的最大下降量及其相应方向确定此轮中的最大下降量及其相应方向 0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 反射点及其函数值反射点及其函数值， 000320315221.512 xxx033()7Ff x检验检验PowellPowell条件条件202302(2)()1.25mFFFFF2030.5()32mFF3073FF 由于满足由于满足PowellPowell条件，则淘汰函数值下降量最条件，则淘汰函数值下降量最大的方向大的方向e1，下一轮的基本方向组为，下一轮的基本方向组为

49、e2， 。03d构成新的方向构成新的方向 0003203121.510.5 dxx沿沿 方向一维搜索得极小点和极小值方向一维搜索得极小点和极小值03d13.81.7x1()7.9f x，此点为下轮迭代初始点。此点为下轮迭代初始点。 按点距准则检验终止条件按点距准则检验终止条件 11220(3.8 1)(1.71)2.886xx需进行第二轮迭代机算。需进行第二轮迭代机算。l（2 2）第）第2 2轮迭代计算轮迭代计算此轮基本方向组为此轮基本方向组为e2， ，分别相当于，分别相当于 ， ，起始点为起始点为 。03d11d12d10 x1x沿沿e2方向进行一维搜索得方向进行一维搜索得 113.81.9

50、x111()7.98ff x以以 为起点沿为起点沿 方向一维搜索得方向一维搜索得11x03d123.961.9x122()7.996ff x确定此轮中函数值最大下降量及其相应方向确定此轮中函数值最大下降量及其相应方向10.08 20.016 12max,0.08m l反射点及其函数值反射点及其函数值1113203.963.84.12221.941.72.18xxx133()7.964Ff x检验检验Powell条件，淘汰函数值下降量最大的方条件，淘汰函数值下降量最大的方向向e2，下一轮的基本方向组应为，下一轮的基本方向组应为 ， 。 03d13d构成新的方向构成新的方向1113203.963.

51、80.161.941.70.24dxx沿沿 方向进行一维搜索得方向进行一维搜索得13d242 x2()8f xl检验终止条件检验终止条件 22220(43.8)(2 1.7)0.36xx（3 3）第）第3 3轮迭代计算轮迭代计算此轮基本方向组为此轮基本方向组为 ， ，起始点为，起始点为 ，先，先后沿后沿 ， 方向，进行一维搜索，得方向，进行一维搜索，得03d13d20 x2x03d13d2242 x2142 x，22200 xx*42 x*()8f x故最优解故最优解检验终止条件检验终止条件l 实际上，前两轮迭代的实际上，前两轮迭代的 ， 为共轭方向，由于为共轭方向，由于本例目标函数是二次函数

52、，按共轭方向的二次收敛性，本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行要进行n+1次迭代。次迭代。 13d23d 前面介绍的许多优化方法，除鲍威尔（前面介绍的许多优化方法，除鲍威尔（Powell）法外，都需要计算目标函数的导数，而在实际工程的法外，都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根最优化问题中，目标函数的导数往往很难求出或者根本无法求出。下面所介绍的方法只需要计算目标函数本无法求出。下面所介绍的方法只需要计算目标函数值，无需求其导数，因此

53、计算比较简单，其几何概念值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类也比较清晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。体算法的情况。这也是直接法的一个优点。 是将一个是将一个n维优化问题转化为维优化问题转化为依次沿依次沿n个坐标方向反复进行个坐标方向反复进行一维搜索问题。这种方法的实一维搜索问题。这种方法的实质是把质是把n维问题的求优过程转维问题的求优过程转化为对每个变量逐次进行一维化为对每个变量逐次进行一维求优的循环过程

54、。每次一维搜求优的循环过程。每次一维搜索时，只允许索时，只允许n个变量的一次个变量的一次改动，其余改动，其余(n-1)个变量固定不个变量固定不变。故坐标轮换法也常称单变变。故坐标轮换法也常称单变量法或变量交错法。量法或变量交错法。 此法的效能在很大程度上取决于目标函数的性质。此法的效能在很大程度上取决于目标函数的性质。 （1）计算量少，程序简单，不需要求函数导数的直接）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；探索目标函数最优解的方法；（2）探索路线较长，问题的维数愈多求解的效率愈低。）探索路线较长，问题的维数愈多求解的效率愈低。当维数当维数n10时，则不应采用此法。

55、仅适用于时，则不应采用此法。仅适用于n较少（较少（n 0，模矢加速搜索的加速步长，模矢加速搜索的加速步长因子为因子为a1（通常取（通常取a=2），迭代终止准则为），迭代终止准则为 ( 为为预先确定的正数）。预先确定的正数）。neeen依次是,21);2(, 1, 0),(),()(10转令成功步长加速即若kkjXfYfk0, 0,00jkXY（1 1）其它情形当当,)()(,)()(,11111jjjjjjjjjjjjYYfeYfeYYfeYfeYY（2 2）转令, 1, 1jjnj（3 3）若）若（2 2）；否则，转（）；否则，转（4 4）否则转（否则转（6 6）)2(, 1, 0,10转k

56、kjXYk否则，令否则，令;),( ,计算停止即近似极小点输出若nY（6 6）1, 0,210kkjYYn令否则，否则，转（，转（2 2）（5）)(10kkkXXaXY令,),(),()(10nknYXYfYf令成功试探即若（4 4）转（转（5 5）；）；一、基本思想一、基本思想 单纯形替换法也是一种不使用导数的求解无单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯一个点迭代到另一个更优的点，而是

57、从一个单纯形迭代到另一个更优的单纯形。形迭代到另一个更优的单纯形。定义：单纯形定义：单纯形 n维空间中的恰好有维空间中的恰好有n+1个顶点（极点）的有界的个顶点（极点）的有界的凸多面体称之为一个单纯形。凸多面体称之为一个单纯形。 根据定义，可知，一维空间中的单纯形是线段，根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。形则是四面体。 在单纯形替换算法中，从一个单纯形到另一个单在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这纯形的迭代主要通过反射、扩张、收缩和缩

58、边这4个个操作来实现。下面以二维问题为例来对操作来实现。下面以二维问题为例来对4种操作进行种操作进行说明（参见下图）。说明（参见下图）。（1 1）反射）反射设除了最劣点设除了最劣点X X1 1以外的基余顶点的中心为以外的基余顶点的中心为X X4 4，作，作X X1 1关于点关于点X X4 4的对称点的对称点X X5 5，称，称X X5 5为为X X1 1的反射点。求反射点的过程称的反射点。求反射点的过程称之为反射。之为反射。)()()(321XfXfXf（2 2）扩张）扩张在得到反射点在得到反射点X X5 5之后，如果之后，如果X X5 5优于原单纯形的最劣优于原单纯形的最劣点（即有点（即有

59、），表明反射方向（），表明反射方向（X X5 5XX1 1）是有利方向，）是有利方向，反射成功。若进一步有反射成功。若进一步有 ，可沿反射方向前进适当，可沿反射方向前进适当的距离到点的距离到点X X6 6。X X6 6称之为扩张点，求扩张点的过程称之为扩张。扩称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点张之后，若扩张点X X6 6优于反射点优于反射点X X5 5，则扩张成功，以，则扩张成功，以X X6 6取代取代X X1 1，得，得新单纯形新单纯形XX6 6,X,X2 2,X,X3 3 ；否则，扩张失败，舍弃扩张点，以反射；否则，扩张失败，舍弃扩张点，以反射X X5 5点点取代取

60、代X X1 1，得新单纯形，得新单纯形XX5 5,X,X2 2,X,X3 3 。)()(15XfXf)()(25XfXf设当前的单纯形的顶点为设当前的单纯形的顶点为X X1 1，X X2 2，X X3 3，且有，且有)()()(251XfXfXf如果出现如果出现 。表示反射完全失败，应退回到介于。表示反射完全失败，应退回到介于X X4 4与与X X1 1之间的某个点之间的某个点X X8 8。)()(15XfXf（3 3）收缩）收缩在得到反射点在得到反射点X X5 5之后，如果有之后，如果有表示反射部分成功，方向（表示反射部分成功，方向（X X5 5XX1 1）虽然是有利方向，但）虽然是有利方向

61、，但X X5 5前前进过远，应收缩到介于进过远，应收缩到介于X X4 4与与X X5 5之间的某个点之间的某个点X X7 7。 上述两种从反射点向上述两种从反射点向X1方向后退的过程都称之为收缩。方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点如果收缩点优于原来的最劣点X1，称收缩成功，并以收缩，称收缩成功，并以收缩点取代原最劣点，构成新单纯形点取代原最劣点，构成新单纯形X7,X2,X3或或X8,X2,X3；否；否则，称之为收缩失败，舍弃收缩点。则，称之为收缩失败，舍弃收缩点。（4）缩边）缩边若收缩失败，则应压缩当前单纯形的边长：令若收缩失败，则应压缩当前单纯形的边长：令最优点最优点X3

62、不动，而其余顶点向不动，而其余顶点向X3方向压缩，使边长缩短（通常方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点缩短一半），以产生新单纯形。如下图所示，点X1压缩到点压缩到点X9，点点X2压缩到点压缩到点X10，得新单纯形，得新单纯形X9,X10,X3，这一过程称之为缩，这一过程称之为缩边。边。二、单纯形替换算法二、单纯形替换算法设初始点为设初始点为X X0 0，初始边长，初始边长h h，e ei i为坐标轴方向的单位向量为坐标轴方向的单位向量 ，预定正数预定正数, 2 , 1ni21,（2 2）比较各项点）比较各项点X Xi i的函数值，挑出其中的最优点，记为的函数值，

63、挑出其中的最优点，记为X XL L；最劣；最劣点，记点，记X XH H；次差点，记为；次差点，记为X Xw w；（3 3）求反射中心）求反射中心21nnXX和反射点)(1 112)(01HnnnnHiiinXXaXXXnX其中，其中，a0，通常取，通常取a=1； （1 1）令）令, 2 , 1,100niiXXXniheXX构造单纯形；输出输出XL，为原问题近似极小点；否则，转（，为原问题近似极小点；否则，转（2）。）。构造新单纯形；构造新单纯形；5 . 0（4）根据不同）根据不同情情况，分别进行扩张，况，分别进行扩张，收缩或缩边，其中收缩因子收缩或缩边，其中收缩因子1121max )()(L

64、iniLiXXXfXf（5）如果满足）如果满足kk dg1kkk dGg1kGkkk dQ g111kTkkkTkgdQIggkkk dA g11kkkAAA1kkAG搜索方向搜索方向函数梯度的修正函数梯度的修正因子因子所用目标函数所用目标函数信息信息梯度法梯度法I I（单位阵）（单位阵）一阶导数一阶导数（ 阻 尼 ） 牛（ 阻 尼 ） 牛顿法顿法二阶导数二阶导数共轭梯度法共轭梯度法一阶导数一阶导数变尺度法变尺度法一阶导数，使一阶导数，使（海赛矩阵的逆阵）（海赛矩阵的逆阵）1、梯度法、梯度法 方向方向 负梯度负梯度 用到一阶导数用到一阶导数 适合于精度不高或用于复杂函数寻找一个好的初始点适合于

65、精度不高或用于复杂函数寻找一个好的初始点2、牛顿法、牛顿法 用到一阶导数和海色矩阵，具有二次收敛性用到一阶导数和海色矩阵，具有二次收敛性 要求海色矩阵奇异，且维数不宜太高要求海色矩阵奇异，且维数不宜太高3、共轭梯度法、共轭梯度法 用到一阶导数，具有二次收敛性用到一阶导数，具有二次收敛性4、变尺度法、变尺度法 收敛快，效果好，被认为是目前最有效的无约束优化收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数方法。适用于维数较高，具有一阶偏导数的目标函数 1、坐标轮换法、坐标轮换法 计算效率较低计算效率较低 适合维数较低，目标函数无导数或导数较难求得适合维数

66、较低，目标函数无导数或导数较难求得2、步长加速法、步长加速法 同坐标轮换法，对目标函数的性态的适应性更好同坐标轮换法，对目标函数的性态的适应性更好3、Powell法法 具有二次收敛性，收敛速度较快，可靠性高，被认具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一为是直接法中最有效的方法之一4、单纯形法、单纯形法 思路清楚，收敛慢思路清楚，收敛慢 Powell法优化设计程序法优化设计程序与一维搜索黄金分与一维搜索黄金分割法组合割法组合题目：编程求解函数题目：编程求解函数的极小点的极小点x*。2212112( )242fxxxx xx初始点初始点x x0 0=1,1=1,1T T，迭代精度，迭代精度 。0.001上机地点：上机地点： 时间：周一晚时间：周一晚6:009:30