Optimization

无约束优化方法 本文可能存在纰漏，欢迎大家指出错误！非常感谢！ 本文讲解的是无约束优化方法，主要包括梯度下降法、牛顿法、BFGS 三种。 后续会添加 LBFGS 方法的说明。 基本问题 对于无约束优化问题，变量$x\in R^n$，目标函数为： $$ \min_x f(x) $$ 泰勒级数 基于梯度的问题都会涉及泰勒级数问题。简单来说，泰勒级数就是在级数$f(x)$在点$x_0$的邻域内具有$n+1$阶导数的前提下，可以使用$n$阶泰勒级数去近似表示邻域内的函数$f(x)$，如下所示： $$ f(x)=f(x_0)+\nabla f(x_0)(x-x_0)+\frac{\nabla^2 f(x_0)}{2!}(x-x_0)^2+\cdots+\frac{\nabla^n f(x_0)}{n!}(x-x_0)^n $$ 梯度下降法 梯度下降法是一种通过迭代来求取极值的方法，它使用目标函数的一阶导数信息，每次迭代取目标函数下降最快的方向作为搜索方向，即梯度的反方向。下面首先说明为什么目标函数下降最快的方向为梯度的反方向，然后再继续说明梯度下降法。 搜索方向 假设目前已经经过了$k-1$次迭代，到达第$k$次迭代。选择自变量$x_k$处，对函数$f(x)$进行一阶泰勒展开，可以得到： $$ f(x)=f(x_k)+\nabla f(x_k)(x-x_k)+o(x) $$ 其中$o(x)$相对一阶泰勒为无穷小量，可以近似忽略，而$\nabla f(x_k)$是一个具体数值，表示函数$f(x)$在点$x_k$处的梯度值。结合上式，可以看作对于$f(x)$，是从$f(x_k)$出发，$x-x_k$是下一步的方向，记作$\alpha g$，$\alpha g$具体含义可以视作$x$沿着单位向量$g\in R^n$的方向迭代，$\alpha$表示步长参数。此时可以结合前文提到的含义，对一阶泰勒展开进行变形： $$ f(x_k)-f(x)=-\nabla f(x_k)(x-x_k)=-\alpha \nabla f(x_k)g $$ 参考无约束优化的基本问题，是希望函数$f(x)$的取值尽可能小，即希望每一次迭代$f(x_k)-f(x)$尽可能大。上式中，步长参数$\alpha>0$，可以认为极大化$f(x_k)-f(x)$等价于： $$ \min \nabla f(x_k)\cdot g $$ 其中$\nabla f(x_k)\cdot g$表示两个向量的乘积，显然，两个向量方向相反时便能取得最小值，如果希望迭代后的目标函数能够以最快速度下降，迭代的方向$g$应该是$\nabla f(x_k)$的反方向，也即梯度的反方向，此时$x$沿着$-\nabla f(x)$的方向前进便能得到极小值。 综上所述，梯度下降法的算法如下： $$ x^{k+1}\coloneqq x^k-\alpha\nabla f(x_k) $$ 牛顿法 牛顿法不同于梯度下降法，在于牛顿法额外引入了二阶导数信息。假设目前已经经过了$k-1$次迭代，到达第$k$次迭代，应用二阶泰勒展开对目标函数在自变量$x_k$处进行展开： $$ f(x)=f(x_k)+\nabla f(x_k)(x-x_k)+(x-x_k)^T\frac{\nabla^2 f(x_k)}{2}(x-x_k)+o(x^2) $$ 同理，无穷小量$o(x^2)$相对于二阶泰勒展开可以近似忽略。当上式导数为 0 时，得到的点即可作为下一次自变量的值$x_{k+1}$。 对等式两侧同时对$x$进行求导，令导数为 0 求得的极值点即为下一次迭代的取值$x_{k+1}$： ...