1、机械优化设计何军良何军良10:301 上海海事大学上海海事大学Shanghai Maritime University 1909 2009 2004 1912 1958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目 录CONTENTS一维搜索方法无约束优化方法线性规划 约束优化方法 10:30第四章 无约束优化方法 概述01 最速下降法 牛顿型方法 共轭方向与共轭方向法020304 共轭梯度法05 变尺度法 坐标轮换法 鲍威尔方法060708 单形替换法0910:30344.1 概述工程问题大都为有约束优化问题。为什么要研究无约束优化问题?1.有些实际问题，其数学模型本身就是一个无
2、约束优化问题。2.通过熟悉它的解法可以为研究约束优化问题打下良好的基础。3.约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。10:3054.1 概述无约束优化问题是：TnxxxX21求n 维设计变量 nRXXfXfminmin使目标函数00021nxfxfxf0f无约束优化问题极值存在的必要条件：10:3064.1 概述 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。（1）间接法要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法不使用导数信息，如坐标轮换法、鲍威
3、尔法、单形替换法等。用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的(n 20)问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。搜索方向的构成问题乃是无约束优化方法的关键。其搜索方向直接取定或由计算目标函数值所得的信息来确定。1(0,1,2,)kkkkdkxx10:3074.1 概述7 71.选择初始迭代点x0。2.从迭代点xk出发进行搜索，确定使目标函数值下降的搜索方向dk。3.确定适当的步长因子k，求xk+1=xk+k dk，使f(xk+1)f(xk)。4.选择适当的终止准则，若xk+
4、1满足终止准则，则终止迭代计算，并输出局部最优点x*xk+1；否则，令kk+1，返回步骤(2)继续进行优化搜索。无约束优化方法求解的四个步骤:10:3084.2 最速下降法（1）基本思想搜索方向d取该点的负梯度方向 (最速下降方向)，使函数值在该点附近的范围内下降最快。()fx1(0,1,2,)kkkkdkxx1()(0,1,2,)kkkkafkxxx终止判别条件1kkxx10:3094.2 最速下降法（2）计算方法为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有1()()min()min()kkkkkkaaffaffa f xxxxx()kfxk步长
5、因子求解方法：解析法：根据极值点必要条件。黄金分割法牛顿法抛物线法10:30104.2 最速下降法（2）计算方法根据一元函数极值的必要条件及复合函数求导公式得 ()()()0Tkkkkfff xxx1()()0kTkffxx1()()min()min()kkkkkkaaffaffa f xxxxx1()0kTkdd10:30114.2 最速下降法（3）现象最速下降法的搜索路径1.在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。2.搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。3.形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。10:30124.2 最速下降法4.在远离极小点位置
6、，每次迭代可使函数值有较多的下降。5.在接近极小点位置，每次迭代行进的距离缩短，收敛速度减慢。6.最速下降性”只是迭代点邻域的局部性质。从全局看，并非最速下降方向。（3）现象10:30134.2 最速下降法（4）计算步骤1)给定初始迭代点x0，精度，维数n；2)令k0；3)计算xk的梯度 ；4)以xk点为出发点，求 方向上的最优步长k，有 ；5)终止判别？若满足条件，输出最优解，xk+1 x*,f*f(x*)。否则，令k k+1，转步骤3)。()kfx()kfx1()kkkkfxxx1kkxx10:30144.2 最速下降法（4）计算步骤10:30154.2 最速下降法（5）举例沿负梯度方向进
7、行一维搜索，有02,2Tx例：求目标函数 的极小点。取初始点2221)(xxfx解：初始点处梯度：4422)(0210 xxxxf)(001xfxx10:30164.2 最速下降法（5）举例0为一维搜索最佳步长，应满足极值必要条件 122000()min(24)(24)min()f x 00()16(24)0 00.5100 x 010024242424x 10:30174.2 最速下降法（5）举例0)(0022)(0)(121111xxxxfxxff第一次迭代设计点位置和函数值 因此，迭代终止：0)(001xxxfT10:30184.2 最速下降法（5）举例10:30194.2 最速下降法（
8、5）举例例：用最速下降法求 222125)(xxXf极小点，精度 解：1）取初始点 。TX2,20104)(0Xf初始梯度1004502)(0210XxxXf2）沿负梯度方向一维搜索0000001100242100422)(XfXX3）求最优步长0001.0初始点处函数值221000000()min()min2425 2100min()()8(24)5000(2100)00.02003072f Xf Xf X 10:30204.2 最速下降法（5）举例4)计算新的迭代点位置和函数值686164.3)(103071785.0919877.110024212001XfX5）迭代终止条件判断16.0
9、)2103071785.0()2919877.1(22201XX继续迭代。取初始点为X1，继续重复1-5步，直到满足精度要求。迭代10次的结果是：00)(00*XfX10:30214.2 最速下降法（5）举例 这个问题的目标函数的等值线为一簇椭圆,迭代点从X0 走的是一段锯齿形路线，见图。10:30224.2 最速下降法（5）举例221212(,)y yyy其等值线由椭圆变成一簇同心圆。00102()10424()220yyyyy则函数 f(X)变为：y1=x1,y2=5x2将上例中目标函数 引入变换222125)(xxXf 仍从 ,即 出发进行最速下降法寻优。此时：TX2,20Ty10,20
10、10:30234.2 最速下降法（5）举例1000000()242410201020yyy 0 0为一维搜索最佳步长，可由极值条件：10022()min()min()()(24)(1020)yyy0()00560.5112从而算得一步计算后设计点的位置及其目标函数：由沿负梯度方向进行一维搜索：10:30244.2 最速下降法（5）举例010124010200()0 yy经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。10:30254.2 最速下降法（5）举例例：用最速下降法求下面无约束优化问题：10:30264.2 最速下降法（5）举例10:
11、30274.2 最速下降法（5）举例10:30284.2 最速下降法（5）举例10:30294.2 最速下降法（6）收敛性分析最速下降法的收敛速度和变量的尺度关系很大。在适当条件下，收敛速度的估计公式：式中m表示f(x)的海塞矩阵的最大特征值上界，M表示f(x)的海塞矩阵的最小特征值的下界1624*625kkxxxx对于等值线为椭圆的二次型函数222125)(xxXf其海塞矩阵为20050G特征值为2，50因此212*1*kkmxxxxM收敛性较慢10:30304.2 最速下降法（7）最速下降法的典型特征由于一维搜索是求 kkkkXfXfXf1 0dd的极小。故应满足：即 011kTkkTkk
12、kkkkkXfXfXfXfXfdXfXdfdXdf因此，在梯度法中，相邻两次搜索方向（即相邻两次迭代点的梯度方向）是正交的。10:30314.2 最速下降法（7）最速下降法的典型特征1.理论明确，程序简单，对初始点要求不严格。2.对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。3.梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。4.梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆(球)的目标函数，一次搜索即可达到极小点。10:30324.3 牛顿型方法（1）基本思
13、想在xk邻域内用一个二次函数 来近似代替原目标函数，并将 的极小点作为对目标函数 求优的下一个迭代点 。经多次迭代，使之逼近目标函数 的极小点。牛顿法是求函数极值的最古老算法之一。()x()x()f x1kx()f x10:30334.3 牛顿型方法（2）迭代公式原函数:近似二次函数:求 的极小点 ，要求其梯度等于零。()f x2()()()()()1()()()2kkTkkTkkffff xxxxxxxxxxx()x*x10:30344.3 牛顿型方法（2）迭代公式（牛顿方向）1）迭代方向：*1k2）步长因子：令由此，这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛G是一个常矩阵，其
14、中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。121()()()()0kkkkkff xxxxx112()()kkkkff xxxx12()()kkkdff xx10:30354.3 牛顿型方法（3）举例例：求目标函数 的极小点。解：取初始点2212()25fxxx02,2Tx102010102402()()121000050ff xxxx1004502)(0210 xxxxf50002)(02xf00 x经过一次迭代即求得极小点()0fx10:30364.3 牛顿型方法（4）阻尼牛顿法对于正定二次函数，牛顿法可以直达极小点。对于非二次函数，基本牛顿法的步长因子恒为1，有时
15、会导致迭代发散而失效，如果采用上述牛顿迭代公式，有时会使函数值上升。问题提出 10:30374.3 牛顿型方法（4）阻尼牛顿法比如，对于如下问题：2122121100minxxxXf 当TX5.05.005.60Xf50510Xf20020020010202Xf0052.00102.00102.00102.0102Xf新迭代点2398.04898.0010201XfXfXX26035.01Xf 当TX00010Xf020Xf20000202Xf005.0005.0102Xf新迭代点01010201XfXfXX1001Xf01XfXf问题提出 10:30384.3 牛顿型方法（4）阻尼牛顿法迭代
16、公式121()()(0,1,2,)kkkkkkkkdffkxxxxxk阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：1()()min()kkkkkkkffdfdxxx10:30394.3 牛顿型方法（4）阻尼牛顿法迭代步骤1）给定初始点x0，收敛精度，置k=0；2）计算3）求其中k是沿dk一维搜索最优步长；4）检查收敛精度。若 时停止，否则k=k+1，返回第二步。11222()()()()()kkkkkkfffdff 、xxxxx1kkkkdxx1kkxx10:30404.3 牛顿型方法（4）阻尼牛顿法算法特点1）不能保证每次迭代都使函数值下降。举例说明：用阻尼牛顿法求函数 的最优解
17、。初始点 2221411xxxxXf000X函数的梯度011221102111220124102210221231000XfxXfxxxxXfXX10:30414.3 牛顿型方法（4）阻尼牛顿法算法特点牛顿方向0220011201020XfXfd020000001dXX0116400f01000000XXf结果说明迭代后的新点仍为原点，无法继续迭代。原因是海赛矩阵不定，导致失败。10:30424.3 牛顿型方法（4）阻尼牛顿法算法特点2）初始点应选在x*附近，有一定难度；3）尽管每次迭代都不会是函数值上升，但不能保证每次下降 4）收敛速度较牛顿法慢，但对初始点无特殊要求，实用性更好5）要求海赛
18、矩阵正定（保证有极小值）和非奇异（保证有逆矩阵）。这使得该法对复杂多变量目标函数的优化问题无实用价值；6）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。10:30434.3 牛顿型方法（5）牛顿型法与梯度法对比1(0,1,2,)kkkkdkxx1()(0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx一般迭代式：梯度法：牛顿法：阻尼牛顿法：10:3044（1）共轭方向的概念4.4 共轭方向与共
19、轭方向法设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足 ，则称向量d0和d1关于矩阵G共轭。01()0TdGd01()0Tdd如果G=I（单位矩阵），就有 ，d0和d1方向正交，即与单位矩阵共轭的方向是正交方向，所以正交方向是共轭方向的一个特例。但两者不能混淆。共轭但不正交正交但不共轭对于2112G0111,11dd 共轭正交0111,02dd 0110,01dd 10:3045（1）共轭方向的概念4.4 共轭方向与共轭方向法假设目标函数f(x)在极值点附近的二次近似函数为1()2TfTxx Gxb xc对二维情况任选取初始点x0沿某个下降方向d0作一维搜索，得x11000 xx
20、d10:3046（1）共轭方向的概念4.4 共轭方向与共轭方向法1100()0Tff xxdd0d0 x0 x1x*1 11d11()fxd1如果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象。1()fx 取下一次的迭代搜索方向d1直指极小点x*。因为0是沿d0方向搜索的最佳步长，即在点x1处函数f(x)沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有10:3047（1）共轭方向的概念4.4 共轭方向与共轭方向法如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x*，即有111xxd那么这样的d1方向应该满足什么
21、条件呢?对于前述的二次函数:1()2TfTxx Gxb xc11()fxGxb有10:3048（1）共轭方向的概念4.4 共轭方向与共轭方向法当 时，1xx10 x*是f(x)极小点，应满足极值必要条件，故有()0fxGxb111111()()()ff xG xdbxGd001()0TdGd将等式两边同时左乘 ,同时 得：0()Td10()0Tfxd10:3049（1）共轭方向的概念4.4 共轭方向与共轭方向法01()0TdGd 就是使d1直指极小点x*，d1所必须满足的条件。两个向量d0、d1和称为G的共轭向量，或称d0和d1对G是共轭方向。021()()0Tfdx d10:3050（1）共
22、轭方向的概念4.4 共轭方向与共轭方向法()0,0,1,2,1,iTji jmijdGd 则称d0,d1,dm-1是对G共轭n 定义：若设G为n*n对称正定矩阵，若n维空间中有m个非零向量系d0,d1,dm-1是满足 当G=I（单位矩阵）时，d0,d1,dm-1正交。共轭概念是正交概念的推广，正交是共轭的特例。10:3051（2）共轭方向的性质4.4 共轭方向与共轭方向法n 性质1 若非零向量系d0,d1,dm-1是对G共轭，则这m个向量是线性无关的。n 性质2 在n维空间中互相共轭的非零向量的个数不超过n。n 性质3 从任意初始点出发，顺次沿m个G的共轭方向d0,d1,dm-1进行一维搜索，
23、最多经过m次迭代就可以找到的二次函数f(x)极小点。10:3052（3）共轭方向法4.4 共轭方向与共轭方向法10:3053（3）共轭方向法4.4 共轭方向与共轭方向法在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。n 格拉姆-斯密特矢量系共轭化方法n 共轭梯度法n 鲍威尔（Powell）法n 10:3054（4）格拉姆-斯密特矢量系共轭化方法4.4 共轭方向与共轭方向法选定n个线性无关的矢量系v0,v1,vn-1，首先取00dv令10110dvd其中10是待定系数，可根据d1与d0的共轭条件来确定，即010100110
24、10000,TTTTdGvdGddG vddGd 从而求得与d0的共轭的d10110100TTdGvdvddGd10:3055（4）格拉姆-斯密特矢量系共轭化方法4.4 共轭方向与共轭方向法设已求得共轭的矢量d0,d1,dk，现求dk+1令111,0kkrkkrrdvd为使dk+1与dj（j=0,1,k）共轭，应有111,00kTTjkjrkkrrdGddG vd由此解得1111,10,TTjjkkkkjkjTkTjjjjjdGvdGvdvddGddGd Why?10:3056（4）格拉姆-斯密特矢量系共轭化方法4.4 共轭方向与共轭方向法由于111,00kTTjkjrkkrrdGddG vd
25、可推导出1011,01,11,1,0TjkTjjkkkkjkkdGvdGdddd由于d0,d1,dk共轭，所以0,TjidGdij i jk 11,0TTjjjkkjdGvdGd即11,TjkkjTjjdGvdGd 10:3057（4）格拉姆-斯密特矢量系共轭化方法4.4 共轭方向与共轭方向法例：求0100Te 的一组共轭矢量系d0,d1,d2解：（1）选定三个单位矢量e0、e1、e2作为一组线性无关矢量系210121012G 1010Te 2001Te（2）取d0=e0，求d110110ded01100021001001211012012101210012100120TTdGedGd 111
26、02Td10:3058（4）格拉姆-斯密特矢量系共轭化方法4.4 共轭方向与共轭方向法（2）求d221022120dedd12122111121221001012100121221031012110120TTdGedGd 0220000TTdGedGd 212133Td（3）判断是否满足共轭的定义0,0,1,20,TijijdGdi jij10:3059（4）格拉姆-斯密特矢量系共轭化方法4.4 共轭方向与共轭方向法对于非二次函数，可在极小点附近用二次函数来近似。1()(*)*2Tf xf xxxG xxx上式中的海塞矩阵相当于二次函数中的矩阵G，但x*未知，当迭代点x0充分靠近x*时，可用G
27、(x0)构造共轭矢量系。10:3060（1）概述4.5 坐标轮换法n许多优化方法都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。n坐标轮换法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。n这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。10:3061（2）基本思想4.5 坐标轮换法又称为单变量法，它是把一个多维无约束优化问题转化为依次沿各坐标方向的一维优化问题。TnTTeee 1.00.0.100.01 21对n维空间中每个坐标依次搜索完一遍，称
28、为完成一个搜索“轮”，然后，将前一轮得到的最优点，作为下一轮搜索的起始点。这样，不断循环，直到满足收敛条件为止。10:3062（2）基本思想4.5 坐标轮换法以二维问题为例进行说明 设有二维目标函数f(X)，其等值线如图所示，计算方法如下：1.选择初始迭代点 ，搜索精度 .0X2.以 为起点，并沿坐标轴 方向搜索，采用一维优化方法确定最优步长 ，并计算 。0XTe01111101eXX3.再以 为起点，并沿坐标轴 方向搜索，采用一维优化方法确定最优步长 ，计算 。1XTe10222212eXX4.到此完成一轮搜索，进行终止条件判别:?若条件满足，则输出最优解 。否则，进行下步。02XX2*2*
29、,XfFXX5.，转步骤(2)，进行下一轮的迭代运算。20XX10:3063例 用坐标轮换法求 的极小值.2112221242xxxxxXf001.0解 1）取初始点 ，沿 方向一维搜索，得:TX110 1101110101101001eXX其中 为一维搜索最佳步长，应满足 0134minmin2101001eXfXf得：21301X 沿 方向一维搜索，得:2e1e02022020102131013eXX其中 为一维搜索最佳步长，应满足 02722minmin21020102eXfXf得：2/12/3302X计算误差 06.20002XX4.5 坐标轮换法（3）算例10:30642）第二次迭代
30、搜索沿 方向一维搜索，得:其中 为一维搜索最佳步长，应满足 得：沿 方向一维搜索，得:2e1e其中 为一维搜索最佳步长，应满足 得：计算误差计算误差 2/33012/3311111110211eXX112/15minmin21110211eXfXf2/12/32/711X121221211122/32/7102/32/7eXX124/312minmin22121112eXfXf4/14/72/712X56.00212XX4.5 坐标轮换法10:30653）第三次迭代搜索沿 方向一维搜索，得:其中 为一维搜索最佳步长，应满足 得：沿 方向一维搜索，得:2e1e其中 为一维搜索最佳步长，应满足 得
31、：计算误差 21228/14/72/7014/72/721211211221eXX8/632/minmin21211221eXfXf4/14/74/1521X222222221224/74/15104/74/15eXX16/1272/2minmin22222122eXfXf8/154/1522X28.01222XX同理，继续迭代，共24次，可得到 8*,24*fX4.5 坐标轮换法10:30例:用坐标轮换法求下列目标函数的无约束最优解。给定初始点 ，精度要求=0.160410)(21212221xxxxxxxF000 x 解：做第一轮迭代计算沿e1方向进行一维搜索11101 1xxe式中，为第
32、一轮的起始点，取10 x100 xx111101000 x 4.5 坐标轮换法10:3066按最优步长原则确定最优步长1，即极小化12111min()1060F x此问题可由某种一维优化方法求出1:01021511150 x 以 为新起点，沿e2方向一维搜索11x1121222255001xxe 以最优步长原则确定2，即为极小化12122min()1060F x5.421254.5x4.5 坐标轮换法10:3067对于第一轮按终止条件检验11222054.56.7xx计算5轮后，有55200.0413xx故近似优化解为527.9883*5.9981xx*(*)7.95025ff x4.5 坐标
33、轮换法10:3068691.给定初始点 ,迭代精度 ,维数n,搜索方向 (i=1n)；nRX0iied 12.置k0；3.置i1；4.置 ；kiXX105.从 点出发,沿方向 进行关于 的一维搜索,求出最优步长 ,使kiX1kidkkikikkikikikidXfdXf11min6.判别i=n?若满足条件则进行步骤7;否则置i+1i,返回步骤5；7.检验是否满足终止迭代条件?若满足则输出最优解;否则置 (i=1n),XnkX0,k+1k,返回步骤3。4.5 坐标轮换法（4）计算步骤0kknXXkid1kid10:3070（4）算法步骤10:30 方法简单，容易实现。当维数增加时，效率明显下降，
34、只适于N10的小型优化问题。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。当函数的等值线族为长、短轴分别与坐标轴平行的椭圆时，如图 a)所示，二次就收敛到极值点；但当函数的等值线族仍为椭圆，仅仅只是长短轴倾斜时，如图 b)所示，多次迭代后逼近极值点；如图 c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到 A 点，再沿两个坐标轴以t0步长测试，目标函数值均上升，计算机判断 A 点为最优点。事实上发生错误。4.5 坐标轮换法（5）方法评价7110:30n 共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。n 以梯度法
35、相邻两次迭代的负梯度方向 呈线性无关且互为正交这点为基础而构造出的一种具有二次收敛的算法。n 每轮搜索方向为一组共轭方向,但第一方向为负梯度方向。4.6 共轭梯度法（1）概述1,kkXfXf7210:30共轭梯度法的搜索方向是在采用梯度法基础上的共轭方向，目标函数 F(x)在迭代点 X(k+1)处的负梯度为-F(X(k+1)，该方向与前一搜索方向S(k)互为正交，在此基础上构造一种具有较高收敛速度的搜索方向。4.6 共轭梯度法（2）搜索方向7310:304.6 共轭梯度法（2）搜索方向740011)(dXfd第二方向：)(00Xfd第一方向：0001dXX0X1d1X0d)(1Xf*d1可表示
36、为两个负梯度方向的线性组合。可以推导出一般搜索方向dk+1需要满足如下条件（1）（2）以dk 与-f(X(k+1)为基底的子空间中，矢量相共轭，即满足：11()kkkkdf Xd 10TkkdG d其中：21()()kkkf Xf X 10:3075221)()(kkkXfXfkkkkdXfd)(11，以后新方向均按下述迭代公式产生：2021001000110)()()()()()()()(XfXfXfXfXfXfXfXfTT因而，001GddT因为（G是二次函数的Hessian 矩阵）故有0)(0001GddXfT00010)(GddGdXfTT0001dXX000101)()()(GdXX
37、GXfXf故有又0)(10XfdT（正交）二次函数cXbGXXXfTT21)(其梯度为bGXXf)(4.6 共轭梯度法（3）推导过程10:30（4）计算 f(Xk+1)，若|f(Xk+1)|，则终止迭代，取X*=Xk+1；否则进行下一步;（1）选初始点 X0 和收敛精度；（2）令k=0，计算d0=-f(X0);（3）沿dk 方向进行一维搜索求 k，得 Xk+1=Xk+k dk;（5）检查搜索次数，若 k=n，则令X0=Xk+1，转(2)，否则，进行下一步;（6）构造新的共轭方向：dk+1=-f(Xk+1)+k dk，令k=k+1，转(3);21()()kkkf Xf X重置负梯度方向4.6 共
38、轭梯度法（4）算法步骤7610:3077k=n给定给定X0,n,k=0,Xk=X0dk=-f(Xk)k=k+1否否是是否否10kXXkkkkkkkdXfdXfXf)()()(1121重置负梯度方向重置负梯度方向)(min:1kkkkkkkkdXfdXX)(11kkXffXX是是停止停止)(1kXf)(),(11kkXfXf计算4.6 共轭梯度法（4）算法步骤10:30n 共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。n 该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算
39、机舍入误差的影响，虽然经过 n 次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。4.6 共轭梯度法（4）算法特点7810:3079例：用共轭梯度法求二次函数 的极小点和极小值。精度211222121242),(xxxxxxxf解：1）取初始点 ,TX1102424422)(12210 xxxxXf初始点模 ，取24)(00Xfd2）沿d0方向一维搜索01000000001424()1222XXdXf X 3）求最优步长4/10)();(min)(min)(00001XfXfXf20)(0Xf01.02/121X则初始梯度4.6 共轭梯度法（5）
40、算例10:30804）计算新的迭代点的梯度及模5)(2124422)(1122111XfxxxxXfX6）计算迭代点的系数和新的共轭方向232244121)(41205)()(001120210dXfdXfXf5）迭代终止条件判断5)(1Xf继续进行迭代计算。4.6 共轭梯度法10:30814.6 共轭梯度法121111022221/23/21/23/2XXd7）再沿d1进行一维搜索，得 8）求最优步长211111()min()min();()01f Xf Xd 242X 9）计算X2的梯度和海赛矩阵21222212240()()0420Xxxf Xf Xxx 222()24G XG正定迭代2次的结果：8)(;2422XfX10:30
