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

一、BFGS算法简介

BFGS算法是使用较多的一种拟牛顿方法,是由Broyden,Fletcher,Goldfarb,Shanno四个人分别提出的,故称为BFGS校正。

    同DFP校正的推导公式一样,DFP校正见博文“优化算法——拟牛顿法之DFP算法”。对于拟牛顿方程:

可以化简为:

则可得:

在BFGS校正方法中,假设:

二、BFGS校正公式的推导   

三、BFGS校正的算法流程

BFGS拟牛顿法的算法流程:

四、求解具体优化问题

   求解无约束优化问题

其中,

python程序实现:

  1. 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
  1. bfgs.py#
#coding:UTF-8  
  
from numpy import *  
from function import *  
  
def bfgs(fun, gfun, x0):  
    result = []  
    maxk = 500  
    rho = 0.55  
    sigma = 0.4  
    m = shape(x0)[0]  
    Bk = eye(m)  
    k = 0  
    while (k < maxk):  
        gk = mat(gfun(x0))#计算梯度  
        dk = mat(-linalg.solve(Bk, gk))  
        m = 0  
        mk = 0  
        while (m < 20):  
            newf = fun(x0 + rho ** m * dk)  
            oldf = fun(x0)  
            if (newf < oldf + sigma * (rho ** m) * (gk.T * dk)[0,0]):  
                mk = m  
                break  
            m = m + 1  
          
        #BFGS校正  
        x = x0 + rho ** mk * dk  
        sk = x - x0  
        yk = gfun(x) - gk  
        if (yk.T * sk > 0):  
            Bk = Bk - (Bk * sk * sk.T * Bk) / (sk.T * Bk * sk) + (yk * yk.T) / (yk.T * sk)  
          
        k = k + 1  
        x0 = x  
        result.append(fun(x0))  
      
    return result  
  1. testBFGS.py#
#coding:UTF-8  
''''' 
Created on 2015年5月19日 
 
@author: zhaozhiyong 
'''  
  
from bfgs import *  
  
import matplotlib.pyplot as plt    
  
x0 = mat([[-1.2], [1]])  
result = bfgs(fun, gfun, x0)  
  
n = len(result)  
ax = plt.figure().add_subplot(111)  
x = arange(0, n, 1)  
y = result  
ax.plot(x,y)  
  
plt.show() 

五、实验结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【论文推荐】最新十篇推荐系统相关论文—内容感知、图卷积神经网络、博弈论、个性化排序、元学习、xDeepFM

【导读】专知内容组既前两天推出十六篇推荐系统相关论文之后,今天为大家又推出十篇推荐系统(Recommendation System)相关论文,欢迎查看!

3123
来自专栏算法channel

算法channel关键词和文章索引

希望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1Tags 排序算法 链表 树 图 动态规划 ...

3365
来自专栏深度学习自然语言处理

如何用简单易懂的例子解释隐马尔可夫模型?(入门篇)

因为文章总共超过5W字,所以我分为两部分,今天这是第一部分,先自己大致了解下什么是HMM,明天将会是具体的通俗公式讲解。加油,每天进步一丢丢O.O

1144
来自专栏数据科学学习手札

(数据科学学习手札22)主成分分析法在Python与R中的基本功能实现

上一篇中我们详细介绍推导了主成分分析法的原理,并基于Python通过自编函数实现了挑选主成分的过程,而在Python与R中都有比较成熟的主成分分析函数,本篇我们...

40310
来自专栏生信小驿站

主成分分析①

principal() 含多种可选的方差旋转方法的主成分分析 fa() 可用主轴、最小残差、加权最小平方或最大似然法估计的因子分析 fa.paralle...

892
来自专栏大数据挖掘DT机器学习

机器学习&数据挖掘知识点大总结

Basis(基础): MSE(Mean Square Error 均方误差), LMS(LeastMean Square 最小均方), LSM(L...

40514
来自专栏机器学习算法与Python学习

常用机器学习与数据挖掘相关术语(该充充电了...)

Sampling(采样): Simple Random Sampling(简单随机采样), OfflineSampling(离线等可能K...

3157
来自专栏机器学习算法原理与实践

用scikit-learn学习LDA主题模型

    在LDA模型原理篇我们总结了LDA主题模型的原理,这里我们就从应用的角度来使用scikit-learn来学习LDA主题模型。除了scikit-learn...

3673
来自专栏PPV课数据科学社区

【学习】常用的机器学习&数据挖掘知识点

Basis(基础): MSE(Mean Square Error 均方误差),LMS(LeastMean Square 最小均方),LSM(Least Squa...

35512
来自专栏Small Code

【TensorFlow】TensorFlow的线性回归

前面 有篇博文 讲了讲Ubuntu环境下安装TensorFlow,今天来说一说在TensorFlow中如何进行线性回归。 训练数据 本次使用的训练数据是美国房价...

4779

扫码关注云+社区