第三章梯度法和共轭梯度法课件.ppt

1、梯度法和共轭梯度法梯度法和共轭梯度法1.无约束最优化问题无约束最优化问题2.梯度法梯度法3.共轭方向法共轭方向法4.共轭梯度法共轭梯度法一一.无约束最优化问题无约束最优化问题无约束最优化问题无约束最优化问题min f(x)s.t.x?Rn其中其中f(x)有一阶连续偏导数。有一阶连续偏导数。解析法解析法：利用函数的解析性质构造迭代公式。：利用函数的解析性质构造迭代公式。二二.梯度法（最速下降法）梯度法（最速下降法）迭代公式：迭代公式：xk?1?x?kdkk如何选择下降最快的方向？如何选择下降最快的方向？?f(xk)函数值增加最快的方向函数值增加最快的方向xk函数值下降的方向函数值下降的方向?f(

2、xk)函数值下降最快的方向函数值下降最快的方向梯度法（最速下降法）：梯度法（最速下降法）：1.搜索方向：搜索方向：d?f(x),也称为最速下降方向；也称为最速下降方向；kkkkkk2.搜索步长搜索步长:?k取最优步长取最优步长,即满足即满足 f(x?kd)?min f(x?d)。?梯度法算法步骤：梯度法算法步骤：1.给定初始点给定初始点 x?R,允许误差允许误差?0,令令k?1。2.计算搜索方向计算搜索方向d?f(x);3.若若|d|?,则停止计算，则停止计算，x为所求极值点；为所求极值点；否则，求最优步长否则，求最优步长?k使得使得 f(x?kd)?min f(x?d)。?kkkk1nkkk

3、k4.令令 xk?1?x?kd,令令k:?k?1,转转2。kk例例.用最速下降法求解用最速下降法求解:min f(x)?x?3x,设初始点为设初始点为x?(2,1),21221T求迭代一次后的迭代点求迭代一次后的迭代点x2。解：解：?f(x)?(2x1,6x2),?d?f(x)?(?4,?6).?x?d?(2?4?,1?6?).令令?(?)?f(x?d)?(2?4?)?3(1?6?)，112211T11TT求解求解min?(?)?13令令?(?)?8(2?4?)?36(1?6?)?0?1?6236?8T211?x?x?1d?(,)31 31收敛性收敛性性质性质.设设 f(x)有一阶连续偏导数，

4、若有一阶连续偏导数，若 步长步长?k满足满足f(x?kd)?min f(x?d)?kkkk则有则有?f(x?kd)d?0。kk令令?(?)?f(x?d)，所以所以证明：证明：kk Tk?(?)?f(xk?dk)Tdk.?f(xk?kdk)?min f(xk?dk)?kk Tk?(?k)?f(x?kd)d?0.注：注：因为梯度法的搜索方向因为梯度法的搜索方向dk?1?f(x?kd)，所以所以kk(dk?1)Tdk?0?dk?1?dk。锯齿现象锯齿现象在极小点附近，目标函在极小点附近，目标函 数可以用二次函数近似数可以用二次函数近似，其等值面近似，其等值面近似椭球面。椭球面。x2x3?x*x1注注

5、最速下降方向反映了目最速下降方向反映了目 标函数的一种局部性质标函数的一种局部性质。它只是它只是局部目标函数值下降最局部目标函数值下降最 快的方向。快的方向。最速下降法是线性收敛最速下降法是线性收敛 的算法。的算法。三、共轭方向法三、共轭方向法1.何谓共轭方向？何谓共轭方向？几何解释几何解释1T设有二次函数设有二次函数f(x)?(x?x)A(x?x)2其中其中A是是n?n对称正定矩阵，对称正定矩阵，x是一个定点。是一个定点。则函数则函数f(x)的等值面的等值面1(x?x)TA(x?x)?c2x是以是以x为中心的椭球面。为中心的椭球面。由于由于?f(x)?A(x?x)?0,而而?f(x)?A,2

6、21f(x)?(x?x)TA(x?x)2因为因为A正定，正定，所以所以?f(x)?A?0,因此因此x是是f(x)的极小点。的极小点。x设设 xdx(1)(0)是在某个等值面上的一是在某个等值面上的一点，点，nx(0)是是 R 中的一个方向，中的一个方向，(1)d(1)(0)沿着沿着 d以最优步长以最优步长搜索得到点搜索得到点x(1)。xd(2)x(1)x1o则则d(1)是点是点 x(1)所在等值面的切向量。所在等值面的切向量。该等值面在点该等值面在点x(1)处的法向量为处的法向量为?f(x1)?f(x(1)?A(x(1)?x).xd(1)d(2)则则 d(1)与与?f(x(1)正交，正交，x(

7、1)x1即即d(1)T(2)?f(x(1)?0。o?f(x1)令令d所以所以?x?x,d(1)TAd(2)?0。(1)即等值面上一点处的切即等值面上一点处的切向量与由这一点向量与由这一点指向极指向极 小点的向量关于小点的向量关于 A共轭。共轭。2.共轭方向共轭方向n12定义定义设设 A是是 n?n的对称正定矩阵，对于的对称正定矩阵，对于 R 中的两个非零向量中的两个非零向量 d 和和d，若有若有1d21TAd2?0，则称，则称d1和和d2关于关于A共轭。共轭。kn设设 d,d,?,d 是是 R 中一组非零向量，如果中一组非零向量，如果 它们两两关于它们两两关于 A共轭，即共轭，即diTAd?0

8、,i?j,i,j?1,2,?,k。j则称这组方向是关于则称这组方向是关于A共轭的，也称它们是一共轭的，也称它们是一 组组A共轭方向。共轭方向。注：注：如果如果A是单位矩阵，则是单位矩阵，则d1T?I?d?0?d21T?d?02?d1?d2共轭是正交的推广。共轭是正交的推广。12k设设A是是n阶对称正定矩阵，阶对称正定矩阵，d,d,?,d是是k个个A共轭的非零共轭的非零定理定理1.向量，则这个向量组线向量，则这个向量组线性无关。性无关。证明证明设存在实数设存在实数?1,?2,?,?k，使得，使得i?1?id?0,jTiki上式两边同时左乘上式两边同时左乘di?1kA，则有，则有?idjTkjTA

9、d?0,因为因为d1,d2,?,d是是k个个A共轭的向量，所以上式共轭的向量，所以上式可化简为可化简为?jdjAdj?0.jT因为因为 d?0,而而 A是正定矩阵，所以是正定矩阵，所以 d所以所以12Ad?0，j?j?0,j?1,2,?,k。k因此因此 d,d,?,d 线性无关。线性无关。1T定理定理 2.设有函数设有函数f(x)?x Ax?bTx?c，2(1)(2)(k)其中其中A是是n阶对称正定矩阵。阶对称正定矩阵。d,d,?,d是是一组一组A共轭向量。共轭向量。以任意的以任意的 x得到点得到点 x(2)(1)?R 为初始点，依次沿为初始点，依次沿 d(3)n(1),d(2),?,d(1)

10、(k)进行搜索，进行搜索，,x,?,x(k?1),则则x(k?1)是函数是函数 f(x)在在 x?Bk上的上的极小点，其中极小点，其中(1)(2)Bk?x|x?id(i),?i?Ri?1(k)k是由是由 d,dn,?,d生成的子空间。特别地生成的子空间。特别地，当当k?n时，时，x(n?1)是是f(x)在在R 上的唯一极小点。上的唯一极小点。推论推论在上述定理条件下，必在上述定理条件下，必有有?f(x(k?1)T)d(i)?0,i?1,2,?,k。3、共轭方向法对于极小化问题对于极小化问题1TTminf(x)?x Ax?b x?c,2其中其中A是正定矩阵，称下述算是正定矩阵，称下述算 法为共轭

11、方向法法为共轭方向法:(1)取定一组取定一组 A共轭方向共轭方向 d(1),d(2),?,d(n)；(2)任取初始点任取初始点x(1),依次按照下式由依次按照下式由x(k)确定点确定点x(k?1),(k?1)(k)(k)?x?x?dk?f(x(k)?d(k)?minf(x(k)?d(k)k?直到某个直到某个 x(k)满足满足?f(x(k)?0。注注由定理由定理2可知，利用共轭方向法可知，利用共轭方向法 求解上述极小化问题，求解上述极小化问题，至多经过至多经过n次迭代必可得到最优解次迭代必可得到最优解。如何选取一组共轭方向？如何选取一组共轭方向？四四.共轭梯度法共轭梯度法：?二次函数情形二次函数

12、情形?非二次函数情形非二次函数情形1 1、二次函数情形二次函数情形Fletcher?Reeves共轭梯度法共轭梯度法:1TTminf(x)?x Ax?b x?c2nn其中其中x?R,A是对称正定矩阵，是对称正定矩阵，b?R，c是常数。是常数。基本思想：基本思想：将共轭性和最速下降方将共轭性和最速下降方向相结合，利用已知迭向相结合，利用已知迭代点代点处的梯度方向构造一组处的梯度方向构造一组 共轭方向，并沿此方向共轭方向，并沿此方向 进行搜索，求出进行搜索，求出函数的极小点。函数的极小点。以下分析算法的具体步骤。以下分析算法的具体步骤。(1)任取初始点任取初始点 x，第一个搜索方向取为，第一个搜索

13、方向取为d(1)(1)?f(x(1)；(2)设已求得点设已求得点 x(k?1)，若若?f(x(k?1)?0，令令 gk?1?f(x(k?1)，则下一个搜索方向则下一个搜索方向d(k?1)按如下方式确定按如下方式确定:令令d(k?1)?gk?1?kd(k)(1)如何确定如何确定?k？要求要求d(k?1)和和d(k)关于关于A共轭。共轭。(k)T则在（则在（1）式两边同时左乘）式两边同时左乘d0?d(k)TA，得，得Ad(k)Ad(k?1)?d(k)TAgk?1?kd(k)T解得解得?k?dd(k)T(k)TAgk?1Ad(k)(2)(3)搜索步长的确定搜索步长的确定:已知迭代点已知迭代点 x(k

14、)和搜索方向和搜索方向 d(k),利用一维搜索确定最优利用一维搜索确定最优 步长步长?k，即求解即求解min?f(x(k)(k)?d(k)(k)。记记令令即有即有?(?)?f(x?d),(k)(k)T(k)?(?)?f(x?d)d?0，A(x(k)?d(k)?bTd(k)?0，令令gk?f(x(k)?Ax(k)?b，则有，则有gk?Ad(k)Td(k)?0，解得解得?k?dT(k)gkd(k)T(k)(3)Ad1TFR算法在算法在m?n次次定理定理3对于正定二次函数对于正定二次函数f(x)?x Ax?bTx?c，2一维搜索后即终止，并一维搜索后即终止，并 且对所有的且对所有的（i 1?i?m）

15、，下列关系成立），下列关系成立(1)d(i)TAd(j)?0,j?1,2,?,i?1;(2)giTgj?0,j?1,2,?,i?1;(3)T(i)gid?T?gigi。注注（1）由定理）由定理 3可知搜索方向可知搜索方向d(1),d(2),?,d(m)是是A共轭的。共轭的。(2)算法中第一个搜索方向算法中第一个搜索方向 必须取负梯度方向，否必须取负梯度方向，否 则构造的搜索则构造的搜索方向不能保证共轭性。方向不能保证共轭性。(3)由定理由定理3的（的（3）可知，）可知，T(i)gid?T?gigi?|gi|?0,2所以所以d是迭代点是迭代点 x(i)(i)处的下降方向。处的下降方向。(4)由定

16、理由定理 3，FR算法中算法中?i的计算公式可以简化。的计算公式可以简化。?i?d(i)T(i)TAgi?1Ad(i)d?gi?1TAd(i)d(i)TAd(i)Tgi?1(i)TA(x(i?1)?x(i)/?iA(x(i?1)?x(i)/?i(i)d?gi?f(x)?Ax(i)?b.?i?Tgi?1(i)T(gi?1?gi)(gi?1?gi)22?|gi?1|?d(i)T2dgi?|gi?1|gi|(4)FR算法步骤：算法步骤：1.任取初始点任取初始点 x(1)，精度要求精度要求?，令，令k?1。2.令令g1?f(x(1),若若|g1|?,停止，停止，x(1)为所求极小点；为所求极小点；否则

17、，令否则，令d(1)?g1,利用公式（利用公式（3）计算）计算?1，令令x(2)?x(1)?1d(1)。3.令令gk?1?f(x(k?1),若若|gk?1|?,停止，停止，x(k?1)为所求极小点；为所求极小点；否则，令否则，令d(k?1)?gk?1?kd(k),其中其中?k用公式（用公式（4）计算。）计算。令令k:?k?1。4.利用公式（利用公式（3）计算）计算?k，令，令 x(k?1)?x(k)?kd(k),转转3。例例 用用FR算法求解下述问题：算法求解下述问题：min22f(x)?2x1?x2初始点取为初始点取为 x(1)?(2,2)T。解：解：?40?40?x1?1.f(x)?(x1

18、,x2)?,?A?2?02?02?x2?T?f(x)?(4x1,2x2).第第1次迭代：次迭代：(1)T令令d?g1?(?8,?4),T(1)g1d而而?1?8?(8,4)?4?40?8?(?8,?4)?02?4?d(1)TAd(1)5?18所以所以x(2)?x(1)?1d(1)5?2 8TT?(2,2)?(?8,?4)?(,)1899T第第2次迭代：次迭代：?8 16T?g2?(,).99?82162|g2|2(9)?(9)4?1?.22281|g1|8?4?d(2)?g2?1d(1)8?16T4?(,)?(?8,?4)T998140T?(1,?4)81?2?dT(2)g2d(2)T(2)A

19、d40?8 16?1?(,)?8199?4?9?20?40?1?402()(1,?4)?4?8102?x(3)?x(2)?2d(2)?2 8T940?(,)?(1,?4)T992081?(0,0)?g3?(0,0)(3)TT?x即为所求极小点。即为所求极小点。2.用于一般函数的共轭梯度法mins.t.f(x)x?Rn对用于正定二次函数的对用于正定二次函数的共轭梯度法进行修改：共轭梯度法进行修改：(1)第一个搜索方向仍取最第一个搜索方向仍取最速下降方向，即速下降方向，即 d(1)?f(x(1)。其它搜索方向按下式计其它搜索方向按下式计 算：算：d(i?1)?f(x(i?1)?id(i),其中其中

20、?i?|?f(x(i?1)|2|?f(x(i)|2。(2)搜索步长搜索步长?i不能利用公式（不能利用公式（3）计算，需由一维搜索）计算，需由一维搜索 确定。确定。(3)算法在有限步迭代后不算法在有限步迭代后不一定能满足停止条件，一定能满足停止条件，此时可采取此时可采取如下措施：如下措施：以以n次迭代为一轮，每次完次迭代为一轮，每次完 成一轮搜索后，如果还成一轮搜索后，如果还 没有求没有求得极小点，则以上一轮得极小点，则以上一轮 的最后一个迭代点作为的最后一个迭代点作为 新的初始点，新的初始点，取最速下降方向作为第取最速下降方向作为第 一个搜索方向，开始下一个搜索方向，开始下 一轮搜索。一轮搜索

21、。注注在共轭梯度法中，计算在共轭梯度法中，计算?i可采用不同形式的公式可采用不同形式的公式，如，如?i?gTi?1Tigi?1ggiFletcherandReeves(FR)共扼梯度法共扼梯度法,1964年年giT?1(gi?1?gi)?i?Polak,RibiereandPolyar(PRP)共轭梯度法共轭梯度法,1969年年Tgigi?i?gdTi?1(i)Tgi?1gi?1DixonandMyers(DY)共扼梯度法共扼梯度法,1972年年?i?gdTi?1(i)T(gi?1?gi)(gi?1?gi)?Sorenson andWolfe(SW)共扼梯度法共扼梯度法?i?d(i)T?2f(xi?1)gi?1?2f(xi?1)d(i)d(i)T?Daniel共扼梯度法共扼梯度法