Lecture7_使用导数的最优化方法.ppt

《Lecture7_使用导数的最优化方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化方法Optimization第十二讲第十章使用导数的最优化方法(分三讲)无约束优化问题算法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法最小二乘法最速下降法最速下降方向取搜索方向:步骤:带精确线搜索的最速下降法例:第一次迭代解:第二次迭代最速下降法的收敛性二次函数情形最速下降法表示为Kantorovich不等式定理（最速下降法—二次情形）定理：条件数非二次情形结论：在相继两次迭代中,梯度方向互相正交.基本思想用一个二次函数去近似目标函数f(x),然后精确地求出这个二次函数的极小点.牛顿法牛顿方向定理：步

2、骤:用Newton法求解无约束问题会出现以下情形：（1）收敛到极小点（2）收敛到鞍点（3）Hesse矩阵不可逆，无法迭代下去优点:（1）Newton法产生的点列{x(k)}若收敛，则收敛速度快---具有至少二阶收敛速率。(2)Newton法具有二次终止性缺点:（1）可能会出现在某步迭代时，目标函数值上升.（2）当初始点远离极小点时，牛顿法产生的点列可能不收敛，或者收敛到鞍点，或者Hesse矩阵不可逆，无法计算.（3）需要计算Hesse矩阵，计算量大.步骤:阻尼牛顿法修正牛顿法共轭梯度法共轭方向定义：例：定

3、理1证明：定理2：证明：定理3：共轭梯度法(FR法)记号：在共轭梯度法中，初始点处的搜索方向取为该点的负梯度方向，即取而以下各共轭方向d(k)由第k次迭代点x(k)处的负梯度-gk与已得的共轭向量d(k-1)的线性组合来确定。以此类推，得定理:FR共轭梯度法例:一般函数的共轭梯度法迭代的延续方法：FR共轭梯度法这是一种求解无约束极值问题的有效算法，由于它既避免了计算二阶导数、矩阵及其求逆过程，又比最速下降法的收敛速度快，特别是对高维问题具有显著的优越性，所以，它被公认为求解无约束极值问题最有效的算法之一。

4、拟牛顿法(Quasi-NewtonMethod)基本原理：阻尼牛顿法:拟牛顿条件拟牛顿法步骤秩1校正一般策略：校正矩阵DFP拟牛顿法定义：DFP公式DFP法计算步骤:例:用DFP方法求解下列问题：第一次迭代第二次迭代DFP拟牛顿法-定理：推论：定理：信赖域方法基本思想：在当前迭代点的某个邻域内（通称取为以当前迭代点为中心的球域，称为信赖域），根据已知的有关优化问题的信息，确定一个模型函数来近似原来的目标函数；然后，在该领域内极小化模型函数确定可能的改进点；最后，根据一定标准决定是否接受这个可能的改进点。基

5、本原理子问题信赖域半径的确定通过比较迭代过程中模型函数和目标函数的下降量,确定下一个迭代过程的信赖域半径.步骤：子问题的精确求解法必要性证明充分性证明第一次迭代:第二次迭代:第三次迭代:非线性最小二乘法问题给定(ti,yi),i=1,…n,拟合一个函数y=f(t,x)，其中x为待定的参数向量,f对x非线性。优化模型记误差根据目标函数是r(x)的二次函数的特点构造简单算法非线性最小二乘拟合)()(2xrxJRT=Ñ讨论牛顿法要计算Hessian矩阵，其中S计算量大若f对x线性,则化为线性最小二乘拟合,此时S

6、=0特定算法考虑如何忽略或近似矩阵S。Gauss-Newton算法：忽略矩阵Sf用R代替，下降方向dk满足G-N算法收敛性依赖f对x的线性程度,及偏差r的大小非线性最小二乘拟合牛顿方程)()(2xrxJRT=ÑLevenbery-Marquardt算法：G-N算法修正其中k>0为修正参数.dk位于牛顿方向(k很小)和负梯度方向(k很大)之间L-M算法非线性最小二乘拟合防止JTJ出现病态