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

article/2025/8/26 14:37:54

一、BFGS算法简介

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

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

$\bigtriangledown f\left ( x_k \right )=\bigtriangledown f\left ( x_{k+1} \right )+G_{k+1}\left ( x_k-x_{k+1} \right )$

可以化简为：

$G_{k+1}\left ( x_{k+1}-x_{k} \right )=\bigtriangledown f\left ( x_{k+1} \right )-\bigtriangledown f\left ( x_{k} \right )$

令 $B_{k+1}\overset{\bigtriangleup }{=}G_{k+1}$ ，则可得：

$B_{k+1}\left ( x_{k+1}-x_{k} \right )=\bigtriangledown f\left ( x_{k+1} \right )-\bigtriangledown f\left ( x_{k} \right )$

在BFGS校正方法中，假设：

$B_{k+1}=B_k+E_k$

二、BFGS校正公式的推导

令 $E_k=\alpha u_ku_k^T+\beta v_kv_k^T$ ，其中 $u_k,v_k$ 均为 $n\times 1$ 的向量。 $y_k=\bigtriangledown f\left ( x_{k+1} \right )-\bigtriangledown f\left ( x_k \right )$ ， $s_k=x_{k+1}-x_k$ 。

则对于拟牛顿方程 $B_{k+1}\left ( x_{k+1}-x_{k} \right )=\bigtriangledown f\left ( x_{k+1} \right )-\bigtriangledown f\left ( x_{k} \right )$ 可以化简为：

$B_{k+1}s_k=y_k$

将 $B_{k+1}=B_k+E_k$ 代入上式：

$\left ( B_k+E_k \right )s_k=y_k$

将 $E_k=\alpha u_ku_k^T+\beta v_kv_k^T$ 代入上式：

$\left ( B_k+\alpha u_ku_k^T+\beta v_kv_k^T \right )s_k=y_k$

$\Rightarrow \alpha \left ( u_k^Ts_k \right )u_k+\beta \left ( v_k^Ts_k \right )v_k=y_k-B_ks_k$

已知： $u_k^Ts_k,v_k^Ts_k$ 为实数， $y_k-B_ks_k$ 为 $n\times 1$ 的向量。上式中，参数 $\alpha$ 和 $\beta$ 解的可能性有很多，我们取特殊的情况，假设 $u_k=rB_ks_k$ ， $v_k=\theta y_k$ 。则

$E_k=\alpha rB_ks_ks_k^TB_k+\beta \theta y_ky_k^T$

代入上式：

$\Rightarrow \alpha \left [ \left ( rB_ks_k\right )^Ts_k \right ]\left ( rB_ks_k \right )+\beta \left [ \left ( \theta y_k \right )^Ts_k \right ]\left ( \theta y_k \right )=y_k-B_ks_k$

$\Rightarrow \left [ \alpha r^2\left ( s_k^TB_ks_k\right ) +1\right ]\left ( B_ks_k \right )+\left [ \beta \theta ^2\left ( y_k^Ts_k \right ) -1\right ]\left (y_k \right )=0$

令 $\alpha r^2\left ( s_k^TB_ks_k\right ) +1=0$ ， $\beta \theta ^2\left ( y_k^Ts_k \right ) -1=0$ ，则：

$\alpha r^2=-\frac{1}{s_k^TB_ks_k}$

$\beta \theta ^2=\frac{1}{y_k^Ts_k}$

则最终的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}$

三、BFGS校正的算法流程

设 $B_{k}$ 对称正定， $B_{k+1}$ 由上述的BFGS校正公式确定，那么 $B_{k+1}$ 对称正定的充要条件是 $y_k^Ts_k$ 。

在博文“ 优化算法——牛顿法(Newton Method)”中介绍了非精确的线搜索准则：Armijo搜索准则，搜索准则的目的是为了帮助我们确定学习率，还有其他的一些准则，如Wolfe准则以及精确线搜索等。在利用Armijo搜索准则时并不是都满足上述的充要条件，此时可以对BFGS校正公式做些许改变：

$B_{k+1}=\begin{cases} B_k & \text{ if } y_k^Ts_k\leq 0 \\ B_k-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k}+\frac{y_ky_k^T}{y_k^Ts_k} & \text{ if } y_k^Ts_k$

BFGS拟牛顿法的算法流程：

四、求解具体优化问题

求解无约束优化问题

$min\; f\left ( x \right )=100\left ( x_1^2-x_2 \right )^2+\left ( x_1-1 \right )^2$

其中， $x=\left ( x_1,x_2 \right )^T\in\mathbb{R}^2$ 。

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-8from numpy import *
from function import *def bfgs(fun, gfun, x0):result = []maxk = 500rho = 0.55sigma = 0.4m = shape(x0)[0]Bk = eye(m)k = 0while (k < maxk):gk = mat(gfun(x0))#计算梯度dk = mat(-linalg.solve(Bk, gk))m = 0mk = 0while (m < 20):newf = fun(x0 + rho ** m * dk)oldf = fun(x0)if (newf < oldf + sigma * (rho ** m) * (gk.T * dk)[0,0]):mk = mbreakm = m + 1#BFGS校正x = x0 + rho ** mk * dksk = x - x0yk = gfun(x) - gkif (yk.T * sk > 0):Bk = Bk - (Bk * sk * sk.T * Bk) / (sk.T * Bk * sk) + (yk * yk.T) / (yk.T * sk)k = k + 1x0 = xresult.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()