优化算法——拟牛顿法之BFGS算法
一、BFGS算法简介
BFGS算法是使用较多的一种拟牛顿方法，是由Broyden，Fletcher，Goldfarb，Shanno四个人分别提出的，故称为BFGS校正。
同DFP校正的推导公式一样，DFP校正见博文“优化算法——拟牛顿法之DFP算法”。对于拟牛顿方程：
可以化简为：
令
则可得：
在BFGS校正方法中，假设：
二、BFGS校正公式的推导
三、BFGS校正的算法流程
BFGS拟牛顿法的算法流程：
四、求解具体优化问题
求解无约束优化问题
其中，
python程序实现：
- 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
- 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 - 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() 五、实验结果
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录