一、BFGS算法

在“”中，我们得到了BFGS算法的校正公式：

$B_{k+1}=B_k-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k}+\frac{y_ky_k^T}{y_k^Ts_k}$

利用Sherman-Morrison公式可对上式进行变换，得到

$B_{k+1}^{-1}=\left ( I-\frac{s_ky_k^T}{y_k^Ts_k} \right )B_k^{-1}\left ( I-\frac{y_ks_k^T}{y_k^Ts_k} \right )+\frac{s_ks_k^T}{y_k^Ts_k}$

令 $H_{k+1}=B_{k+1}^{-1}$ ，则得到：

$H_{k+1}=\left ( I-\frac{s_ky_k^T}{y_k^Ts_k} \right )H_k\left ( I-\frac{y_ks_k^T}{y_k^Ts_k} \right )+\frac{s_ks_k^T}{y_k^Ts_k}$

二、BGFS算法存在的问题

在BFGS算法中。每次都要存储近似Hesse矩阵 $B_k^{-1}$ ，在高维数据时，存储 $B_k^{-1}$ 浪费非常多的存储空间，而在实际的运算过程中。我们须要的是搜索方向。因此出现了L-BFGS算法。是对BFGS算法的一种改进算法。

在L-BFGS算法中。仅仅保存近期的 $m$ 次迭代信息。以减少数据的存储空间。

三、L-BFGS算法思路

令 $\rho _k=\frac{1}{y_k^Ts_k}$ 。 $V_k=I-\frac{y_ks_k^T}{y_k^Ts_k}$ ，则BFGS算法中的 $H_{k+1}$ 能够表示为：

$H_{k+1}=V_k^TH_kV_k+\rho _ks_ks_k^T$

若在初始时，假定初始的矩阵，则我们能够得到：

$H_{1}=V_0^TH_0V_0+\rho _0s_0s_0^T$

$\begin{align*} H_2 &= V_1^TH_1V_1+\rho _1s_1s_1^T\\ &= V_1^T\left ( V_0^TH_0V_0+\rho _0s_0s_0^T \right )V_1+\rho _1s_1s_1^T\\ &= V_1^TV_0^TH_0V_0V_1+V_1^T\rho _0s_0s_0^TV_1+\rho _1s_1s_1^T \end{align*}$

$\cdots$

$\begin{align*} H_{k+1} &= \left ( V_k^TV_{k-1}^T\cdots V_1^TV_0^T \right )H_0\left ( V_0V_1\cdots V_{k-1}V_k \right )\\ &+ \left ( V_k^TV_{k-1}^T\cdots V_1^T \right )\rho _1s_1s_1^T\left ( V_1\cdots V_{k-1}V_k \right )\\ &+ \cdots \\ &+ V_k^T\rho _{k-1}s_{k-1}s_{k-1}^TV_k\\ &+ \rho _ks_ks_k^T \end{align*}$

若此时。仅仅保留近期的 $m$ 步：

$\begin{align*} H_{k+1} &= \left ( V_k^TV_{k-1}^T\cdots V_{k-m}^T \right )H_0\left ( V_{k-m}\cdots V_{k-1}V_k \right )\\ &+ \left ( V_k^TV_{k-1}^T\cdots V_{k-m}^T \right )\rho _1s_1s_1^T\left ( V_{k-m}\cdots V_{k-1}V_k \right )\\ &+ \cdots \\ &+ V_k^T\rho _{k-1}s_{k-1}s_{k-1}^TV_k\\ &+ \rho _ks_ks_k^T \end{align*}$

这样在L-BFGS算法中。不再保存完整的。而是存储向量序列 $\left \{ s_k \right \}$ 和 $\left \{ y_k \right \}$ 。须要矩阵 $H_k$ 时，使用向量序列 $\left \{ s_k \right \}$ 和 $\left \{ y_k \right \}$ 计算就能够得到。而向量序列 $\left \{ s_k \right \}$ 和 $\left \{ y_k \right \}$ 也不是全部都要保存，仅仅要保存最新的 $m$ 步向量就可以。

四、L-BFGS算法中的方向的计算方法

五、实验仿真

lbfgs.py

#coding:UTF-8from numpy import *from function import *def lbfgs(fun, gfun, x0):    result = []#保留终于的结果    maxk = 500#最大的迭代次数    rho = 0.55    sigma = 0.4        H0 = eye(shape(x0)[0])        #s和y用于保存近期m个，这里m取6    s = []    y = []    m = 6        k = 1    gk = mat(gfun(x0))#计算梯度    dk = -H0 * gk    while (k < maxk):                     n = 0        mk = 0        gk = mat(gfun(x0))#计算梯度        while (n < 20):            newf = fun(x0 + rho ** n * dk)            oldf = fun(x0)            if (newf < oldf + sigma * (rho ** n) * (gk.T * dk)[0, 0]):                mk = n                break            n = n + 1                #LBFGS校正        x = x0 + rho ** mk * dk        #print x                #保留m个        if k > m:            s.pop(0)            y.pop(0)                    #计算最新的        sk = x - x0        yk = gfun(x) - gk                s.append(sk)        y.append(yk)                #two-loop的过程        t = len(s)        qk = gfun(x)        a = []        for i in xrange(t):            alpha = (s[t - i - 1].T * qk) / (y[t - i - 1].T * s[t - i - 1])            qk = qk - alpha[0, 0] * y[t - i - 1]            a.append(alpha[0, 0])        r = H0 * qk                    for i in xrange(t):            beta = (y[i].T * r) / (y[i].T * s[i])            r = r + s[i] * (a[t - i - 1] - beta[0, 0])                    if (yk.T * sk > 0):            dk = -r                            k = k + 1        x0 = x        result.append(fun(x0))        return result

function.py

#coding:UTF-8'''Created on 2015年5月19日@author: zhaozhiyong'''from numpy import *#fundef fun(x):    return 100 * (x[0,0] ** 2 - x[1,0]) ** 2 + (x[0,0] - 1) ** 2#gfundef gfun(x):    result = zeros((2, 1))    result[0, 0] = 400 * x[0,0] * (x[0,0] ** 2 - x[1,0]) + 2 * (x[0,0] - 1)    result[1, 0] = -200 * (x[0,0] ** 2 - x[1,0])    return result

testLBFGS.py

#coding:UTF-8'''Created on 2015年6月6日@author: zhaozhiyong'''from lbfgs import *import matplotlib.pyplot as plt  x0 = mat([[-1.2], [1]])result = lbfgs(fun, gfun, x0)print resultn = len(result)ax = plt.figure().add_subplot(111)x = arange(0, n, 1)y = resultax.plot(x,y)plt.show()

实验结果

參考文献

你可能感兴趣的文章