牛顿法（Newton's method）和拟牛顿法（Quasi-Newton methods）

牛顿法（Newton's method）和拟牛顿法（Quasi-Newton methods）是求解无约束优化问题的两种常用方法，它们主要用于寻找函数的极小值点。

牛顿法

牛顿法是一种迭代算法，用于找到函数的根（零点）或者在优化中找到函数的极小值。在优化问题中，牛顿法利用了函数的一阶导数（梯度）和二阶导数（Hessian矩阵）来寻找极小值点。

算法步骤：

1. 选择一个初始点 $x^{(0)}$。

2. 对于第 $k$ 次迭代，计算目标函数 $f(x)$ 在 $x^{(k)}$ 处的梯度 $\nabla f(x^{(k)})$ 和 Hessian 矩阵 $H(x^{(k)})$。

3. 计算搜索方向 $d^{(k)} = -H(x^{(k)})^{-1} \nabla f(x^{(k)})$。

4. 选择一个步长 $\alpha^{(k)}$，通常通过线搜索来确定。

5. 更新 $x^{(k+1)} = x^{(k)} + \alpha^{(k)} d^{(k)}$。

6. 重复步骤2-5，直到满足停止准则（如梯度接近零或达到最大迭代次数）。

优点：

• 当迭代接近极小值点时，收敛速度快。

缺点：

• 需要计算二阶导数，计算成本高。
• 对于非凸问题，可能遇到 Hessian 矩阵不正定或奇异的情况。

拟牛顿法

拟牛顿法是牛顿法的一种变体，它不需要计算二阶导数（Hessian 矩阵），而是通过迭代的方式近似 Hessian 矩阵的逆或者其本身。

算法步骤：

1. 选择一个初始点 $x^{(0)}$ 和一个初始 Hessian 矩阵的近似 $H^{(0)}$。

2. 对于第 $k$ 次迭代，计算梯度 $\nabla f(x^{(k)})$。

3. 计算搜索方向 $d^{(k)} = -H^{(k)} \nabla f(x^{(k)})$。

4. 通过线搜索确定步长 $\alpha^{(k)}$。

5. 更新 $x^{(k+1)} = x^{(k)} + \alpha^{(k)} d^{(k)}$。

6. 更新 Hessian 矩阵的近似 $H^{(k+1)}$，使用如 DFP（Davidon-Fletcher-Powell）或 BFGS（Broyden-Fletcher-Goldfarb-Shanno）等公式。

7. 重复步骤2-6，直到满足停止准则。

优点：

• 不需要计算二阶导数，计算成本较低。
• 对于大规模问题更实用。

缺点：

• 收敛速度可能不如牛顿法快。

在实际应用中，拟牛顿法因其较低的计算成本和良好的性能，被广泛应用于各种优化问题，尤其是在机器学习和深度学习中。