求解信赖域子问题的光滑牛顿法

光滑牛顿法是一种求解信赖域子问题的方法，其基本思想是在信赖域内求解一个二次模型，并使用牛顿法来求解这个模型的最小值点。具体步骤如下：

步骤1：初始化

选择一个初始点 $x_0$，设定信赖域半径 $\Delta_0$ 和牛顿法收敛容限 $\epsilon$，并令 $k=0$。

步骤2：求解二次模型

在当前点 $x_k$ 处，构造二次模型：

$$
m_k(p)=f_k+\nabla f_k^Tp+\frac{1}{2}p^TB_kp
$$

其中，$f_k=f(x_k)$ 是目标函数在 $x_k$ 处的函数值，$\nabla f_k$ 是目标函数在 $x_k$ 处的梯度，$B_k$ 是目标函数在 $x_k$ 处的海森矩阵或拟牛顿矩阵。

步骤3：求解子问题

在信赖域 $\Delta_k$ 内求解下列子问题：

$$
\min_{\|p\|\leq \Delta_k}m_k(p)
$$

可以使用任意优化算法来求解上述子问题，例如共轭梯度法、牛顿法、拟牛顿法等。

步骤4：更新迭代点

设 $p_k$ 是子问题的最优解，令 $x_{k+1}=x_k+p_k$，计算目标函数在 $x_{k+1}$ 处的函数值 $f_{k+1}=f(x_{k+1})$ 和梯度 $\nabla f_{k+1}$。

步骤5：更新信赖域半径

根据当前点 $x_k$ 和迭代点 $x_{k+1}$ 的改变量 $\Delta x_k=x_{k+1}-x_k$ 和函数值改变量 $\Delta f_k=f_{k+1}-f_k$，计算实际下降量 $\rho_k=\frac{\Delta f_k}{m_k(0)}$ 和预测下降量 $\hat{\rho}_k=\frac{\Delta f_k}{m_k(0)-m_k(p_k)}$。

如果实际下降量 $\rho_k$ 较小，则缩小信赖域半径 $\Delta_{k+1}$；如果预测下降量 $\hat{\rho}_k$ 较大，则增大信赖域半径 $\Delta_{k+1}$；否则保持信赖域半径不变。

步骤6：判断收敛

如果 $\|\nabla f_k\|\leq \epsilon$，则停止迭代；否则令 $k=k+1$，返回步骤2。

需要注意的是，在求解子问题时，需要保证 $B_k$ 是正定矩阵，否则需要对其进行修正，例如使用 BFGS 方法进行修正。此外，为了保证算法的收敛性和稳定性，还需要进行一些其他的细节处理，例如限制信赖域半径的最大值和最小值，避免牛顿步长过大等。