共轭方向法精品课件

1、共轭方向法第1页，共76页，2022年，5月20日，7点11分，星期一算法特点（）建立在二次模型上，具有二次终止性（）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点（）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法第2页，共76页，2022年，5月20日，7点11分，星期一共轭方向及其性质定义:设是中任一组非零向量，如果：则称是关于共轭的注：若则是正交的，因此共轭是正交的推广第3页，共76页，2022年，5月20日，7点11分，星期一定理:设为阶正定阵，非零向量组关于共轭，则必线性无关推论:设为阶正定阵，非零向量组关于共轭，则向量构成的一组

2、基推论:设为阶正定阵，非零向量组关于共轭，若向量与关于共轭，则第4页，共76页，2022年，5月20日，7点11分，星期一共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代Step3:计算使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.具有二次终止性，但是它仅是一个概念性算法，实现它的关键在于如何选取共轭方向，不同的选取会产生不同的共轭方向法.第5页，共76页，2022年，5月20日，7点11分，星期一共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生成的维超平面第6页，共76页，2022年，5月20日，7点11分，星期一引理1:设是连续

3、可微的严格凸函数，维向量组线性无关，则：是在上唯一极小点的充要条件是：第7页，共76页，2022年，5月20日，7点11分，星期一证：构造：分析：是(1)维严格凸函数(2)是在上的极小点的充要条件是是在上的极小点第8页，共76页，2022年，5月20日，7点11分，星期一定理2:设为阶正定阵，向量组关于共轭，对正定二次函数由任意开始，依次进行次精确线搜索：则：（）（）是在上的极小点推论:当时，为正定二次函数在上的极小点第9页，共76页，2022年，5月20日，7点11分，星期一共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：第10页，共76页，2022年，5月20日，7点

4、11分，星期一共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）第11页，共76页，2022年，5月20日，7点11分，星期一系数的其他形式（）FR公式（1964）（2）PRP公式（1969）第12页，共76页，2022年，5月20日，7点11分，星期一FR共轭梯度法算法Step1:给出Step2:计算如果停Step3:Step4:由精确线搜索求Step5:转Step2.第13页，共76页，2022年，5月20日，7点11分，星期一例4：用FR共轭梯度法求解：解：化成形式(1)第14页，共76页，2022年，5

5、月20日，7点11分，星期一(2)第15页，共76页，2022年，5月20日，7点11分，星期一第16页，共76页，2022年，5月20日，7点11分，星期一例5：用FR共轭梯度法求解：解：化成形式(1)第17页，共76页，2022年，5月20日，7点11分，星期一(2)第18页，共76页，2022年，5月20日，7点11分，星期一FR共轭梯度法收敛定理定理4:假定在有界水平集上连续可微，且有下界，那么采用精确线搜索下的FR共轭梯度法产生的点列至少有一个聚点是驻点，即：(1)当是有穷点列时，其最后一个点是的驻点(2)当是无穷点列时，它必有聚点，且任一聚点都是的驻点第19页，共76页，2022年

6、，5月20日，7点11分，星期一再开始FR共轭梯度法算法Step1:给出Step2:计算如果停，Step4:否则Step3:由精确线搜索求并令：计算若令转Step2;如果停.第20页，共76页，2022年，5月20日，7点11分，星期一Step5:若令转step2.Step6:计算Step7:如果令转step2,否则转step3.第21页，共76页，2022年，5月20日，7点11分，星期一作业：FR共轭梯度法（上机）上机实现FR共轭梯度法并求解Rosenbrock函数，初始点选线搜索分别采用黄金分割法与强Wolfe线搜索，并对比第22页，共76页，2022年，5月20日，7点11分，星期一

7、4.4 拟牛顿法第23页，共76页，2022年，5月20日，7点11分，星期一基本思想本质上是基于逼近牛顿法的方法牛顿法每次都计算1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法本节介绍Broyden族拟牛顿法：DFP算法和BFGS算法第24页，共76页，2022年，5月20日，7点11分，星期一算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：思考：要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造矩阵列要求：的选取既能逐步逼近又无需计算二阶导数，且具备以下条件：第25页，共76页，2022年，5月20日

8、，7点11分，星期一C1：是对称正定阵C2：由经简单修正而得：C3：满足下面的拟牛顿方程（推导如下）设是二次连续可微的，第26页，共76页，2022年，5月20日，7点11分，星期一令：则：令：因此：（对二次函数为等式）若非奇异：设想：（拟牛顿方程）这样就可很好的近似第27页，共76页，2022年，5月20日，7点11分，星期一拟牛顿算法Step1:给出Step2:计算Step3:Step4:精确线搜索求Step5:Step6:计算若停；否则转Step7.Step7:校正使拟牛顿方程成立Step8:转Step3.第28页，共76页，2022年，5月20日，7点11分，星期一DFP校正公式是维待

9、定向量要求：所以：令：得：因此：所以：（DFP校正公式）第29页，共76页，2022年，5月20日，7点11分，星期一例6：用DFP算法求解：取解：(1)第30页，共76页，2022年，5月20日，7点11分，星期一(2)第31页，共76页，2022年，5月20日，7点11分，星期一注:（）DFP算法具有二次终止性（）搜索方向是共轭方向：第32页，共76页，2022年，5月20日，7点11分，星期一DFP校正公式的正定继承性引理2:设为正定阵，且则：为正定阵的充要条件是定理5:在DFP算法中，如果正定，则整个矩阵列都正定第33页，共76页，2022年，5月20日，7点11分，星期一DFP算法的

10、二次终止性推论:在上面定理条件下：（1）DFP算法至多经过次迭代就可得到极小点，即存在有：（2）若则第34页，共76页，2022年，5月20日，7点11分，星期一BFGS校正公式(称为关于的BFGS校正公式或互补DFP公式)由上式可得：第35页，共76页，2022年，5月20日，7点11分，星期一对称秩一校正公式要求：要求Hesse逆近似也是对称的，即：取：因此：第36页，共76页，2022年，5月20日，7点11分，星期一注:（1）通常不能保证（2）分母可能取零,修正公式不再有意义的正定性（3）逼近程度高，近来用于信赖域算法，取得了很好的效果第37页，共76页，2022年，5月20日，7点1

11、1分，星期一Broyden族取注：得DFP校正注：得BFGS校正得对称秩一校正其中：第38页，共76页，2022年，5月20日，7点11分，星期一Broyden族算法性质定理6:设在上连续可微，给定在精确线搜索下，由Broyden族算法产生的点列与参数无关结论：可将DFP算法的性质推广到整个Broyden族第39页，共76页，2022年，5月20日，7点11分，星期一作业(1)用FR共轭梯度法求解：(2)用DFP算法求解：第40页，共76页，2022年，5月20日，7点11分，星期一第 五 章无约束最优化方法第41页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化 （

12、f） min f(x) f : RnR 5.1 最优性条件 设 f 连续可微 必要条件：若x*l.opt. 则f(x*)=0 (驻点)。 当 f 凸时， x*l.opt. f(x*)=0 注意： f(x) f(x*)+ Tf(x*)(x-x*), x. 故 f(x*) f(x)， x. （ 由于Tf(x*) =0）5.2 最速下降法 在迭代点 x(k) 取方向 d(k)= f(x(k) ) 精确一维搜索 最 速 下降法：梯度方向函数值变化最快的方向第42页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.2 最速下降法（续）x(1), 0, k=1| f(x(k)

13、) |0得 x(k+1)=x(k)+kd(k)k=k+1第43页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.2 最速下降法（续）特点：全局收敛，线性收敛，易产生扭摆现象而造成早停。 （当x(k)距最优点较远时，速度快，而接近最优点时，速度下降）原因：f(x)=f(x(k)+Tf(x(k)(x-x(k) + o|x-x(k)| 当 x(k)接近 l.opt.时 f(x(k) ) 0，于是高阶项 o|x-x(k)|的影响可能超过Tf(x(k)(x-x(k) 。5.3 Newton法及其修正一、 Newton法： 设f(x)二阶可微，取f(x)在x(k)点附近的二阶

14、Taylor近似函数： qk(x)=f(x(k)+ Tf(x(k)(x-x(k) +12 (x-x(k)T2f(x(k) (x-x(k) 求驻点： qk(x)= f(x(k)+ 2f(x(k) (x-x(k)=0第44页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化Newton法： （续） 当2f(x(k) 正定时，有极小点： x(k+1)=x(k)-2f(x(k) -1 f(x(k) Newton迭代公式 实用中常用 2f(x(k) S= -f(x(k) 解得s(k) x(k+1)=x(k)+s(k)x(1), 0, k=12f(x(k) S= -f(x(k) 得

15、s(k) , x(k+1)=x(k)+s(k)| s(k) |0 使 2f(x(k) + I 正定， 尽量小。特点：全局二阶收敛。第49页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.4 共轭梯度法一、共轭梯度法的方向： 设f(x)=(1/2)xTGx+bTx+c Gnn对称正定，b Rn,从最速下降方向开始，构造一组共轭方向：设初始点x(1),取d(1)= -f(x(1) (最速下降方向) 设k1,已得到k个相互共轭的方向d(1),d(2), ,d(k),以及，由x(1)开始依次沿上述方向精确一维搜索得到点x(2), ，x(k),x(k+1).即有下式： x(

16、i+1)=x(i)+id(i) , i=1,2, ,k 精确一维搜索保证方向导数为0： fT(x(i+1)d(i)=0, i=1,2, ,k 在x(i+1)点构造新方向d(k+1)为-f(x(k+1) 与d(1),d(2), ,d(k)的组合：第50页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.4 共轭梯度法一、共轭梯度法的方向： （续）使d(k+1)与d(1),d(2), ,d(k)都共轭： d(k+1) TG d(j) =0 , j= 1,2, ,k Gram-Schmidt过程： i, j= 1,2, ,k 记 y(j)= f(x(j+1) -f(x(j

17、) =G(x(j+1)-x(j)=jGd(j) . 根据式，有 d(i)T y(j) = j d(i)T G d(j)=0 , ij 根据，有 d(k+1) T y(j) = j d(k+1)T G d(j)=0 , j= 1,2, ,k 这里的j应为i第51页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.4 共轭梯度法一、共轭梯度法的方向： （续） jk, ij 有 f(x(j+1)T d(i)=0 由式 由式 f(x(j+1)T f(x(i)=0 i0d(1)=- f(x(1),k=1k=k+1k=1| f(x(k)|0得 k x(k+1)=x(k)+k d

18、(k) k=n?x(1)=x(n+1)d(1)=- f(x(1),k=1求 kd(k+1)=- f(x(k+1)+ kd(k)yNyN重新开始第55页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.4 共轭梯度法三、算法特点： 1、全局收敛（下降算法）；线性收敛； 2、每步迭代只需存储若干向量（适用于大规模问题）； 3、有二次终结性（对于正定二次函数，至多n次迭代可达opt.） 注：对不同的 k公式，对于正定二次函数是相等的，对非正定二次函数，有不同的效果，经验上PRP效果较好。第56页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化5.

19、5 变尺度法一、变尺度法的基本思路： (f)min f(x), f: R n R1、基本思想： 用对称正定矩阵H(k)近似2f(x(k), 而H(k)的产生从给定H(1)开始逐步修整得到。2、算法框图：x(1),H(1)对称0, k=1d(k)=-H(k) f(x(k)一维搜索得kx(k+1)=x(k)+ k d(k)|x(k+1)-x(k)|0那么DFP法产生的 对称正定。注：下列各情况下有sTy0： 1 f(x)为正定二次函数； 2 精确一维搜索时； 3 前章介绍的不精确一维搜索时。可以证明： DFP法在精确一维搜索前提下，超线性收敛。2、BFGS法 若把前面的推导，平行地用在y=Bs公式

20、上，可得到第64页，共76页，2022年，5月20日，7点11分，星期一第五章 5.5 变尺度法二、2、BFGS法（续）用此公式求方向时，需用到矩阵求逆或解方程： d= -B-1 f(x) 或 Bd= - f(x)由于每次只有秩2的变换，这里的计算量仍可以降下来。为了得到H-公式，可对上面 求逆（推导得）：BFGS法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用前文中介绍的不精确一维搜索有全局收敛性。 第65页，共76页，2022年，5月20日，7点11分，星期一第五章 5.5 变尺度法三、Broyden族 当在秩2公式中，、 任意选取时可得到不同的公式，经过理论推导，可得到

21、下列结果：第66页，共76页，2022年，5月20日，7点11分，星期一第五章 5.5 变尺度法三、Broyden族（续）第67页，共76页，2022年，5月20日，7点11分，星期一第五章 无约束最优化 5.6 直接算法 min f(x)一、单纯形法及可变多面体算法1、单纯形法基本思路： 设 x(0),x(1), x(n)是R n中n+1个点构成的一个当前的单纯形。 比较各点的函数值得到：x max,x min使 f( x max)=maxf(x(0),f(x(1), ,f(x(n) f( x min)=minf(x(0),f(x(1), ,f(x(n) 取单纯形中除去x max点外，其他各

22、点的形心：去掉x max，加入x(n+1)得到新的单纯形。重复上述过程。第68页，共76页，2022年，5月20日，7点11分，星期一第五章 5.6 直接算法一、1、单纯形法基本思路： （续）几点注意： 当x(n+1)又是新单纯形的最大值点时，取次大值点进行反射； 若某一个点x出现在连续m个单纯形中的时候，取各点与x连线的中点（n个）与x点构成新的单纯形，继续进行。经验上取 m 1.65n+0.05n2 例如：n=2时，可取m 1.65 2+0.05 4 =3.5 可取 m=4.12345789106111213第69页，共76页，2022年，5月20日，7点11分，星期一第五章 5.6 直接

23、算法一、1、单纯形法基本思路： （续） 优点：不需求导数，不需要一维搜索。 缺点：无法加速，收敛慢，效果差。2、改进单纯形法： （可变多面体算法） 设第k步迭代得到n+1个点： x(0),x(1), x(n) ，得到x max,x min及 通过下列4步操作选新迭代点： 1 反射： 取反射系数 0,(单纯形法中 =1) 2 扩展：给定扩展系数 1,计算。（加速）第70页，共76页，2022年，5月20日，7点11分，星期一第五章 5.6 直接算法一、 2、改进单纯形法： （续） 若f(y(1) f(y(2), 那么y(2)取代x max; 否则， y(1)取代x max 。若maxf(x(i)

24、| x(i) x max f(y(1) f(x min), y(1)取代x max 。3 收缩：若f(x max ) f(y(1) f(x(i), x(i) x max ,计算 ,以y(3)取代x max 。4 减半：若f(y(1) f(x max ), 重新取各点，使 x(i)= x min +1 2(x(i) - x min ) 得到新单纯形。经验上：=1,0.40.6, 2.33.0 . 有人建议:=1, =0.5， =2 。算法停机准则取：第71页，共76页，2022年，5月20日，7点11分，星期一第五章 5.6 直接算法二、模式搜索法： Hooke & Jeeves 19611、基本思想与主要过程： 利用两类移动（探测性移动和模式性移动）进行一步迭代： 探测性移动的目的：探求一个沿各坐标方向的新点并得到 一 个“有前途”的方向； 模式性移动的目的：沿上述“有前途”方向加速移动。主要过程：第k步迭代，设已得到x(k) 1探测性移动： 给定步长k ，设通过模式性移动得到y(0), 依次沿各坐标方向e(i)=(0, ,