重庆科创学院-现代设计方法之24 无约束设计的最优化方法

1、主讲人：魏良庆主讲人：魏良庆1 1、PowellPowell法的应用计算法的应用计算2 2、梯度法的应用计算、梯度法的应用计算3 3、共轭梯度法的应用计算、共轭梯度法的应用计算4 4、变尺度法的应用计算、变尺度法的应用计算2.4 2.4 多维无约束优化方法多维无约束优化方法 l共轭与共轭方向的概念共轭与共轭方向的概念l共轭方向的形成共轭方向的形成l常用的无约束优化设计方法的基本步常用的无约束优化设计方法的基本步骤与几何解释骤与几何解释2.4 2.4 多维无约束优化方法多维无约束优化方法 l第第2 2章第一节所列举的机械优化设计问题，章第一节所列举的机械优化设计问题，都是在一定的限制条件下追求某

2、一指标为都是在一定的限制条件下追求某一指标为最小，它们都属于多维约束优化问题。工最小，它们都属于多维约束优化问题。工程问题大都如此。程问题大都如此。 为什么要研究多维无约束优化问题为什么要研究多维无约束优化问题? 2.4 2.4 多维无约束优化方法多维无约束优化方法 (1) (1)有些实际问题，其数学模型本身就是一个多有些实际问题，其数学模型本身就是一个多维无约束优化问题。维无约束优化问题。 (2)(2)通过熟悉它的解法可以为研究多维约束优化通过熟悉它的解法可以为研究多维约束优化问题打下良好的基础。问题打下良好的基础。 (3)(3)多维约束优化问题的求解可以通过一系列多多维约束优化问题的求解可

3、以通过一系列多维无约束优化方法来达到。维无约束优化方法来达到。所以多维无约束优化所以多维无约束优化问题的解法是优化设计方法的基本组成部分，也问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。是优化方法的基础。2.4 2.4 多维无约束优化方法多维无约束优化方法 多维无约束优化问题是：多维无约束优化问题是：求求n n维设计变量维设计变量使目标函数：使目标函数： 12Tnx xxx( )minfxmin( )nfRxx各种多维无约束优化解法的区别：各种多维无约束优化解法的区别：搜索方向的不同搜索方向的不同2.4 2.4 多维无约束优化方法多维无约束优化方法 分类：分类：（1 1）直接解法

4、）直接解法-不使用导数信息，如不使用导数信息，如坐标轮换坐标轮换 法、法、PowellPowell法、随机搜索法、单纯形法法、随机搜索法、单纯形法等等（2 2）间接解法）间接解法( (解析法解析法) )-要使用导数，要使用导数，二阶有二阶有 梯度法、共轭梯度法、二阶以上用牛顿法梯度法、共轭梯度法、二阶以上用牛顿法1(0,1,2,)kkkkSkxx搜索方向的构成问题是多维无约束优化方法的关键搜索方向的构成问题是多维无约束优化方法的关键2.4 2.4 多维无约束优化方法多维无约束优化方法 从选定的某初始点从选定的某初始点x x(k(k) )出发，沿着以一出发，沿着以一定规律产生的搜索方向定规律产生

5、的搜索方向S S(k(k) )，取适当的步长，取适当的步长a a(k(k) ), ,逐次搜寻函数值下降的新迭代点逐次搜寻函数值下降的新迭代点x x(k+1)(k+1), ,使之逐步通近最优点使之逐步通近最优点x x* *。 2.4 2.4 多维无约束优化方法多维无约束优化方法 可以把可以把初始点初始点x x(k(k) )、搜索方向搜索方向S S(k(k) )、迭代步长迭代步长a a(k(k) )称为优化方法算法的三要素。其中以称为优化方法算法的三要素。其中以搜索方向搜索方向S S(k(k) )更为突出和重要更为突出和重要，它从根本上决定一个算法的，它从根本上决定一个算法的成败、收敛速率的快慢等

6、。成败、收敛速率的快慢等。 一个算法的搜索方向成为该优化方法的基本一个算法的搜索方向成为该优化方法的基本标志，标志，分析、确定搜索方向分析、确定搜索方向S S(k(k) )是研究优化方法的是研究优化方法的最根本的任务之一最根本的任务之一。2.4 2.4 多维无约束优化方法多维无约束优化方法 函数的函数的负梯度方向负梯度方向是函数值下降最快的方向是函数值下降最快的方向搜索方向搜索方向S S取该点的负梯度方向取该点的负梯度方向 ( (最速下降最速下降方向方向) )，使函数值在该点附近的范围内下降最快。，使函数值在该点附近的范围内下降最快。( )fx1(0,1,2,)kkkkSkxx1() (0,1

7、,2, )kkkka fk xxx2.4 2.4 多维无约束优化方法多维无约束优化方法 为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向 能够能够获得最大的下降值，其步长因子获得最大的下降值，其步长因子 应取一应取一维搜索的最佳步长。即有维搜索的最佳步长。即有()kfxk1()() min ()min ( )kkkkkkaaffa ffa f xxxxx2.4 2.4 多维无约束优化方法多维无约束优化方法 l根据一元函数极值的必要条件和多元复根据一元函数极值的必要条件和多元复合函数求导公式，得合函数求导公式，得 ( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kT

8、kSS2.4 2.4 多维无约束优化方法多维无约束优化方法 在最速下降在最速下降( (梯度梯度) )法中，相邻两个迭代点上法中，相邻两个迭代点上的函数梯度的函数梯度相互垂直相互垂直。而搜索方向就是负梯度方。而搜索方向就是负梯度方向，因此向，因此相邻两个搜索方向互相垂直相邻两个搜索方向互相垂直。这就是说。这就是说在迭代点向函数极小点靠近的过程，走的是曲折在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成的路线。形成“之之”字形的锯齿现象，而且字形的锯齿现象，而且越接越接近极小点锯齿越细。近极小点锯齿越细。 2.4 2.4 多维无约束优化方法多维无约束优化方法 开始给定结束0,x()kkf d

9、x1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 2.4 2.4 多维无约束优化方法多维无约束优化方法 例例2.4-1 2.4-1 求目标函数求目标函数 的极小点。的极小点。初始点初始点解：初始点处函数值及梯度分别为解：初始点处函数值及梯度分别为02,2Tx00102()10424()50100 xfxfxxx2212( )25fxxx2.4 2.4 多维无约束优化方法多维无约束优化方法 沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有0100002 4()2 100fxxx0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件 12

10、2( )min (2 4 )25(2 100 )min ( )f x2.4 2.4 多维无约束优化方法多维无约束优化方法 00( )8(2 4) 5000(2 100)0 算出一维搜索最佳步长算出一维搜索最佳步长 06260.020 030 7231252第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 01202 41.9198772 1000.307178 5 10 x1( ) 3.686164fx继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 0 0Tx()0fx2.4 2.4 多维无约束优化方法多维无约束优化方法 这一问题的目标函数这一问题的目标函

11、数f f( (x x) )的等值线为一簇椭圆。的等值线为一簇椭圆。将上例中目标函数将上例中目标函数 引入变换引入变换 y1=x1,y2=5x2则函数则函数f(x)f(x)变为：变为：2212( )25fxxx221212(,)y yyy其等值线由椭圆变成一簇同心圆。其等值线由椭圆变成一簇同心圆。2.4 2.4 多维无约束优化方法多维无约束优化方法 仍从仍从 即即 出发进行最速下降法出发进行最速下降法寻优。此时：寻优。此时：02,2Tx02,10Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索沿负梯度方向进行一维搜索：1000000()2 42410 201020 yyy

12、2.4 2.4 多维无约束优化方法多维无约束优化方法 为一维搜索最佳步长，可由极值条件：为一维搜索最佳步长，可由极值条件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552从而算得一步计算后设计点的位置及其目标函数：从而算得一步计算后设计点的位置及其目标函数：2.4 2.4 多维无约束优化方法多维无约束优化方法 010124010200()0 yy经变换后，只需一次迭代，就可找到最优解。经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。等值线由椭圆变成圆。1 12.4

13、2.4 多维无约束优化方法多维无约束优化方法 （1）理论明确，程序简单，理论明确，程序简单，对初始点要求不严格。对初始点要求不严格。（2）对一般函数而言，收对一般函数而言，收敛速度并不快，因为最速敛速度并不快，因为最速下降方向仅是指某点的一下降方向仅是指某点的一个个局部局部性质。性质。2.4 2.4 多维无约束优化方法多维无约束优化方法 （4）梯度法的收敛速度与目标函数的性质密切相梯度法的收敛速度与目标函数的性质密切相关。对于关。对于等值线等值线( (面面) )为同心圆（球）的目标函数，为同心圆（球）的目标函数，一次搜索即可达到极小点。一次搜索即可达到极小点。（3）相邻两次搜索方向的正交性决定

14、了迭代过程相邻两次搜索方向的正交性决定了迭代过程的的路线呈锯齿状路线呈锯齿状，在，在远离极小点时逼近速度较快，远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。而在接近极小点时逼近速度较慢。2.4 2.4 多维无约束优化方法多维无约束优化方法 设设G G为为n nn n阶阶实对称正定矩阵实对称正定矩阵，如果有两个，如果有两个n n维维向量向量S S0 0和和S S1 1满足满足 ，则称向量，则称向量S S0 0与与S S1 1 关于矩阵关于矩阵G G共轭共轭。01()0TSS G2.4 2.4 多维无约束优化方法多维无约束优化方法 01()0TSS G当当G为单位矩阵时为单位矩阵时，01

15、()0TSS 假设目标函数假设目标函数f(x)在极值点附近的二次近似函数为在极值点附近的二次近似函数为1( )2TfTxx Gxb xc对二维情况对二维情况任选取初始点任选取初始点x0沿某个下降方向沿某个下降方向S0作一维搜索，得作一维搜索，得x11000Sxx2.4 2.4 多维无约束优化方法多维无约束优化方法 因为因为 是沿是沿S0方向搜索的最佳步长，即在方向搜索的最佳步长，即在点点x1处函数处函数f（x）沿方向沿方向S0的方向导数为零的方向导数为零。考虑到点。考虑到点x1处方向导数与梯度之间的关系，故有处方向导数与梯度之间的关系，故有01100()0TffSS xx如果按最速下降法，选择

16、负梯度方向如果按最速下降法，选择负梯度方向 为搜为搜索方向，则将发生索方向，则将发生锯齿锯齿现象现象 。1( )f x2.4 2.4 多维无约束优化方法多维无约束优化方法 2.4 2.4 多维无约束优化方法多维无约束优化方法 0S0 x0 x1x*1 11S11()fx0取下一次的迭代搜索方向取下一次的迭代搜索方向S1直指极小点直指极小点x* S12.4 2.4 多维无约束优化方法多维无约束优化方法 l如果能够选定这样的搜索方向，那么对于二元如果能够选定这样的搜索方向，那么对于二元二次函数二次函数只需顺次进行只需顺次进行S0、S1两次直线搜索就两次直线搜索就可以求到极小点可以求到极小点x*，即

17、有，即有111Sxx那么这样的那么这样的S1方向应该满足什么条件呢方向应该满足什么条件呢 ? ?01()0TSS G2.4 2.4 多维无约束优化方法多维无约束优化方法 对于前述的二次函数对于前述的二次函数: :有有11( )fxGxb1( )2TfTxx Gxb xc当当 时时 。1xx10 x* *是是f( (x) )极小点，极小点，应满足极值必要条件，故有应满足极值必要条件，故有( )0f xG x b1111111( )()( )fSfxSb xG xbxG0将等式两边同时左乘将等式两边同时左乘 得：得：0()TS01()0TSS G2.4 2.4 多维无约束优化方法多维无约束优化方法

18、 01()0TSS G就是使就是使S1直指极小点直指极小点x*，S S1 1所必须满足的条件。所必须满足的条件。两个向量两个向量S S0 0和和S S1 1称为称为G的共轭向量，或称的共轭向量，或称SO和和S S1 1对对G是共轭方向。是共轭方向。 021()( )0TSfSx2.4 2.4 多维无约束优化方法多维无约束优化方法 性质性质1 1 若非零向量系若非零向量系S0, ,S1, ,S2,Sm-1是是对对G共轭共轭，则这则这m个向量是线性无关个向量是线性无关的的。性质性质2 2 在在n维空间中维空间中互相共轭的非零向量的个数互相共轭的非零向量的个数不超过不超过n。 性质性质3 3 从任意

19、初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭方的共轭方向向S0, ,S1, , S2,进行一维搜索，进行一维搜索，最多经过最多经过n次迭代次迭代就可以找到的就可以找到的二次二次函数函数f( (x) )极小点。极小点。 2.4 2.4 多维无约束优化方法多维无约束优化方法 开始给定结束00,xd1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共轭方向关键：新的共关键：新的共轭方向轭方向确定确定2.4 2.4 多维无约束优化方法多维无约束优化方法 l共轭梯度法是共轭方向法中的一种共轭梯度法是共轭方向法中的一种，该方法中，该方法中每一个共轭向量都是每一

20、个共轭向量都是依赖于迭代点处的负梯度依赖于迭代点处的负梯度而构造出来而构造出来。l从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索: :2.4 2.4 多维无约束优化方法多维无约束优化方法 1(0,1,2, )kkkkSkxx()kkSf x设与设与Sk共共轭的下一个方向轭的下一个方向Sk+1由由Sk和点和点xk+1的负的负梯度的线形组合构成，即：梯度的线形组合构成，即：11()kkkkSfS x21()( )0kTkSfSx共轭条件：共轭条件：2.4 2.4 多维无约束优化方法多维无约束优化方法 则：则：21()( )() 0kTkkkfffSxxx解得：解得：212()()

21、()()()()kTkkkkTkkffffffxxxxxx2.4 2.4 多维无约束优化方法多维无约束优化方法 ()kkfxGxb则则11()kkfxGxb上两式相减，并代入上两式相减，并代入1kkkkSxx1()()kkkkSff Gxx令令1( )2TfTxx Gxb xc为函数的泰勒二次展开式为函数的泰勒二次展开式2.4 2.4 多维无约束优化方法多维无约束优化方法 11()kkkkSfSx1()()kkkkSffGxx将式将式与式与式两边相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：11()()()()0kkkkkffffxxxx21112()()()()()()kkTkkkTk

22、kffffffxxxxxx2.4 2.4 多维无约束优化方法多维无约束优化方法 因此因此11()kkkkSfS x212()()kkkffxx1(0,1,2,)kkkkSkxx2.4 2.4 多维无约束优化方法多维无约束优化方法 2.4 2.4 多维无约束优化方法多维无约束优化方法 迭代精度迭代精度 。 2212112( )242fxxxxxx ，已知初始点已知初始点1,11,1T T解：解：1 1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻计算初始点处的梯度计算初始点处的梯度0120212244( )422xxfxxxx0.0012.4 2.4 多维无约束优化方法多维无约束优化方法 01

23、20212244()422xxfxxxx01000001 4141 212S xx为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足1002()min()min(40203)ffSxx2.4 2.4 多维无约束优化方法多维无约束优化方法 得:00.25120.5x2 2）第二次迭代：）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5SfS x2.4 2.4 多维无约束优化方法多维无约束优化方法 得:211222 20.51.50.5 1.5Sxx代入目标函数代入目标函数22( ) (2 2 )2(0.5 1.5 )2(2 2 )(0.5 1.5 ) 4(

24、2 2 )( )f x 2.4 2.4 多维无约束优化方法多维无约束优化方法 ( )0 得得122240,( )8,( )20ff xxx因因2()0fx收敛。收敛。由由从而有：从而有：2.4 2.4 多维无约束优化方法多维无约束优化方法 共轭梯度法特点共轭梯度法特点1 1）每步迭代只需存储若干向量（适用于大）每步迭代只需存储若干向量（适用于大规模问题）；规模问题）；2 2）有二次终结性（对于正定二次函数，至）有二次终结性（对于正定二次函数，至多多n n次迭代可达次迭代可达opt.opt.） 2.4 2.4 多维无约束优化方法多维无约束优化方法 1 1、梯度法：、梯度法：搜索方向为目标函数负梯

25、度方向，搜索方向为目标函数负梯度方向，计算速度开始搜索下降快，愈接近极值点下降愈计算速度开始搜索下降快，愈接近极值点下降愈慢。对初始点的选择要求不高，适合与其它方法慢。对初始点的选择要求不高，适合与其它方法结合使用。结合使用。2 2、共轭梯度法：、共轭梯度法：第一步搜索沿负梯度方向，然第一步搜索沿负梯度方向，然后沿负梯度的共轭方向搜索。后沿负梯度的共轭方向搜索。计算效率优于梯度计算效率优于梯度法。法。对初始点没有特殊的要求，不需要计算二阶对初始点没有特殊的要求，不需要计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当。偏导数矩阵及其逆矩阵，计算量与梯度法相当。适用于各种大规模的问题适用于各种大规

26、模的问题。2.4 2.4 多维无约束优化方法多维无约束优化方法 鲍威尔（鲍威尔（PowellPowell）法是）法是直接利用函数值来构造共直接利用函数值来构造共轭方向的一种方法轭方向的一种方法 1( )2TfTxx Gxb xc对函数：对函数：基本思想：基本思想：在不用导数的前提下，在迭代中逐在不用导数的前提下，在迭代中逐次构造次构造G的共轭方向的共轭方向2.4 2.4 多维无约束优化方法多维无约束优化方法 jjk kkkSd dgg gk+1k+1xxk+1设设xk, xk+1为从不同点出发，沿同一方向为从不同点出发，沿同一方向Sj进行一维进行一维搜索而得到的两个极小点。搜索而得到的两个极小

27、点。 jS2.4 2.4 多维无约束优化方法多维无约束优化方法 根据梯度和等值面相垂直的性质，根据梯度和等值面相垂直的性质，Sj和和xk, ,xk+1两两点处的梯度点处的梯度gk，gk+1之间存在关系之间存在关系: :1()0,()0jTkjTkSSgg另一方面，对于上述二次函数，其另一方面，对于上述二次函数，其xk，xk+1两点处两点处的梯度可表示为的梯度可表示为: :11,kkkkgGxbgGxb2.4 2.4 多维无约束优化方法多维无约束优化方法 因而有因而有11() ()()()0j Tkkj TkkSSggG xx1kkkSxx取取这说明只要沿这说明只要沿Sj方向分别对函作两次一维搜

28、索，方向分别对函作两次一维搜索，得到两个极小点得到两个极小点xk和和xk+1，那么这两点的，那么这两点的连线所连线所给出的方向给出的方向Sk就是与就是与Sj一起一起对对G共轭共轭的方向。的方向。2.4 2.4 多维无约束优化方法多维无约束优化方法 1 1）任选一初始点）任选一初始点x0，再，再选两个线性无关的向量，选两个线性无关的向量，如 坐 标 轴 单 位 向 量如 坐 标 轴 单 位 向 量e1=1,0T和和e2=0,1T作为作为初始搜索方向。初始搜索方向。2 2）从）从x0出发，顺次沿出发，顺次沿e1，e2作一维搜索，得作一维搜索，得 点，两点连线点，两点连线得一新方向得一新方向S100

29、12,xxx1x2x0o oe1e2d1d2x*102x10 x11x12x01x11002S xx2.4 2.4 多维无约束优化方法多维无约束优化方法 用用S1代替代替e1形成两个线形成两个线性无关向量性无关向量S1, e2 ，作，作为下一轮迭代的搜索方为下一轮迭代的搜索方向。再从向。再从 出发，沿出发，沿S S1 1作一维搜索得点作一维搜索得点 ，作为下一轮迭代的初始作为下一轮迭代的初始点。点。 02x10 xx1x2x0o oe1e2d1d2x*102x10 x11x12x01x2.4 2.4 多维无约束优化方法多维无约束优化方法 x1x2x0o oe1e2d1d2x*102x10 x1

30、1x12x01x3 3）从出发）从出发 ，顺次，顺次沿沿e2,S1作一维搜索，作一维搜索，得到点得到点 ，两点，两点连线得一新方向连线得一新方向: :1112,x x21120S xx10 x2.4 2.4 多维无约束优化方法多维无约束优化方法 沿沿S S2 2作一维搜索得点作一维搜索得点x2 即是二维问题的极即是二维问题的极小点小点x* 方法的基本迭代格式方法的基本迭代格式包括包括共共轭方向产生和轭方向产生和方向替换两主要步骤。方向替换两主要步骤。x1x2x0o oe1e2d1d2x*102x10 x11x12x01x2.4 2.4 多维无约束优化方法多维无约束优化方法 把二维情况的基本算法

31、扩展到把二维情况的基本算法扩展到n维，则鲍维，则鲍威尔基本算法的要点是：威尔基本算法的要点是： 在每一轮迭代中总有一个始点（第一轮的在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和始点是任选的初始点）和n个线性独立的搜索个线性独立的搜索方向。从始点出发顺次沿方向。从始点出发顺次沿n个方向作一维搜索个方向作一维搜索得一终点，由得一终点，由始点和终点决定了一个新的搜索始点和终点决定了一个新的搜索方向。方向。 2.4 2.4 多维无约束优化方法多维无约束优化方法 l用这个方向替换原来用这个方向替换原来n n个方向中的一个，于是个方向中的一个，于是形成新的搜索方向组。替换的原则是形成新的搜索

32、方向组。替换的原则是去掉原方去掉原方向组的第一个方向而将新方向排在原方向的最向组的第一个方向而将新方向排在原方向的最后。后。此外规定，从这一轮的搜索终点出发沿新此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。下一轮迭代的始点。这样就形成算法的循环。 上述基本算法仅具有理论意义上述基本算法仅具有理论意义 。2.4 2.4 多维无约束优化方法多维无约束优化方法 因为在迭代中的因为在迭代中的n个搜索方向有时会变成线个搜索方向有时会变成线性相关而不能形成共轭方向的情况性相关而不能形成共轭方向的情

33、况。从而。从而导致可能求不到极小点，所以上述基本算导致可能求不到极小点，所以上述基本算法有待改进。法有待改进。 2.4 2.4 多维无约束优化方法多维无约束优化方法 在鲍威尔基本算法中，每一轮迭代都用连结始点在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的第一个向量，而不管它的“好坏好坏”，这是产生向，这是产生向量组线性相关的原因所在。量组线性相关的原因所在。 2.4 2.4 多维无约束优化方法多维无约束优化方法 在改进的算法中在改进的算法中首先判断原向量组是否需要替首先判断原向量组是否需要替换

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

35、替换某一方向 。1kSkmS2.4 2.4 多维无约束优化方法多维无约束优化方法 令在令在k次循环中次循环中00231()()()kknknFfFfFfxxx01,kkknnx x x100()2kkkkkknnnnxxxxxx（）分别称为一轮迭代的分别称为一轮迭代的始点、终点和反射点始点、终点和反射点。2.4 2.4 多维无约束优化方法多维无约束优化方法 则在循环中函数下降最多的第则在循环中函数下降最多的第m次迭代是次迭代是() (0,1,2, )kiiffinx1(1,2, )iiiffin 记记：11maxmimmi nff 相应的方向为相应的方向为 。kmS002,nFfFf因此因此2

36、.4 2.4 多维无约束优化方法多维无约束优化方法 为了构成共为了构成共轭性好的方向组，须遵循下列准则：轭性好的方向组，须遵循下列准则：在在k次循环中，若次循环中，若满足条件满足条件：30FF202302(2)()mFFF FF2030.5()mFF则选用新方向则选用新方向Sk，并在第并在第k+1迭代中用迭代中用Sk替换对应于替换对应于 的方向的方向 。否则，仍然用原方向组进行第。否则，仍然用原方向组进行第k+1迭代。迭代。mkmS2.4 2.4 多维无约束优化方法多维无约束优化方法 这样重复迭代的结果，后面加进去的向量都彼此对这样重复迭代的结果，后面加进去的向量都彼此对G共轭，共轭，经经n轮

37、迭代即可得到一个由轮迭代即可得到一个由n个共轭方向所组成的方向组。对个共轭方向所组成的方向组。对于于n次函次，最多次函次，最多n次就可找到极小点，而对一般函数，往往次就可找到极小点，而对一般函数，往往要超过要超过n n次才能找到极小点（这里次才能找到极小点（这里“n”表示设计空间的维表示设计空间的维数）。数）。 2.4 2.4 多维无约束优化方法多维无约束优化方法 例例2.4-5 2.4-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数的最优解。已知初始点的最优解。已知初始点1,1T，迭代精度，迭代精度221211 2( )242fxxxxxx0.001解：（解：（1 1）第）第1 1

38、轮迭代计算轮迭代计算0011 x0000()3Fff x2.4 2.4 多维无约束优化方法多维无约束优化方法 沿沿e1方向进行一维搜索方向进行一维搜索0201min()43fxe12得得00101 11132101 xxe011( )7ffx2.4 2.4 多维无约束优化方法多维无约束优化方法 以以 为起点，沿第二坐标轴方向为起点，沿第二坐标轴方向e2进行一维搜索进行一维搜索01x0212min ()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x2.4 2.4 多维无约束优化方法多维无约束优化方法 确定此轮中的最大下降量及其相应方向确定此轮中的最大下

39、降量及其相应方向0010101()()4ffff xx0021212()()0.5ffff xx12max,4m 2.4 2.4 多维无约束优化方法多维无约束优化方法 反射点及其函数值反射点及其函数值000320315221.512 xxx033( )7Ffx检验检验PowellPowell条件条件202302(2)()1.25mFFF FF2030.5()32mFF2.4 2.4 多维无约束优化方法多维无约束优化方法 l由于满足由于满足PowellPowell条件，则淘汰函数值下降量最条件，则淘汰函数值下降量最大的方向大的方向e1，下一轮的基本方向组为下一轮的基本方向组为e2， 。03S构成

40、新的方向构成新的方向 0003203121.510.5S xx2.4 2.4 多维无约束优化方法多维无约束优化方法 沿沿 方向一维搜索得极小点和极小值方向一维搜索得极小点和极小值03S13.81.7x1()7.9f x此点为下轮迭代初始点。此点为下轮迭代初始点。 按点距准则检验终止条件按点距准则检验终止条件 11220(3.8 1)(1.7 1)2.886xx需进行第二轮迭代计算。需进行第二轮迭代计算。2.4 2.4 多维无约束优化方法多维无约束优化方法 （2 2）第）第2 2轮迭代计算轮迭代计算此轮基本方向组为此轮基本方向组为e2， ，分别相当于分别相当于 ， ，起始点为起始点为 = 03S

41、11S12S10 x1x沿沿e2方向进行一维搜索得方向进行一维搜索得 113.81.9x11()7.98f x2.4 2.4 多维无约束优化方法多维无约束优化方法 以以 为起点沿为起点沿 方向一维搜索得方向一维搜索得11x03S123.961.9x122()7.996ffx确定此轮中函数值最大下降量及其相应方向确定此轮中函数值最大下降量及其相应方向10.08 20.016 12max,0.08m 2.4 2.4 多维无约束优化方法多维无约束优化方法 l反射点及其函数值反射点及其函数值1113203.963.84.12221.941.72.18 xxx133()7.964Ff x检验检验Powe

42、llPowell条件，淘汰函数值下降量最大的方向条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为下一轮的基本方向组应为 ， 。 03S13S2.4 2.4 多维无约束优化方法多维无约束优化方法 构成新的方向构成新的方向1113203.963.80.161.941.70.24Sxx沿沿 方向进行一维搜索得方向进行一维搜索得13S242 x2()8f x2.4 2.4 多维无约束优化方法多维无约束优化方法 检验终止条件检验终止条件 22220(4 3.8)(2 1.7)0.36xx（3 3）第）第3 3轮迭代计算轮迭代计算此轮基本方向组为此轮基本方向组为 ， ，起始点为起始点为 ，先先

43、后沿后沿 ， 方向方向，进行一维搜索，得进行一维搜索，得03S13S20 x2x03S13S2142 x2242 x2.4 2.4 多维无约束优化方法多维无约束优化方法 检验终止条件检验终止条件 故最优解故最优解 22200 xx*42 x*()8f x2.4 2.4 多维无约束优化方法多维无约束优化方法 实际上，前两轮迭代的实际上，前两轮迭代的 ， 为共轭方向，由于本例目为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行轮的结果就是问题的最优解，但每一轮迭代都需要进行n n+1

44、+1次迭代。次迭代。13S23S2.4 2.4 多维无约束优化方法多维无约束优化方法 补充知识：补充知识：牛顿法牛顿法( )x( )x( )f x1kx( )f x2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx设设 为为 的极小点的极小点 1kx( )x1() 0kx21()()()0kkkkffxxxx2.4 2.4 多维无约束优化方法多维无约束优化方法 121()() (0,1,2, )kkkkffk xxxx这就是多元函数求极值的这就是多元函数求极值的牛顿法迭代公式牛顿法迭代公式。 对于二次函数，海赛矩阵是一个常矩阵，其中对于二次函数，海赛矩阵

45、是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。需一步就可找到极小点。2.4 2.4 多维无约束优化方法多维无约束优化方法 例例2 24 4 求目标函数求目标函数 的极小点的极小点。初始点初始点2212( )25fxxx02,2Tx102010102402( )( )121000050ff xxxx经过一次迭代即求得极小点经过一次迭代即求得极小点 ，函数极小值函数极小值 。00 x()0fx2.4 2.4 多维无约束优化方法多维无约束优化方法 开始给定结束0,x21()()kkkff dxx1:min()kkkkkkk

46、fxxdxd1kkxx*1kxx否是1kk0k 2.4 2.4 多维无约束优化方法多维无约束优化方法 l 牛顿法的主要缺点牛顿法的主要缺点是每次迭代都要计是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维这样工作量很大。特别是矩阵求逆，当维数高时工作量更大数高时工作量更大 。 2.4 2.4 多维无约束优化方法多维无约束优化方法 变尺度法是在牛顿法的思想上进行了重大改进变尺度法是在牛顿法的思想上进行了重大改进的一类方法。的一类方法。 1.1.基本思想基本思想 变量的尺度变换是放大或缩小各个坐标。通过变量的尺度变换是放

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

48、降法只需一次迭代即可求得极小点。可求得极小点。2.4 2.4 多维无约束优化方法多维无约束优化方法 Ak 是需要构造是需要构造nn的一个对称方阵，称为的一个对称方阵，称为变尺度矩阵变尺度矩阵如如Ak=I, 则得到梯度法则得到梯度法 ；21()kkf Ax 则得到阻尼牛顿法则得到阻尼牛顿法 ；如如迭代方向：迭代方向：1()(0,1,2, )kkkSfkAx迭代公式：迭代公式：1()(0,1,2, )kkkkkfkxxAx变尺度法的关键在于尺度矩阵变尺度法的关键在于尺度矩阵A Ak k的产生。的产生。2.4 2.4 多维无约束优化方法多维无约束优化方法 从初始矩阵从初始矩阵A0=I( (单位矩阵单

49、位矩阵) )开始，通过对公式开始，通过对公式 1kkkAAA中修正矩阵中修正矩阵 的不断修正，在迭代中逐步逼近于的不断修正，在迭代中逐步逼近于 kA1()kGx因此，一旦达到最优点附近，就可望达到牛顿法的因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度收敛速度。2.4 2.4 多维无约束优化方法多维无约束优化方法 1 1）DFPDFP法（法（DavidonDavidon-Fletcher-Powell)-Fletcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111()( )kkkkkkkkff gggxxxxx式中式中2.4 2.4 多维无约束优化方法多维

50、无约束优化方法 DFPDFP算法由于舍入误差和一维搜索不精确，有可能算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGSBFGS算法对于维数较高问题具有更好的稳定性。算法对于维数较高问题具有更好的稳定性。 1 kk Tk Tkkkkk Tk Tkk TkkkkTkk TxxgAgAxxxgxgAgxxgA2.4 2.4 多维无约束优化方法多维无约束优化方法 开始给定结束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gx

51、gggxxx11kkk AAA01kxx0k kkk dA g是否2.4 2.4 多维无约束优化方法多维无约束优化方法 l解：解： 1）取初始点取初始点 ，为了按为了按DFPDFP法构法构造第一次搜寻方向造第一次搜寻方向S0，需计算初始点处的梯度，需计算初始点处的梯度221212112( ,)242f x xxxxxx01 1Tx01200212244( )422xxfxx xgx2.4 2.4 多维无约束优化方法多维无约束优化方法 取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I，则第一，则第一次搜寻方向为次搜寻方向为 00010440122S A g2.4 2.4 多维无约束优化方法多维无约束优化方法 沿沿S0方向进行一维搜索，得