机器学习算法1牛顿法,拟牛顿法,DFP,BFGS,L-BFGS 原理及代码详解(3)

川长思鸟来 2022-05-27 12:21 159阅读 0赞

![70][]

![70 1][]

![70 2][]

![70 3][]

######################## 拟牛顿_BFGS算法#######################
    
    #算法描述:
    '''
    BFGS算法与DFP步骤基本相同，区别在于更新公式的差异
    '''
    def bfgs(fun,gfun,hess,x0):
        #功能：用BFGS族算法求解无约束问题：min fun(x)
        #输入：x0是初始点，fun,gfun分别是目标函数和梯度
        #输出：x,val分别是近似最优点和最优解,k是迭代次数  
        maxk = 1e5#最大迭代次数
        rho = 0.55#非线性搜索中的B因子
        sigma = 0.4#非线性搜索中的δ因子
        epsilon = 1e-5#设定迭代终止得的阈值
        k = 0#初始化迭代次数
        n = np.shape(x0)[0]#用于初始化海森单位矩阵和校正部分
        #海森矩阵可以初始化为单位矩阵
        Bk = np.eye(n)#np.linalg.inv(hess(x0)) #或者单位矩阵np.eye(n)
    
        while k < maxk:
            gk = gfun(x0)#计算得到梯度
            if np.linalg.norm(gk) < epsilon:
                break
            dk = -1.0*np.linalg.solve(Bk,gk)#计算得到步向
            m = 0#初始化搜索步长次数
            mk = 0#用于返回搜索步长最小非负整数m
            while m < 20: # 用Armijo搜索求步长
                if fun(x0+rho**m*dk) < fun(x0)+sigma*rho**m*np.dot(gk,dk):
                    mk = m
                    break
                m += 1
    
            #BFGS校正
            x = x0 + rho**mk*dk#更新x的值
            sk = x - x0#更新x后计算sk
            yk = gfun(x) - gk#更新x后计算计算yk
    
            if np.dot(sk,yk) > 0:    
                Bs = np.dot(Bk,sk)
                ys = np.dot(yk,sk)
                sBs = np.dot(np.dot(sk,Bk),sk) 
    
                Bk = Bk - 1.0*Bs.reshape((n,1))*Bs/sBs + 1.0*yk.reshape((n,1))*yk/ys
    
            k += 1
            x0 = x#更新x0,k,进行下一次循环
    
        return x0,fun(x0),k#分别是最优点坐标，最优值，迭代次数 
    
    #print(bfgs(fun,gfun,hess,[6,10]))#海森矩阵初始化为单位矩阵,大部分情形优于dfp算法

#(array([1., 1.]), 4.7269333203271764e-20, 46)

[70]: /images/20220527/abb2839f370b4c978c3e7cc0a39fe071.png
[70 1]: /images/20220527/1beb5730a10b4d90bf7f6ef804a54390.png
[70 2]: /images/20220527/5df3c505c13b4f99a1d505245c7e371c.png
[70 3]: /images/20220527/2bf3d49b777c4ceeb7242ee66398320b.png