最优化算法速通 - 无约束优化

二次型函数

对称正定

收敛阶

收敛阶越高, 收敛率越高, 收敛速度越快.

• 拟线性收敛: ,
• 线性收敛: ,
• 超线性收敛:
• 二次收敛:

任意收敛序列的收敛阶大于等于 1.

梯度下降法

记

最速下降法

使用二次型精确步长公式, 则

• 精确步长线搜索, 搜索方向与梯度正交
• 能保证单调下降
• 能全局收敛
• 会形成锯齿状震荡轨迹, 效率低
• 最坏情况 ( 是 的一个特征向量时), 收敛阶为 1

固定步长法

只需要取 ,

满足 时收敛.

牛顿法

类似一维牛顿法, 利用二次型来近似, 需要二阶可导, 可求 Hessian 矩阵.

二阶 Taylor 展开:

若 , 可求 的极小点, 得迭代公式

• 若二次型非正定, 则牛顿法搜索方向不一定是下降方向
• 目标函数是二次型时, 收敛阶为

需要初始点靠近极小点才有非常好的收敛性.

共轭类方法

• 共轭方向: .
  
• 对称正定, 则共轭向量组线性无关.
• 构造共轭向量组: Gram-Shimidt 正交化, 给定一组线性无关变量

基本共轭方向算法

给定初始点 和一组关于 共轭的方向 , 迭代公式:

使用二次型精确步长公式:

对于二次型, 任意初始点, 基本共轭方向算法能在 次迭代内收敛到全局极小点.

共轭方向算法中, , 有

扩张子空间定理:

每迭代一次, 都能在到目前为止的共轭方向张成的子空间中取到最优解.

共轭梯度法

不需要预先给定 的一组共轭方向, 能在迭代的过程中利用梯度不断产生共轭方向.

1. , 给定初始值
2. 1. 若 , 停止迭代
5. 1. 若 停止迭代
8. , 回到第三步

非线性共轭梯度法

对于一般的函数, 用 Hessian 矩阵代替 , 但计算每个迭代点处的 Hessian 矩阵计算量大. 使用其他方法来近似代替 Hessian.

对于 , 使用一般的线搜索方法.

对于 , 有三种近似的公式.

Hestenes-Stiefel: 用 替代

Polak-Ribiere: 近似认为 , 有

Fletcher-Reeves: 近似认为

拟牛顿法

希望避免牛顿法中求 Hessian 矩阵, 同时避免对矩阵求逆. 设法近似 , 在迭代中更新近似.

迭代公式:

1. 拟牛顿方向:
2. 步长:
3. 更新迭代点:

矩阵 需要是对称矩阵, 目标函数是二次型函数时要满足 . 二次型问题中记 Hessian 矩阵为 , 则能保证拟牛顿方向 是 共轭的.

记 , 拟牛顿方程:

方程的解不唯一.

秩 1 校正

在 上添加一个秩 1 矩阵得到 , 再求解拟牛顿方程:

已知 , 可求解 和

得到迭代公式

初始时 可以任选对称正定实矩阵.

问题:

1. 即使是二次型问题, 也可能非正定, 可能不是下降方向.
2. 秩 1 公式的分母接近 0 会导致计算困难.

DFP 算法 (秩 2 算法)

解方程组

代入得

取一组特解

得到迭代公式

DFP 公式能保证 正定则 正定, 但 接近奇异时可能会被卡住.

BFGS 算法

除了构造 的近似矩阵 , 也构造 的近似矩阵 , 满足:

由对称性, 从 DFP 公式得到

Sherman-Morrison 公式: 若 非奇异, 列向量 , . 则

应用两次 Sherman-Morrison 公式简化 的计算