机械优化设计4无约束方法

1、航空航天学院第四章第四章 无约束优化方法无约束优化方法3) 3) 坐标轮换法坐标轮换法4) 4) 鲍威尔法鲍威尔法2) 2) 牛顿法牛顿法1) 1) 最速下降法最速下降法航空航天学院 第第1章所列举的机械优化设计问题，都是在一定的限制条件章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。都如此。 为什么要研究无约束优化问题为什么要研究无约束优化问题? (1)有些实际问题，其数学模型本身就是一个无约束优化问题。有些实际问题，其数学模型本身就是一个无约束优化问题。 (2)通过熟悉它

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

3、有理论意义，但在实际应用中受到限制。极小点，这种方法有理论意义，但在实际应用中受到限制。和一维问题一样，若多元函数和一维问题一样，若多元函数F(X)不可微，亦无法求解。但不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。古典极值理论是无约束优化方法发展的基础。 航空航天学院一）无约束优化问题描述一）无约束优化问题描述4-1 4-1 概概 述述 若若F(X)F(X)存在一阶导数，则可按照如前所述的极值条件来确定其存在一阶导数，则可按照如前所述的极值条件来确定其极值点可能的位置极值点可能的位置( (称为驻点称为驻点) )。即求方程。即求方程 的解。也就是求的解。也就是求X X，使其满足

4、，使其满足0F1200.0nFxFxFx特点：特点：1. n1. n个未知量个未知量n n个方程的方程组，一般是非线性的个方程的方程组，一般是非线性的2. 2. 求解该方程组与求无约束极值一样困难，求解该方程组与求无约束极值一样困难， 甚至更困难。甚至更困难。12min() (4-1) ,TnnF XXx xxR航空航天学院二）无约束优化问题求解概述二）无约束优化问题求解概述 若用数值计算方法求解问题若用数值计算方法求解问题4-14-1，按照寻优思路不同，可分为：，按照寻优思路不同，可分为：搜索类方法和单纯形类方法。搜索类方法和单纯形类方法。1(0,1,2,)kkkkXXa Sk1. 1. 若

5、给定方向若给定方向Sk，多维无约束优化问题，多维无约束优化问题一维优化设计问题一维优化设计问题2. 2. 若未给定方向若未给定方向Sk，不同搜索类无约束优化，不同搜索类无约束优化方法的区别在于方法的区别在于确定其搜索方向确定其搜索方向Sk的方法不同的方法不同 爬山类方法。搜索方向的构成问题是无约爬山类方法。搜索方向的构成问题是无约束优化方法的关键束优化方法的关键 搜索类基本思想是从某一给定的初始点搜索类基本思想是从某一给定的初始点X0开始，沿给定的搜索方开始，沿给定的搜索方向向S0进行搜索，确定步长进行搜索，确定步长a0使函数值沿使函数值沿S0下降最大下降最大(或达到给定的或达到给定的值值)

6、。其迭代格式如下：。其迭代格式如下：航空航天学院开始给定x0和S0以及，k=1最小化F(Xk+akSk)结束收敛？形成新Sk，k=k+1爬山类方法的寻优思想航空航天学院步长和方向的形成和确定方法不同就派生出不同的步长和方向的形成和确定方法不同就派生出不同的n n维无约维无约束优化方法，按照是否用到函数的导数束优化方法，按照是否用到函数的导数三）求解方法分类三）求解方法分类1. 1. 直接法直接法( (不用导数的信息不用导数的信息) )2. 2. 间接法间接法( (用到导数的信息用到导数的信息) )坐标轮换法坐标轮换法单形替换法单形替换法鲍威尔鲍威尔(Powell)(Powell)最速下降法最速

7、下降法共轭梯度法共轭梯度法牛顿法牛顿法航空航天学院4-2 4-2 最速下降法最速下降法( (梯度法梯度法) )一）梯度方向一）梯度方向* *可取最优步长或下降步长可取最优步长或下降步长二）基本思想二）基本思想 梯度方向是目标函数上升最快的方梯度方向是目标函数上升最快的方向，负梯度方向则是最速下降方向；向，负梯度方向则是最速下降方向；)()()()() 1(kkkkXFXX2 2）迭代公式迭代公式1 1）沿沿负梯度方向搜索负梯度方向搜索：)()()()(kkkgXFS kg三）终止判别条件三）终止判别条件航空航天学院 为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向 能够获得最大的下能够获得

8、最大的下降值，其步长因子降值，其步长因子 应取一维搜索的最佳步长。即有应取一维搜索的最佳步长。即有()kf xk1()()min()min ( )kkkkkkaaffaffa f xxxxx根据一元函数极值的必要条件和多元复合函数求导公式，得根据一元函数极值的必要条件和多元复合函数求导公式，得( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kTkss航空航天学院 在最速下降法中，相邻在最速下降法中，相邻两个迭代点上的函数梯度相两个迭代点上的函数梯度相互垂直。而搜索方向就是负互垂直。而搜索方向就是负梯度方向，因此相邻两个搜梯度方向，因此相邻两个搜索方向互相垂直。这就是说

9、索方向互相垂直。这就是说在迭代点向函数极小点靠近在迭代点向函数极小点靠近的过程，走的是曲折的路线。的过程，走的是曲折的路线。形成形成“之之”字形的锯齿现象，字形的锯齿现象，而且越接近极小点锯齿越细。而且越接近极小点锯齿越细。 最速下降法的搜索路径最速下降法的搜索路径航空航天学院航空航天学院给定给定 X0 ，K=0 ，X（K）=X0K=K+1X(k)=XX*= X（K）F*=F（X*）结结 束束NY计算计算)()(,kkgg)(kg 从从 出发出发，沿沿 搜索得搜索得)(kX)(kg)()()(kkkgXX* * “最速下降性最速下降性”只只是迭代点邻域的局部是迭代点邻域的局部性质。从全局看，并

10、性质。从全局看，并非最速下降方向。非最速下降方向。四四. .迭代步骤迭代步骤航空航天学院特点特点（1 1）初始点可任选，每次迭代计算量小，存储量少，）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。迭代，目标函数值下降很快，然后慢慢逼近局部极小点。 （2 2）任意相邻两点的搜索方向是正交的，它的迭代路）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。

11、得很小，越走越慢。 航空航天学院4. 4. 例例4-14-1 解：解：010224()50100 xxF Xx沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有a0 0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件2212()+25 F Xxx求的极小值 取初始点取初始点X X0 0=2=2，22T T，则初始点处函数值及梯度分别为，则初始点处函数值及梯度分别为0()104F X0000001100242100422)(aaaXFXX)(min)1002(25)42min( )(min)(220001aaaXFXFXFa航空航天学院及第一次迭代设计点位置和函

12、数值及第一次迭代设计点位置和函数值完成了最速下降法的第一轮迭代。经完成了最速下降法的第一轮迭代。经10次迭代后，得到最优解次迭代后，得到最优解 从而得到一维搜索的最佳步长为从而得到一维搜索的最佳步长为00.02003072a 3686164)(,103071785. 0919877. 110024212001XFaaX0)1002(5000)42(8 )(000aaa0)(,00*XFX航空航天学院 若引入变换，令若引入变换，令 这个问题的目标函数这个问题的目标函数F(X)的等值线为一簇椭圆，迭代点从的等值线为一簇椭圆，迭代点从X0X0走的是一段锯齿形路线，如图所示走的是一段锯齿形路线，如图所

13、示22115xyxy 则函数则函数F(x1,x2)变为变为222121),(yyyy 其等值线就从椭圆族变为圆族。仍从其等值线就从椭圆族变为圆族。仍从X X0 0=2=2，22T T，即，即Y Y0 0=2=2，1010T T出发进行最速下降法寻优。此时有出发进行最速下降法寻优。此时有航空航天学院010224()220yyYy沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有a0 0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件0()104Y0000001201042204102)(aaaYYY)(min)(min)(001aYYYa22)2010()42(

14、 )(aaa0)2010(40)42(8- )(0aaa航空航天学院从而得出第一次迭代设计点位置和函数值从而得出第一次迭代设计点位置和函数值可见经过坐标变换后，只需经可见经过坐标变换后，只需经1次迭代后，得到最优解次迭代后，得到最优解 从而得到一维搜索的最佳步长为从而得到一维搜索的最佳步长为0260.552a 0)(,002010421001YaaY0)(,00*XFX航空航天学院M是是f( (x) )的海赛矩阵最大特征值的上界的海赛矩阵最大特征值的上界当相邻两个迭代点之间满足上述关系时，我们称相应的迭代方法当相邻两个迭代点之间满足上述关系时，我们称相应的迭代方法具有线性收敛速度的迭代法。具有

15、线性收敛速度的迭代法。 二次型函数的对角形矩阵刻画了椭圆长短轴，表示度量的矩二次型函数的对角形矩阵刻画了椭圆长短轴，表示度量的矩阵或者是表示尺度的矩阵。最速下降法的收敛速度和变量的尺度阵或者是表示尺度的矩阵。最速下降法的收敛速度和变量的尺度关系很大。最速下降法收敛速度的估计式关系很大。最速下降法收敛速度的估计式21*2(1)kkmxxxxMm是是f( (x) )的海赛矩阵最小特征值的下界的海赛矩阵最小特征值的下界航空航天学院5. 5. 方法评价：方法评价：l迭代过程简单，对初始点的选择，要迭代过程简单，对初始点的选择，要求不高。求不高。l梯度方向目标函数值下降迅速只是个梯度方向目标函数值下降迅

16、速只是个局部性质，从整体来看，不一定是收敛局部性质，从整体来看，不一定是收敛最快的方向。最快的方向。l以二维二次函数为例，相邻两次的搜以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形接近极值点处，容易陷入稳定的锯齿形搜索路径。搜索路径。l梯度法的收敛速度与目标函数的性质梯度法的收敛速度与目标函数的性质密切相关。对于等值线密切相关。对于等值线( (面面) )为同心圆为同心圆（球）的目标函数，一次搜索即可达到（球）的目标函数，一次搜索即可达到极小

17、点。极小点。航空航天学院4-3 4-3 牛顿法牛顿法kkkkgHXXX1)()1(0)()(*kkkXXHg（牛顿方向牛顿方向）kkkgHS1)(1）迭代方向迭代方向：* * 最速下降法只利用了函数一阶导数的信息，在极值点附近收敛较慢，从函数等值最速下降法只利用了函数一阶导数的信息，在极值点附近收敛较慢，从函数等值线特性分析可知，在极值点附近，函数具有二次函数的特性，如果利用二次导数的线特性分析可知，在极值点附近，函数具有二次函数的特性，如果利用二次导数的信息，在极值点附近进行寻优，应该具有较快的收敛速度？信息，在极值点附近进行寻优，应该具有较快的收敛速度？一一. . 原始牛顿法原始牛顿法一）

18、基本思路一）基本思路 用目标函数的近似二次函数的极小点来近似原函数的极小点；用目标函数的近似二次函数的极小点来近似原函数的极小点；二）原始牛顿法的迭代公式二）原始牛顿法的迭代公式原函数原函数:)(XF)()()()(21)()(kkTkkTkkXHXXgXFX近似二次函数近似二次函数:0)()(kkkXHgX令令1)(k2）步长因子步长因子：CXBAXXXFTT21)(BAXXF)(航空航天学院对于二次函数，对于二次函数，f f（x x）的泰勒展开式不是近似的，而是精确的。海赛矩阵）的泰勒展开式不是近似的，而是精确的。海赛矩阵是一个常矩阵，其中各元素为常数。因此，无论从任何点出发，只需一步是一

19、个常矩阵，其中各元素为常数。因此，无论从任何点出发，只需一步就可找到极小点。就可找到极小点。二次收敛：若某一迭代方法能使二次函数在有限次迭代内达到极小点。牛二次收敛：若某一迭代方法能使二次函数在有限次迭代内达到极小点。牛顿方法是二次收敛的顿方法是二次收敛的航空航天学院求逆矩阵？求逆矩阵？解，设解，设B B是是A A的逆矩阵，根据定义得的逆矩阵，根据定义得解得：解得：b1=1,b2=-2,b3=0,b4=1, 即即 设设A是是n阶方阵，如果存在阶方阵，如果存在n阶方阵阶方阵B, 满足满足AB=BA=E则称则称A是可逆矩阵，是可逆矩阵，B是是A的逆矩阵。的逆矩阵。E是是n阶单位矩阵阶单位矩阵100

20、11021102143214321bbbbbbbbBAAB1201A逆矩阵的求法：逆矩阵的求法：定义法；公式法定义法；公式法( (伴随矩阵法伴随矩阵法) )求矩阵求矩阵的逆矩阵的逆矩阵11201A航空航天学院 例例4-24-2 解：解：010224()50100 xxF Xx代入牛顿法迭代公式，得代入牛顿法迭代公式，得从而经过一次迭代即求得极小点和函数值从而经过一次迭代即求得极小点和函数值2212()+25 F Xxx求的极小值 取初始点取初始点X X0 0=2=2，22T T，则初始点处梯度，海赛矩阵及其逆阵，则初始点处梯度，海赛矩阵及其逆阵分别为分别为00100450/1002/122)(

21、)(010201XFXFXX2020()050F X2011/20()01/50F X航空航天学院二）阻尼牛顿法二）阻尼牛顿法)()()(1)()()()1(kkkkkXfXHXX* *具有二次收敛性，但用到二阶导数矩阵求逆具有二次收敛性，但用到二阶导数矩阵求逆仍取牛顿方向，但改用最优步长因子，在牛顿方向上仍取牛顿方向，但改用最优步长因子，在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象：进行一维搜索，避免了迭代后函数值上升的现象：从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因极

22、值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。基本牛顿法的步长因子恒为函数值上升。基本牛顿法的步长因子恒为1 1，有时会导致迭代，有时会导致迭代发散而失效。发散而失效。1. 1. 问题的提出问题的提出2. 2. 改进方法改进方法在在H Hk k正定时可保证收敛性。正定时可保证收敛性。 航空航天学院K=0 ，X（K）=X0K=K+1NX*= X（K）F*=F（X*）结结 束束Y3.3.阻尼牛顿法的迭代步骤阻尼牛顿法的迭代步骤kg计算计算kkgg ,计算计算 ，KKKgHS1)(

23、1 KH由由 出发出发，沿沿 方向搜索得方向搜索得 )()()()1(KKKKSXX)(KX)(KS给定给定 X0 ，航空航天学院方法特点方法特点 （1）初始点应选在）初始点应选在X*附近，有一定难度；附近，有一定难度； （2）尽管每次迭代都不会使函数值上升，但不能保证每次下降）尽管每次迭代都不会使函数值上升，但不能保证每次下降 ； （3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；牛顿法方向； （4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二

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

25、Ax航空航天学院4-3 变尺度法变尺度法 DFP变尺度法首先有戴维顿（变尺度法首先有戴维顿（Davidon）与）与1959年提出，年提出，又于又于1963年由弗莱彻（年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。为现代公认的较好的算法之一。 DFP法是基于牛顿法的思想又作了重要改进。这种算法仅法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。渐逼近牛顿方向，具有较快的收敛速度。 航空航天学院

26、变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。尺度变换技巧能显把函数的偏心程度降低到最低限度。尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。著地改进几乎所有极小化方法的收敛性质。值时值时 ,需要进行需要进行10次迭代才能达到极小点次迭代才能达到极小点0,0Tx 如作变换如作变换 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍，则目标函数等值线由一簇椭圆变成倍，则目标函数等值线由一簇椭圆变成一簇同心圆。一簇同心圆。x2例如在用最速下降法求例如在用最速下降法求 极小极小221212(,)25

27、f航空航天学院221212(,)y yyy 消除了函数的偏心，用最速下降法只需一次迭代即可求消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。得极小点。 梯度法构造简单，只用到一阶偏导数，计算量小，初始梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；其主要点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。时，即使对二次正定函数收敛也非常慢。 牛顿法收敛很快，对于二次函数只需迭代一次便达到最牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到

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

29、算二阶导数。时，就可以不再需要计算二阶导数。 变尺度法的关键在于尺度矩阵变尺度法的关键在于尺度矩阵A Ak k的产生的产生 。对于二次函数对于二次函数:1( )2TTfxx Gxb xc航空航天学院xQx进行尺度变换进行尺度变换在在新的坐标系中，函数新的坐标系中，函数f(x)的二次项变为：的二次项变为：1122TTTx Gxx Q GQx目的：减少二次项的偏心目的：减少二次项的偏心如如G是正定，则总存在矩阵是正定，则总存在矩阵Q，使得：使得：TQ GQI 用矩阵用矩阵Q-1右乘等式两边，得：右乘等式两边，得：用用矩阵矩阵Q左乘等式两边，得：左乘等式两边，得：1TQ GQTQQ GI所以所以1T

30、QQG上式上式说明：二次函数矩阵说明：二次函数矩阵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( )25fxxx在例在例42中中122121222011( )2505022Txfxxx xxxx Gx20050G如取如取102105

31、 2Q11002010221050101005 25 2TQ GQI航空航天学院航空航天学院航空航天学院 牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面(或超球面)，使设计空间中任意点处函数的梯度都通过极小点，用最速下降法只需一次迭代就可达到极小点。这就是对变换前的二次函数，在使用牛顿方法时，由于其牛顿方向直接指向极小点，因此只需一次迭代就能找到极小点。航空航天学院2.构造尺度矩阵构造尺度矩阵Ak从初始矩阵从初始矩阵A0=I(单位矩阵单位矩阵)开始，通过对公式开始，通过对公式 1kkkAAA因此，一旦达到最优点附近，就可望达到牛顿法因此，一旦达

32、到最优点附近，就可望达到牛顿法的收敛速度的收敛速度。1）DFP法（法（Davidon-Fletcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111()()kkkkkkkkff gggxxxxx式中式中中修正矩阵中修正矩阵 的不断修正，在迭代中逐步逼近于的不断修正，在迭代中逐步逼近于 kA11()kGx。航空航天学院2）BFGS算法算法(Broyden-Fletcher-Gold frob-Shanno ) DFP算法由于舍入误差和一维搜索不精确，有算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法可能导致构造矩阵的正定性遭到破坏，以

33、至算法不稳定。不稳定。BFGS算法对于维数较高问题具有更好的算法对于维数较高问题具有更好的稳定性。稳定性。 1 kkTkTkkkkkTkTkkTkkkkTkkTxxgAgAxxxgxgAgxxgA航空航天学院开始给定结束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gxgggxxx11kkk AAA01kxx0k kkk dA g是否航空航天学院例例4-3： 用用DFP算法求下列问题的极值：算法求下列问题的极值：221212112( ,)242f x xxxxx x01200212244()422xxfx

34、xxgx取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为则第一次搜寻方向为 l解：解： 1）取初始点）取初始点 ，为了按，为了按DFP法构造第一次法构造第一次搜寻方向搜寻方向d0，需计算初始点处的梯度需计算初始点处的梯度01 1Tx00010440122 dA g航空航天学院 沿沿d0方向进行一维搜索，得方向进行一维搜索，得010000014141 212 xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足01002()min()min(40203)ffxxd得得:00.25120.5x,2）再按）再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向d

35、1，需计算需计算1121212241422xxxxxg航空航天学院010143224ggg0102110.510.5 xxx代入校正公式代入校正公式000000000000TTTTxxAggAAxggAg1310.5340.543310.53444=航空航天学院100AAA21191010.5912112550010.50.251216194152550100=第二次搜寻方向为第二次搜寻方向为1118665 dA g再沿再沿d1进行一维搜索，得进行一维搜索，得12111182560.55xxd航空航天学院为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足12112811()min()min(

36、4)52ffxxd154242 x,得得3）判断）判断x2是否为极值点是否为极值点梯度梯度: : 2122212240()420 xxfxx xx海赛矩阵海赛矩阵 :2222()24fx航空航天学院梯度为零向量梯度为零向量, ,海赛矩阵正定。可见点满足极值充要条海赛矩阵正定。可见点满足极值充要条件，因此为极小点。件，因此为极小点。 *242Txx*()8f x航空航天学院针对牛顿法，提出了变尺度法针对牛顿法，提出了变尺度法 收敛速度比较慢收敛速度比较慢每次迭代需要计算二阶导数矩阵，每次迭代需要计算二阶导数矩阵，矩阵求逆计算量大，存储量大矩阵求逆计算量大，存储量大1. 1. 牛顿型方法牛顿型方法

37、2. 2. 最速下降法最速下降法针对最速下降法，提出了只用梯度信息，但收针对最速下降法，提出了只用梯度信息，但收敛速度更快的共轭梯度法敛速度更快的共轭梯度法航空航天学院1. 1. 基本思想：基本思想： 每次以一个变量坐标轴作为每次以一个变量坐标轴作为搜索方向，将搜索方向，将 n n维的优化问题轮维的优化问题轮流地转化为一系列一维搜索问题。流地转化为一系列一维搜索问题。例，第例，第 k k轮迭代的第轮迭代的第 i i 次搜索，次搜索，是固定除是固定除 x xi i外的外的 n-1 n-1 个变量，个变量，沿沿 x xi i 变量坐标轴作一维搜索，变量坐标轴作一维搜索，求得极值点求得极值点 x x

38、i i(k(k) ) n n 次搜索后次搜索后获得极值点序列获得极值点序列 x x1 1(k)(k), x, x2 2(k(k）, , , x xn n(k(k) )，若未收敛，则开始第，若未收敛，则开始第 k+1 k+1 次迭代，直至收敛到最优点次迭代，直至收敛到最优点 x x* *。 4-5 4-5 坐标轮换法坐标轮换法航空航天学院TnTTeee 1.00.0.100.01 211)1)几何描述几何描述( (以二维问题为例）以二维问题为例）二）迭代步骤二）迭代步骤依次沿个依次沿个n n个正交坐标轴的方向搜索：个正交坐标轴的方向搜索：一）搜索方向一）搜索方向。：次搜索的收敛条件轮第第；：次搜

39、索的迭代公式轮第第；：次搜索的步长轮第第向；个设计变量的坐标轴方为第次搜索的方向：轮第第)()()()()(1)()()()(,.,2 , 1,kikikikikikikikikieikniexxikeikieik航空航天学院2) 坐标轮换法流程图坐标轮换法流程图从从 出发沿出发沿 方向进行一维搜索得方向进行一维搜索得 ：1iXieiiiiieXX1)(iXFF 1ini 给给定定,0nX0XXn1iiFFXXn结束结束10kkXXn1k是否否是航空航天学院2.2.算法特点算法特点 等值线为椭圆等值线为椭圆, ,且长短轴分别平行于坐标轴时且长短轴分别平行于坐标轴时-高效高效一般情况一般情况-低

40、效低效方法简单，容易实现。方法简单，容易实现。当维数增加时，效率明显下降。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。受目标函数的性态影响很大。 如图如图 a) a) 所示，二次就收敛到极值点；所示，二次就收敛到极值点； 如图如图 b) b) 所示，多次迭代后逼近极值点；所示，多次迭代后逼近极值点； 如图如图 c) c) 所示，目标函数等值线出现山脊所示，目标函数等值线出现山脊（或称陡谷），若搜索到（或称陡谷），若搜索到 A A 点，再沿两个坐标点，再沿两个坐标轴，以轴，以t t0 0步长测试，目标函数值均上升，计步长测试，

41、目标函数值均上升，计算机判断算机判断 A A 点为最优点。事实上发生错误。点为最优点。事实上发生错误。航空航天学院 4-6 共轭方向法共轭方向法 l1.共共轭方向：轭方向：l 设设G为为nn阶实对称正定矩阵，如果有两个阶实对称正定矩阵，如果有两个n维向量维向量d0和和d1满足满足 ，则称向量，则称向量d0与与d1 关于矩阵关于矩阵G共共轭。轭。01()0TdGd当当G为单位矩阵时，为单位矩阵时，01()0Tdd假设目标函数假设目标函数f(x) 在极值点附近的二次近似函数为在极值点附近的二次近似函数为1( )2TfTxx Gxb xc对二维对二维情况情况任选取初始点任选取初始点x0沿某个下降方向

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

43、1()fxd1航空航天学院 如果能够选定这样的搜索方向，那么对于二元二次如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行函数只需顺次进行d0、d1两次直线搜索就可以求到两次直线搜索就可以求到极小点极小点x* * ，即有即有111xxd那么这样的那么这样的d1方向应该满足什么条件呢方向应该满足什么条件呢 ? ?对于前述的二次函数对于前述的二次函数: :1( )2TfTxx Gxb xc当当 时，时，1xx10 x* *是是f( (x) )极小点，应满足极值必要条件，故有极小点，应满足极值必要条件，故有()0fxGxb111111()()()ff xG xdbxGd0将等式两边同时左乘

44、将等式两边同时左乘 得得：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维空间中互相共轭的非零向量的个数不超过维空间中互相共轭的非零向量的个数不超过n。 性

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

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

47、d21()( )0kTkfdx d共轭条件：共轭条件：航空航天学院 则：则：21()( )()0kTkkkfff xxxd解解得：得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc为为函数的泰勒二次展开式函数的泰勒二次展开式()kkfxGxb则则11()kkfxGxb上两式相上两式相减，并代入减，并代入1kkkkxxd1()()kkkkff Gdxx航空航天学院1()()kkkkff Gdxx将式将式11()kkkkf dxd与式与式转置两边相乘，应用转置两边相乘，应用共轭条件共轭条件得：得：11()() ()()0kkTkkkf

48、fff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd航空航天学院航空航天学院2212112( )242fxxxx xx，已知初始点，已知初始点1,11,1T Tl解：解： 1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度0120212244()422xxfxxxx010000014141 212 xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足1002()min()min(40203)ffxxdl迭代精度迭代精

49、度 。 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收敛。收敛。( )0 由由22240,()8,()20ff xxx从而有：从而有：航空航天学院 鲍威尔法是以共轭方向为基础的收敛较快的直接法之鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。一，是一种

50、十分有效的算法。 1964年，鲍维尔提出这种年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。维搜索求极小点。并在以后的实践中进行了改进。 4.7 4.7 鲍威尔鲍威尔( (PoweelPoweel) )法法航空航天学院一一. .PoweelPoweel法（法（共轭方向法、方向加速法）：共轭方向法、方向加速法）：1.1.基本思想：直接利用函数值来构造共轭方向基本思想：直接利用函数值来构

51、造共轭方向 若沿连接相邻两轮搜索末端的向量若沿连接相邻两轮搜索末端的向量 S S 方向搜索，收方向搜索，收敛速度加快。敛速度加快。其中：)1(2)2(2xxS 因为两条平行线因为两条平行线 S S1 1, S, S2 2 与同心椭圆族相切，两个切与同心椭圆族相切，两个切点的连线点的连线 S S 直指中心。称直指中心。称 S S1 1, S, S2 2 与与 S S 为共轭方向。为共轭方向。 目的目的：以共轭方向打破振荡，加速收敛。：以共轭方向打破振荡，加速收敛。 这种方法是在研究具有正定矩阵这种方法是在研究具有正定矩阵A A的二次函数的二次函数 极小化的基础上形成。极小化的基础上形成。cXbH

52、XXXFTT21)(航空航天学院2.2.共轭方向生成共轭方向生成 设设X Xk，X Xk+1+1为从不同点出发，沿同一方向为从不同点出发，沿同一方向S Sj j进行一维搜索得到两个极小点，进行一维搜索得到两个极小点，如图所示。根据梯度与等值面垂直的性质，如图所示。根据梯度与等值面垂直的性质，S Sj j与与X Xk k，X Xk+1k+1两点处的梯度两点处的梯度g gk k，g gk+1k+1存在关系存在关系0)( 0)(1kTjkTjgSgS 对于上述二次函数，对于上述二次函数，其其Xk，Xk+1两点处梯度可表示为两点处梯度可表示为 11bHXgbHXgkkkk 相减得相减得 )(11kkk

53、kXXHgg 因而有因而有11() ()()() 0jTjTkkkkSggSH XX 若取方向若取方向kkkXXS1则则 Sk 和和Sj 共轭共轭 只要沿只要沿S Sj j方向分别对函数作两次一维搜索，得到两个极小点方向分别对函数作两次一维搜索，得到两个极小点Xk，Xk+1，两个切点两个切点( (极小点极小点) )的连线所给的方向，就是与的连线所给的方向，就是与 S Sj j 一起对一起对H H为共轭方向。为共轭方向。航空航天学院3. 3. 共轭方向的定义：共轭方向的定义：共轭。阵则称这组向量是关于矩能满足若有一组非零向量，为正定实对称矩阵设正交。和则即，时则，为单位矩阵若的方向是共轭方向。和

54、是关于矩阵共轭，和则称向量满足，和维向量若有两个，为实对称正定矩阵设AjiASSSSSASSSSISSIASSSSASSSSnAjTinTTT),(0,., 00,02121212121212121航空航天学院4. 4. 共轭方向的性质：共轭方向的性质：二次收敛性。为步可收敛至极值点，称多方向进行一维搜索，至出发，依次沿从任意初始点，次函数个非零向量，则对于二矩阵共轭的是关于设矩阵共轭。中每一个向量关于，也是与向量组，向量和搜索，分别得到最优点方向进行一维出发，沿和分别从两个初始点个非零向量，对于函数矩阵共轭的是关于设。满足，个向量则可以构造出是线性无关的向量组，若是线性无关的。个非零向量矩阵

55、共轭的这组关于）（）（）（）（）（）（nniSxAXXXBCxfnASSSAniSxxSxxniSxxxfnASSSjiSASSSSnSSSSSSnAiTTniiniTinnn),.,2 , 1(21)(,.,),.,2 , 1(),.,2 , 1()(,.,)(,0,.,.,.,)0(211221)2(0)1(021)2()2(222211121121航空航天学院5. 5. 步骤：步骤： 迭代。若不满足，则作下一轮。则若满足。或是否满足收敛条件：每轮迭代结束时，检验。的极值点作第三次搜索，求得，沿此方向构筑共轭方向：。的极值点一维搜索，分别求得方向作两次，分别沿令第二轮迭代：)1(32100

56、10101023202222221112)1(320*,kkkkkkxxfffxxxxfxxSxxxfSSxx 。的极值点作第三次搜索，求得，沿此方向构筑共轭方向：。的极值点分别求得作两次一维搜索，两个坐标轴方向，依次沿，令选初始点第一轮迭代：131012112111211)0(10)0(,xxfxxSxxxfSSxxx航空航天学院2x3x1xo0X1e2e3e 3 3）若目标函数为正定二次函数，）若目标函数为正定二次函数，n n轮结束后即可到达最优点。轮结束后即可到达最优点。 2 2）每轮迭代产生一个新方向取代原来的第一方向，替换原则）每轮迭代产生一个新方向取代原来的第一方向，替换原则是去掉

57、原方向组的第一个方向而将新方向排在原方向的最后；是去掉原方向组的第一个方向而将新方向排在原方向的最后；n n轮轮迭代后可产生迭代后可产生n n个彼此共轭的方向个彼此共轭的方向；nX 1 1）开始采用坐标轴方向）开始采用坐标轴方向；顺次沿顺次沿n n个方向做一维搜索得到一个方向做一维搜索得到一个终点，由始点和终点构成一个新的方向。个终点，由始点和终点构成一个新的方向。要点要点航空航天学院 2 2）在改进的算法中首先要判断原向量组是否需要替换。若需）在改进的算法中首先要判断原向量组是否需要替换。若需要替换，还要进一步判断原向量组哪个向量最坏，然后在用新的方要替换，还要进一步判断原向量组哪个向量最坏

58、，然后在用新的方向替换这个最坏的方向或向量，以保证逐次生成共轭方向向替换这个最坏的方向或向量，以保证逐次生成共轭方向； 1 1）每一轮迭代都用由始点和终点构成一个新的搜索方向代替）每一轮迭代都用由始点和终点构成一个新的搜索方向代替原方向组的第一个向量，而不管它的原方向组的第一个向量，而不管它的“好坏好坏”。向量组线性相向量组线性相关关改进鲍威尔算法改进鲍威尔算法 3 3）每轮迭代中始点）每轮迭代中始点X0 0k，终点，终点Xnk和反射点和反射点Xn+1k 201kknknXXX沿方向沿方向 01kknknXXS移动一个移动一个 0kknXX 距离距离)(,)( ,)(132000knnknkX

59、FGFXFGFXFG)0,1,2,.( )(niXFFkiiiiiFF1mminimFF11max令令航空航天学院 a a）若不满足判别条件，则下轮迭代仍用原方向组，并以）若不满足判别条件，则下轮迭代仍用原方向组，并以Xnk和和Xn+1k中函数值小者作为下轮迭代的始点。中函数值小者作为下轮迭代的始点。 4 4）根据是否满足判别条件）根据是否满足判别条件23022032003)(5 . 0)(2( GGGGGGGGGmm 确定是否要对原方向组进行替换确定是否要对原方向组进行替换 b b）若满足判别条件，则下轮迭代对方向组进行替换，将）若满足判别条件，则下轮迭代对方向组进行替换，将Sk补补充到充到

60、原方向组的最后位，而除掉原方向组的最后位，而除掉Snk。即新方向组为即新方向组为S1k，S2k，Sm-1k，Sm+1k, Snk，Sn+1k作为下轮迭代的搜索方向。下一轮迭代的作为下轮迭代的搜索方向。下一轮迭代的始点取为始点取为Sn+1k方向进行一维搜索的极小点方向进行一维搜索的极小点X0k1 5 5）判断是否满足收敛准则）判断是否满足收敛准则航空航天学院 这样重复迭代的结果，后面加进去的向量都彼此对这样重复迭代的结果，后面加进去的向量都彼此对G共轭共轭，经，经n轮迭代即可得到一个由轮迭代即可得到一个由n个共轭方向所组成的方向组个共轭方向所组成的方向组。对于二次函次，最多。对于二次函次，最多n