最优化理论与应用-9

《最优化理论与应用-9》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化理论与应用第9讲-大规模无约束优化电子科技大学自动化工程学院彭晓明1内容提要不精确牛顿法线搜索牛顿-共轭梯度法信任域牛顿-共轭梯度有内有限内存存拟的拟牛牛顿法部分可分离函数问题2不精确牛顿法线搜索牛顿-共轭梯度法信任域牛顿-共轭梯度有内有限内存存拟的拟牛牛顿法部分可分离函数问题3不精确牛顿法回忆一下在牛顿法中求解牛顿方向pN的方程式k所谓不精确牛顿法(inexactNewtonMethod)的目的是求解pNk的近似(不精确)值,而避免对HiHessian矩阵进行分解4不精确牛顿法本课讲述使用共轭梯度法(()CG)的不精确牛顿法回忆一下共轭梯度法中的残差(

2、residual)不精确牛顿方向5不精确牛顿法当下面条件满足时结束CG的迭代其中，0<η<1kη被称为是强迫序列(forcingksequesequence)nce)6不精确牛顿法当时，不精确牛顿法的收敛速度是超线性的当时，不精确牛顿法的收敛速度是二次的学习两种方法线搜索牛顿-共轭梯度法信任域牛顿-共轭梯度法7不精确牛顿法线搜索牛顿-共轭梯度法信任域牛顿-共轭梯度有内有限内存存拟的拟牛牛顿法部分可分离函数问题8线线顿搜索牛顿-共轭梯度法回忆一下线性共轭梯度法的实用形式9线线顿搜索牛顿-共轭梯度法线搜索牛顿-共轭梯度法采用线性共轭梯度法的实用形式求解

3、牛顿方向pN在r≤∇ηf条件满方向pk，在rkkk≤∇η条件满足时停止共轭梯度法的迭代，从而得到pN的不精确解p。kk为了讨论方便，下面用B代替kHessian矩阵2用d代替算法Hessian矩阵∇fk，用dj5.2中的共轭方向p,用z代替算法kj5.2中的x，得到下面的算法7.110k线线顿搜索牛顿-共轭梯度法ηkB非正定k共轭梯满足停止度迭代条件法线搜索11线线顿搜索牛顿-共轭梯度法由于共轭梯度法中要求B是正定k矩阵，因此当出现B是非正定情k况则终止算法。当共轭梯度法在迭代开始时(j(j0)=0)发现B是非正定的，则返回当前k梯度的负方向作为pN的不−∇fk

4、k精确解pk否则返回当前的z作为pN的不精jk确解p12k线线顿搜索牛顿-共轭梯度法不足之处：当Hessian矩阵2接∇fk近奇异矩阵时，p会很长，使得k在进行线搜索时即使经过很多次尝试找到的α也不能让目标函数k显著减小13不精确牛顿法线搜索牛顿-共轭梯度法信任域牛顿-共轭梯度有内有限内存存拟的拟牛牛顿法部分可分离函数问题14信任域牛顿-共轭梯度法回忆一下信任域方法求解的问题下面要讨论的StihSteihaug算法采用线性共轭梯度法求解p的近似值为了讨论方便，用d代替算法5.2j中的共轭方向p,用z代替算法5.2kj中的x，得到下面的算法727.2k15信任

5、域牛顿-共轭梯度法16信任域牛顿-共轭梯度法说明如果当j=0时有dTBd0≤0,则0k∇fkp=−Δkk∇fk恰好是柯西点pCk回忆一下柯西点17柯西点((yCauchyppoint))同”信任域方法其实计算柯西点是求解下面的问题”中的公式(4.3)问题(a)问题(b)柯西点18信任域牛顿-共轭梯度法说明否则得到z为1如果

6、

7、z

8、

9、<Δ，则z恰好也是柯西1k1点pC；继续运行算法，随后得到k的z会满足m(z)≤m(z)。jkjk119信任域牛顿-共轭梯度法说明而如果

10、

11、z

12、

13、≥Δ，则返回的p也柯1kk西点pCk其他情况类推结论：Steihaug算法得

14、到的p满足km(p)≤m(pC),也即kkkkm(0)-m(p)≥m(0)-m(pC)kkkkkk20信任域牛顿-共轭梯度法可以证明(Nocedal,p.172)，由算法7.2得到的向量序列{z}满足j即随着算法的进行，得到的p的k长度会增加，但不会超出信任域范围21不精确牛顿法线搜索牛顿-共轭梯度法信任域牛顿-共轭梯度有内有限内存存拟的拟牛牛顿法部分可分离函数问题22有限内存存顿的拟牛顿法拟牛顿法的一个问题：真实的n×n阶Hessian矩阵可能是一个稀疏矩阵，而拟牛顿法得到的近似矩阵是一个稠密矩阵所谓稠密(dense)矩阵是指非0元素占所有元素比例较大的矩阵

15、；反之，非零元素占全部元素比例很小的矩阵称为是稀疏((psparse))矩阵23有限内存存顿的拟牛顿法因此，如果当要求解问题的维数n是一个很大的数时，拟牛顿法得到的近似矩阵需要很大的内存来存储下面将要学习L-BFGS方法用于解决内存有限时的BFGS更新问题24BFGS方法回忆一下BFGS算法(算法6.1)线搜索方法时用到的算法353.5和3.6TTTHIk+1=−()ρρkkksyyHk()I−kkks+ρkkkss;25有限内存存顿的拟牛顿法回忆一下BFGS算法(算法6.1)其中26有限内存存顿的拟牛顿法L-BFGS方法的思想是：不存储