最优化方法总结

最优化方法总结：包括最优性条件、无约束问题最优化方法（最速下降法、牛顿法等）、约束问题最优化方法（可行下降法、罚方法等）

最优化

• 最优性条件
  • 无约束极值问题最优性条件
    • 必要条件(局部）
      • 一阶必要条件：梯度为0
      • 二阶必要条件：梯度为0，Hesse矩阵半正定
    • 充分条件(局部）
      • 二阶充分条件：梯度为0，Hesse矩阵正定
    • 充要条件(全局）
      • 可微凸函数
      • 梯度为0
  • 约束极值问题最优性条件
    • 不等式约束问题一阶最优性条件
      • Fritz John一阶必要条件（局部）
        • 验证Fritz John条件
      • KT一阶必要条件（局部）
        • 验证KT点、直接求KT点
          • 子主题
      • 全局一阶条件
        • 满足KT条件
        • 凸问题
    • 一般化约束问题一阶最优性条件
      • Fritz John一阶必要（局部）
      • KT条件一阶必要（局部）
      • 全局最优一阶
        • 满足KT条件
        • 凸问题
    • 一般约束问题二阶最优性条件
      • 二阶必要条件
      • 二阶充分条件
      • 判断一个点是否是局部最优点
        • 1、一阶必要条件：判断是否是KT点，且求出w,v
        • 2、二阶充分条件：是否存在d满足条件/或G为空集
• 最优化方法
  • 无约束问题最优化方法
    • 最速下降法
      • 算法
      • 锯齿现象
    • 牛顿法（二次终止性）
      • 阻尼牛顿法
        • 增加了一维搜索，迭代方向一定不会上升，但由于Hessen矩阵可能非正定，可能存在无法产生新点的问题，导致算法失效
      • 修正牛顿法
    • 共轭梯度法（二次终止性）
      • 初始方向需取最速下降方向
      • 二次凸函数的共轭梯度法
    • 拟牛顿法
      • • 秩1校正
          • 可能不正定
        • DFP算法
        • BFGS算法
      • 1、具有二次终止性2、只需要计算一阶导3、具有超线性收敛速率
  • 约束问题最优化方法
    • 可行方向法
      • 1、确定可行方向（转化为求解线性规划问题）
      • 2、确定搜索步长
      • 3、确定初始可行点
        • 猜一个/或引入人工变量、求解辅助问题
    • 罚函数法
      • 外点罚函数
        • 不一定在可行域，但接近可行域
      • 内点罚函数
        • 一定在可行域，但只适用于不等式约束问题
• 一维搜索
  • 函数逼近法
    • 牛顿法
    • 割线法
• 特殊优化问题
  • 凸集、凸函数、凸问题
  • 线性规划
    • 基本性质
      • 1、可行域为凸集
      • 2、若存在有限最优解，则最优值一定在某极点
      • 3、存在有限最优解的充要条件：cdi为非负数，其中di为可行域的极方向
    • 基本可行解
      • 约束的极点集和基本可行解集等价（即基本可行解点就是极点），从而线性规划问题可归结为求最优基本可行解
    • 单纯形法求解线性规划问题
      • 非单纯形表
      • 单纯形表
        • 有现成单位阵
        • 无现成单位阵
          • 两阶段法
          • 大M法
      • 对偶单纯形表
        • 求线性规划的对偶问题
        • 性质
          • 对偶定理
            • cx>=wb
          • 若线性规划问题存在一个对应基B的最优基本可行解，则单纯形乘子w=Cb*B-1是对偶问题的一个最优解
          • 互补松弛性质
        • 对偶单纯形法