最优化计算方法(工程优化)第4章

1、 最优性条件最优性条件 最速下降法最速下降法 牛顿法及其阻尼牛顿法牛顿法及其阻尼牛顿法 共轭方向法共轭方向法 共轭梯度法共轭梯度法 变尺度法（变尺度法（DFP算法和算法和BFGS算法）算法） 目的是找目的是找 中的一点中的一点 ，使对，使对 ，均有，均有 ，称，称 为为(1)的全局极小点。的全局极小点。 min( ):(1)nf xfRR无约束最优化问题：无约束最优化问题：*()( )f xf xnR*xnxR 求解求解 (1)的计算方法称为的计算方法称为无约束最优化方法无约束最优化方法。*x( ),min( )min( ),( ),.nx Dx Rf xxDf xF xF xothers其中

2、 无约束最优化方法应用广泛，理论也比较成熟；无约束最优化方法应用广泛，理论也比较成熟； 可将约束优化问题转化为无约束优化问题来处理；可将约束优化问题转化为无约束优化问题来处理；解析法无约束优化方法直接法：利用函数的一阶或二阶导数的方法：利用函数的一阶或二阶导数的方法收敛速度快，需要计算梯度或者收敛速度快，需要计算梯度或者Hesse矩阵矩阵：仅利用函数值的信息，寻找最优解：仅利用函数值的信息，寻找最优解不涉及导数，适用性强，但收敛速度慢不涉及导数，适用性强，但收敛速度慢可求得目标函数的梯度时使用解析法可求得目标函数的梯度时使用解析法在不可能求得目标函数的梯度或偏导数时使用直接法在不可能求得目标函

3、数的梯度或偏导数时使用直接法本章介绍解析法本章介绍解析法 所谓所谓最优性条件最优性条件，是指最优化问题的最优解所要满足的，是指最优化问题的最优解所要满足的必要条件或充分条件必要条件或充分条件。 这些条件对于最优化算法的建立和最优化理论的推导都是这些条件对于最优化算法的建立和最优化理论的推导都是至关重要的。至关重要的。 解析法要用到目标函数的梯度或者解析法要用到目标函数的梯度或者Hesse矩阵，容易想到矩阵，容易想到利用一阶必要条件将无约束优化问题转化成一个梯度为利用一阶必要条件将无约束优化问题转化成一个梯度为0 0确定确定的方程组。的方程组。 这里用到的一阶必要条件就是最优性条件。这里用到的一

4、阶必要条件就是最优性条件。 设设 ，若，若 为为 的局部极小点，且在的局部极小点，且在 内连续可微，则内连续可微，则 *( )0.f x:nf RRx( )f x( *)N x*x xf 若若 为为 的局部极小点，且在的局部极小点，且在 内内 二次连续二次连续可微，则可微，则 半正定。半正定。 *xN xf*2*( )0,( )f xf x 设设 ，若在，若在 内内 二次连续可微，且二次连续可微，且 正定，则正定，则 为为 的严格局部极小的严格局部极小 点。点。 如果如果 负定，则负定，则 为为 的严格局部极大点。的严格局部极大点。*( )0,f x:nf RRx( )f x( *)N x 2

5、f x( )f x 2f xx( )f x 设设 是凸函数且在是凸函数且在 处连续可微，则处连续可微，则 为为 的全局极小点的充要条件是的全局极小点的充要条件是 设设 是严格凸函数且在是严格凸函数且在 处连续可微，若处连续可微，若 则则 为为 的唯一全局极小点。的唯一全局极小点。*( )0,f x:nf RRx( )f xxx( )f x*( )0.f x:nf RRx利用最优性条件求解下列问题：利用最优性条件求解下列问题：令令即即：得到驻点：得到驻点：利用二阶条件利用二阶条件判断驻点是否判断驻点是否是极小点是极小点 332122111min33f xxxxx22122121,2 ,ffxxx

6、xx 0,f x212221 020 xxx 12341111,.0202xxxx 利用一阶条件利用一阶条件求驻点求驻点函数函数的的Hesse阵：阵：在点在点处的处的Hesse阵依次为：阵依次为：利用二阶条件利用二阶条件判断驻点是否判断驻点是否是极小点是极小点 f x234111,.202xxx 12220022xf xx1234, ,x x x x 2120,02f x 2234202 0,.0202f xf x 222 0,0 2f x11,0 x 的行列式小于的行列式小于0 0； 2120,02f x 232002f x 222 00 2f x 242 002f x是正定矩阵；是正定矩阵

7、；是负定矩阵；是负定矩阵；是鞍点；是鞍点；14,x x是极小点；是极小点；2x是极大点。是极大点。3x： 迭代点沿某方向产生根据迭代点是否沿某个方向产生信赖域方法： 迭代点在某区域内搜索产线搜索方法生 对某些较简单的函数，这样做有时是可行的；对某些较简单的函数，这样做有时是可行的； 但对一般但对一般n元函数元函数 f(x) 来说，由条件来说，由条件 得到的是一个得到的是一个非线性方程组，解它相当困难。非线性方程组，解它相当困难。 为此，常直接使用迭代法。为此，常直接使用迭代法。( )0f x:1kk(1) 选定某一初始点选定某一初始点，并令，并令(2) 确定搜索方向确定搜索方向(3) 从从出发

8、，沿方向出发，沿方向求步长求步长，以产生下一个迭代点，以产生下一个迭代点(4) 检查得到的新点检查得到的新点是否为极小点或近似极小点。是否为极小点或近似极小点。，转，转(2)继续进行迭代。继续进行迭代。 在以上步骤中，选取步长在以上步骤中，选取步长可选用精确一维搜索或者非精确一可选用精确一维搜索或者非精确一维搜索，维搜索， 下降方向的选取正是下面我们要介绍的，下降方向的选取正是下面我们要介绍的，下降方向选取的不下降方向选取的不同，得到不同的算法。同，得到不同的算法。若是，则停止迭代。若是，则停止迭代。否则，令否则，令1x:1.k .kdkxkdk+1.kx+1kx从而得到第从而得到第 k+1次

9、迭代点，即次迭代点，即步长步长 由精确一维搜索得到。由精确一维搜索得到。k负梯度方向负梯度方向 这是函数值减少这是函数值减少最快的方向最快的方向 假设假设 f 连续可微，连续可微，()kkdf x 0()min()kkkkkf xdf xd1+()kkkkkkkxxdxf x负梯度方向负梯度方向 是函数值减少最快的方向是函数值减少最快的方向 ？令令 是单位长度的向量，是单位长度的向量， P是什么方向时，函数值是什么方向时，函数值 下降最快？也就是下降最快？也就是p是什么方向时，是什么方向时， 取得最小值？取得最小值？ 当当 时，时， 最小，最小值为最小，最小值为 ，此时由，此时由 可得可得 (

10、)kkdf x p1,0,p()( )+( )( )Tf xpf xf xpo()f xp( )Tf xp( )( )cos( ),)Tf xpf xpf xp cos( ),)1f xp ( )Tf xp( )f x ( )( )Tf xpf x ( )( )f xpf x 最速下降法是求最速下降法是求多元函数极值多元函数极值的的最古老最古老的数值算的数值算法，早在法，早在1847年法国数学家年法国数学家Cauchy提出该算法，后来提出该算法，后来Curry作了进一步的研究。作了进一步的研究。 该方法直观，简单，计算方便，而且后来的一些新的该方法直观，简单，计算方便，而且后来的一些新的有效的

11、方法大多数是对它的改进，或受它的启发而得到有效的方法大多数是对它的改进，或受它的启发而得到的。的。1x:1k (), *kkf xxx()kkdf x (1) 选定某一初始点选定某一初始点， 并令并令(2) 若若 ，否则转（，否则转（3）；）； 由精确一维搜索确定步长步长由精确一维搜索确定步长步长 ，即由一个极小化，即由一个极小化问题求得最佳步长问题求得最佳步长0(3)kmin()kkf xd1,1,kkkkxxdkk令令 转（转（2）。）。算法框图算法框图x1, 0, k=1| f(xk ) |0得得 xk+1=x(k)+kdkk=k+12212121min( )224 ,f xxxx xx

12、111+4+=12xd，11( )=+=1+4 ,12fxdf 0=( )8020, 利用最速下降法求解利用最速下降法求解令令22= 1+42 122 1+4124 1+4解解：函数的梯度为：函数的梯度为1212224( ),2+4xxf xxx第第1次迭代：次迭代：取取11,1.Tx 14,2f x 114=,2df x2=402031=1/4,得得222+=1/2+2xd，22( )=+=2+ ,1/2+2fxdf 0=( )105, 令令22= 2+2 1/2+22 2+1/2+24 2+,221=,2df x 2=5511/21=1/4,得得14=,2d2111142=+=+1/4=1

13、21/2xxd ，第第2次迭代：次迭代：21,2f x2=1/2,3222215/2=+=+1/2=1/223/2xxd ，32,1f x1212224( ),2+4xxf xxx335/2+2+=3/2xd，33( )=+=5/2+2 ,3/2fxdf 0=( )205, 令令22= 5/2+22 3/22 5/2+23/24 5/2+2332=,1df x2=10527/4得得第第3次迭代：次迭代：3=1/4,43335/223=+=+1/4=3/215/4xxd，41/2,1f x35/2=3/2x，32,1f x继续迭代可得到函数的近似最优解。继续迭代可得到函数的近似最优解。 设目标函

14、数设目标函数 f (x)连续可微，且水平集连续可微，且水平集 有界，则最速下降法或者在有限迭代步后终止；或者得有界，则最速下降法或者在有限迭代步后终止；或者得 到点列到点列 ，它的任何聚点都是，它的任何聚点都是f (x)的驻点。的驻点。 在收敛定理的假设下，若在收敛定理的假设下，若f (x)为凸函数，则最速下降法为凸函数，则最速下降法 或在有限迭代步后达到最小点；或得到点列或在有限迭代步后达到最小点；或得到点列 ，它，它 的任何聚点都是的任何聚点都是 f (x)的全局最小点。的全局最小点。1( )()Lx f xf xkxkx 最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法在两个相邻

15、点之间的搜索方向是正交的。 最速下降法向极小点逼近是曲折前进的，这种现象称为最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿锯齿现象现象。 除特殊的目标函数和极特殊的初始点外，这种现象都会发生。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。令令利用精确一维搜索，可得利用精确一维搜索，可得由此得出由此得出1. 相邻两次迭代的方向互相垂直相邻两次迭代的方向互相垂直( )(),kkf xd ()()0kkTkkkf xdd 0=()kkTkkf xdd()kkf xd+1=()kTkdd+1=()kTkf xd0 x1x2x0d1d2d注：注：在最速下降法中，利用精确一维在最速下降法中，

16、利用精确一维搜索求最搜索求最佳步长，使得相邻两次迭代佳步长，使得相邻两次迭代的搜索方向总是垂直的，的搜索方向总是垂直的，使得逼近极小点过程是使得逼近极小点过程是“之之”字形，字形， 这样从任何一个初始点开始，都可以很快到达极小点附这样从任何一个初始点开始，都可以很快到达极小点附近，但是近，但是越靠近极小点步长越小，移动越慢，越靠近极小点步长越小，移动越慢，导致最速下降导致最速下降法的收敛速度很慢。法的收敛速度很慢。 实际运用中，在可行的计算时间内得不到需要的结果。实际运用中，在可行的计算时间内得不到需要的结果。对正定二次函数，用最速下降法产生的点列：偶数项点对正定二次函数，用最速下降法产生的点

17、列：偶数项点 列均在一条直线上，奇数项点列也均在一条直线上，且列均在一条直线上，奇数项点列也均在一条直线上，且 都过最优点都过最优点. 对正定二次函数对正定二次函数 ，用最速下降法产生的点，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点上，且都过最优点. 则：则： 12Tf xx Ax分析分析：因为相邻方向正交，：因为相邻方向正交， 242/ / /./ /kddd22kAxtAx() kkkdf xAx因为22,ktdtd22.kxtxt与与k有关有关 2212min( )25f xxx12,2

18、Tx 14,100,Tf x0( )8(24 )5000(2 100 ), 为了清除为了清除最佳步长最速下降法中最佳步长最速下降法中两个搜索方向正交两个搜索方向正交的不良后的不良后果，提出了许多改进的方法，如：果，提出了许多改进的方法，如：(1) 选择不同初始点选择不同初始点令令取初始点取初始点22( )= (24 ,2100 )= 2425 2100f 11=4, 100Tdfx 第第1次迭代次迭代11+= 24 ,2100Txd16260.0200307231252得得21121+1.919877, 0.3071785 10Txxd然后再从然后再从 开始新的迭代，经过开始新的迭代，经过10

19、次迭代，得最优解次迭代，得最优解 计算中可以发现，开始几次迭代，步长比较大，函数值下计算中可以发现，开始几次迭代，步长比较大，函数值下降将较快，但当接近最优点时，步长很小，目标函数值下降很降将较快，但当接近最优点时，步长很小，目标函数值下降很慢。慢。2x*(0,0)Tx 221.919877, 0.3071785 10Tx如果不取初点为如果不取初点为 而取而取 1(2,2)Tx 1(100,0)Tx *(0,0)Tx 111122,50200,0,Tfxxx一步就得到了极小点。一步就得到了极小点。 可见：可见：造成锯齿现象与初始点的选择有关造成锯齿现象与初始点的选择有关，但怎样选一，但怎样选一

20、个初始点也是一件困难的事。个初始点也是一件困难的事。11,21(100,0) ,Tx 11=200,0,Tdfx 220= 10020025 00400 100200dd 22(100200 ,00 )= 10020025 00,f 2111+100,0+1/2200,0= 0,0TTTxxd第第1次迭代次迭代 虽然后一初始点较前一初始点离最优点虽然后一初始点较前一初始点离最优点 远，远，但迭代中不含上面出现的锯齿现象。但迭代中不含上面出现的锯齿现象。 采用非精确一维搜索求步长采用非精确一维搜索求步长, 可使相邻两个迭代点处的梯度不正交，从而改变收敛性。可使相邻两个迭代点处的梯度不正交，从而改

21、变收敛性。 对于最速下降法，有时为了减少计算工作量，采用固定步对于最速下降法，有时为了减少计算工作量，采用固定步长，称为固定步长最速下降法。长，称为固定步长最速下降法。 但但 到底取多大，没有统一的标准，到底取多大，没有统一的标准， 取小了，收敛太慢，取小了，收敛太慢，而而 取大了，又会漏掉极小点。取大了，又会漏掉极小点。（2）采用不精确的一维搜索：）采用不精确的一维搜索：2kkkdxx（3）采用加速梯度法：）采用加速梯度法： 由于最速下降法在极小点附近成由于最速下降法在极小点附近成“锯齿锯齿”状，因此下降过状，因此下降过程中的搜索方向可取程中的搜索方向可取 下两步继续用最速下降方向即下两步继

22、续用最速下降方向即负梯度方向负梯度方向。 Shah等人于等人于1964年提出了一种年提出了一种“平行切线法平行切线法”（简记为（简记为PARTAN法），又称加速梯度法。法），又称加速梯度法。负梯度方向和负梯度方向和 结合结合2kkkdxx这两种方向交替使用，效用要比最速下降法好的多。这两种方向交替使用，效用要比最速下降法好的多。1x kx0k 21211,0.kx则二次函数二次函数 A为对称正定，为对称正定， 分别分别 为其最小和最大特征值，从任意初点为其最小和最大特征值，从任意初点 出发，对二次函出发，对二次函 数，用最速下降法产生的序列数，用最速下降法产生的序列 ，对于，对于 有有( )

23、1/2,Tf xx Ax12, 由于由于 而函数而函数 的极小点恰好是的极小点恰好是 。故最速下。故最速下降法对于降法对于二次函数关于任意初点均收敛二次函数关于任意初点均收敛，而且是，而且是线性收敛线性收敛的。的。1( )2Tf xx Ax122121()()(),kkf xf x+1+11221121kkxx*0 x 下面说明最速下降法收敛性的几何意义。考虑具有对称正下面说明最速下降法收敛性的几何意义。考虑具有对称正交矩阵的函数交矩阵的函数12, 0,f x xc c函数的等值线为函数的等值线为其中其中 22112211( )22Tf xx Axxx1200A210改写为：改写为：22122

24、212122xxcc12 c22 c121222c22 c0 x1x 这是以这是以 和和 为半轴的为半轴的椭椭圆圆 从下面的分析可见从下面的分析可见 两个特征值的相对两个特征值的相对 大小决定最速下降法的收敛性。大小决定最速下降法的收敛性。 （1）当）当 时，等值线时，等值线变为圆变为圆 此时此时 因而由上述定理知因而由上述定理知：212101100 | 0 xx 即只需迭代一步就到了极小点，这表明最速下降法用于等即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标出发时，只需迭代一步就到了极小点值线为圆的目标出发时，只需迭代一步就到了极小点。1x2x1x2x（2）当）当 时时,

25、等值线为椭圆。此时对于一般的初始点等值线为椭圆。此时对于一般的初始点将产生锯齿现象。将产生锯齿现象。2210121kkxx （3）当）当 ， 等值线是很扁的椭圆等值线是很扁的椭圆 此时此时 ，对于一般的初始点，对于一般的初始点,收敛收敛 速度可能十分缓慢，锯齿现象严重。速度可能十分缓慢，锯齿现象严重。21211120 x1x2x 前面介绍精确一维搜索时介绍了牛顿法，即用目标函前面介绍精确一维搜索时介绍了牛顿法，即用目标函数的二次泰勒多项式近似代替函数本身，用二次多项式的极数的二次泰勒多项式近似代替函数本身，用二次多项式的极小点近似函数的极小点。小点近似函数的极小点。 这种方法可以推广到多维的情

26、形。这种方法可以推广到多维的情形。 求解无约束极小化问题的最古老的算法之一，现在已经求解无约束极小化问题的最古老的算法之一，现在已经发展成一类算法发展成一类算法-Newton型方法。型方法。1+12kkkkxxfxfx 1()=()kkkkf xxxfx一维优化的一维优化的Newton迭代公式迭代公式多维优化的多维优化的Newton迭代公式迭代公式 算法的基本思路：算法的基本思路： 考虑从考虑从 到到 的迭代过程，在的迭代过程，在 点处对函数点处对函数 Tayloy展开：展开：kx1kx f x 22( )()1()2TkkkTkkkkf xf xf xx xx xf xx xo x x 令令

27、 ，有，有kx略去高阶项略去高阶项 21( )( )()2TTkkkkkkf xQ xf xf xx xx xf xx x 20kkkQ xf xf xxx 若若Hesse矩阵矩阵 正定，则正定，则 存在，由此求出存在，由此求出二次函数二次函数 的极小点为的极小点为 ：以此以此 作为作为 极小点极小点 的一个新的近似。此公式的一个新的近似。此公式即为多元函数求极值的即为多元函数求极值的Newton迭代公式迭代公式。 Q x1kx*x f x2=kkkf xxxf x2kf x12kf x1+12kkkkxxfxfx f x1x11,: 1ffxk12kkkdf xf x 选定初始点选定初始点

28、, 计算计算已知目标函数已知目标函数 , 给定误差限给定误差限 . 如果如果 ，算法停止，算法停止， ，否，否 则转步骤则转步骤3。 计算搜索方向计算搜索方向kf x*kxx1,1kkkxxdkk 令令，转步骤，转步骤2. 步骤步骤3中的中的Newton迭代公式，可以换成通过方程组迭代公式，可以换成通过方程组 求得求得 ，这样可以减少计算工作，这样可以减少计算工作量，而且解线性方程组已有标准程序。量，而且解线性方程组已有标准程序。注意：此时步注意：此时步长取常数长取常数12+=0kkkf xdf xkd称为牛顿方向称为牛顿方向x1, 0, k=12f(xk) d= -f(xk) 得得dk ,

29、xk+1=xk+dk| dk | ,12120TkmmpAppp=+.+TkkkpAp=,故故01kkm= ,= ,., ,0TkipApik = ,0=0+TkkkpAp+.+证明证明： 利用利用性质性质2即可。即可。 若若Rn中的非零向量中的非零向量p1,p2, pm是是A共轭向量组，则这共轭向量组，则这m 个向量是线性无关的。个向量是线性无关的。 在在n维空间中互相共轭的非零向量的个数不超过维空间中互相共轭的非零向量的个数不超过n。 Rn中线性无关的非零向量最多有中线性无关的非零向量最多有n个。个。 设设n元函数元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设正定，又设n

30、维非零维非零 向量组向量组p1, p2, pn是是A共轭向量组，从任意点共轭向量组，从任意点x1出发，依次出发，依次 以以p1, p2, pn 为搜索方向进行精确一维搜索，则为搜索方向进行精确一维搜索，则 (1) f(xk+1)与与p1, p2, pk (k=1,2,n)正交；正交； (2) 最多最多n次迭代必达到二次函数次迭代必达到二次函数f(x)的极小点。的极小点。 性质性质4中中(1) f(xk+1)与与p1, p2, pk (k=1,2,n)正交；正交；( )f xAxb 是按照精确一维搜索得到的，所以有是按照精确一维搜索得到的，所以有11()kkf xAxb1( )2TTf xx A

31、xb xck1()0kTkf xp1()()kkkkf xf xAp1()0,1,2,.,1.kTif xpik下证下证()kkkA xpb()kkkAxbAp()kkkf xAp 111()kkkkkf xApAp .11111().iikkikkf xApApAp ,1,2,.,1,ik证明：证明：111111()()().()()TTkiiiiTiikTikTikkf xpf xpAppAppApp 11111()().()()iTiiTiiiTkiTkkkf xppAppAppAp 0 ,P1, P2 , Pn 是是A共轭向量组共轭向量组111111()().kiikkikkf xf

32、xApApAp ,故故 f(xk+1)与与p1, p2, pk (k=1,2,n)正交。正交。性质性质4中中(1) f(xk+1)与与p1, p2, pk (k=1,2,n)正交；正交；性质性质4中中(2) 最多最多n次迭代必达到二次函数次迭代必达到二次函数f(x)的极小点。的极小点。 假设假设 都不是都不是0，下证，下证 12(),(),.,()nf xf xf x1()0.nf x 利用利用(1)的结果，的结果， 与与A共轭向量组共轭向量组P1, P2 , Pn 都都正交，由正交，由性质性质1可知，可知，1()nf x1()0.nf x证明：证明： 在在n维空间中与维空间中与n个线性无关的

33、向量都正交的一定是零向量。个线性无关的向量都正交的一定是零向量。 设设n元函数元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设正定，又设n维非零向量组维非零向量组p1, p2, pn是是A 共轭向量组，从任意点共轭向量组，从任意点x1出发，相继以出发，相继以p1, p2, pn 为搜索方向进行精确一维搜索，则为搜索方向进行精确一维搜索，则 (1) f(xk+1)与与p1, p2, pk (k=1,2,n)正交；正交； (2) 最多最多n次迭代必达到二次函数次迭代必达到二次函数f(x)的极小点。的极小点。 一个算法若能在有限步内求得正定二次函数的极小点，一个算法若能在有限步内求得

34、正定二次函数的极小点， 则称该算法具有二次收敛性则称该算法具有二次收敛性(又称二次终止性又称二次终止性)。 由由性质性质4可知，若能找到一组可知，若能找到一组A共轭向量，共轭向量， 则前面提到的结合最速下降法和则前面提到的结合最速下降法和Newton法优点的算法就找到了，法优点的算法就找到了，就是就是共轭方向法共轭方向法， 这个算法具有二次收敛性。这个算法具有二次收敛性。 在下降迭代法中，若取下降方向是共轭方向，所得到的方法在下降迭代法中，若取下降方向是共轭方向，所得到的方法我们称为我们称为。怎么选取共轭方向？怎么选取共轭方向？ 共轭方向的选取有很大任意性，而一组不同的共轭方向共轭方向的选取有

35、很大任意性，而一组不同的共轭方向就对应着不同的共轭方向法。就对应着不同的共轭方向法。 作为一种迭代算法，我们自然希望共轭方向能在迭代过作为一种迭代算法，我们自然希望共轭方向能在迭代过程中逐次生成。程中逐次生成。 下面先以下面先以正定二次函数为例，介绍一种生成共轭方向的方正定二次函数为例，介绍一种生成共轭方向的方法法，再将这种方法推广到非二次函数上。，再将这种方法推广到非二次函数上。 这种方法这种方法中每一个共轭向量都是依赖于迭代点处的负梯度而中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来构造出来，所以称为，所以称为共轭梯度法共轭梯度法，它，它是共轭方向法中的一种。是共轭方向法中的一种。令

36、令1( ),2TTf xx Axb xcAA正定T (2) 若若 ，停止，停止，成的正交锥中找一个向量成的正交锥中找一个向量 ，即令，即令 使得使得 与与 共轭，即共轭，即由由21()0.TpAp(1) 从任取初始点从任取初始点x1 出发，沿出发，沿负梯度方向负梯度方向进行精确一维搜索进行精确一维搜索:2111,xxp11()pf x 2()0f x2()f x1p2p2211()pf xp 1p2p212111()0(), TTpApf xpAp可得可得21111()()TTf xAppAp否则在否则在 和和 张张1? (5) 若若 ，停止，停止，成的正交锥中找一个向量成的正交锥中找一个向量

37、 ，即令，即令 使得使得 与与 共轭，即共轭，即由由1()0.kTkpAp(3) 在在x2 处沿处沿 p2 方向进行精确一维搜索，方向进行精确一维搜索，3222,xxp1()0kf x1()kf xkp1kp11()kkkkpf xp kp1kp11()0() kTkkkTkkpApf xpAp可得可得1()()kTkkkTkf xAppAp(4) 以此类推，以此类推，45,.x x否则在否则在 和和 张张?k这样便构造了一组向量这样便构造了一组向量11(),1,2,.,1, kkkkpf xpkn12,.,np pp 实际上，这组向量实际上，这组向量 是一个是一个A共轭向量组。共轭向量组。1

38、2,.,np pp相邻两个向量是共轭的相邻两个向量是共轭的11(), pf x1()(),kTkkkTkf xAppAp设向量组设向量组 是由上述方法产生的向量组，向量是由上述方法产生的向量组，向量 组组 是由各点的梯度生成的向量组，是由各点的梯度生成的向量组， ( ) 则则 (1) 是正交向量组；是正交向量组； (2) 是是A共轭向量组。共轭向量组。12,.,np pp() kkgf x12,.,np pp12,.,ng gg12,.,ng gg设向量组设向量组 是由上述方法产生的向量组，向量组是由上述方法产生的向量组，向量组 是由各点的梯度生成的向量组，是由各点的梯度生成的向量组， ( )

39、 则则 (1) 是正交向量组；是正交向量组； (2) 是是A共轭向量组。共轭向量组。12,.,np pp( )kkgf x12,.,np pp12,.,ng gg12,.,ng gg 2=i n由由 的构造过程知，的构造过程知，ip12,p p是是A共轭的，即共轭的，即210= ,TpAp结论结论(2)成立；成立；利用精确一维搜索的性质知，利用精确一维搜索的性质知，120= ,Tgp而而11=,pg故故210= ,Tgg结论结论(1)成立。成立。 =(1)(2),= +1.iin kn k假设时，结论成立 下证时结论仍成立由假设可知，要证明由假设可知，要证明 时结论成立，只需证明时结论成立，只

40、需证明1= +n k1+kg(a) 证明证明所以所以结论结论(a)成立，进而结论成立，进而结论(1)成立。成立。与与12,.,kg gg正交，正交，1+kp与与12,.,kp ppA共轭。共轭。1+kg与与12,.,kg gg正交正交;12,.,kp pp是是A共轭向量组，共轭向量组，利用性质利用性质4(1)可知，可知， 设设n元函数元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设正定，又设n维非零向量组维非零向量组p1, p2, pn是是A 共轭向量组，从任意点共轭向量组，从任意点x1出发，相继以出发，相继以p1, p2, pn 为搜索方向进行精确一维搜索，则为搜索方向进行精

41、确一维搜索，则 (1) f(xk+1)与与p1, p2, pk (k=1,2,n)正交；正交；因为因为111(),1,(),2,., ,iiiif xipf xpin10,1,2,., ,+=Tikgpik11111,1,2,., ,+=TikTkiTiikigpigggppik0= ,(b) 证明证明结论结论(b)成立，进而结论成立，进而结论(2)成立。成立。1+kp与与12,.,kp pp是是A共轭的共轭的;由由 的构造过程知，的构造过程知，1121+= , ,., -TkipApikip1+kp与与kp是是A共轭的共轭的;下证下证1+kp与与121 -,.,kp pp是是A共轭的共轭的;

42、1+= TikgAp121=0= , ,., -TkipApik，11()+iiiiiiiiiiggAxbgA xpbgAp11+=TTkiikpApgAp11+=Tiikiggg 111+=/Tikiiggg0=112+=0= , ,.,Tkiggik，1+=TkikkgpAp设向量组设向量组 是由上述方法产生的向量组，向量是由上述方法产生的向量组，向量 组组 是由各点的梯度生成的向量组，是由各点的梯度生成的向量组， ( ) 则则 (1) 是正交向量组；是正交向量组； (2) 是是A共轭向量组。共轭向量组。12,.,np pp() kkgf x12,.,np pp12,.,ng gg注：为保

43、证方向的共轭性，初始方向取负梯度方向。注：为保证方向的共轭性，初始方向取负梯度方向。12,.,ng gg 设设n元函数元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设正定，又设n维非零维非零 向量组向量组p1, p2, pn是是A共轭向量组，从任意点共轭向量组，从任意点x1出发，相出发，相 继以继以p1, p2, pn 为搜索方向进行精确一维搜索，则为搜索方向进行精确一维搜索，则 (1) f(xk+1)与与p1, p2, pk (k=1,2,n)正交；正交； (2) 最多最多n次迭代必达到正定二次函数次迭代必达到正定二次函数f(x)的极小点。的极小点。 11111(),(),1

44、,2,.,1,(*)().()kkkkkTkkkTkpf xpf xpknf xAppAp 是一个是一个A共轭向量组共轭向量组12,.,np pp每一个搜索方向都依赖迭代点处的每一个搜索方向都依赖迭代点处的负梯度构造出来负梯度构造出来，对应的算法称为，对应的算法称为共轭梯度法共轭梯度法。存在问题：计算量、存储量都很大存在问题：计算量、存储量都很大11111(),(),1,2,.,1,(*)().()kkkkkTkkkTkpf xpf xpknf xAppAp 针对针对 f(x)=1/2xTAx+bTx+c, A=AT正定，最多正定，最多n次迭代达到极次迭代达到极小点找到了一组共轭方向：小点找到

45、了一组共轭方向：针对一般的函数，将这组方向进行推广：针对一般的函数，将这组方向进行推广：2 kAfx直接对直接对(*)式推广：式推广：在正定二次函数在正定二次函数的前提下，将的前提下，将 变形变形怎么解决呢？怎么解决呢？能否将能否将 中的中的A去掉？去掉？kk设设 ，向量组，向量组 是由上述方法构造的是由上述方法构造的A共轭向量组，共轭向量组， ，利用前面所得，利用前面所得 的公式，得到几个等价的计算公式：的公式，得到几个等价的计算公式：1( ),2TTf xx Ax b x c AA正定T12,.,np pp()kkgf x 1+1()()(,1967)()()(1)TkkTkkkTkkTk

46、kgApf xApDanielpAppAp +1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg 1+1()kkkkkkkkkkggAxbgA xpbgAp 利用定理利用定理1，可知，可知 是正交向量组，因此是正交向量组，因此(2)中中 ; 并且并且 .+1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg 12,.,ng gg

47、10+=Tkkgg10+=Tkkgp+122(4)(Re,1964)kkkgFlecherevesg +1+1()(3)(,1972)()kkkTkkTggDixonMyerspg +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg -1-12-1-1)()kkkkkTkTkkkkkpgppggpgg在(3)中，由,得到( +122(4)(Re,1964)kkkgFlecherevesg +1+1+1() ()(2)(,1972)() ()kkkkkTkk TgggSorenson Wolfepgg 1+11() ()=()()()(2)k

48、TkTkTTkkkkkkkkpggpggpggg中 +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg 对于正定二次函数，上面得到的对于正定二次函数，上面得到的5个计算公式是等价的；个计算公式是等价的； 这这5种共轭梯度法也是完全等价的；种共轭梯度法也是完全等价的；1+1()()(,1967)()()(1)TkkTkkkTkkTkkgApf xApDanielpAppAp +1+1+1() ()(2)(,1972)() ()kkkkkTkkTgggSorensonWolfepgg +1+1()(3)(,1972)()kkkTkkTggDix

49、onMyerspg +1+1() ()(5)(,1969)()kkkkkTkTgggPolyakPolakRibieregg +122(4)(Re,1964)kkkgFlecherevesg SW共轭梯度法共轭梯度法DM共轭梯度法共轭梯度法FR共轭梯度法共轭梯度法PPR共轭梯度法共轭梯度法介绍介绍FR共轭梯度法共轭梯度法Daniel共轭梯度法共轭梯度法简洁，用的最多简洁，用的最多更好用更好用 对于非二次函数，产生的搜索方向不再相同，对于非二次函数，产生的搜索方向不再相同， 利用公式利用公式(2)-(5), (1)中含有中含有Hesse矩阵，通常不用矩阵，通常不用1x+122,kkkgg步骤步骤

50、1. 选定初始点选定初始点 。步骤步骤2. 如果如果 ，算法停止，算法停止， ，否则转步骤，否则转步骤3。步骤步骤4. 精确一维搜索找最佳步长精确一维搜索找最佳步长 ，令，令1g*1xx*+1,kxx步骤步骤3. 取取k1kkkkxxp步骤步骤5. 如果如果 ，算法停止，算法停止， 否则转步骤否则转步骤6。+1kg步骤步骤6. 如果如果k=n, 令令 k=1 ，转步骤，转步骤4; 否则转步骤否则转步骤7。步骤步骤7. 计算计算 转步骤转步骤4。11=, =1.pg k1+11+1=,=,kkxxpg+11,1, kkkkpgpkk步骤步骤4. 精确一维搜索找最佳步长精确一维搜索找最佳步长 ，令

51、，令*+1kxxk1kkkkxxp步骤步骤5. 如果如果 ，算法停止，算法停止， ，否则转步骤，否则转步骤6。+1kg步骤步骤6. 如果如果k=n, 令令 算法停止算法停止,k=1 ，转步骤，转步骤4; 否则转步骤否则转步骤7。步骤步骤7. 计算计算 转步骤转步骤4。1+11+1=,=,kkxxpg 误差可能会使误差可能会使n步迭代得不到正定二次函数的极小点。步迭代得不到正定二次函数的极小点。 Rn中共轭方向最多有中共轭方向最多有n个，个，n步后构造的搜索方向不再是共轭的步后构造的搜索方向不再是共轭的， 会降低收敛速度，会降低收敛速度，步骤步骤6：重新开始技术：重新开始技术：xn+1作为新的作

52、为新的x1+122,kkkgg+11,1, kkkkpgpkk2212112( )242fxxxx xx，已知初始点，已知初始点(1,1)T解：解： 1）第一次迭代：沿负梯度方向搜寻）第一次迭代：沿负梯度方向搜寻计算初始点处的梯度计算初始点处的梯度11211212244()422x xxxgf xxx=, 迭代精度迭代精度 。 1142pg ,1114141212xp 0.001精确一维搜索求最佳步长，精确一维搜索求最佳步长，令令10.25211120.5xxp,221()2gf x ,11141 2xp 112()(14 12 ) 40203f xpf =,=, 08020= =, 得得不满

53、足精度，继续迭代：不满足精度，继续迭代：2）第二次迭代：）第二次迭代：2221150.2520gg2121pgp 22xp220.5x,212g,142p,142g,21.5,22220.51.50.5 1.5,精确一维搜索求最佳步长，精确一维搜索求最佳步长， 11()(220 5 1 5 )=, . + . f xpf22(22 )2(0.5 1.5 )2(22 )(0.5 1.5 )4(22 )=因因30g得到最优解得到最优解:3222xxp=+令令21 , 0= , 得得 22(2 2 )2(0.5 1.5 )2(2 2 )(0.5 1.5 )4(2 2 )= 330()0gf x ,1

54、1220.51.5=xp42, 342xx *. 共轭梯度法对正定二次函数，具有二次收敛性；共轭梯度法对正定二次函数，具有二次收敛性； 对非二次函数，由于目标函数的对非二次函数，由于目标函数的Hesse矩阵不再是常数矩矩阵不再是常数矩阵，因而产生的方向不再是共轭方向；阵，因而产生的方向不再是共轭方向； 共轭梯度法在一定条件下也是收敛的，且收敛速度通常优共轭梯度法在一定条件下也是收敛的，且收敛速度通常优于最速下降法，具有较高的求解效率。于最速下降法，具有较高的求解效率。 设设 f (x)存在连续一阶偏导数，且函数为凸函数，且水平集存在连续一阶偏导数，且函数为凸函数，且水平集 有界，则由共轭梯度法

55、得到的点列有界，则由共轭梯度法得到的点列 有如下有如下性质：性质：(1) 为严格单调下降序列，且为严格单调下降序列，且 存在；存在；(2) 的任意聚点的任意聚点 都是都是 f (x)的最优解。的最优解。1( )()Lx f xf x kx( )kf x kx*xlim()kkf x 共轭梯度法在无约束优化方法中占有重要的地位，是目前最共轭梯度法在无约束优化方法中占有重要的地位，是目前最常用的方法之一。常用的方法之一。 (1) 对凸函数全局收敛（下降算法）；对凸函数全局收敛（下降算法）； (2) 计算公式简单，不用求计算公式简单，不用求Hesse矩阵或者逆矩阵，计算量小，矩阵或者逆矩阵，计算量小

56、， 存储量小，每步迭代只需存储若干向量，存储量小，每步迭代只需存储若干向量，适用于大规模问适用于大规模问 题题； (3) 具有二次收敛性；具有二次收敛性； (对于正定二次函数，至多对于正定二次函数，至多n次迭代可达最优解）次迭代可达最优解） (4) Crowder和和Wolfe证明，证明，共轭梯度法的收敛速率不坏于最速共轭梯度法的收敛速率不坏于最速 下降法下降法。如果初始方向不用负梯度方向，则其收敛速率是线。如果初始方向不用负梯度方向，则其收敛速率是线 性收敛的；性收敛的； (5) 共轭梯度法是目前共轭梯度法是目前求解无约束优化问题最常用的方法之一求解无约束优化问题最常用的方法之一。注：不同的

57、注：不同的k公式，对于正定二次函数是等价的，公式，对于正定二次函数是等价的， 对非正定二次函数，有不同的效果，对非正定二次函数，有不同的效果，经验上经验上PPR 效果较好效果较好。 Newton法和阻尼法和阻尼Newton法具有收敛速度快的优点，但法具有收敛速度快的优点，但需要计算需要计算Hesse矩阵的逆，矩阵的逆，计算量大，存储量也很大。计算量大，存储量也很大。12= kkkpf xf x 为减少计算量，用一个为减少计算量，用一个n阶阶对称正定矩阵对称正定矩阵Hk近似代替近似代替Hesse矩阵的逆矩阵的逆 ，即，即 ，从而搜索方，从而搜索方向是向是 ，由此搜索方向产生的方法称为变尺度法，由

58、此搜索方向产生的方法称为变尺度法， Hk称为尺度矩阵，这是一种称为尺度矩阵，这是一种拟拟Newton法法，被认为是无约束优，被认为是无约束优化问题中最有效的方法之一化问题中最有效的方法之一。12kfx12kkHfx kkkpH g 任取初始点任取初始点x1,初始尺度矩阵初始尺度矩阵H1,令令k=1. 计算计算 利用精确一维搜索找最佳步长利用精确一维搜索找最佳步长 ，令，令 令令 ，转步骤，转步骤2。+1=+1kkkHHHkk，kHk+1=+.kkkkxxp. kkkpH gx1, H1对称对称0, k=1dk=- Hkf(xk)一维搜索得一维搜索得k xk+1=xk+ k dk|xk+1-xk

59、| ?修正修正Hk产生产生Hk+1Stop. xk+1-解解k=k+1yN构造构造 Hk的原则的原则变尺度法的关键在于如何构造变尺度法的关键在于如何构造Hk，为了使算法有较快的收敛速为了使算法有较快的收敛速度，需要满足以下几个原则：度，需要满足以下几个原则：拟牛顿性质，二次收敛性，稳定性。拟牛顿性质，二次收敛性，稳定性。拟牛顿性质拟牛顿性质在在 点处对函数点处对函数 作二阶作二阶 Tayloy展开：展开：1kx 111212111( )()1()2TkkkTkkkkf xf xf xx xx xf xx xo x x( )f x 略去高阶项略去高阶项 11112111( )()2TTkkkkk

60、kf xf xf xx xx xf xx x在在xk+1 附近，函数两端求导，得附近，函数两端求导，得1211( )kkkf xf xf xx x211+1kkkkkggf xxx令令 可得可得记记21(1)kkkgf xxHesse矩阵矩阵 对称正定，又有对称正定，又有121(2) kkkxf xg = ,=,kkkx x gf x1+1=,=,kkkkkkg ggx xx2+1kf x 11112111( )()2TTkkkkkkf xf xf xx xx xf xx x211+1+kkkkkggf xxx=(3)kkgA x1=(4)kkxAg( )=1/2+TTf xx Ax b x