二阶优化方法

对于优化方法Optimization，大体而言，有如下几类：

• 基于梯度的优化, 一阶方法  (Gradient-based optimization 1st order methods) 
• 
  
  •  plain grad, steepest descent, conjugate grad., Rprop, stochastic grad.
  • adaptive stepsize heuristics
•  约束优化 Constrained Optimization 
• 
  
  • squared penalties, augmented Lagrangian, log barrier
  • Lagrangian, KKT conditions, Lagrange dual, log barrier ↔ approx. KKT
• 二阶方法 2nd order methods 
• 
  
  • Newton, Gauss-Newton, Quasi-Newton, (L)BFGS 
  • constrained case, primal-dual Newton
• Special convex cases 
• 
  
  • 线性规划；二次规划；Linear Programming, (sequential) Quadratic Programming
  • Simplex algorithm
  • relation to relaxed discrete optimization
•  Black box optimization (“0th order methods”) 
• 
  
  • 黑盒随机搜索  - blackbox stochastic search
  • Markov Chain Monte Carlo methods
  • 遗传算法 - evolutionary algorithms

到目前为止，在无约束和有约束的情况下，我们仅依赖于基于梯度的方法。而现在，二阶方法局部地逼近f(x)：

• 使用二阶泰勒展开式（给定 Hessian \triangledown ^2 f(x) ）
• 从数据估计Hessian

二阶方法只有在Hessian到处都是正定的时才起作用↔f（x）是凸的。注-局部地或全局地逼近f(x)也是黑盒优化中的它的核心概念。

为什么二阶优化优于梯度？

1.它拥有更好的方向,如下图所示：

 2.步长更佳:

• 一整步直接跳至局部平方的近似最小值。 
• 通常这已经是一个很好的启发式方法 
• 额外的步长减小是直线的 

• Their application on constrained problems

二阶方法有：

• 牛顿
• 高斯-牛顿 Gauss-Newton 
• 拟牛顿 Quasi-Newton 
• BFGS（Broyden–Fletcher–Goldfarb–Shanno algorithm），(L)BFGS （Limited-memory BFGS）（避免求解Hessian矩阵）

符号：

目标函数：

f:\mathbb{R}^n \rightarrow \mathbb{R} 

梯度向量:

\triangledown f(x)=[\frac{\partial }{\partial _x}f(x)]^T \in \mathbb{R}^n

Hessian (symmetric matrix) （对称矩阵）：

\triangledown^2 f(x)=\begin{bmatrix}
 \frac{\partial^2 }{\partial _{x_1}\partial _{x_1}}f(x)&  \frac{\partial^2 }{\partial _{x_1}\partial _{x_2}}f(x) & ... & \frac{\partial^2 }{\partial _{x_1}\partial _{x_n}}f(x) \\ 
  \frac{\partial^2 }{\partial _{x_1}\partial _{x_2}}f(x)&  &  & \vdots \\ 
\vdots  &  &  & \vdots \\ 
  \frac{\partial^2 }{\partial _{x_n}\partial _{x_2}}f(x) & ... & ... &   \frac{\partial^2 }{\partial _{x_n}\partial _{x_n}}f(x)
\end{bmatrix}

 \in \mathbb{R}^{n\times n}
 
 
 

泰勒展开式（泰勒公式一句简单的描述：就是用多项式函数去逼近光滑函数）：

f(x')=f(x)+(x'-x)^T \triangledown f(x')=f(x) + \frac{1}{2}(x'-x)\triangledown^2f(x)(x'-x)

最终优化问题的定义：

min_x f(x)

为了找到f(x)的根（零点）

 上图是使用一阶信息来更新x的走向。为了找到一阶梯度的f(x)的根（零点）

x \leftarrow x-\frac{f'(x)}{f''(x)}

对所有的x \in \mathbb{R}^n：

x \leftarrow x- \triangledown ^2 f(x)^{-1} \triangledown f(x)

这就是使用二阶梯度信息对x进行跟新。Hessian 方法拥有O(N^2)个元素，H^{-1}拥有O(N^3)个元素。这里N是参数的值；所以二阶方法不会用在mainstream DL架构中。

Newton method：下图是自适应的步长为 α 的伪代码如下：

 第3行计算牛顿步长 。 第三行是对于泰特展开式的求解，即二次函数（抛物线函数）求最小值，第三行是对泰特展开式中的函数求导：也就是对目标函数求导。求出步长后，更新x值，来寻找最优值。

 \triangle=\triangledown^2f(x)^{-1} \triangledown f(x)

使用特殊的Lapack例程Dposv来求解Ax=b（使用Cholesky分解）

-λ称为damping，也就是抛物线绕目前x的“陡峭”程度。 当λ→∞时，当\lambda \rightarrow \infty，Δ与-\bigtriangledown f(x)共线性，但|Δ|=0 。

【来源：https://ipvs.informatik.uni-stuttgart.de/mlr/marc/teaching/13-Optimization/04-secondOrderOpt.pdf 】

发展历史

描述

优化算法已经有很悠远的历史了。

“牛顿法”一词源于Isaac Newton在De Analysi per Aequationes Numero terminorum Infinitas（写于1669年，由William Jones出版于1711年）和De Metodis Fluxionum et Serierum Infinitarum（写于1671年，由John Colson翻译出版于1736年）中对该方法的一种特殊情况的描述。 然而，他的方法与上面给出的现代方法有很大的不同:牛顿只应用于多项式。 他不计算逐次逼近x_n，而是计算一个多项式序列，并且只在末尾得到根x的逼近。 最后，牛顿认为这种方法是纯代数的，而没有提到它与微积分的联系。 牛顿可能是从越南的一个类似但不太精确的方法推导出他的方法的。

Vieta方法的精髓可以在波斯数学家Sharaf al-Din al-Tusi的工作中找到，而他的继任者Jamshíd al-Káshí(Ypma 1995)使用牛顿方法的一种形式来求解x^p−n=0来寻找n的根。 计算平方根的牛顿法的一个特例很早就为人所知，通常称为巴比伦法。

17世纪日本数学家关泽明（Seki Kówa)用牛顿法解一元方程组，但与微积分的联系并不存在。

牛顿方法最早发表于1685年约翰·沃利斯的《A Treatise of Algebra both Historical and Practical 》中。1690年，Joseph Raphson在《Analysis aequationum universalis》中发表了一篇简明的描述。Raphson再次把牛顿的方法看作纯粹的代数方法，并把它的使用限制在多项式上，但他用逐次逼近x_n来描述方法，而不是用牛顿使用的更复杂的多项式序列。 最后，在1740年，Thomas Simpson将牛顿法描述为使用微积分求解一般非线性方程组的迭代方法，本质上也给出了上述描述。 在同一篇文章中，Simpson还对两个方程组进行了推广，并指出牛顿法可以通过将梯度设为零来求解优化问题。

1879年，Arthur Cayley在Newton-Fourier假想问题中首次注意到将Newton方法推广到次数大于2且初值复杂的多项式复根的困难。 这为有理函数迭代理论的研究开辟了道路。

第一个拟牛顿算法是由Argonne国家实验室的物理学家William C.Davidon提出的。 他在1959年开发了第一个拟牛顿算法:DFP（Davidon–Fletcher–Powell formula）更新公式，后来由Fletcher和Powell在1963年推广，但现在很少使用。 目前最常用的拟牛顿算法是SR1公式（用于“对称秩一”）、BHHH方法、BFGS方法（由Broyden、Fletcher、Goldfarb和Shanno在1970年提出的方法）及其低内存扩展算法L-BFGS。 Broyden类是DFP和BFGS方法的线性组合。

BFGS是以Charles George Broyden, Roger Fletcher, Donald Goldfarb 和 David Shanno命名的算法。

在拟牛顿法中，不需要计算Hessian矩阵。 Hessian是通过分析连续梯度向量来更新的。 拟牛顿法是求高维问题一阶导数根的割线法的推广。 在多维空间中，割线方程是欠定的，而拟牛顿方法在约束解的方式上是不同的，通常是通过在Hessian的当前估计上添加一个简单的低秩更新。

主要事件

发展分析

瓶颈

对于牛顿方法来说，使用这种方法的缺点很多。 首先，如果我们选择一个离精确根太远的x_0，并不能保证牛顿法会收敛。 同样，如果我们的切线变得平行或几乎平行于X轴，我们不能保证用这种方法收敛。 而且，由于每次迭代都要计算两个函数f(x_k)和f'(x_k)，因此该方法的计算量很大。 另一个缺点是，我们必须有一个函数表示函数的导数。只从给定的数据来说，这不是总是可能的。

牛顿法的优点是收敛速度快，缺点是在用牛顿法进行最优化求解的时候需要求解Hessian矩阵。

【来源：https://en.wikiversity.org/wiki/The_Newton%27s_method 】

未来发展方向

尽管另外两种优化方法Nelder-Mead 和simulated annealing两者不需要梯度信息，因此在梯度不可用或无法计算时很有用（但可能会更慢，并且需要更多的参数微调）。 二阶方法的求导固然好，但是计算量大也是它的一个软肋，如何减小计算量是一个值得思考的问题。对于二阶方法是有使用限制的，并不是对所有的数据都可以用。对于二阶方法的普适性可以进一步研究。

【来源：智能图像处理如何实现机器视觉及其应用的高效智能？  】

Contributor : Ruiying Cai