无约束优化问题的优化算法

无约束优化问题的优化算法，1、最速下降法、牛顿法、共轭梯度法主要原理 2、如何判断结果是否为最优点。

无约束问题最优化方法

• 最速下降法
  • 算法
  • 性质
    • 锯齿现象
      • 最速下降法的相邻两个搜索方向是正交的。
    • 收敛速度：条件数r越小收敛速度越快（条件数：Hessen矩阵最大特征值/最小特征值）(r-1)^2/(r+1)^2
• 牛顿法（二次终止性）
  • 性质
    • 对于二次凸函数，牛顿法迭代一次便到极小点
    • 牛顿方向不一定是下降方向，则不一定收敛
  • 改进的牛顿法
    • 阻尼牛顿法
      • 增加了一维搜索，迭代方向一定不会上升，但由于Hessen矩阵可能非正定，可能存在无法产生新点的问题，导致算法失效
    • 修正牛顿法
      • 修正Hessen矩阵，保证其正定性
    • 拟牛顿法
      • • 秩1校正
          • 可能不正定
        • DFP算法
        • BFGS算法
      • 1、具有二次终止性2、只需要计算一阶导3、具有超线性收敛速率
• 共轭梯度法（二次终止性）
  • 初始方向需取最速下降方向
  • 二次凸函数的共轭梯度法
    • 1、确定搜索方向
    • 2、确定搜索步长（或直接求解关于lambda的最小化问题）
  • 性质
• 判断问题是否是最优解
  • 无约束问题的判断条件
    • 1、凸函数
      • 梯度为0
    • 2、非凸函数
      • 梯度为0，且Hessen矩阵正定