梯度下降法
梯度下降法用来求解目标函数的极值。这个极值是给定模型给定数据之后在参数空间中搜索找到的。迭代过程为：
梯度下降方法的问题：
每一步走的距离在极值点附近非常重要，如果走的步子过大，容易在极值点附近震荡而无法收敛。
解决办法：将alpha设定为随着迭代次数而不断减小的变量，但是也不能完全减为零。
牛顿法
牛顿法是为了求解函数值为零的时候变量的取值问题的，具体地，当要求解 f(θ)=0时，如果 f可导，那么可以通过迭代公式。
当θ是向量时，牛顿法可以使用下面式子表示：
其中H叫做海森矩阵，H (-1) 表示的是海森矩阵的逆矩阵 ，其实就是目标函数对参数θ的二阶导数。
牛顿法的优点：
牛顿法收敛速度相比梯度下降法很快，而且由于海森矩阵的的逆在迭代中不断减小，起到逐渐缩小步长的效果。
缺点：
牛顿法的缺点就是计算海森矩阵的逆比较困难，消耗时间和计算资源。因此有了拟牛顿法。
-
网上一个牛顿法求解的例子：
海森矩阵的定义：
- 代码实现：
用牛顿法求解 f = 100 * (x2-x1** 2) ** 2 + (1-x1)**2
import numpy as np
import matplotlib.pyplot as plt
#梯度的公式
def tidu(x):
return np.array([-400*x[0]*(x[1]-x[0]**2)-2*(1-x[0]),200*(x[1]-x[0]**2)])
#海森矩阵的公式
def hessian(x):
return np.array([[-400*(x[1]-3*x[0]**2)+2,-400*x[0]],[-400*x[0],200]])
#牛顿法
def newton(x):
print("初始点为 : ",x)
res=[]
res.append(x)
i = 1
imax = 1000
delta = 1
#迭代的条件是小于imax，或者是更新的距离小于一个很小的数值
while i<imax and delta>10**(-5):
p = -np.dot(np.linalg.inv(hessian(x)),tidu(x))
x_new = x + p
res.append(x_new)
delta = sum((x-x_new)**2) # 更新的距离
print("初始点为 : ",x_new)
i=i+1
x=x_new # 更新x
return np.array(res)
if __name__ =="__main__":
# 用牛顿法求解 f=100*(x2-x1**2)**2+(1-x1)**2
X1=np.arange(-1.5,1.5+0.05,0.05)
X2=np.arange(-3.5,2+0.05,0.05)
[x1,x2]=np.meshgrid(X1,X2)
f=100*(x2-x1**2)**2+(1-x1)**2; # 给定的函数
plt.contour(x1,x2,f,20) # 画出函数的20条轮廓线
x0 = np.array([-1.2,1])
res=newton(x0)
res_x=res[:,0]
res_y=res[:,1]
plt.plot(res_x,res_y)
plt.show()
然后就是拟牛顿法了
- 拟牛顿法
todo
牛顿法需要求海森矩阵，这个矩阵需要计算二阶偏导数，比较复杂。为了改良这个问题，提出了拟牛顿法。
基本idea是：不求二阶偏导数，构造出一个近似的海森矩阵。
参考：
https://www.zhihu.com/question/19723347
https://blog.csdn.net/xmu_jupiter/article/details/47402497
https://blog.csdn.net/u014688145/article/details/53688585
