?个人主页：欢迎访问Ali.s的首页
⏰ 最近更新：2022年8月8日
⛽ Java框架学习系列：【Spring】【SpringMVC】【Mybatis】
? Java项目实战系列：【飞机大战】【图书管理系统】
? Java算法21天系列：【查找】【排序】【递归】
⛳ Java基础学习系列：【继承】【封装】【多态】
? 通信仿真学习系列：【硬件】【通信】【MATLAB】
? 个人简介：通信工程本硕?、Java程序员?。目前只会CURD?
? 点赞 ? 收藏 ?留言 ? 都是我最大的动力?
一、拟牛顿法介绍
为了解决牛顿法中可能出现在某步迭代时，目标函数数值上升的问题，引入阻尼牛顿法进行修正，但是在牛顿法和阻尼牛顿法中都存在计算Hesse矩阵的问题，使得在多次迭代时可能会出现计算量过大的问题，为解决Hesse矩阵的问题，引入共轭梯度法对优化问题进行处理。它不需要对Hesse矩阵进行计算，只需要对函数的一阶导数进行处理，不仅克服了最速下降法收敛慢的缺点，而且避免了牛顿法需要计算Hesse矩阵并求逆的缺陷，拟牛顿法通过正定矩阵近似Hesse矩阵的逆矩阵或Hesse矩阵，简化了这一计算过程。而拟牛顿法中对满足条件的正定矩阵的给出了表述：
(1)正定矩阵近似等于Hesse矩阵，还得相应的算法产生的方向近似于牛顿方向，这样有利于保证算法的较快收敛速度。
(2)在保证矩阵是正定的前提下，还要求是对称的，确保函数的下降方向。
(3) 矩阵的更新规则比较简单，基本采用r（A）=1的矩阵进行校正;
二、拟牛顿法原理
设函数f在x(k+1)处的二次近似模型为：
对上式进行求导，得到g(x):
其中梯度差为：
根据位移的物理定义得到位移为：
所以根据公式推导，得到梯度差与位移的关系：
现在使用拟牛顿法构造出Hesse矩阵的近似矩阵Bk，通常称作是拟牛顿条件
搜索方向由牛顿法中可知，为负梯度方向，所以
根据上面拟牛顿法的特点介绍，可以假设：
下面对r(A)=1做校正，为保证秩的约束，所以上式中Ek的值取：
由梯度差和位移的关系可知：
通过数学公式的推导和处理，得到：
而通过上式可以看出，uk向量与等式右边的向量是平行关系，只存在倍数的延伸，所以令：
那么得到的Ek的值为：
若满足下面条件：
可以取：
此时
所以得到对称秩为1的校正公式为：
三、拟牛顿法步骤
- 给定初始点x(0)，设置允许误差0<ε<1，初始化对称正定矩阵，令K=0;
- 计算初始点的梯度，与允许误差做判断；
- 计算搜索方向，与牛顿法中类似；
- 使用线性搜索，求最优步长因子；
- 进行迭代，满足线性一维搜索;
- 令K=K+1，重复步骤3;
四、拟牛顿法代码
拟牛顿函数：
function [k,x,val]=sr1(fun,gfun,x0,epsilon,N)
if nargin<5,
N=1000;
end
if nargin<4,
epsilon=1.e-5;
end
beta=0.55;
sigma=0.4;
k=0;
n=length(x0);
Hk=eye(n);
while(k<N)
gk=feval(gfun,x0);
dk=-Hk*gk;
if(norm(gk)<epsilon),
break;
end
m=0;
mk=0;
while(m<20)
if(feval(fun,x0+beta^m*dk)<=feval(fun,x0)+sigma*beta^m*gk'*dk)
mk=m;
break;
end
m=m+1;
end
x=x0+beta^mk*dk;
sk=x-x0; yk=feval(gfun,x)-gk;
Hk=Hk+(sk-Hk*yk)*(sk-Hk*yk)'/((sk-Hk*yk)'*yk);
k=k+1; x0=x;
end
val=feval(fun,x0);
梯度函数
function gf=gfun(x)
gf=[4*(x(1)-x(2)^2);-8*x(2)*(x(1)-x(2)^2)+2*(x(2)-2)];
五、拟牛顿法测试
function f=fun(x)
f=2*(x(1)-x(2)^2)^2+(x(2)-2)^2;
进行校验处理：
总结
为了不计算二阶导，减少计算量，采用了差分近似微分的思想，正定矩阵近似等于Hesse矩阵，还得相应的算法产生的方向近似于牛顿方向，保证算法的较快收敛速度。在保证矩阵是正定的前提下，还要求是对称的，确保函数的下降方向。 对拟牛顿法还以可以进行进一步的优化，比如DFP和BFGS等等。