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

最优化方法Optimization第十二讲 第十章使用导数的最优化方法 分三讲 无约束优化问题算法 最速下降法牛顿法共轭梯度法拟牛顿法信赖域法最小二乘法 最速下降法 最速下降方向 取搜索方向 步骤 带精确线搜索的最速下降法 例 第一次迭代 解 第二次迭代 最速下降法的收敛性 二次函数情形 最速下降法表示为 Kantorovich不等式 定理 最速下降法 二次情形 定理 条件数 非二次情形 结论 在相继两次迭代中 梯度方向互相正交 基本思想用一个二次函数去近似目标函数f x 然后精确地求出这个二次函数的极小点 牛顿法 牛顿方向 定理 步骤 用Newton法求解无约束问题会出现以下情形 1 收敛到极小点 2 收敛到鞍点 3 Hesse矩阵不可逆 无法迭代下去 优点 1 Newton法产生的点列 x k 若收敛 则收敛速度快 具有至少二阶收敛速率 2 Newton法具有二次终止性 缺点 1 可能会出现在某步迭代时 目标函数值上升 2 当初始点远离极小点时 牛顿法产生的点列可能不收敛 或者收敛到鞍点 或者Hesse矩阵不可逆 无法计算 3 需要计算Hesse矩阵 计算量大 步骤 阻尼牛顿法 修正牛顿法 共轭梯度法 共轭方向 定义 例 定理1 证明 定理2 证明 定理3 共轭梯度法 FR法 记号 在共轭梯度法中 初始点处的搜索方向取为该点的负梯度方向 即取 而以下各共轭方向d k 由第k次迭代点x k 处的负梯度 gk与已得的共轭向量d k 1 的线性组合来确定 以此类推 得 定理 FR共轭梯度法 例 一般函数的共轭梯度法 迭代的延续方法 FR共轭梯度法 这是一种求解无约束极值问题的有效算法 由于它既避免了计算二阶导数 矩阵及其求逆过程 又比最速下降法的收敛速度快 特别是对高维问题具有显著的优越性 所以 它被公认为求解无约束极值问题最有效的算法之一 拟牛顿法 Quasi NewtonMethod 基本原理 阻尼牛顿法 拟牛顿条件 拟牛顿法步骤 秩1校正 一般策略 校正矩阵 DFP拟牛顿法 定义 DFP公式 DFP法计算步骤 例 用DFP方法求解下列问题 第一次迭代 第二次迭代 DFP拟牛顿法 定理 推论 定理 信赖域方法 基本思想 在当前迭代点的某个邻域内 通称取为以当前迭代点为中心的球域 称为信赖域 根据已知的有关优化问题的信息 确定一个模型函数来近似原来的目标函数 然后 在该领域内极小化模型函数确定可能的改进点 最后 根据一定标准决定是否接受这个可能的改进点 基本原理 子问题 信赖域半径的确定 通过比较迭代过程中模型函数和目标函数的下降量 确定下一个迭代过程的信赖域半径 步骤 子问题的精确求解法 必要性证明 充分性证明 第一次迭代 第二次迭代 第三次迭代 非线性最小二乘法 问题 给定 ti yi i 1 n 拟合一个函数y f t x 其中x为待定的参数向量 f对x非线性 优化模型 记误差 根据目标函数是r x 的二次函数的特点构造简单算法 非线性最小二乘拟合 讨论 牛顿法要计算Hessian矩阵 其中S计算量大 若f对x线性 则化为线性最小二乘拟合 此时S 0 特定算法考虑如何忽略或近似矩阵S Gauss Newton算法 忽略矩阵S f用R代替 下降方向dk满足 G N算法 收敛性依赖f对x的线性程度 及偏差r的大小 非线性最小二乘拟合 牛顿方程 Levenbery