资源预览内容
第1页 / 共45页
第2页 / 共45页
第3页 / 共45页
第4页 / 共45页
第5页 / 共45页
第6页 / 共45页
第7页 / 共45页
第8页 / 共45页
第9页 / 共45页
第10页 / 共45页
亲,该文档总共45页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
最优性条件 最速下降法 牛顿法及其阻尼牛顿法 共轭方向法 共轭梯度法 变尺度法(DFP算法和BFGS算法),第4章 无约束最优化方法,无约束最优化问题:,设 是对称正定矩阵, 如果 则称向 量p 和q是A共轭的(或称为A正交)。,如果对有限个向量 ,有,共轭方向法-共轭方向及其性质,若 则p与q是正交的。,定义1,定义2,则称这个向量组是A-共轭 (或A正交)向量组,也称它们是一组A共轭方向。,共轭是正交的推广,共轭向量组是正交向量组的推广。,性质2 若Rn中的非零向量p1,p2, pm是A共轭向量组,则这m 个向量是线性无关的。,性质3 在n维空间中互相共轭的非零向量的个数不超过n。,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定,又设n维非零 向量组p1, p2, pn是A共轭向量组,从任意点x1出发,依 次以p1, p2, pn 为搜索方向进行精确一维搜索,则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交; (2) 最多n次迭代必达到二次函数f(x)的极小点。,性质1 在n维空间中与n个线性无关的向量都正交的一定是零向 量。,共轭方向法-共轭方向的性质,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定,又设n维非零向量组p1, p2, pn是A共轭向量组,从任意点x1出发,相继以p1, p2, pn 为搜索方向进行精确一 维搜索,则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交; (2) 最多n次迭代必达到二次函数f(x)的极小点。,共轭方向法-共轭方向的性质,定义:一个算法若能在有限步内求得正定二次函数的极 小点,则称该算法具有二次收敛性(又称二次终止性)。,由性质4可知,若能找到一组A共轭向量p1, p2, pn 则前面提到的结合最速下降法和Newton法优点的算法就找到了,就是共轭方向法,,在下降迭代法中,若取下降方向是共轭方向,所得到的方法我们称为共轭方向法。,怎么选取共轭方向?,这个算法具有二次收敛性。,共轭方向的生成与共轭梯度法,共轭方向的选取有很大任意性,而一组不同的共轭方向 就对应着不同的共轭方向法。 作为一种迭代算法,我们自然希望共轭方向能在迭代过 程中逐次生成。,下面先以正定二次函数为例,介绍一种生成共轭方向的方 法,再将这种方法推广到非二次函数上。 这种方法中每一个共轭向量都是依赖于迭代点处的负梯度, 因此称为共轭梯度法,它是共轭方向法中的一种。,令,(2) 若 ,停止, 成的正交锥中找一个向量 ,即令 使得 与 共轭,即,由,共轭梯度法,(1) 从任取初始点x1 出发,沿负梯度方向进行精确一维搜索:,可得,否则在 和 张,(5) 若 ,停止, 成的正交锥中找一个向量 ,即令 使得 与 共轭,即,由,共轭梯度法,(3) 在x2 处沿 p2 方向进行精确一维搜索,,可得,(4) 以此类推,,否则在 和 张,共轭梯度法,这样便构造了一组向量,实际上,这组向量 是一个A共轭向量组。,相邻两个向量是共轭的,共轭梯度法,定理1:设向量组 是由上述方法产生的向量 组,向量组 是由各点的梯度生成的 向量组, ( ) 则 (1) 是正交向量组; (2) 是A共轭向量组。,共轭梯度法,定理1:设向量组 是由上述方法产生的向量组,向量组 是由各点的梯度生成的向量组, ( ) 则 (1) 是正交向量组; (2) 是A共轭向量组。,证明:归纳法:,由 的构造过程知,,是A共轭的,即,结论(2)成立;,利用精确一维搜索的性质知,,而,故,结论(1)成立。,由假设可知,要证明 时结论成立,只需证明,(a) 证明,所以,结论(a)成立,进而结论(1)成立。,与,正交,,与,A共轭。,与,正交;,是A共轭向量组,,利用性质4(1)可知,,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定,又设n维非零向量组p1, p2, pn是A 共轭向量组,从任意点x1出发,相继以p1, p2, pn 为搜索方向进行精确一维搜索,则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交;,因为,(b) 证明,结论(b)成立,进而结论(2)成立。,与,是A共轭的;,由 的构造过程知,,与,是A共轭的;,下证,与,是A共轭的;,共轭梯度法,定理1:设向量组 是由上述方法产生的向量组, 向量组 是由各点的梯度生成的向量组, ( ) 则 (1) 是正交向量组; (2) 是A共轭向量组。,注:为保证方向的共轭性,初始方向取负梯度方向。,共轭梯度法,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定,又设n维非零 向量组p1, p2, pn是A共轭向量组,从任意点x1出发,相 继以p1, p2, pn 为搜索方向进行精确一维搜索,则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交; (2) 最多n次迭代必达到正定二次函数f(x)的极小点。,是一个A共轭向量组,每一个搜索方向都依赖迭代点处的负梯度,对应的算法称为共轭梯度法。,共轭梯度法,存在问题:计算量、存储量都很大,针对 f(x)=1/2xTAx+bTx+c, A=AT正定,最多n次迭代达到极 小点找到了一组共轭方向:,针对一般的函数,将这组方向进行推广:,直接对(*)式推广:,在正定二次函数 的前提下,将 变形,怎么解决呢?,能否将 中的A去掉?,定理2:设 ,向量组 是由上述方法构造的A共轭向量组, ,利用前面 所得的公式,得到几个等价的计算公式:,共轭梯度法,利用定理1,可知 是正交向量组,因此(2)中 ; 并且 .,共轭梯度法,对于正定二次函数,上面得到的5个计算公式是等价的; 这5种共轭梯度法也是完全等价的;,SW共轭梯度法,DM共轭梯度法,FR共轭梯度法,PPR共轭梯度法,介绍FR共轭梯度法,Daniel共轭梯度法,简洁,用的最多,更好用,对于非二次函数,产生的搜索方向不再相同, 利用公式(2)-(5), (1)中含有Hesse矩阵,通常不用,步骤1. 选定初始点 。,步骤2. 如果 ,算法停止, ,否则转步骤3。,步骤4. 精确一维搜索找最佳步长 ,令,FR共轭梯度法的计算步骤,步骤3. 取,步骤5. 如果 ,算法停止, 否则,步骤6. 如果k=n, 令 k=1 ,转步骤4; 否则转步骤7。,步骤7. 计算 转步骤4。,转步骤6。,步骤4. 精确一维搜索找最佳步长 ,令,FR共轭梯度法的计算步骤,步骤5. 如果 ,算法停止, ,否则转步骤6。,步骤6. 如果k=n, 令 算法停止,k=1 ,转步骤4; 否则转步骤7。,步骤7. 计算 转步骤4。,误差可能会使n步迭代得不到正定二次函数的极小点。 Rn中共轭方向最多有n个,n步后构造的搜索方向不再是共轭 的, 会降低收敛速度,,步骤6:重新开始技术:xn+1作为新的x1,FR共轭梯度法,,已知初始点(1,1)T,例题 用FR共轭梯度法求下列问题的极值,解: 1)第一次迭代:沿负梯度方向搜寻 计算初始点处的梯度,迭代精度 。,FR共轭梯度法,精确一维搜索求最佳步长,,令,FR共轭梯度法,得,不满足精度,继续迭代:,2)第二次迭代:,FR共轭梯度法,精确一维搜索求最佳步长,,因,得到最优解:,FR共轭梯度法,令,得,共轭梯度法对正定二次函数,具有二次收敛性; 对非二次函数,由于目标函数的Hesse矩阵不再是常数矩 阵,因而产生的方向不再是共轭方向; 共轭梯度法在一定条件下也是收敛的,且收敛速度通常优 于最速下降法,具有较高的求解效率。,FR共轭梯度法,设 f (x)存在连续一阶偏导数,且函数为凸函数,且水平集 有界,则由共轭梯度法得到的点列 有如下 性质: (1) 为严格单调下降序列,且 存在; (2) 的任意聚点 都是 f (x)的最优解。,FR共轭梯度法,共轭梯度法在无约束优化方法中占有重要的地位,是目 前最常用的方法之一。,收敛性定理:,(1) 对凸函数全局收敛(下降算法); (2) 计算公式简单,不用求Hesse矩阵或者逆矩阵,计算量 小,存储量小,每步迭代只需存储若干向量,适用于大 规模问题; (3) 具有二次收敛性; (对于正定二次函数,至多n次迭代可达最优解),共轭梯度法的特点,(4) Crowder和Wolfe证明,共轭梯度法的收敛速率不坏 于最速下降法。 如果初始方向不用负梯度方向,则其收敛速率是线 性收敛的; (5) 共轭梯度法是目前求解无约束优化问题最常用的方 法之一。,共轭梯度法的特点,注:不同的k公式,对于正定二次函数是等价的, 对非正定二次函数,有不同的效果,经验上PPR 效果 较好。,作业: P 100 4.9, 4.10, 4.12, 4.13, 4.14, 4.17-4.19,Newton法和阻尼Newton法具有收敛速度快的优点,但 需要计算Hesse矩阵的逆, 计算量大,存储量也很大。,变尺度法-一类特殊的拟Newton法,为减少计算量,用一个n阶对称正定矩阵Hk近似代替Hesse 矩阵的逆 ,即 ,从而搜索方 向是 ,由此搜索方向产生的方法称为变尺度法, Hk称为尺度矩阵,这是一种拟Newton法,被认为是无约束优 化问题中最有效的方法之一。,所谓拟Newton法是指由Newton法的思想出发产生的一类方法。,变尺度法-一类特殊的拟Newton法,变尺度法的计算步骤 步骤1. 任取初始点x1,初始尺度矩阵H1,令k=1. 步骤2. 计算 步骤3. 利用精确一维搜索找最佳步长 , 步骤4. 令 ,转步骤2。,其中 称为修正矩阵。 不同的修正矩阵,对应着不同的变尺度法。,变尺度法的算法框架,构造 Hk的原则,变尺度法的关键在于如何构造Hk,为了使算法有 较快的收敛速度,需要满足以下几个原则: 拟牛顿性质, 二次收敛性, 稳定性。,变尺度法-一类特殊的拟Newton法,构造 Hk的原则,拟牛顿性质,在 点处对函数 作二阶 Tayloy展开:,变尺度法-一类特殊的拟Newton法,略去高阶项,在xk+1 附近,函数两端求导,得,令 可得,记,变尺度法-一类特殊的拟Newton法,Hesse矩阵 对称正定,又有,变尺度法-一类特殊的拟Newt
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号