优化算法——拟牛顿法之L-BFGS算法

时间：2023-03-10 04:10:37
优化算法——拟牛顿法之L-BFGS算法

一、BFGS算法

在“优化算法——拟牛顿法之BFGS算法”中，我们得到了BFGS算法的校正公式：

优化算法——拟牛顿法之L-BFGS算法

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

优化算法——拟牛顿法之L-BFGS算法

令优化算法——拟牛顿法之L-BFGS算法，则得到：

优化算法——拟牛顿法之L-BFGS算法

二、BGFS算法存在的问题

在BFGS算法中。每次都要存储近似Hesse矩阵优化算法——拟牛顿法之L-BFGS算法

B_k^{-1}" title="B_k^{-1}" alt="" />，在高维数据时，存储优化算法——拟牛顿法之L-BFGS算法浪费非常多的存储空间，而在实际的运算过程中。我们须要的是搜索方向。因此出现了L-BFGS算法。是对BFGS算法的一种改进算法。

在L-BFGS算法中。仅仅保存近期的优化算法——拟牛顿法之L-BFGS算法次迭代信息。以减少数据的存储空间。

三、L-BFGS算法思路

令优化算法——拟牛顿法之L-BFGS算法

\rho&space;_k=\frac{1}{y_k^Ts_k}" title="\rho _k=\frac{1}{y_k^Ts_k}" alt="" />。优化算法——拟牛顿法之L-BFGS算法

V_k=I-\frac{y_ks_k^T}{y_k^Ts_k}" title="V_k=I-\frac{y_ks_k^T}{y_k^Ts_k}" alt="" />，则BFGS算法中的优化算法——拟牛顿法之L-BFGS算法

H_{k+1}" title="H_{k+1}" alt="" />能够表示为：

优化算法——拟牛顿法之L-BFGS算法

若在初始时，假定初始的矩阵优化算法——拟牛顿法之L-BFGS算法

H_0=I" title="H_0=I" alt="" />，则我们能够得到：

优化算法——拟牛顿法之L-BFGS算法

H_{1}=V_0^TH_0V_0+\rho&space;_0s_0s_0^T" title="H_{1}=V_0^TH_0V_0+\rho _0s_0s_0^T" alt="" />

优化算法——拟牛顿法之L-BFGS算法

\begin{align*}&space;H_2&space;&=&space;V_1^TH_1V_1+\rho&space;_1s_1s_1^T\\&space;&=&space;V_1^T\left&space;(&space;V_0^TH_0V_0+\rho&space;_0s_0s_0^T&space;\right&space;)V_1+\rho&space;_1s_1s_1^T\\&space;&=&space;V_1^TV_0^TH_0V_0V_1+V_1^T\rho&space;_0s_0s_0^TV_1+\rho&space;_1s_1s_1^T&space;\end{align*}" title="\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*}" alt="" />

优化算法——拟牛顿法之L-BFGS算法

优化算法——拟牛顿法之L-BFGS算法

若此时。仅仅保留近期的优化算法——拟牛顿法之L-BFGS算法步：

优化算法——拟牛顿法之L-BFGS算法

\begin{align*}&space;H_{k+1}&space;&=&space;\left&space;(&space;V_k^TV_{k-1}^T\cdots&space;V_{k-m}^T&space;\right&space;)H_0\left&space;(&space;V_{k-m}\cdots&space;V_{k-1}V_k&space;\right&space;)\\&space;&+&space;\left&space;(&space;V_k^TV_{k-1}^T\cdots&space;V_{k-m}^T&space;\right&space;)\rho&space;_1s_1s_1^T\left&space;(&space;V_{k-m}\cdots&space;V_{k-1}V_k&space;\right&space;)\\&space;&+&space;\cdots&space;\\&space;&+&space;V_k^T\rho&space;_{k-1}s_{k-1}s_{k-1}^TV_k\\&space;&+&space;\rho&space;_ks_ks_k^T&space;\end{align*}" title="\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*}" alt="" />

这样在L-BFGS算法中。不再保存完整的优化算法——拟牛顿法之L-BFGS算法

H_k" title="H_k" alt="" />。而是存储向量序列优化算法——拟牛顿法之L-BFGS算法和优化算法——拟牛顿法之L-BFGS算法。须要矩阵优化算法——拟牛顿法之L-BFGS算法时，使用向量序列优化算法——拟牛顿法之L-BFGS算法

\left&space;\{&space;s_k&space;\right&space;\}" title="\left \{ s_k \right \}" alt="" style="font-family:KaiTi_GB2312; font-size:18px" />和优化算法——拟牛顿法之L-BFGS算法计算就能够得到。而向量序列优化算法——拟牛顿法之L-BFGS算法和优化算法——拟牛顿法之L-BFGS算法也不是全部都要保存，仅仅要保存最新的优化算法——拟牛顿法之L-BFGS算法步向量就可以。

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

优化算法——拟牛顿法之L-BFGS算法

五、实验仿真

lbfgs.py

#coding:UTF-8

from 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 *

#fun

def fun(x):

    return 100 * (x[0,0] ** 2 - x[1,0]) ** 2 + (x[0,0] - 1) ** 2

#gfun

def 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 result

n = len(result)

ax = plt.figure().add_subplot(111)

x = arange(0, n, 1)

y = result

ax.plot(x,y)

plt.show()

实验结果

优化算法——拟牛顿法之L-BFGS算法

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZ2xlMTk4OTAxMDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="" />

參考文献

相关文章