二阶优化方法

最优化方法,是指解决最优化问题的方法。所谓最优化问题,指在某些约束条件下,决定某些可选择的变量应该取何值,使所选定的目标函数达到最优的问题。即运用最新科技手段和处理方法,使系统达到总体最优,从而为系统提出设计、施工、管理、运行的最优方案。

来源:百度百科
简介

对于优化方法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.它拥有更好的方向,如下图所示:

image.png 2.步长更佳:

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

• Their application on constrained problems

二阶方法有:

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

符号:

目标函数:

image.png

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

梯度向量:

image.png

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

Hessian (symmetric matrix) (对称矩阵):


image.png

\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}
 
 
 

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

image.png

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

最终优化问题的定义:

image.png

min_x f(x)

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

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

Screen Shot 2018-12-31 at 11.01.07 AM.png

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

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

Screen Shot 2018-12-31 at 11.02.20 AM.png

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:下图是自适应的步长为 α 的伪代码如下:

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

image.png \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的当前估计上添加一个简单的低秩更新。

主要事件

年份事件相关论文/Reference
1685约翰·沃利斯的最早发表牛顿方法Wallis, J. (2007). A treatise of algebra, both historical and practical.
1959William C.Davidon1959年开发了第一个拟牛顿算法Davidon, W. C. (1991). Variable metric method for minimization. SIAM Journal on Optimization, 1(1), 1-17.
1970BFGS方法(由Broyden、Fletcher、Goldfarb和Shanno提出的方法)  Avriel, M. (2003). Nonlinear programming: analysis and methods. Courier Corporation.  
1981  Gill, P. E., Murray, W., & Wright, M. H.   对优化算法进行优化Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical optimization.
1992Fischer, A.提出一个特殊的牛顿优化方法Fischer, A. (1992). A special Newton-type optimization method. Optimization, 24(3-4), 269-284.
2010Martens, J.将Hessian-free优化加入到深度学习中Martens, J. (2010, June). Deep learning via Hessian-free optimization. In ICML (Vol. 27, pp. 735-742).
2018Gower, R. M.提出了使用二阶梯度方法加速随机举证转换Gower, R. M., Hanzely, F., Richtárik, P., & Stich, S. (2018). Accelerated stochastic matrix inversion: general theory and speeding up BFGS rules for faster second-order optimization. arXiv preprint arXiv:1802.04079.

发展分析

瓶颈

对于牛顿方法来说,使用这种方法的缺点很多。 首先,如果我们选择一个离精确根太远的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

相关人物
David Shanno
David Shanno
Donald Goldfarb
Donald Goldfarb
Roger Fletcher
Roger Fletcher
多里戈
多里戈
Holger Hoos
Holger Hoos
德裔加拿大计算机科学家、莱顿大学的机器学习教授、 AAAI 会员。他的研究兴趣集中在经验算法上,应用于人工智能、生物信息学和运筹学。
简介
相关人物