最优化方法 尹秋响课件第五章

1、本章要点：本章要点：单纯形单纯形单纯形搜索法的基本思想单纯形搜索法的基本思想共轭方向、共轭方向法的基本定理共轭方向、共轭方向法的基本定理PowellPowell共轭方向法的基本思想共轭方向法的基本思想最速下降法的基本思想及特点最速下降法的基本思想及特点NewtonNewton法基本思想及特点法基本思想及特点牛顿方向牛顿方向MarquardtMarquardt法基本思想法基本思想最小二乘问题最小二乘问题共轭梯度法基本思想共轭梯度法基本思想拟拟NewtonNewton法的基本思想法的基本思想第五章第五章 无约束非线性问题的解法无约束非线性问题的解法 学习的重要性：学习的重要性：1、直接用于无约束的

2、实际问题；直接用于无约束的实际问题；2、其基本思想和逻辑结构可以推广到约束问题；其基本思想和逻辑结构可以推广到约束问题；3、约束问题可以转化成无约束问题求解。约束问题可以转化成无约束问题求解。方法分类：方法分类：1、间接法：、间接法：对简单问题，求解必要条件或充分条件；对简单问题，求解必要条件或充分条件；2、迭代算法：、迭代算法：零阶法：只需计算函数值零阶法：只需计算函数值 f(x) 一阶法：需计算一阶法：需计算 f(x)二阶法：需计算二阶法：需计算 2f(x) 直接法直接法梯度法梯度法5.1 直接直接搜索法搜索法优点：计算不太复杂；易于实施与快速调试；所需的准备时间较少优点：计算不太复杂；易

3、于实施与快速调试；所需的准备时间较少5.1.1 单纯形搜索单纯形搜索法法1962年由年由Spendley, Hext和和Himsworth提出，提出，80年代得到证明年代得到证明 x1 x2 x3 （一）（一）单纯形单纯形空间中最简单、其空间中最简单、其 “维数维数”与空间维数相同的图形与空间维数相同的图形 x2 x1 n维空间中具有维空间中具有n+1个顶点的个顶点的 “n维超多面体维超多面体” 称为称为n维单纯形维单纯形如果各顶点间的距离（棱长）相等，则称为正规单纯形如果各顶点间的距离（棱长）相等，则称为正规单纯形（二）（二）单纯形法的基本思想单纯形法的基本思想初始单纯形初始单纯形搜索方向搜

4、索方向与步长与步长 比较单纯形比较单纯形顶点的函数值顶点的函数值 新近似点新近似点 新的单纯形新的单纯形以以 min f(x1, x2)为例为例 ，说明迭代过程，说明迭代过程x2x1PHPLfH fG fL PFPR反射反射PR fRfR 扩张失败扩张失败 PS =PR新单纯形新单纯形PGPLPS PSPEPSPR压缩压缩PS fS 0，令，令 x( i ) = x( 0 )+he( i ) , (i=1,2,n) 其中其中 e( i ) = (0,.,0,1,0,0)T 为单位坐标向量为单位坐标向量 第第i个分量为个分量为1 x2 x1 x(0)x(1)x(2)hh(2) 取初始步长取初始步

5、长h0，令，令 x( i ) = x( 0 )+Z( i ) , (i=1,2,n) 其中其中 Z( i ) = (q,.,q,p,q,q)T第第i个分量为个分量为p hnnq211 hnnnp211x2x1x(0)x(1)x(2)hqp p q棱长为棱长为h的正规单纯形的正规单纯形 2、计算函数值计算函数值fi = f (x(i)，(i=0,1,2,n)，并比较大小，找出最差点，并比较大小，找出最差点 x(H)，次差，次差 点点x(G) 和最好点和最好点x(L)，即，即fL = f (x(L) = min fi fH = f (x(H) = max fi fG = f (x(G) = max

6、 fi 0in 0in 0in iH 计算除去计算除去x(H)后的形心后的形心 x(F) )(1)(1Hniixxn3、按终止准则判断是否已达到精度要求，若已达到，停止计算，否则转按终止准则判断是否已达到精度要求，若已达到，停止计算，否则转44、求反射点求反射点x(R)5、将将fR 与与fL ，fG 和和fH 作比较作比较 (1)若若fRfL ,反射成功，进行扩张，扩张点反射成功，进行扩张，扩张点x(E) 若若fEfL ，扩张成功，令，扩张成功，令 x(H)= x(E) ,转向转向2 否则，扩张失败，令否则，扩张失败，令 x(H)= x(R) ,转向转向2(2)若若fLfRfG ,反射成功，但

7、改进不大，不进行扩张，反射成功，但改进不大，不进行扩张， x(H)= x(R) ,转向转向2(3)若若fGfRfH ,反射不太成功，在反射不太成功，在x(F)与与 x(R)之间压缩之间压缩(4)若若fRfH , 反射失败，在反射失败，在x(H)与与 x(F)之间压缩之间压缩 6、若若fSfH ，压缩成功，令，压缩成功，令 x(H)= x(S) ,转向转向2 否则，进行收缩。否则，进行收缩。 PHPGPLPFPRPE几点说明：几点说明：1、关于初始步长关于初始步长h的选取的选取 （一般可取（一般可取0.5h15） (1) 开始取开始取h为为1.62；(2) 进行到发现进行到发现fH fL 已已

8、很小，但尚未达到精度，这时取很小，但尚未达到精度，这时取x(0)= x(L)， 重新开始重新开始， 并取步长为：并取步长为： 当离精度要求已不远时，当离精度要求已不远时，h=0.51； 当离精度要求还很远时，当离精度要求还很远时，h 2。2、终止准则终止准则 P1093、扩张因子扩张因子 r =1.22例例5.1.1 用单纯形搜索法求解用单纯形搜索法求解 min f(x) =6010 x14x2x12 +x22x1x2 设设x(0)=0, 0T , e(1) = 1, 0T, e(2) = 0, 1T, 取取h=2, =0.5, =2, =1, 终止准则为终止准则为|(fHfL)/fL|0.0

9、01x1 x2x(H)x(G)x(F)x(R)x(E)x(L)x1x2x(H)x(L)x(G)x(F)x(R)x1x2x(G)x(H)x(L)x(F)x(R)x(E)5.1.3 Powell共轭方向共轭方向法（方向加速法）法（方向加速法） 1964年由年由Powell提出，后经提出，后经Zangwoll（1967年）和年）和Brent（1973年）改进，年）改进， 是迄今为止是迄今为止最有效的直接搜索法最有效的直接搜索法。 该算法该算法有效有效地地利用利用了了迭代迭代过程中的过程中的历史信息历史信息，建立起能，建立起能加速收敛加速收敛的方向的方向 有理论基础，有理论基础，以二次对称函数以二次对

10、称函数 f(x) = c + bTx + 1/2 xTAx 为模型为模型进行研究。进行研究。? 为什么选择二次函数作为模型为什么选择二次函数作为模型 ?1、在非线性目标函数中，最简单的是二次函数，故任何对一般函数有效在非线性目标函数中，最简单的是二次函数，故任何对一般函数有效 的方法首先应对二次函数有效；的方法首先应对二次函数有效；2、在最优点附近，非线性函数可用一个二次函数作近似，故对二次函数在最优点附近，非线性函数可用一个二次函数作近似，故对二次函数 使用良好的方法，通常对一般函数也有效；使用良好的方法，通常对一般函数也有效；3、很多实际问题的目标函数是二次函数。很多实际问题的目标函数是二

11、次函数。（一）（一）共轭方向共轭方向 设设A是是nn阶对称正定矩阵，阶对称正定矩阵，p(0), p(1)为两个为两个n维向量，若维向量，若 成立成立 p(0)T A p(1) = 0 则称向量则称向量p(0)与与p(1)为为A共轭或共轭或A正交，称该两向量的方向为正交，称该两向量的方向为A共轭方向。共轭方向。 若若 AI（单位矩阵），（单位矩阵），p(0)T p(1) = 0，即，即p(0)与与p(1)是正交的。是正交的。“共轭共轭”是是“正交正交”概念概念的推广的推广 =|p(0)|.|p(1)|cos 021 1 , 22121120 , 1 p Ap App , 21p , 01p ,

12、2112A(1)(0)T(1)(0)(1)(0)因为共轭的。是与则例：例：? 共轭方向有什么用共轭方向有什么用 ?（二）（二）共轭方向法的基本定理共轭方向法的基本定理定理定理5.1.1：设设A为为nn阶对称正定矩阵，阶对称正定矩阵，p(0), p(1)，, p(n-1)为为n个相互个相互A共轭共轭 的的n维非零向量（即维非零向量（即p(i) 0, i=0,1, n-1, 且且p( i )T A p( j ) = 0，i j），）， 则此向量系必线性无关。则此向量系必线性无关。 推推 论：论： 在在n维空间中，互相共轭的非零向量的个数不超过维空间中，互相共轭的非零向量的个数不超过n个。个。 定理

13、定理5.1.2：若若p(0), p(1), , p(n-1)是是n个非零的个非零的A共轭向量，则二次目标函数共轭向量，则二次目标函数 f(x) = c + bTx + 1/2 xTAx的最优点的最优点 x*为为( )1*( )( )( )0iTniiTiipbxppAp! 可得到非二次函数最优点的一个近似点；其中可得到非二次函数最优点的一个近似点；其中A是是Hesse矩阵！矩阵！? 上式用于非二次函数，可否得到最优点上式用于非二次函数，可否得到最优点 ？定理定理5.1.3:设设A为为n阶对称正定矩阵，对于二次目标函数阶对称正定矩阵，对于二次目标函数f(x) = c + bTx + 1/2 xT

14、Ax，从任意初始点从任意初始点x(0)出发，逐次进行一维搜索，即出发，逐次进行一维搜索，即 min f ( x( i )+ t p( i ) ) = f ( x( i )+ti p( i ) ) i0 若搜索方向若搜索方向p(0), p(1), , p(n-1)是非零的是非零的A共轭向量，则至多进行共轭向量，则至多进行n次迭代必可次迭代必可得到极小点得到极小点x* ，即有，即有 x( i+1) =x( i ) +ti p( i ) , i =0,1,n1 x* = x( k ) , 0kn 上述搜索方法具上述搜索方法具有二次收敛性有二次收敛性? 对非二次函数，采用上述方法，对非二次函数，采用上

15、述方法，n 次迭代是否也可得到极小点次迭代是否也可得到极小点 ？? 如何简便地找出如何简便地找出n个个A共轭的向量共轭的向量 ？定理定理5.1.4:假设假设1. n元函数元函数f(x) = c + bTx + 1/2 xTAx 中的矩阵中的矩阵A是对称正定的；是对称正定的；2. 向量向量p(0), p(1), , p(m-1) (mn)是互相是互相A共轭的；共轭的；3. x(0), x(1)是不同的任意两点，分别从是不同的任意两点，分别从x(0), x(1)出发，依次沿出发，依次沿p(0), p(1), , p(m-1) 作一维精确搜索，设最后一次一维搜索的极小点分别为作一维精确搜索，设最后一

16、次一维搜索的极小点分别为x(0)*和和x(1)*, 那么，那么， 向量向量 p = x(0)*x(1)*与与p(0), p(1), , p(m-1)互为互为A共轭。共轭。已知前已知前m个共轭方向，个共轭方向，就可以找到第就可以找到第m+1个共轭方向个共轭方向p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*x(0)x(1)p(0)p(0)p(1)p(1)x(0)*x(1)*p(2)x*（三）（三）Powell共共轭方向法的基本思想轭方向法的基本思想) 1, 1 (), 1 () 1, 1 () 2, 1 () 2 , 1 () 1 , 1 () 0 , 1 () 0()0 , 1

17、 (), 1 () 1 () 1()2() 1 ()0( nxxpnpnpnppxxxxxxxxnnn) 1, 2(), 2() 1, 2() 2, 2() 2 , 2() 1 , 2() 0 , 2() 1, 1 ()0 , 2(), 2()2() 1 () 1()2() 1 ( nxxpnpnpnppnxxxxxxxxnn) 1, 3(), 3() 1, 3() 2, 3() 2 , 3() 1 , 3() 0 , 3() 1, 2()0 , 3(), 3()3()2() 1 ()3()2( nxxpnpnpnppnxxxxxxxxn) 1,(),() 1,() 2,() 2 ,() 1

18、,() 0 ,() 1, 1()0,(),()() 1()2() 1() 1( nnxxpnnpnnpnnnpnpnnnxxxxxxxxnnnnnnn表表5.1.1 Powell共轭方向法的迭代过程共轭方向法的迭代过程阶段起点阶段起点x(k, 0)n+1次一维搜索过程次一维搜索过程新共轭方向新共轭方向)(kp一边搜索，一边搜索，一边找共轭方向一边找共轭方向共分共分n个阶段，每一阶段都进行个阶段，每一阶段都进行n+1次搜索，最后产生一个共轭方向次搜索，最后产生一个共轭方向任意任意n个线性无关的方向个线性无关的方向二维空间中的二维空间中的Powell方法示意方法示意p(0)p(1)e(2)e(1)

19、p(0) =e(1)p(1) =e(2)以以二次函数二次函数f(x1 , x2 ) 为例为例x(1,0)x(1,1)x(1,2)(1)pp(1)x(2,2)(2)px(2,0)x(2,1)x*对于二次函数对于二次函数,x* 即为极小点即为极小点（四）（四）Powell方法的原始算法方法的原始算法开始开始给定给定x(0) , e(1) , e(2) , e(n) 及及 否否x(k) = x(k, n)+k p(n -1) 其中其中k为最优步长为最优步长 k=1, p( i ) = e(i+1), i=0, 1, , n-1 j=0, x(k, j) = x( k-1 ) x(k, j+1) =

20、x(k, j)+j p( j ) 其中其中j为最优步长为最优步长 j=j+1 j=n满足精度满足精度否否k=k+1 x*=x(k+1)结束结束是是是是 p( i ) = p(i+1), i=0, 1, , n-2(, )(,0)(1)(, )(,0)|k nknk nkxxpxx几点说明几点说明1、迭代中逐次产生的是共轭方向，是较好的搜索方向，所以迭代中逐次产生的是共轭方向，是较好的搜索方向，所以Powell法又称法又称 方向加速法方向加速法；2、原始算法仅有理论意义。原始算法仅有理论意义。因为只有在每次搜索均为一维完全精确搜索因为只有在每次搜索均为一维完全精确搜索的条件下，每个阶段产生的方向

21、才是相互共轭的条件下，每个阶段产生的方向才是相互共轭的方向。的方向。但实际一维搜索都是近似的，产生的方向不但实际一维搜索都是近似的，产生的方向不一定共轭，一定共轭，有时甚至是线性相关的有时甚至是线性相关的，导致搜，导致搜索空间降维，这时将找不到真正的极小点。索空间降维，这时将找不到真正的极小点。p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*p(1) 对于一般函数对于一般函数, n个阶段迭代后一般得不到极小点个阶段迭代后一般得不到极小点,但由于共轭方向的个数只有但由于共轭方向的个数只有n个个, 如果继续按上述如果继续按上述方法迭代方法迭代, 产生的方向就不再是相互共轭方向了产生

22、的方向就不再是相互共轭方向了, 收敛速度会变慢收敛速度会变慢.（五）（五）原始算原始算法一种简便改进法一种简便改进重新开始重新开始：每进行每进行n个阶段的迭代，或当收敛速度变慢时，以当前点为起点，个阶段的迭代，或当收敛速度变慢时，以当前点为起点， 回到第一步重新开始回到第一步重新开始（六）（六）改进的改进的Powell算法算法1. 基本思想基本思想 :为克服搜索方向的线性相关问题，为克服搜索方向的线性相关问题，Powell对原始算法进行了改进。对原始算法进行了改进。? 如何判定方向组是如何判定方向组是“最相互共轭最相互共轭”的的 ?定理定理5.1.5 设设A是是n阶对称正定矩阵，方向组阶对称正

23、定矩阵，方向组p(0), p(1), ,p(n-1) 按下式意义是规范化的：按下式意义是规范化的： p( i )T A p( i ) = 1， ( i=0,1, n-1), 置置Q p(0), p(1), ,p(n-1) ，则方向组，则方向组p(0), p(1), ,p(n-1) 相互相互A共轭的充要条件为：共轭的充要条件为： 行列式行列式 |Q| 的值达到它的最大值。的值达到它的最大值。改进改进Powell算法的算法的理论基础理论基础在每个阶段产生新的方向在每个阶段产生新的方向p后后, 更换方向组的方法更换方向组的方法不是一律去掉第一个方向不是一律去掉第一个方向p(0), 而是有选择地去掉某

24、个方向而是有选择地去掉某个方向 p(J), 原则是原则是使新的方向组使新的方向组“ 最相互共轭最相互共轭”5.2 梯度梯度法法直接搜索法收敛速度一般比较慢，需要计算大量的函数值。直接搜索法收敛速度一般比较慢，需要计算大量的函数值。梯度反映了函数值变化的规律，充分利用梯度信息构造算梯度反映了函数值变化的规律，充分利用梯度信息构造算法，能加速收敛。法，能加速收敛。使用函数的梯度（一阶导数）或使用函数的梯度（一阶导数）或Hesse矩阵（二阶导数）的矩阵（二阶导数）的优化算法称为梯度法优化算法称为梯度法目标：目标：求出平稳点求出平稳点 （满足（满足 f(x)=0的的x * ）。）。由于由于 f(x)=

25、0 一般是非线性方程组，解析法往往行不通，一般是非线性方程组，解析法往往行不通， 所以梯度法通常也是逐次逼近的迭代法所以梯度法通常也是逐次逼近的迭代法假定：假定： f(x)和和 2f(x)连续存在连续存在5.2.1 最速下降法最速下降法(Cauchy法法)1847年年Cauchy提出。特点提出。特点是是直观易懂，但收敛速度慢直观易懂，但收敛速度慢（一）（一）基本思想基本思想x(k+1) = x(k) + tk p(k)x(k)x*p(k) = f(x (k) )x(k+1)p(k+1) = f(x (k+1) )瞎子下山：瞎子下山：由于他看不到哪里由于他看不到哪里是山谷，不可能沿直接指向山是山

26、谷，不可能沿直接指向山谷的路线走，他只能在当前位谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然里最陡就往哪里前进一步，然后在新的位置上再用手杖寻找后在新的位置上再用手杖寻找最陡方向，再下降一步。这就最陡方向，再下降一步。这就是最速下降法的形象比喻。是最速下降法的形象比喻。？多变量最优化迭代解法的一般迭代公式多变量最优化迭代解法的一般迭代公式可用一维搜索技术解决可用一维搜索技术解决关键是如何确定搜索方向关键是如何确定搜索方向p(k)迭代公式迭代公式 x(k+1) = x(k) tk f(x(k) ) （二）（二）算法算法开始开始给定给定x

27、(0) , M , 1 , 2 , 令令 k=0计算计算 f( x(k ) ) | f( x(k ) )| Mx*=x(k)是是结束结束是是一维搜索求一维搜索求tk 精度为精度为 2 否否x(k+1) = x(k) tk f(x(k) ) k=k+1 x(k+1)p(k)x(k)f(x)等值面等值面 f(x (k+1) )x(0)x(1)x(2)两维情形下最速下降法搜索路径两维情形下最速下降法搜索路径（三）（三）最速下降法的搜索路径呈直角锯齿形最速下降法的搜索路径呈直角锯齿形tk（四）（四）优缺点优缺点1、优点：、优点：计算简单，需记忆的容量小；计算简单，需记忆的容量小；对初始点要求低，稳定性

28、高；远离极小点对初始点要求低，稳定性高；远离极小点时收敛快，常作为其它方法的第一步。时收敛快，常作为其它方法的第一步。2、缺点：、缺点：收敛速度较慢（线性或不收敛速度较慢（线性或不高于线性）。原因是最速下降方向只高于线性）。原因是最速下降方向只有在该点附近有意义。有在该点附近有意义。尤其当目标函数等值面是很扁的椭圆、尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时，收敛更慢。椭球或类似图形时，收敛更慢。定理定理5.2.1 设从点设从点x(k) 出发，沿方向出发，沿方向p作作一维搜索，一维搜索， tk为最优步长因子，即为最优步长因子，即 f(x(k) + tk p) = min f( x(k)

29、 + t p) 则成立则成立 f(x(k) + tk p) T p =0, 即新点处的梯度与搜索方向垂直。即新点处的梯度与搜索方向垂直。tp(k+1)例例5.2.1 用最速下降法求函数用最速下降法求函数 f (x1, x2)x12+4x22 的极小点，（迭代两次），的极小点，（迭代两次）， 并验证相邻两个搜索方向是正交的。初始点取为并验证相邻两个搜索方向是正交的。初始点取为x(0)=1,1T 。解：解：梯度梯度 f (x)2x1, 8x2 T 。1. 第一次迭代：第一次迭代： f ( x(0) )2, 8 T ， x(1) = x(0) + t0 p(0) = x(0) t0 f (x(0)

30、1,1T t0 2, 8 T 用一维搜索求用一维搜索求t0 ，对简单，对简单f(x)，可用解析法求解：，可用解析法求解：设设 0 (t)f ( x(1) )f ( 1,1T t2, 8 T )(12t)2+4(18t)2 0(t)520t680 t0 0.130769x(1) =0.738462, 0.046152T2. 第二次迭代：第二次迭代： f ( x(1) )1.476924, 0.369216 Tx(2) = x(1) t1 f (x(1) =0.7384621.476924t10.046152+0.369216t1 1(t)f ( x(2) )(0.7384621.476924t)

31、2+4(0.046152+0.369216t)2 1(t)2.317625t+5.453173t0 t1 0.45005x(2) =0.110762, 0.110767T f ( x(2) )0.221524, 0.886136 T3. 验证相邻两个搜索方向是正交的：验证相邻两个搜索方向是正交的： f (x(0)T f (x(1) =2, 8 1.476924, 0.369216 T =0.00012 0 f (x(1)T f (x(2) = 1.476924, 0.369216 0.221524, 0.886136 T =0.000001 05.2.2 Newton法（二阶方法）法（二阶方法

32、）？由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别好的方向，有没有更好的方向好的方向，有没有更好的方向 ?)x0(x)f(xx21x)f(x)f(xf(x)3(k)2TT(k)(k) xf(x;(k)f(x)在在x(k)处的处的二次近似函数二次近似函数（一）基本（一）基本Newton法法取取 f(x; x(k)的平稳点作为的平稳点作为f(x) 最优点的一个近似点最优点的一个近似点 f (x; x(k) = f (x(k)+ 2f (x(k) x = 0 x x(k) = x = 2f (x(k)1 f (x(k)Newt

33、on迭代公式迭代公式 x(k+1) = x(k) 2f (x(k)1 f (x(k)x(k)f(x(k)f(x; x(k)x(k+1) 或或 x(k+1) = x(k)H(x(k)1g(x(k)H(x(k)1g(x(k)! 当当f(x)是二次函数时，一次迭代就可达到平稳点是二次函数时，一次迭代就可达到平稳点 ！! 当当f(x)是单变量函数时，本方法即为是单变量函数时，本方法即为Newton-Raphson法法！结束结束 基本基本Newton法的算法法的算法开始开始给定给定x(0) , , 令令 k=0计算计算g(k) = f( x(k ) ) x*=x(k)是是p(k) =H(x(k)1g(k

34、)x(k+1) = x(k) +p(k) k=k+1否否计算计算 H(x(k)|g(k )| 例例5.2.2 用基本用基本Newton法求函数法求函数 f (x1, x2)8x12+4x1x2+5x22 的极小点。的极小点。 初始点取为初始点取为x(0)=10, 10T 。解：解： f (x)16x1+4x2, 4x1+10 x2 T 2f (x)H(x)= 16 4 4 10H(x)1 =10 4 4 161144 x(1) = x(0)H(x(0)1 f (x(0)1010= 10 4 4 16114420014000因为因为f(x)是二次函数，所以一步迭代就达到平稳点，又因为是二次函数，

35、所以一步迭代就达到平稳点，又因为H(x(1)是正是正定矩阵，所以定矩阵，所以x(1)是极小点。是极小点。说明：说明：1、基本、基本Newton法要求法要求Hesse矩阵具有逆矩阵。矩阵具有逆矩阵。如果如果H(x(k)是正定的，则是正定的，则H(x(k)1必存在，从而算法是可行的，并且保证求得必存在，从而算法是可行的，并且保证求得的平稳点是极小点。的平稳点是极小点。然而在迭代过程中要求然而在迭代过程中要求H(x(k)是正定的这一条件不一定能保证，只有当初始是正定的这一条件不一定能保证，只有当初始点合适时才能满足。一般在极小点附近的点合适时才能满足。一般在极小点附近的Hesse矩阵容易为正定的。矩

36、阵容易为正定的。所以所以基本基本Newton法在极小点附近才比较有效法在极小点附近才比较有效。2、 Newton法的搜索方向法的搜索方向H (x)1 f (x)不一定是下降方向。不一定是下降方向。因为若是下降方向，则应有因为若是下降方向，则应有 f (x)TH (x)1 f (x)0，但由于，但由于H (x)1不一定是正定的，所以上式不一定成立不一定是正定的，所以上式不一定成立3、Newton法的最大优点是：当初始点选得合适时收敛很快，具有二阶收法的最大优点是：当初始点选得合适时收敛很快，具有二阶收敛敛 速度，是目前算法中最快的一种。速度，是目前算法中最快的一种。 对初始点要求高，一般要求初始

37、点离极小点较近，否则不收敛。有时即使是对初始点要求高，一般要求初始点离极小点较近，否则不收敛。有时即使是收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。4、方向、方向H (x)1 f (x)称为称为Newton方向，是一个好方向，对二次函数此方向方向，是一个好方向，对二次函数此方向 直指平稳点。直指平稳点。（二）修正（二）修正Newton法法? 怎样才能使怎样才能使Newton法成为一个下降算法法成为一个下降算法 ？修正修正Newton迭代公式：迭代公式： x(k+1) = x(k) tk H(x(k)1 f (x(k)

38、沿沿Newton方向一维方向一维搜索得到的最优步搜索得到的最优步长长 保证了保证了 f(x(k+1) f(x(k) ，且不必要求且不必要求H(x)为正定矩阵。为正定矩阵。? 出现出现 (1) H(x(k) 1不存在；或不存在；或(2) tk =0 时怎么办时怎么办 ？改用最速下降法改用最速下降法 ，即，即 p(k) = f (x(k) 修正修正Newton法与基本法与基本Newton法的优点是：法的优点是： 收敛快，程序简单。前者更实用可靠。收敛快，程序简单。前者更实用可靠。缺点是要求计算缺点是要求计算Hesse矩阵及其逆矩阵，计算量大，尤其当维数矩阵及其逆矩阵，计算量大，尤其当维数n较大时。

39、较大时。5.2.3 Marquart法法最速下降法的优点：对初始点要求不高，稳定性好；远离最优点时收敛较快。最速下降法的优点：对初始点要求不高，稳定性好；远离最优点时收敛较快。 缺点是离最优点较近时收敛很慢。缺点是离最优点较近时收敛很慢。牛顿法的优缺点刚好与最速下降法相反。牛顿法的优缺点刚好与最速下降法相反。 1963年年Marquardt提出将最速下降法与提出将最速下降法与Newton法结合，开始用最速下降法，法结合，开始用最速下降法，在接近最优点时用在接近最优点时用Newton法。法。 在迭代公式在迭代公式x(k+1) = x(k) +tk p(k)中，取步长中，取步长tk1 ，搜索方向为

40、，搜索方向为p(k) 2f (x(k) + kI1 f (x(k)其中其中 k同时起控制搜索方向和步长的作用，同时起控制搜索方向和步长的作用，I为单位矩阵为单位矩阵 (1) 开始阶段取很大，如开始阶段取很大，如 0=104 ，p(0) 2f (x(0) + 0I1 f (x(0) f (x(0) 1 0(2) 在迭代过程中，让在迭代过程中，让 k0， p(k) 2f (x(k)1 f (x(k)（一）方法思想（一）方法思想最速下降法最速下降法 Newton法法 具体在每一步是否缩小具体在每一步是否缩小 k，要通过检验目标函数值来决定，要通过检验目标函数值来决定 ：若若f(x(k+1) f(x(

41、k)，取，取 k+1 1，重作第，重作第k步迭代。步迭代。 （二）算法（二）算法开始开始给定给定x(0) , M， , 令令 k=0， 0=104 x*=x(k)是是结结束束p(k) = 2f (x(k) + kI1 f (x(k)否否否否 kM是是计算计算 f( x(k ) ) | f( x(k ) ) | x(k+1) = x(k) +p(k)f(x(k+1) f(x(k) k+1= 0.5 k , k=k+1是是否否 k= 2 k（三）评注（三）评注 PP124I 可推广为可推广为半正定矩半正定矩阵阵若若 2f (x(k) + kI1不存在不存在x(k+1) = x(k) + tkp(k

42、)5.2.4 非线性最小二乘问题非线性最小二乘问题（一）最小二乘问题（一）最小二乘问题在工程实际问题中，经常遇到一类特殊的求极小值问题，其目标函数具有在工程实际问题中，经常遇到一类特殊的求极小值问题，其目标函数具有平方和形式：平方和形式：nm (x),fF(x)m1i2i例例5.2.3 求解方程组求解方程组fi(x)=0，（，（i=1,2, m)的问题可化为求解下列优化问题的问题可化为求解下列优化问题m1i2i(x)f F(x)min例例5.2.4 通过通过m组实验数据来建立物理量组实验数据来建立物理量y与另外与另外l个物理量个物理量t1, t2 , tl 之间的函数关系：之间的函数关系：y

43、= Y(t1, t2 , , tl ; x1, x2, , xn) “接近接近”的衡量标准常用平方和形的衡量标准常用平方和形式式 m1i2im1i2(i)221(i)l(i)2(i)1m1i2(i)(i)(x)fy)x,.,x,x;t,.,t ,Y(t)yy(F(x)即要确定其中即要确定其中n个待定参数个待定参数x1,x2,xn ，使得经验公式的计算值，使得经验公式的计算值 与实验值与实验值 尽可能地接近。尽可能地接近。(i)y(i)y求解求解min F(x) 为求解方便，引入向量函数为求解方便，引入向量函数 f(x)=f1(x),f2(x),fm(x)T 最小二乘问题化为：最小二乘问题化为：

44、 min F(x) = min f(x)Tf(x) = min |f(x)|2（二）最小二乘问题的求解（二）最小二乘问题的求解可直接用前面介绍的单纯形法、可直接用前面介绍的单纯形法、Powell共轭方向法、最速下降法、共轭方向法、最速下降法、Newton法、法、Marquart法求解法求解 最小二乘法最小二乘法 （Gauss-Newton法）法）！ 如用如用Newton法求解，则要求法求解，则要求F(x)的的Hesse矩阵，是否可以不求矩阵，是否可以不求H(x) ！由于最小二乘问题目标函数形式的特殊性，可用计算一阶导数来代替二阶导由于最小二乘问题目标函数形式的特殊性，可用计算一阶导数来代替二阶

45、导数的计算数的计算 ： F(x(k)=2J(x(k)Tf(x(k) Newton方向：方向： p(k) = 2F(x(k)1 F(x(k)Jacobi 矩阵矩阵 J(x)=Jij(x)mn Jij(x) = jix(x)f 2F(x(k) 2J(x(k)TJ(x(k) 迭代公式：迭代公式：x(k+1) = x(k) J(x(k)TJ(x(k)1 J(x(k)Tf(x(k) x(k+1) = x(k) J(x(k)TJ(x(k)1 J(x(k)Tf(x(k) 修正修正Gauss-Newton迭代公式迭代公式tk? ! 如果在某次迭代中如果在某次迭代中J(x(k)TJ(x(k)变成奇异的，则变成奇

46、异的，则Gauss-Newton法失效法失效 !可直接取负梯度方向可直接取负梯度方向J(x(k)Tf(x(k) 为搜索方向为搜索方向修正修正Gauss-Newton法的算法法的算法: P1275.2.5 共轭梯度法共轭梯度法 由由Powell共轭方向法可知，共轭方向是好方向，是否有比共轭方向法可知，共轭方向是好方向，是否有比Powell共轭方向共轭方向 法更简单的方法构建共轭方向？法更简单的方法构建共轭方向？（一）（一）FletcherReeves共轭梯度法的基本思想共轭梯度法的基本思想任取初始点任取初始点x(0) ，然后沿着逐次迭代产生的共轭方向，然后沿着逐次迭代产生的共轭方向p(k)进行一

47、维搜索：进行一维搜索：x(k+1) = x(k) + tk p(k)得到下一个迭代点。得到下一个迭代点。当当f(x)为二次函数为二次函数时，至多经过时，至多经过n次次迭代就可得到极小迭代就可得到极小点点构造共轭方向构造共轭方向p(0),p(n-1)的方法：的方法： p(0) = f(x(0) p(k+1) = f(x(k1) + kp(k) 即下一个共轭方向是当前点处负即下一个共轭方向是当前点处负梯度方向与已求得的最后一个共梯度方向与已求得的最后一个共轭方向的线性组合。轭方向的线性组合。 p(0) = f(x(0) f(x(1)p(1) = f(x(1)+ 0p(0)x(0)x(1) ! 要使

48、得要使得p(0),p(n-1)相互共轭，相互共轭， 显然显然 k不能随便取不能随便取 ！2(k)21)(k(k)T(k)1)(kT1)(kk)f(x)f(x)f(x)f(x)f(x)f(x记记 g(k) = f(x(k)FR共轭梯度法的迭代公式：共轭梯度法的迭代公式：x(k+1) = x(k) + tk p(k)p(k+1) = g(k) + kp(k) k=|g(k)|2 |g(k+1)|2 p(0) = g(0) 以二次目标函数为模型，经推导得：以二次目标函数为模型，经推导得：（详细看（详细看P129下半页的内容，注意下半页的内容，注意式式5.2.19及及5.2.20的推导）的推导）几点说

49、明：几点说明：1、“ 重新开始重新开始”的策略的策略原因同原因同Powell共轭梯度法（误差、共轭梯度的个数）共轭梯度法（误差、共轭梯度的个数）2、何时执行重新开始步骤？、何时执行重新开始步骤？ 见见PP131（二）（二）FR法的算法法的算法开始开始给定给定x(0) , |g(k+1 )| 否否k=0， p(0)=g(0) x*=x(0)是是结束结束g(0) = f( x(0 ) )|g(0)| x(k+1) = x(k) + tk p(k), g(k+1) = f(x(k+1 )其中其中tk为最优步长为最优步长x(0)=x(k+1)g(0)=g(k+1)是是否否ak = |g(k+1)|2

50、/ |g(k )|2 p(k+1) = g(k) + kp(k) k=k+1x*=x(k+1)是是结束结束k = n 否否例例5.2.6 用用FR共轭梯度法解共轭梯度法解 min f (x)6010 x1 4x2 +x12 +x22 x1x2 初始点取为初始点取为x(0)=0, 0T 。解：解： f (x)102x1x2, 42x2x1 T p(0) g(0) f (x (0)10, 4T进行一维搜索，对简单进行一维搜索，对简单f(x)，可用解析法求解：，可用解析法求解：f (x(1)= f (x(0)t p(0)= f (x)|x=10t, 4tT = 60116t+76t2f (t)152

51、0t1160 t0 0.76315789x(1) = x(0) + t0 p(0) =7.63157894, 3.052631578Tg(1) f (x (1)2.21052631, 5.52631579Ta0= |g(1)|2 / |g(0 )|2 =35.42659277 / 116p(1) = g(1) + 0p(0) =0.84349308, 6.747922437T再用解析法求最优步长再用解析法求最优步长 t1 得得t1 0.436781609x(2) = x(1) + t1 p(1) =7.999999993, 5.999999997Tg(2) f (x (2)0, 0T所以，所以

52、，x* = 8, 6T f * = 8（三）（三）其它的共轭梯度法（自学）其它的共轭梯度法（自学）（四）（四）评注评注1、共轭梯度法的优点是不必计算、共轭梯度法的优点是不必计算Hesse矩阵及其逆矩阵，程序简单，对大规模矩阵及其逆矩阵，程序简单，对大规模 问题很有吸引力。对一般函数为超线性收敛。问题很有吸引力。对一般函数为超线性收敛。2、收敛速度依赖于一维搜索的精确性及、收敛速度依赖于一维搜索的精确性及Hesse矩阵的特征值的分布。矩阵的特征值的分布。5.2.6 拟拟Newton法（变尺度法）法（变尺度法）Newton法的最大优点是靠近极小点时收敛速度快，主要缺点是要计算法的最大优点是靠近极小

53、点时收敛速度快，主要缺点是要计算Hesse矩阵及其逆矩阵，计算量大矩阵及其逆矩阵，计算量大? 有没有可能既保持有没有可能既保持Newton法快速的优点，又不计算法快速的优点，又不计算Hesse矩阵及其逆矩阵矩阵及其逆矩阵 ?1959年年Davidon提出变尺度法，提出变尺度法，1963年经年经Fletcher和和Powell改进，形成改进，形成DFP法法1970年年Broyden等人提出更稳定的等人提出更稳定的BFGS变尺度法。变尺度法。（一）（一）拟拟Newton法与变尺度法法与变尺度法若一个算法的一维搜索方向为若一个算法的一维搜索方向为p(k) =H(k) f(x(k) H(k)g(k)

54、其中其中H(k)称为尺度矩阵（称为尺度矩阵（nn阶），由于迭代过程中阶），由于迭代过程中H(k)是变化的，该算法为变尺度法是变化的，该算法为变尺度法如果一个变尺度法的尺度矩阵满足拟如果一个变尺度法的尺度矩阵满足拟Newton条件条件 x(k+1)x(k) = H(k+1) f(x(k+1) f(x(k)则称为拟则称为拟Newton法法（二）（二）拟拟Newton法的基本思想法的基本思想Newton方向方向 p(k) = 2f(x(k)1 f(x(k)? 不想求不想求Hesse矩阵及其逆矩阵，有什么办法矩阵及其逆矩阵，有什么办法 ?从从形式形式上模仿，造一个方向上模仿，造一个方向： p(k) =

55、H(k) f(x(k)尺度矩阵尺度矩阵H(k) 既近似既近似 2f(x(k)1 ，计，计算又要方便！算又要方便！H(k)应满足的条件：应满足的条件： (1).满足拟满足拟Newton条件：条件：x(k+1)x(k) = H(k+1) f(x(k+1) f(x(k)(2).H(k)为正定矩阵，这样为正定矩阵，这样p(k)为下降方向为下降方向(3).由由H(k)出发计算出发计算H(k+1)应简便应简便:(4).应使算法具有二次收敛性。应使算法具有二次收敛性。校正矩阵校正矩阵H(k+1)H(k)E(k)（三）（三）DFP算法算法 p(0) = f(x(0) H(0) = I p(k) = H(k)

56、f(x(k) x(k+1) =x(k)+tkp(k)H(k+1)H(k) s(k) s(k)Ts(k)T y(k)H(k) y(k)Ty(k)T H(k) y(k)T H(k) y(k)其中其中 y(k) = g(k+1)g(k) s(k) = x(k+1)x(k)1、上述算法具有三个性质：、上述算法具有三个性质：(1) 校正公式的分母总大于零校正公式的分母总大于零, 校正公式总有物理意义；校正公式总有物理意义；(2) H(k)都是正定的，所以每次迭代方向都是下降方向；都是正定的，所以每次迭代方向都是下降方向；(3) 对二次函数对二次函数 f(x) = c+bTx+0.5xTAx (A为正定矩

57、阵为正定矩阵)，迭代得到的搜索方向，迭代得到的搜索方向 p(0), p(1) , p(k1)相互相互 A共轭，所以共轭，所以DFP是一种共轭方向法；是一种共轭方向法； 且且 H(n) = A1 ，说明，说明H(k) 逐次逼近逐次逼近A1 2、DFP法的重新开始策略法的重新开始策略由于计算的舍入误差及一维搜索精度不够，会破坏由于计算的舍入误差及一维搜索精度不够，会破坏H(k)的正定性，导致算法失效。的正定性，导致算法失效。（1）一维搜索后，如果一维搜索后，如果 f(x(k+1) f(x(k)，意味着，意味着 p(k) 不是下降方向，不是下降方向， H(k)不是正不是正 定矩阵，则重新开始，重置定

58、矩阵，则重新开始，重置H(k) = I；（2）每迭代每迭代n+1次后重新开始，令次后重新开始，令x(0) = x(k+1) , H(0) = I3、DFP法的算法法的算法开始开始给定给定x(0) , |g(k+1 )| f0 =f( x(0 ) ) , g(0) = f( x(0 ) )x(k+1) = x(k) + tk p(k), 其中其中tk为最优步长为最优步长fk+1 =f(x(k+1 ), g(k+1) = f(x(k+1 )x(0)=x(k+1)f0 = fk+1g(0)=g(k+1)是是否否y(k) = g(k+1)g(k) s(k) = x(k+1)x(k)x*=x(k+1)是是结束结束k = n 否否fk+1 fk否否是是H(0)= I， p(0)=g(0) , k=0p(k+1) = H(k+1) g(k+1) k=k+1H(k+1)H(k) s(k)