2.7.2.3 牛顿和拟牛顿法

2.7.2.3.1 牛顿法: 使用Hessian (二阶微分))

牛顿法使用局部二元近似来计算跳跃的方向。为了这个目的，他们依赖于函数的前两个导数梯度和Hessian。

状况糟糕的二元函数:

注意，因为二元近似是精确的，牛顿法是非常快的。

状况糟糕的非二元函数:

这里我们最优化高斯分布，通常在它的二元近似的下面。因此，牛顿法超调量并且导致震荡。

状况糟糕的极端非二元函数:

在scipy中, 最优化的牛顿法在scipy.optimize.fmin_ncg()实现 (cg这里是指一个内部操作的事实，Hessian翻转, 使用共轭梯度来进行)。scipy.optimize.fmin_tnc() 可以被用于限制问题，尽管没有那么多用途:

In [7]:

def f(x):   # rosenbrock函数
    return .5*(1 - x[0])**2 + (x[1] - x[0]**2)**2
def fprime(x):
    return np.array((-2*.5*(1 - x[0]) - 4*x[0]*(x[1] - x[0]**2), 2*(x[1] - x[0]**2)))
optimize.fmin_ncg(f, [2, 2], fprime=fprime)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 9
         Function evaluations: 11
         Gradient evaluations: 51
         Hessian evaluations: 0

Out[7]:

array([ 1.,  1.])

注意与共轭梯度（上面的）相比，牛顿法需要较少的函数评估，更多的梯度评估，因为它使用它近似Hessian。让我们计算Hessian并将它传给算法:

In [7]:

def hessian(x): # Computed with sympy
    return np.array(((1 - 4*x[1] + 12*x[0]**2, -4*x[0]), (-4*x[0], 2)))
optimize.fmin_ncg(f, [2, 2], fprime=fprime, fhess=hessian)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 9
         Function evaluations: 11
         Gradient evaluations: 19
         Hessian evaluations: 9

Out[7]:

array([ 1.,  1.])

注意：在超高维，Hessian的翻转代价高昂并且不稳定 (大规模 > 250)。

注意：牛顿最优化算法不应该与基于相同原理的牛顿根发现法相混淆，scipy.optimize.newton()。

2.7.2.3.2 拟牛顿方法: 进行着近似Hessian

BFGS: BFGS (Broyden-Fletcher-Goldfarb-Shanno算法) 改进了每一步对Hessian的近似。

状况糟糕的二元函数:

在准确的二元函数中, BFGS并不像牛顿法那么快，但是还是很快。

状况糟糕的非二元函数:

这种情况下BFGS比牛顿好, 因为它的曲度经验估计比Hessian给出的好。

状况糟糕的极端非二元函数:

In [9]:

def f(x):   # rosenbrock函数
    return .5*(1 - x[0])**2 + (x[1] - x[0]**2)**2
def fprime(x):
    return np.array((-2*.5*(1 - x[0]) - 4*x[0]*(x[1] - x[0]**2), 2*(x[1] - x[0]**2)))
optimize.fmin_bfgs(f, [2, 2], fprime=fprime)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 16
         Function evaluations: 24
         Gradient evaluations: 24

Out[9]:

array([ 1.00000017,  1.00000026])

L-BFGS: 限制内存的BFGS介于BFGS和共轭梯度之间: 在非常高的维度 (> 250) 计算和翻转的Hessian矩阵的成本非常高。L-BFGS保留了低秩的版本。此外，scipy版本, scipy.optimize.fmin_l_bfgs_b(), 包含箱边界:

In [8]:

def f(x):   # rosenbrock函数
    return .5*(1 - x[0])**2 + (x[1] - x[0]**2)**2
def fprime(x):
    return np.array((-2*.5*(1 - x[0]) - 4*x[0]*(x[1] - x[0]**2), 2*(x[1] - x[0]**2)))
optimize.fmin_l_bfgs_b(f, [2, 2], fprime=fprime)

Out[8]:

(array([ 1.00000005,  1.00000009]),
 1.4417677473011859e-15,
 {'funcalls': 17,
  'grad': array([  1.02331202e-07,  -2.59299369e-08]),
  'nit': 16,
  'task': 'CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL',
  'warnflag': 0})

注意：如果你不为L-BFGS求解器制定梯度，你需要添加approx_grad=1