第四章 无约束非线性问题的解法 本章要点： 最速下降法的基本思想及特点 牛顿方向 Newton法基本思想及特点

Presentation on theme: "第四章 无约束非线性问题的解法 本章要点： 最速下降法的基本思想及特点 牛顿方向 Newton法基本思想及特点"— Presentation transcript:

1 第四章 无约束非线性问题的解法 本章要点： 最速下降法的基本思想及特点 牛顿方向 Newton法基本思想及特点
第四章 无约束非线性问题的解法 本章要点： 最速下降法的基本思想及特点 牛顿方向 Newton法基本思想及特点 共轭方向、共轭方向法的基本定理 共轭梯度法基本思想 拟Newton法的基本思想

2 学习的重要性： 1、直接用于无约束的实际问题； 2、其基本思想和逻辑结构可以推广到约束问题； 3、约束问题可以转化成无约束问题求解。 方法分类： 1、间接法：对简单问题，求解必要条件或充分条件； 2、迭代算法： 零阶法：只需计算函数值 f(x) 一阶法：需计算 ▽f(x) 二阶法：需计算 ▽2f(x) 直接法 梯度法

3 考虑无约束优化问题： 本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较成熟。另一方面，通常可以把一些约束优化问题转化为无约束问题来处理，所以它是最优化方法中的基本方法。 这些方法通常要用到函数的一阶或二阶导数。 在实际问题中，也常遇到函数的解析表达式比较复杂，有的甚至写不出明显的解析表达式，因而导数很难求出或无法求出，这时基于梯度的方法不能用，需要采取另一种所谓的直接法（或直接搜索法）。直接法是仅仅利用函数值的信息，去寻找最优解的一类方法。在后面第九章有介绍。

4 直接搜索法收敛速度一般比较慢，需要计算大量的函数值。梯度反映了函数值变化的规律，充分利用梯度信息构造算法，能加速收敛。
使用函数的梯度（一阶导数）或Hesse矩阵（二阶导数）的优化算法统称为梯度法。 算法目标：求出平稳点 （满足f(x)=0的x * ）。 由于 f(x)=0 一般是非线性方程组，解析法往往行不通， 所以梯度法通常是逐次逼近的迭代法。 假定： f(x)和 2f(x)连续存在

5 ？ §4.1 最速下降法(Cauchy法) 1847年Cauchy提出。特点是直观易懂，但收敛速度慢。 （一）基本思想
多变量最优化迭代解法的一般迭代公式： 可用一维搜索技术解决 x(k+1) = x(k) + tk d(k) 关键是如何确定搜索方向d(k) 瞎子下山：由于他看不到哪里是山谷，不可能沿直接指向山谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然后在新的位置上再用手杖寻找最陡方向，再下降一步。这就是最速下降法的形象比喻。 x(k) d(k+1) =－f(x (k+1) ) ？ d(k) =－f(x (k) ) x* x(k+1) 最速下降法迭代公式 x(k+1) = x(k) －tk f(x(k) )

6 下面看一下理论推导： 设函数f(x)在xk附近连续可微，且gk=  f(xk) ≠0，由Taylor展式 可知，若记x-xk=tdk，则满足(dk)Tgk<0的方向dk是下降方向。当t取定后，(dk)Tgk的值越小，即- (dk)Tgk的值越大，函数下降的越快。由Cauchy-Schwartz不等式 当且仅当dk=-gk时， (dk)Tgk 最小，从而-gk是最速下降方向。 最速下降法的迭代格式为：

7 x(k+1) = x(k) －tk f(x(k) )
（二）算法 开始 给定x(0) , M , 1 , 2 , 令 k=0 计算f( x(k ) ) ||f( x(k ) )|| < 1 x*=x(k) 是 结束 是 否 k>M 一维搜索求tk 精度为 2 否 x(k+1) = x(k) －tk f(x(k) ) k=k+1

8 （三）最速下降法的搜索路径呈直角锯齿形 定理4.1 设从点x(k) 出发，沿方向d作精确一维搜索， tk为最优步长因子，即 f(x(k) + tk dk) = min f( x(k) + t dk) 则成立 f(x(k) + tk d) T d =0, 即新点处的梯度与搜索方向垂直。 即 t>0 d(k) f(x (k+1) ) f(x)等值面 x(k+1) d(k+1) tk x(k)

9 二维情形下最速下降法搜索路径： x(2) x(0) x(1) 由此可以看出，最速下降法仅是算法的局部性质。对于许多问题，全局看最速下降法并非“最速下降”，而是下降的较缓慢。数值试验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快，后来由于出现“锯齿”现象，下降就比较缓慢。

10 其原因就是精确一维搜索（最优步长）满足 f(x(k+1)) T dk =0， 即 f(x(k+1)) T f(x(k)) =dk+1Tdk =0， 这表明在相邻的两个迭代点上函数f(x)的两个梯度方向是互相直交的，即，两个搜索方向互相直交，这就产生了锯齿形状。当接近极小点时，步长愈小，前进愈慢。 这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。 这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路，因此反而是不好的。

11 例：问题： 为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发现了不少方法，如： (1) 选择不同初始点 取初点 为求 ， 沿
为求 ， 沿 方向从 出发求 的极小点 即进行线搜索 则 解得

12 然后再从 开始新的迭代，经过10次迭代，得最优解 计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点时，步长很小，目标函数值下降很慢。如果不取初点为 而取
虽然后一初点较前一初点离最优点 远，但迭代中不会出现上面的锯齿现象。这时： 一步就得到了极小点。

13 对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长λ的方法，称为固定步长最速下降法。只要λ充分小，总有：
可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。 （2）采用不精确的一维搜索：用一维搜索求出的步长为 时，我们不取 ，而用 的一个近似值作为 , 这样可使相邻两个迭代点处的梯度不正交，从而改变收敛性。 对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长λ的方法，称为固定步长最速下降法。只要λ充分小，总有： 但λ到底取多大，没有统一的标准， λ取小了，收敛太慢，而λ取大了，又会漏掉极小点。——不精确线搜索解决这个问题

14 （四） 收敛性分析 定理4.2 设目标函数 f (x)一阶可微，且水平集 有界，则最速下降法或者在有限步迭代后终止；或者得到点列 ，它的任何极限点都是f (x)的驻点。 证明：见文中定理4.1的证明 推论4.1 如果函数f (x)为凸函数，则应用最速下降法，或者在有限步迭代后终止；或者得到点列 的任何极限点都是全局极小点。 证明：见课本P69推论4.2 下面讨论最速下降法用于二次函数时的收敛性分析。

15 用于二次函数时的收敛性分析 定理4.3：对于二次函数 Q为对称正交， 分别为其最小最大特征值，从任意初点 出发，对此二次函数，用最速下降法产生的序列 ，对于 有 并且 由于 ，则 而函数 的极小点恰好是 。故最速下降法对于二次函数关于任意初点均收敛，而且是线性收敛的。

16 下面说明最速下降法收敛 性的几何意义。考虑具有对称正定矩阵的函数
其中 这个函数的等值线为 (c＞0) ，改写为：

17 这是以 和 为半轴的橢圆，从下面的分析可见 两个特征值的相对大小决定最速下降法的收敛性。
这是以 和 为半轴的橢圆，从下面的分析可见 两个特征值的相对大小决定最速下降法的收敛性。 （1）当 时，等值线变为圆 此时 因而由上述定理知： 即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标函数时，从任意初始点出发，只需迭代一步就到了极小点。 （2）当 时, 等值线为椭圆。此时对于一般的初始点将产生锯齿现象。

18 （3）当 ， 等值线是很扁的椭圆，此时 对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。

19 （五）优缺点 1、优点：计算简单，需记忆的容量小；对初始点要求低，稳定性高；远离极小点时收敛快，常作为其它方法的第一步。 2、缺点：收敛速度较慢（线性或不高于线性）。原因是最速下降方向只有在该点附近有意义。 最速下降方向只是局部下降最快的方向，在全局来看，下降速度是比较慢的。尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时，收敛更慢。

20 例4.1 用最速下降法求函数 f (x1, x2)＝x12+4x22 的极小点，（迭代两次），
并验证相邻两个搜索方向是正交的。初始点取为x(0)=[1,1]T 。 解：梯度 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))＝ [1,1]T － t0 [2, 8 ]T 用一维搜索求t0 ，对简单f(x)，可用解析法求解： 设0 (t)＝f ( x(1) )＝f ( [1,1]T － t[2, 8 ]T )＝(1－2t)2+4(1－8t)2 ’0(t)＝520t－68＝0 t0 ＝ x(1) =[ , － ]T

21 2. 第二次迭代： f ( x(1) )＝[ , － ]T x(2) = x(1) － t1 f (x(1)) = － t1 － t1 1(t)＝f ( x(2) )＝( － t)2+4(－ t)2 ’1(t)＝－ t t＝ t1 ＝ x(2) =[ , ]T f ( x(2) )＝[ , ]T 3. 验证相邻两个搜索方向是正交的： f (x(0))T f (x(1)) =[2, 8] [ , － ]T =  0 f (x(1))T f (x(2)) = [ , － ] [ , ]T =  0

22 建议大家对二次函数编程实践(无需集成一维搜索算法)
建议大家对一般函数结合一维搜索方法编程实践.

23 §4.2 Newton法（二阶方法） （一）基本Newton法 设函数f(x)是二次可微函数， 又设函数x(k)是f(x)的极小点的一个
？由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别好的方向，有没有更好的方向 ? （一）基本Newton法 设函数f(x)是二次可微函数， 又设函数x(k)是f(x)的极小点的一个 估计，我们把设函数f(x)在x(k)展成Taylor级数，并取二阶近似： 取 f(∆x; x(k))的平稳点作为f(x) 最优点的一个近似点 f(x)在x(k)处的 二次近似函数 令f (∆x; x(k)) = f (x(k))+ 2f (x(k))x = 0 设函数f(x)的Hesse矩阵可逆，由上式可得：

24 ! 当f(x)是单变量函数时，本方法即为一维搜索的Newton法！
x－ x(k) = x = －2f (x(k))－1f (x(k)) f(x(k)) Newton法迭代公式： x(k+1) = x(k)－2f (x(k))－1f (x(k)) 或 x(k+1) = x(k)－H(x(k))－1g(x(k)) f(x; x(k)) 这样，知道x(k)后，算出在这一点处目标函数的梯度和Hesse矩阵的逆，代入便得到后继点x(k+1) 。 －H(x(k))－1g(x(k)) x(k+1) x(k) ! 当f(x)是单变量函数时，本方法即为一维搜索的Newton法！ ! 当f(x)是二次函数时，一次迭代就可达到平稳点 ！

25 Newton法的二次终止性 设有二次凸函数 f(x)=1/2xTAx+bTx+c 其中A对称正定矩阵。 我们先用极值条件求解。令 得最优解： 下面用Newton法求解。任取初始点x(1)，根据Newton法迭代公式有： 显然， 即一步迭代达到最优解。 以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经过有限次迭代比达到极小点。这种性质称为二次终止性。

26 开始 给定x(0) ,  , 令 k=0 计算g(k) =f( x(k ) ) 是 ||g(k )|| <  x*=x(k)
基本Newton法的算法框图： 开始 给定x(0) ,  , 令 k=0 计算g(k) =f( x(k ) ) ||g(k )|| <  x*=x(k) 是 结束 否 计算 H(x(k)) p(k) =－H(x(k))－1g(k) x(k+1) = x(k) +p(k) k=k+1

27 例4.2 用基本Newton法求函数 f (x1, x2)＝8x12+4x1x2+5x22 的极小点。
初始点取为x(0)=[10, 10]T 。 解： f (x)＝[16x1+4x2, 4x1+10x2 ]T 2f (x)＝H(x)= H(x)－1 = － 4 － 1 144 x(1) = x(0)－H(x(0))－1f (x(0)) 10 = － ＝ － 4 － 1 144 200 140 因为f(x)是二次函数，所以一步迭代就达到平稳点，又因为H(x(1))是正定矩阵，所以x(1)是极小点。

28 例4.3：用Newton法求 的极小点。 解：取初点 则： 代入Newton迭代公式得： 此即为问题的最优点

29 关于Newton法的几点说明： 1、基本Newton法要求Hesse矩阵具有逆矩阵。
如果H(x(k))是正定的，则H(x(k))－1必存在，从而算法是可行的，并且保证求得 的平稳点是极小点。 然而在迭代过程中要求H(x(k))是正定的这一条件不一定能保证，只有当初始 点合适时才能满足。一般在极小点附近的Hesse矩阵容易为正定的。 所以基本Newton法在极小点附近才比较有效。 2、 Newton法的搜索方向－H (x)－1f (x)不一定是下降方向。 因为若是下降方向，则应有f (x)T[－H (x)－1f (x)]<0，即 f (x)TH (x)－1f (x)>0，但由于H (x)－1不一定是正定的，所以上式不一定成立。

30 3、Newton法的最大优点是：当初始点选得合适时收敛很快，具有二阶收敛速度，是目前讲过的算法中最快的一种，且不需一维搜索。
对初始点要求高，一般要求初始点离极小点较近，否则不收敛。有时即使是收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。 4、方向－H (x)－1f (x)称为Newton方向，是一个好方向，对二次函数此方向直指平稳点。 对于目标函数是二次函数的无约束优化问题，从任意初始点出发，利用Newton法一步迭代即可得到最优解，也就是Newton法具有二次终止性。

31 5、牛顿算法可视为椭球范数 下的最速下降算法。 事实上，欧氏空间 中一般范数 下的方向导数定义为： （它显然与范数 有关） 显然，
的最优解就是函数 在 处对应于范数 的最速下降方向。容易理解，这个解与所取的范数有关。 a) 当取欧氏范数（2范数）时，可证 是最速下降方向；

32 b) 若取椭球范数 ，最速下降方向则为 事实上， 即 ，有 （意味着 为方向导数下界）

33 另一方面，若取 时 方向导数达到下界 ，故 是对于椭球范数 下的最速下降方向。

34 6、牛顿算法实际上是非线性方程组的牛顿迭代法。
由于求解 等价于求解非线性方程组 设 是当前迭代点，若 ，则 若 是方程组的解，否则将 在 处线性化，得 将上述线性方程组的解作为 的近似解，得 故有 这恰好就是牛顿迭代公式。

35 沿Newton方向一维搜索得到的最优步长
由以上分析可知，固定的步长因子不能保证目标函数有合理的改善，甚至不能保证算法下降，因此有必要对牛顿算法作一些改进，一个最直接的改进是：在牛顿算法中加入一维搜索。 （二）修正(阻尼)Newton法 修正Newton迭代公式： x(k+1) = x(k)－ tk H(x(k))－1f (x(k)) 沿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较大时。

36 计算 H(x(k))，若可逆p(k) =－H(x(k))－1g(k);否则p(k) =－g(k);
阻尼Newton法的算法框图： 常用如下Armijo不精确搜索 开始 给定x(0) ,  , 令 k=0 计算g(k) =f( x(k ) ) ||g(k )|| <  x*=x(k) 是 结束 否 计算 H(x(k))，若可逆p(k) =－H(x(k))－1g(k);否则p(k) =－g(k); 一维搜索求tk x(k+1) = x(k) + tk p(k) k=k+1

37 阻尼Newton法的收敛性 定理4.4 设 f (x)存在连续二阶偏导数，函数的Hessian矩阵 正定, 且水平集 有界，则阻尼牛顿法或者
在有限步迭代后终止；或者得到的无穷点列 有如下性质 1） 为严格单调下降序列； 2） 有唯一极限点 ，它是 f (x)的最小点。 证明：见文P70中定理4.3的证明.

38 Newton法与最速下降法结合(1)——Marquart法
最速下降法的优点：对初始点要求不高，稳定性好；远离最优点时收敛较快。 缺点是离最优点较近时收敛很慢。 1963年Marquardt提出将最速下降法与Newton法结合，开始用最速下降法， 在接近最优点时用Newton法。 （一）方法思想 牛顿法的优缺点刚好与最速下降法相反。 在迭代公式x(k+1) = x(k) +tk p(k)中，取步长tk＝1 ，搜索方向为 p(k) ＝－[2f (x(k)) +kI]－1f (x(k)) 其中 k同时起控制搜索方向和步长的作用，I为单位矩阵 (1) 开始阶段取很大，如0=104 ， p(0) ＝－[2f (x(0)) +0I]－1f (x(0)) － f (x(0)) 1 0 最速下降法 (2) 在迭代过程中，让k0， p(k) －2f (x(k))－1f (x(k)) Newton法 具体在每一步是否缩小 k，要通过检验目标函数值来决定 ： 若f(x(k+1)) < f(x(k))，取k+1 < k ; 否则，取k+1=k, >1，重作第k步迭代。

39 p(k) =－ [2f (x(k)) +kI]－1f (x(k))
（二）算法 开始 给定x(0) , M， , 令 k=0， 0=104 计算 f( x(k ) ) || f( x(k ) ) || <  x*=x(k) 是 结束 是 否 k>M I 可推广为半正定矩阵 p(k) =－ [2f (x(k)) +kI]－1f (x(k)) 否 若[2f (x(k)) +kI]－1 不存在 x(k+1) = x(k) +p(k) f(x(k+1)) < f(x(k)) 否 k= 2k k+1= 0.5k , k=k+1 是 x(k+1) = x(k) + tkp(k)

40 1° f(x(k)+λkd(k)) ≤ f(x(k))+ δλk▽f(x(k)) Td(k)
Newton法与最速下降法结合(2)——Goldstein-Price方法(G-P法) 取 d(k)= -[▽2f(x(k)) ]-1 ▽f(x(k)) ， ▽2f(x(k)) 正定 - ▽f(x(k)) ，否则 采用下列不精确一维搜索：求λk , 满足Goldstein准则 1° f(x(k)+λkd(k)) ≤ f(x(k))+ δλk▽f(x(k)) Td(k) 2° f(x(k)+λkd(k)) ≥f(x(k))+ (1-δ) λk ▽f(x(k)) Td(k) 其中δ ∈(0,1／2) 特点：在一定条件下， G-P法全局收敛。但当▽2f(x(k)) 非正定情况较多时，收敛速度降为接近线性。

41 §4.3 共轭方向法 最速下降法，计算步骤简单，开始几步收敛较快，但往后收敛速度越来越慢；在最优解的附近，牛顿法以及修正牛顿法收敛速度快，但需要计算Hesse矩阵及其逆矩阵，计算量和存储量都很大。 因此人们希望能找到一种好的算法，它的收敛速度介于最速下降法与牛顿法之间，这种算法能够具有牛顿法收敛速度快的优点，又有最速下降法计算简单的优点，并且不需要计算Hesse矩阵的逆矩阵，对于二次函数只需有限次迭代就能达到最优解。 这就是我们要讨论的共轭方向法。 共轭梯度法就是其中一种，它是利用梯度生成共轭方向的共轭方向法。

42 下面我们先从几何上直观地介绍共轭方向，然后再给出严格的定义。
（一）共轭方向 下面我们先从几何上直观地介绍共轭方向，然后再给出严格的定义。 如图所示，AB，CD过椭圆的中心，CD平行于椭圆上在点A，B的切线，在几何上称AB与CD为共轭直径。AB与CD的方向称为共轭方向。 p1 D A p1 C B Martin和Tee提出可以利用上述椭圆的（或n维椭球）的这种共轭性质来获得较快的收敛速度。n=2时，若在椭圆上两点A，B的切线平行，则直线AB必过椭圆的中心。在点A，B的切线方向与AB的方向称为共轭方向。这种共轭关系如何表示呢？有如下定理：

43 引理4.4 设f(x)=1/2xTAx+bTx+c，AT=A>0，给定方向p1，在与p1平行的两条直线上（如图），f(x)的最小点为x1，x2，则 p1TAp2=0, （p2=x2-x1）
证：因为 g1=Ax1+b，g2=Ax2+b，则 g2-g1=A(x2-x1)， 又因为x1，x2为f(x)在此二直线上的最小点，则 p1Tg1=0，p2Tg2=0，所以 p1T(g2-g1)=0， 综上可得 p1T(g2-g1)= p1TA(x2-x1)=0 ， 所以 p1TAp2=0, （p2=x2-x1）。 注：该示意图说明沿任意p1得到极小点后，沿其共轭方向p2必找到二维问题的极小点！

44 下面给出共轭的一般定义： 定义：设A是n×n阶对称正定矩阵， （1）p(0), p(1)为两个n维向量，若成立 p(0)T A p(1) = 0 则称向量p(0)与p(1)为A共轭或A正交，称这两向量的方向为A共轭方向。 （2）若有一组向量p(0), p(1),…, p(m)，满足 p(i)T A p(j) = 0， （i≠j，i, j=1,2,…m） 则称向量组p(0), p(1),…, p(m)为A共轭（或A正交）的向量组。 若 A＝I（单位矩阵），则 p(0)T p(1) = 0，即 p(0)与p(1)是正交的。 =||p(0)||.||p(1)||cosθ “共轭”是“正交”概念的推广

45 例1：设 验证 p(0)，p(1)为 A 共轭向量。 解：因为 则 p(0) 与 p(1) 是 A 共轭的。

46 （二）共轭方向的性质——共轭方向法的基本定理
定理4.5：设A为n×n阶对称正定矩阵，p(1), p(2)，…, p(m)为m个相互A共轭 的n维非零向量（即p(i)0, i=1,2,…, m, 且p( i )T A p( j ) = 0，i j）， 则此向量组必线性无关。 推 论： 在n维空间中，互相共轭的非零向量的个数不超过n个。 引理4.6（n维直交定理）(1) 若p(0), p(1), …, p(n-1)是线性无关的n维向量组； (2) 若n维向量x和p(0), p(1), …, p(n-1) 都直交； 则 x=0。

47 命题：设A为n×n阶对称正定矩阵，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维向量 x 可表示： 定理4.6：若p(0), p(1), …, p(n-1)是n个非零的A共轭向量，则二次目标函数 f(x) = c + bTx + 1/2 xTAx的最优点 x*为 ? 上式用于非二次函数，可否得到最优点 ？ ! 可得到非二次函数最优点的一个近似点；其中A是Hesse矩阵！

48 ? 如何简便地找出n个A共轭的向量 ？ ? 对非二次函数，采用上述方法，n 次迭代是否也可得到极小点 ？ 定理4.7:
设A为n阶对称正定矩阵，对于二次目标函数 f(x) = c + bTx + 1/2 xTAx， 从任意初始点x(1)出发，逐次进行一维搜索，即 min f ( x( i )+ t p( i ) ) = f ( x( i )+ti p( i ) ) i≥0 若搜索方向p(1), p(2), …, p(n)是非零的A共轭向量，则至多进行n次迭代必可 得到极小点x* ，即有 x( i+1) =x( i ) +ti p( i ) , i =1,2,…,n x* = x( k ) , 1≤k≤n+1 上述搜索方法具有二次收敛性 ? 对非二次函数，采用上述方法，n 次迭代是否也可得到极小点 ？ ? 如何简便地找出n个A共轭的向量 ？

49 （三）Powell共轭方向法 定理: 假设 1. n元函数f(x) = c + bTx + 1/2 xTAx 中的矩阵A是对称正定的；
定理: 假设 1. n元函数f(x) = c + bTx + 1/2 xTAx 中的矩阵A是对称正定的； 2. 向量p(0), p(1), …, p(m-1) (m<n)是互相A共轭的； 3. x(0), x(1)是不同的任意两点，分别从x(0), x(1)出发，依次沿p(0), p(1), …, p(m-1) 作精确一维搜索，设最后一次一维搜索的极小点分别为x(0)*和x(1)*, 那么， 向量 p = x(0)*－x(1)*与p(0), p(1), …, p(m-1)互为A共轭。 已知前m个共轭方向， 就可以找到第m+1个共轭方向 p(1) p(0) p(1) x* x(1)* x(1) p(2) x(1) p(0) x(1)* x* x(0) p(0) x(0)* p(0) p(1) x(0)* x(0)

50 Powell共轭方向法的基本思想 任意n个线性无关的方向 表4.1 Powell共轭方向法的迭代过程 一边搜索，
阶段起点x(k, 0) n+1次一维搜索过程 新共轭方向 ………………………………………………………………………………………………………… 一边搜索， 一边找共轭方向 共分n个阶段，每一阶段都进行n+1次搜索，最后产生一个共轭方向

51 二维空间中的Powell方法示意 以二次函数f(x1 , x2 ) 为例 e(2) e(1) p(0) =e(1) p(1) =e(2)
对于二次函数, x* 即为极小点 p(0) x(1,0) x(1,1)

52 Powell方法的原始算法框图 开始 x*=x(k+1) 结束 是 给定x(0) , e(1) , e(2) ,…, e(n) 及 k=1, p( i ) = e(i+1), i=0, 1, …, n-1 j=0, x(k, j) = x( k-1 ) 否 k=k+1 满足精度 x(k, j+1) = x(k, j)+λj p( j ) 其中λj为最优步长 否 x(k) = x(k, n)+λk p(n -1) 其中λk为最优步长 j=j+1 j=n 是 p( i ) = p(i+1), i=0, 1, …, n-2

53 1、迭代中逐次产生的是共轭方向，是较好的搜索方向，所以Powell法又称 方向加速法；
几点说明 1、迭代中逐次产生的是共轭方向，是较好的搜索方向，所以Powell法又称 方向加速法； 2、原始算法仅有理论意义。 因为只有在每次搜索均为一维完全精确搜索 的条件下，每个阶段产生的方向才是相互共轭 的方向。 p(1) x(0) x(1) p(0) x(0)* x(1)* x* p’(1) 但实际一维搜索都是近似的，产生的方向不 一定共轭，有时甚至是线性相关的，导致搜 索空间降维，这时将找不到真正的极小点。 对于一般函数, n个阶段迭代后一般得不到极小点, 但由于共轭方向的个数只有n个, 如果继续按上述 方法迭代, 产生的方向就不再是相互共轭方向了, 收敛速度会变慢.

54 原始Powell算法一种简便改进 改进的Powell算法 用新方向替换掉方向 p(J)！ 详细参阅教材P.263-276
重新开始：每进行n个阶段的迭代，或当收敛速度变慢时，以当前点为起点， 回到第一步重新开始 改进的Powell算法 为克服搜索方向的线性相关问题，Powell对原始算法进行了改进。 基本思想 : 在每个阶段产生新的方向p后, 更换方向组的方法不是一律去掉第一个方向p(0), 而是有选择地去掉某个方向 p(J), 原则是使新的方向组“ 最相互共轭” ? 如何判定方向组是“最相互共轭”的 ? 用新方向替换掉方向 p(J)！ 详细参阅教材P

55 §4.4 共轭梯度法 由Powell共轭方向法可知，共轭方向是好方向，是否有比Powell共轭方向 法更简单的方法构建共轭方向？
§4.4 共轭梯度法 由Powell共轭方向法可知，共轭方向是好方向，是否有比Powell共轭方向 法更简单的方法构建共轭方向？ 共轭方向的选取有很大任意性，但高维空间构造一组共轭方向却非易事！作为迭代算法，我们自然希望共轭方向能在迭代过程中逐次生成。 下面介绍一种生成共轭方向的方法，它是利用每次一维最优化所得到的点处的梯度来生成共轭方向，这种方法称为共轭梯度法，具体做法如下： ——其实教材p.78倒数第三行开始就讨论共轭梯度法！

56 即下一个共轭方向是当前点处负梯度方向与已求得的最后一个共轭方向的线性组合。
共轭梯度法的基本思想 对f(x) = c + bTx + 1/2 xTAx，任取初始点x(0) ，取 p(0) = －f(x(0))，k=0; 然后沿着已得到的共轭方向p(k)进行一维搜索： x(k+1) = x(k) + tk p(k) 得下一个迭代点, 并构造新的方向 p(k+1) = －f(x(k＋1)) + kp(k) , k=k+1返回! 总结：构造共轭方向p(0),…,p(n-1)的方法框架是 当f(x)为二次函数时，至多经过n次迭代就可得到极小点 p(0) = －f(x(0)) p(k+1) = －f(x(k＋1)) + kp(k) 即下一个共轭方向是当前点处负梯度方向与已求得的最后一个共轭方向的线性组合。 －f(x(1)) x(0) p(0) =－f(x(0)) x(1) p(1) =－f(x(1))+ 0p(0) ! 要使得p(0),…,p(n-1)相互共轭， 显然k不能随便取 ！

57 理论基础——P79页定理4.8: 保证得到的n个方向是A-共轭的！
共轭梯度法的基本思想 任取初始点x(0) ，取 p(0) = －f(x(0))，k=0; 然后沿着已得到的共轭方向p(k)进行一维搜索： x(k+1) = x(k) + tk p(k) 得下一个迭代点, 并构造新的方向 p(k+1) = －f(x(k＋1)) + kp(k) , k=k+1返回! 理论基础——P79页定理4.8: 保证得到的n个方向是A-共轭的！ 5个等价的公式(二次目标函数时) P81页详细证明. P81 (4)前面无负号.

58 F－R共轭梯度法 以二次目标函数f(x) = c + bTx + 1/2 xTAx为模型，其中A是对称正定矩阵，从最速下降方向开始，构造一组共轭方向，经推导得： 记 g(k) =f(x(k)) F－R共轭梯度法的迭代公式： x(k+1) = x(k) + tk p(k) p(k+1) = －g(k) + kp(k) ||g(k+1)||2 k= ||g(k)||2 p(0) = －g(0)

59 几点说明： 1、“重新开始”的策略 由于共轭梯度法中各搜索方向的共轭性依赖于初始方向为负梯度方向，共轭方向只有n个，为了保证共轭方向的优越性，所以每迭代n步后，重新从一个负梯度方向开始。 原因同Powell共轭梯度法（误差、共轭梯度的个数） 2、何时执行重新开始步骤？ 一轮完成之后重新开始

60 对于凸二次函数，为了避免计算原问题二阶海赛矩阵，减少计算量，利用前面所得的公式，可以得到几个等价的计算公式：
——Daniel(1967) ——Polyak-Polak-Ribiere(1969) ——Myers(1972) ——Flecher-Reeves(1964) ——Sorenson-wolfe(1972)

61 F－R法的算法框图 给定x(0) ,  g(0) =f( x(0 ) ) ||g(0)|| <  x*=x(0) 是 否
开始 给定x(0) ,  g(0) =f( x(0 ) ) ||g(0)|| <  x*=x(0) 是 结束 否 k=0， p(0)=－g(0) x(0)=x(k+1) g(0)=g(k+1) 是 x(k+1) = x(k) + tk p(k), g(k+1) =f(x(k+1 )) 其中tk为最优步长 p(k+1) = －g(k) + kp(k) k=k+1 ||g(k+1 )|| <  x*=x(k+1) 是 结束 k = n 否 否 ak = ||g(k+1)||2 / ||g(k )||2

62 f (x(1))= f (x(0)＋t p(0))= f (x)|x=[10t, 4t]T = 60－116t+76t2
例4.2 用F－R共轭梯度法解 min f (x)＝60－10x1 －4x2 +x12 +x22 －x1x2 初始点取为x(0)=[0, 0]T 。 解：f (x)＝[－10＋2x1－x2, －4＋2x2－x1 ]T p(0)＝ －g(0) ＝－ f (x (0))＝[10, 4]T 进行一维搜索，对简单f(x)，可用解析法求解： f (x(1))= f (x(0)＋t p(0))= f (x)|x=[10t, 4t]T = 60－116t+76t2 f ’(t)＝152t－116＝0 t0 ＝ x(1) = x(0) + t0 p(0) =[ , ]T g(1) ＝f (x (1))＝[ , － ]T a0= ||g(1)||2 / ||g(0 )||2 = / 116 p(1) = －g(1) + 0p(0) =[ , ]T 再用解析法求最优步长 t1 得 t1 ＝ x(2) = x(1) + t1 p(1) =[ , ]T g(2) ＝f (x (2))＝[0, 0]T 所以，x* = [8, 6]T f * = 8

63 共轭梯度法评注 1、共轭梯度法的优点是不必计算Hesse矩阵及其逆矩阵，程序简单，对大规模问题很有吸引力。对凸二次函数最多n步终止，而对一般函数为超线性收敛。 2、收敛速度依赖于一维搜索的精确性及Hesse矩阵的特征值的分布。

64 2. 凡用到矩阵A的地方， 需要用现行点处的海赛矩阵▽2f (x(k))
对一般函数的共轭梯度法注意问题 把前面的共轭梯度法推广到对于一般函数的共轭梯度法，需要注意的几点: 1. 步长 λk 不能够用前面的公式计算, 用其他的一维搜索方法来确定。 2. 凡用到矩阵A的地方， 需要用现行点处的海赛矩阵▽2f (x(k)) 3. 用这种方法求任意函数的极小点，一般来说，有限步迭代是达不到的。所以需要采取一些策略。 4. 一种方法是直接延续，一直利用我们的方法做下去，即到了n步仍然不停止，直到满足了停止条件。

65 5. 另一种方法是把n步作为一轮，每搜索一轮后，取一次最速下降方向，开始下一轮。这种策略称为“重新开始”或“重置”。 ——更常用
由于共轭梯度法中各个搜索方向的共轭性依赖于初始方向为负梯度方向，共轭方向只有n个，为了保持共轭方向性，所以每次迭代n步后，重新从一个负梯度方向开始。另外由于每次计算的λk 和βk不精确，所以有积累误差，它影响到算法的收敛性，通常为了避免积累误差，所以重新开始整个算法。 6. 对于一般函数时，前面的几种共轭梯度法计算βk得到的搜索方向是不同的，所以不是等价的。经验证对于二次凸规划，一般用FR方法，对于一般函数利用PPR方法。

66 有界，则由共轭梯度法得到的点列 有如下性质
7. 利用非精确一维搜索方法 （1）得到的方法有可能不是下降方法，当不是下降方向的时候，用最速下降方向重新开始。但是这样的重新开始可能使大量的，因此会降低计算效率。 （2）利用一个下降的原则去控制。 算法的收敛性分析: 定理4.10 设 f (x)存在连续一阶偏导数，且函数为凸函数，且水平集 有界，则由共轭梯度法得到的点列 有如下性质 1） 为严格单调下降序列，且 存在； 2） 的任意极限点 都是 f (x)的最优解。 证明：见文中P.85定理 4. 10的证明

67 §4.5 拟Newton法（变尺度法） Newton法的最大优点是靠近极小点时收敛速度快，主要缺点是要计算Hesse矩阵及其逆矩阵，计算量大. ? 有没有可能既保持Newton法快速的优点，又不计算Hesse矩阵及其逆矩阵 ? 1959年Davidon提出变尺度法，1963年经Fletcher和Powell改进，形成DFP法; 1970年Broyden等人提出更稳定的BFGS变尺度法。它被认为是无约束优化问题中最有效的方法之一。 思想： 牛顿方向：p(k) =－  2f(x(k)) -1g(k) 近似为 p(k) =－ H(k) g(k) 优点： H(k)称为尺度矩阵，且迭代过程中H(k)是变化的，该算法为变尺度法; 只要H(k)正定，方向必是下降方向; 若变化H(k)不断近似于 2f(x(k)) -1，则算法可以保持牛顿法的快速收敛的优势！

68 N y Hk+1=Hk+ΔHk 算法框图： x(1), H1对称 ε>0, k=1 k=k+1 d(k)=-Hk gk 一维搜索得λk
x(k+1)=x(k)+ λkdk ||x(k+1)-x(k)||< ε? Hk+1=Hk+ΔHk Stop. x(k+1)----解 k=k+1 y N

69 尺度矩阵H(k) 既近似2f(xk)－1 ，计算又要方便！
从形式上模仿，造一个方向： 尺度矩阵H(k) 既近似2f(xk)－1 ，计算又要方便！ p(k) =－Hk f(x(k)) H(k)应满足的条件： 记： Δg(k) = g(k+1)－g(k) , Δx(k) = x(k+1)－x(k) (1) 满足拟Newton条件：Δxk = Hk+1Δgk (2) H(k)为正定矩阵，这样p(k)为下降方向； (3) 由H(k)出发计算H(k+1)应简便: H(k+1)＝H(k)＋ΔH(k) 校正矩阵 (4) 算法具有二次收敛性： H(n+1)= 2f(x*)－1 .

70 DFP算法： Davidon(1959), Fletcher and Powell (1963)， 令
Δ Hk=αk u(k) (u(k))T+ βk v (k) (v (k))T αk, βk 是常数，u(k) , v (k)是n维列向量。这样定义的ΔHk是秩为2的对称矩阵, 所以称为秩2校正。 令 u(k)= Δxk , v (k)= Hk Δgk , 则由拟牛顿条件有

71 DFP算法： 1、上述算法具有三个性质： (1) 校正公式的分母总大于零, 校正公式总有意义； (2) H(k)都是正定的，所以每次迭代方向都是下降方向； (3) 对二次函数 f(x) = c+bTx+0.5xTAx (A为正定矩阵)，迭代得到的搜索方向 p(0), p(1) ,…, p(n－1)相互 A共轭，所以DFP是一种共轭方向法；且 H(n) = A－1 ，说明H(k) 逐次逼近A－1 .

72 2、DFP法的重新开始策略 由于计算的舍入误差及一维搜索精度不够，会破坏H(k)的正定性，导致算法失效。
（1）一维搜索后，如果 f(x(k+1)) f(x(k))，意味着 p(k) 不是下降方向， H(k)不是正 定矩阵，则重新开始，重置H(k) = I； （2）每迭代n+1次后重新开始，令x(0) = x(n+1) , H(0) = I

73 p(k+1) = －H(k+1) g(k+1) k=k+1 y(k) = g(k+1)－g(k) s(k) = x(k+1)－x(k)
3、DFP法的算法 开始 给定x(0) ,  f0 =f( x(0 ) ) , g(0) =f( x(0 ) ) H(0)= I， p(0)=－g(0) , k=0 x(0)=x(k+1) f0 = fk+1 g(0)=g(k+1) 是 x(k+1) = x(k) + tk p(k), 其中tk为最优步长fk+1 =f(x(k+1 )), g(k+1) =f(x(k+1 )) p(k+1) = －H(k+1) g(k+1) k=k+1 ||g(k+1 )|| <  x*=x(k+1) 是 结束 fk+1  fk 否 k = n 否 是 否 y(k) = g(k+1)－g(k) s(k) = x(k+1)－x(k) H(k+1)＝H(k)＋ － s(k) s(k)T s(k)T y(k) H(k) y(k)Ty(k)T H(k) y(k)T H(k) y(k)

74 定理4.12：若 , 则DFP方法构造的矩阵Hi (i=1,2,…,n)为对称正定矩阵。
证明：数学归纳法（Schwartz不等式，正定矩阵的性质，精确一维搜索的结果。） 参见课本P92的证明 注：搜索方向d k = - Hk gk一定是下降方向。

75 证明参见P93-P96页 若目标函数是正定二次函数，则DFP算法经过有限步迭代必达到极小点，即具有二次收敛性。
其中Q为n阶对称正定矩阵。由DFP方法产生的搜索方向为 ，产生的矩阵为 ，则有如下结论成立。 (1) (2) (3) (4) 证明参见P93-P96页

76 定理4.15 设 f (x)存在连续一阶偏导数，且函数为凸函数，且水平集 有界，则由DFP法得到的点列 有如下性质
2. 若H1是单位向量，则 所以DFP方法也是一种共轭梯度法。 定理4.15 设 f (x)存在连续一阶偏导数，且函数为凸函数，且水平集 有界，则由DFP法得到的点列 有如下性质 1） 为严格单调下降序列，且 存在； 2） 的任意极限点 都是 f (x)的最优解，且有: 证明：参见P96的证明

77 BFGS方法——应用最普遍的方法(一般函数)
由前面的推导，我们知道 为了利用不包含二阶导数的矩阵Hk+1取代▽2f(x(k))， 令 Bk+1满足 该公式称为另一种拟牛顿条件。 由于上面的公式只需要交换 就可以得到前面的拟牛顿条件。因此只需要在Hk的递推公式中互换 ，并用Bk+1 , Bk 分别取代Hk+1 , Hk，就

78 就得到Bk的递推公式，所以关于Bk的修正公式为
该公式称为关于矩阵B的BFGS修正公式，有时也称为DFP的对偶公式。 设Bk+1可逆，则有 所以 满足拟牛顿条件 令

79 对Bk+1两边求拟，得到 这个重要公式是由Broyden,Fletcher,Goldfard 和Shanno于1970年提出来的。它可以象DFP公式一样使用，数值计算实例表明，它比DFP要好，目前得到广泛的应用。 BFGS法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用前文中介绍的不精确一维搜索有全局收敛性。

80 小 结 x(k+1) = x(k) + tk p(k) 多变量最优化迭代解法的一般迭代公式 最优步长 可用一维搜索技术解决 不同的搜索方向p(k), 构成不同的算法 算法名称 搜索方向p(k) Powell共轭方向法 共轭方向 最速下降法 p(k) =－f(x (k) ) Newton法 p(k) = －2f (x(k))－1f (x(k)) Marquart法 p(k) ＝－[2f (x(k)) +kI]－1f (x(k)) F-R共轭梯度法 p(0) = －f(x(0)) p(k+1) = －f(x(k＋1)) + kp(k) DFP，BFGS法 （拟Newton法） p(0) = －f(x(0)) p(k+1) = － H(k) f(x(k))

81 方法的比较与选择 1、间接法：对简单问题，求解必要条件或充分条件； 2、迭代算法： 零阶法：只需计算函数值 f(x) 直接法
梯度法 Newton法 从收敛速度考虑：梯度法快于直接法 拟Newton法 (变尺度法) 共轭梯度法 Powell共轭方向法 单纯形法 最速下降法

82 作业：P99 ch , , , 4.24,4.26