四、牛顿法
4.1 牛顿法原理
🚩牛顿法的原理是使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。
迭代过程如下：
4.2 牛顿法代码演示
def f(x): return (x - 3) ** 3 # 定义函数 def fd(x): return 3 * ((x - 3) ** 2) # 定义一阶导数 y = [0] # 初始值 def newtonMethod(n, assum): count = n x = assum next_x = 0 A = f(x) # 函数值 B = fd(x) # 导数值 print('A = %0.4f' % (A) + ', B = %0.4f' % (B) + ', time = %d' % (count)) if f(x) == 0.0: # 是不是f(x) = 0的解 return count, x else: # 不是方程 = 0的解，迭代更新 next_x = x - A / B y.append(next_x) print('next_x = %0.4f' % (next_x)) if abs(A - f(next_x)) < 1e-6: # 满足精确值，退出，什么都没做，只是打印 # 设置迭代跳出条件，同时输出满足f(x) = 0的x值 print('方程的解为： f(x) = 0, x = %0.4f'% (next_x)) else: # 不满足精确度，再次调用这个方法，递归 return newtonMethod(n + 1, next_x) # 设置从0开始计数，x0 = 4 newtonMethod(0, 0) x = np.linspace(0, 6, 100) plt.plot(x, f(x)) # 原图 _ = plt.scatter(y, f(np.array(y)), color = 'red') # 更新过程点
4.3 求解最优化问题
🚩牛顿法最优化公式如下：
其中：
可得最终的优化公式为：
复杂问题简单化，多元函数降级为一元函数，那么最优化牛顿法泰勒二阶展开的更新公式为：
梯度下降法只用到了一阶导数的信息，牛顿法既用到了一阶导数的信息，也用到了二阶导数的信息。梯度下降法是用线性函数来代替目标函数，牛顿法是用二次函数来代替目标函数，所以说牛顿法的收敛速度是更快的。
4.4 求解最优化代码演示
4.4.1 使用牛顿法求最优化（11步得到答案，2.0062）
import numpy as np import matplotlib.pyplot as plt # 构建方程 f = lambda x : (x - 2) ** 4 + 10 # 导函数 g1 = lambda x : 4 * (x - 2) ** 3 g2 = lambda x : 12 * (x - 2) ** 2 # 创建模拟数据并可视化 x = np.linspace(1, 3, 100) y = f(x) plt.plot(x, y) y = [2.8] def newtonMethod(n, assum): count = n x = assum next_x = 0 A = g1(x) B = g2(x) print('A = %0.4f' % (A) + ',B = %0.4f' % (B) + ',次数 = %d' % (count)) if f(x) == 0.0: return count, x else: next_x = x - A / B y.append(next_x) print('next_x = %0.4f' % (next_x),) if abs(f(x) - f(next_x)) < 1e-8: # 设置迭代跳出条件，同时输出满足f(x) = 0的x值 print('方程的解为： f(x) = 0, x = %0.4f'% (next_x)) else: return newtonMethod(n + 1, next_x) # 设置从0开始计数，x0 = 4 newtonMethod(0, 2.8) _ = plt.scatter(y,f(np.array(y)), color = 'red')
4.4.2 使用梯度下降求最优解（207步得到答案，2.04349）
import numpy as np import matplotlib.pyplot as plt # 构建方程 f = lambda x : (x - 2) ** 4 + 10 # 导函数 g1 = lambda x : 4 * (x - 2) ** 3 eta = 0.3 # 学习率 # 随机（瞎蒙）,初始值 x = 2.8 # 多次while 循环，每次梯度下降，更新，记录一下上一次的值 # 比较精确度 # 一开始故意设置差异，目的为了有区分，不能一上来就停止 last_x = x + 0.1 # 精确度，人为设定 precision = 1e-8 print('-----------------随机x是：', x) # 每次梯度下降，求解出来的x值，一开始随机给的 x_ = [x] # Python中列表 count = 0 while True: if np.abs(f(x) - f(last_x)) < precision: # 更新时，变化甚微，满足精确度，终止 break # 更新，梯度下降 # x是当前数值，赋值给上一个值 last_x = x count += 1 x = x - eta * g1(x) # 梯度下降公式 x_.append(x) print('+++++++++++++++更新之后的x是：%0.5f' % (x)) print('+++++++++++++++梯度下降次数：', count) # x1是NumPy数组 x1 = np.linspace(0, 11.5, 100) y1 = f(x1) plt.figure(figsize = (9, 6)) plt.plot(x1, y1) # 散点图 x_ = np.array(x_) _ = plt.scatter(x_, f(x_), color = 'red', s = 30)
4.5 拟牛顿法
🚩如上节所说，牛顿法虽然收敛速度快，但是需要计算海塞矩阵的逆矩阵H-1,而且有时目标函数的海塞矩阵无法保持正定（多元函数微分学），从而使得牛顿法失效。为了克服这两个问题，人们提出了拟牛顿法。这个方法的基本思想是：不用二阶偏导数而构造出可以近似海塞矩阵（或海塞矩阵的逆）的正定对称阵。不同的构造方法就产生了不同的拟牛顿法。
下面我们先推导一下拟牛顿条件，它给“对海塞矩阵（或海塞矩阵的逆）做近似”提供了理论指导，指出了用来近似的矩阵应该满足的条件。
对 ᐁf(x) 做二阶泰勒展开我们得到了以下近似：
令：
所以：
以上即为拟牛顿条件！
