BFGS算法.pdf，全局优化算法

BFGS算法

山东理工大学 数学学院

Contents

拟牛顿法BFGS

Logistic预测模型

练习

最速下降法

案例

超线性收敛速度。

牛顿法的特点是：收敛速度快，迭代次数少，但是当Hessian 矩阵很稠密时，每次迭代的计算量很大。随着数据规模的增大，那么Hessian矩阵会越大， 需要的存储空间会增多，计算量也会增大，

有时候大到不可计算，所以针对海量数据的计算，牛顿法不再适用。 拟牛顿法是在牛顿法的基础上引入了Hessian矩阵的近似矩阵，避免每次迭代都计算Hessian矩阵的逆，它 的收敛速度介于梯度

下降法和牛顿法之间。拟牛顿法跟牛顿法一样，也是不能处理太大规模的数据，因为计算 量和存储空间会开销很多。拟牛顿法虽然每次迭代不像牛顿法那样保证是最优化的方向，但是近似矩阵始

终是 正定的，因此算法始终是朝着最优化的方向在搜索。

拟牛顿法的基本思想是在牛顿法中用Hessian矩阵的某个近似矩阵来代替它。在高数中，学过泰勒公式，如下

关于泰勒展开的更多内容，可以参考这里：泰勒公式介绍，泰勒公式应用。泰勒公式是用一个近似的多项式

来代替原来复杂的函数表达式。对于拟牛顿法来说，构造二次模型。如下

忽略高阶无穷小部分，进行求导得到 ,令 ,得到 ,由于H矩阵维度超大，求逆矩阵非常困难，

计算复杂度非常高。BFGS算法 算法本质：一种通过迭代逼近的拟牛顿算法。

先建立目标函数文件examLogistic.m

% function y=examLogistic(x)

% yhat=1e-3*[185 350 263 335 560 570 263 214 276 435 476 452 442 404 458 427 409 430 421 444 539 632 749 690 679]';

% for i=1:25

% z(i)=(yhat(i)-1/(1+x(2)*exp(-i*x(1))))^2;

% end

% y=sum(z);

% function [ xstar,fxstar,iter ] = BFGS( f_name,x0,flag,varepsilon )

% %UNTITLED3 此处显示有关此函数的摘要

% % 此处显示详细说明

% [f,g]=feval(f_name,xk);%根据梯度公式直接计算目标函数的梯度值

% end

% while norm(g)>varepsilon

% dk=Gauss2(B,-g,1);

% lambda=p618(f_name,xk,dk,a0,h0,t,e);

% xkplus1=xk+lambda*dk;

% if flag==0

% gkplus1=MyGradient(f_name,xkplus1);

% elseif flag==1

% [f,gkplus1]=feval(f_name,xkplus1);