Optimal Method

梯度下降法

简介

1. 一个一阶最优化算法
2. 函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索
3. 找到一个函数的局部极小值

算法

缺点

1. 靠近局部极小值时速度减慢。
2. 直线搜索可能会产生一些问题。（局部最优）
3. 可能会“之字型”地下降。（如下图）

牛顿法

简介

1. 利用一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似

算法

缺点

1. 局部牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性，如果初始点远离最小点可能不收敛
2. 与梯度下降法相比，使用牛顿法收敛更快（使用二阶矩阵，迭代更少次数）。但是每次迭代的时间比梯度下降法长

​ 下图中，红色为牛顿法，绿色为梯度下降法

坐标下降法

简介

1. 简单但却高效的非梯度优化算法
2. 依次沿着坐标轴的方向循环最小化目标函数值

算法

针对多变量的 xk 选取 i 维度进行优化：

缺点

1. 对于非平滑函数，坐标下降法可能会遇到问题。下图展示了当函数等高线非平滑时，算法可能在非驻点中断执行。

凸优化

1. 研究定义于凸集中的凸函数最小化的问题

2. 定义：

   

拉格朗日乘子法

简介

1. 与先前优化方法不同，拉格朗日乘子法寻找多元函数在其变量受到一个或多个条件的约束时的极值的方法
2. 将一个有n个变量与k个约束条件的最优化问题转换为一个解有n + k个变量的方程组的解的问题

算法

引入拉格朗日乘数(可以为任何数)

f(x,y) 求极值，g(x,y)=c 为约束条件， 对于不同 d 值存在 f(x,y) = d 的等高线，当 g=c 与 f(x,y) = d 相切时出现极值

向量表示（f，g相切）：

将原方程与约束条件综合考虑为一个方程进行优化

分类讨论

• 等式约束：

  

  

• 不等式约束：

  

  

证明（wiki）

KKT条件

1. 对于不等式条件约束的优化，拉格朗日乘子没有办法消除它的约束，仅能推导出最优解一定满足的性质
2. KKT条件是所有不等式约束的最优解都必须得满足的条件
3. 满足KKT条件的不一定是最优解，但是最优解一定得满足KKT条件

拉格朗日对偶

简介

1. 原问题是不可解的情况下，通过对偶问题更易求解
2. 几乎所有的凸优化问题都满足强对偶性

算法

拉格朗日乘子 & KKT & 对偶