第五章无约束问题算法（III）.ppt

第五章 无约束问题算法（III） ——共轭梯度法 共轭方向法的思路 对于简单的二次函数 共轭方向法的思路 共轭方向法的思路 共轭方向法的思路 在三维情况下,上面的迭代过程可以用图形来表示. 共轭方向法的思路 上面的方法对一般的二次函数是否适用呢? 考虑问题 共轭方向法的思路 在空间Rn上,重新定义内积与范数: 共轭方向法的思路 在Rn上,按照上面定义的内积给出一组正交基p1,p2,···,pn, 共轭方向法的思路 共轭方向法的思路 共轭方向法的思路 定义 设n维向量组p1,···,pk线性无关, x(0)∈Rn, 称向量集合 为由点x(0)与 p1,p2,···,pk 生成的k维超平面. 超平面上极小点的判断 若函数f(x)连续可微, p1,p2,···,pk为一组线性无关的n维向量, x(0)∈Rn, 超平面上极小点的判断 超平面上极小点的判断 反之,若 超平面上极小点的判断 引理 设f (x)为连续可微的严格凸函数,又 p1,p2,···,pk为一组线性 无关的n维向量, x1∈Rn ,则 是f(x)在x1与p1,p2,···,pk所生成的k维超平面Hk上唯一极小点的充 分必要条件是 共轭方向法(用于二次函数) 已知k个点与k个方向之后,令xk+1=xk+ak pk,进行精确一维有哪些信誉好的足球投注网站,确定xk+1,再确定pk+1. 共轭向量 共轭方向法(用于二次函数) 注:在前面讨论思路时,根据方向的共轭性(正交性)得到xk+1是目标函数在k维超平面上的极小点(后面的定理将给出严格证明). 根据上一页的推导,根据极小点可以推出共轭性(正交性),即若一种迭代方法每次求出的是二次函数在k维超平面上的极小点,则对应的方向是共轭的. 基本概念 二次终止性 如果一个算法经过有限次迭代就得到正定二次函数的极小点,称该算法具有二次终止性. 共轭方向法 是一种迭代方法,每次所取方向与前面的方向关于G共轭,然后进行精确一维有哪些信誉好的足球投注网站确定步长及下一步的迭代点. 共轭方向的性质 定理 设G为n阶正定矩阵,非零向量组 p1,p2,···,pk关于G共轭,则此向量组线性无关. 共轭方向的性质 共轭方向法(用于二次函数) 定理 设G是n阶正定阵,向量组p1,p2,···,pk关于G共轭,对正定二次函数f(x)=xTGx/2+bTx+c 由任意初始点x1开始,依次进行k次一维有哪些信誉好的足球投注网站,xi+1=xi+aipi(i=1,2,···,k) 则(i)gTk+1pi=0 (i=1,2,···,k). (ii)xk+1是二次函数在k维超平面Hk上的极小点. 推论 当k =n时,xn+1为二次函数在Rn上的极小点. 共轭方向法(用于二次函数) 证明要点:只要证明gTk+1pi=0. 共轭梯度法(共轭方向的形成) 共轭梯度法(共轭方向的形成) 共轭梯度法(共轭方向的形成) 再根据二次函数的性质,有 共轭梯度法(共轭方向的形成) 共轭梯度法(用于二次函数) FR算法 (2)Polak-Ribiere-Polyak公式 共轭梯度法算例 例 用FR共轭梯度法求解(x0=(0,0)T) 从x1出发,沿p1作一维有哪些信誉好的足球投注网站,求 共轭梯度法算例 共轭梯度法算例 FR方法计算结果 从最后两组数据可以看出,虽然函数值下降,但是迭代点离最优点的距离却有所增加. 对于PRP算法,计算过程类似. 计算15步收敛, x*≈(1,1)T 对于此例,PRP方法比FR方法收敛快. 计算结果见下表. PRP方法计算结果 重新开始的共轭梯度法（补充） 对于FR算法和PRP算法,如果初始方向不取负梯度方向,即使对于二次函数,也不能产生n个共轭方向. 因此,在用这两个方法时,如果迭代到距离最优点比较近,函数接近与一个二次函数时,我们重新取有哪些信誉好的足球投注网站方向为负梯度方向. 一般在实际应用中迭代n步或n+1步时重新设定有哪些信誉好的足球投注网站方向为负梯度方向. 重新开始的共轭梯度法 对于前面的例子,采用重新开始的共轭梯度法得到的收敛步数为: FR算法: 迭代n步重新开始,49步收敛 迭代n+1步重新开始,31步收敛 PRP算法: 迭代n步重新开始,27步收敛 迭代n+1步重新开始,13步收敛 由于此处n比较小,改善并不明显. 由g0=(-2,0)T≠0,故取p0=(2,0)T,从x0出发,沿p0作一维有哪些信誉好的足球投注网站, 即求min f (x0+a p0)=6a 2-4a 的极小点, 得a0 =1/3 ,于是x1=x0+a 0 p0=(2/3,0)T,g1=(0,-2/3)T, 由FR公式得b0=g1Tg1/g0Tg0=1/9 故p1=-g1+b0p0=(2/9,2/3)T. 解 注:此处不需求G. 解得a1=3