62-理论方法-信赖域算法

知识点：信赖域算法

知识点概述

信赖域（Trust Region）方法是与线搜索方法并列的另一大类设计优化算法的框架。它在每一步迭代中，先确定一个“信赖域”（通常是一个球），即我们相信二次近似模型在该区域内是可靠的，然后在这个区域内求解一个子问题来获得下一步的位移。

详细解释

• 核心思想:
  1. 在当前点 $x_k$ 建立一个目标函数的二次近似模型 $m_k(p)=f(x_k)+\nabla f(x_k{)}^{T}p+\frac{1}{2}{p}^T{B}_{k}p$。
  2. 定义一个以 $x_k$ 为中心，半径为 ${\Delta }_k$ 的信赖域，$\Vert p\Vert \le {\Delta }_k$。
  3. 求解信赖域子问题：$$\begin{gathered} mi{n}_{ \\ |p \\ |\le {\Delta }_k}{m}_k(p) \end{gathered}$$，得到试探步 $p_k$。
  4. 评估试探步 $p_k$ 的质量。计算实际下降量与模型预测下降量的比值 ${\rho }_k$。
  5. 根据 ${\rho }_k$ 的值来决定是否接受这个试探步，并调整下一步的信赖域半径 ${\Delta }_{k+1}$。如果 ${\rho }_k$ 很大（实际下降与预测很吻合），则扩大信赖域；如果 ${\rho }_k$ 很小或为负（模型预测不准），则缩小信赖域。
• 与线搜索的对比:
  • 线搜索: 先定方向，再定步长。
  • 信赖域: 先定最大步长（信赖域半径），再在区域内同时确定方向和步长。
  • 信赖域方法通常更鲁棒，特别是当海瑟矩阵非正定或病态时，因为它能处理非下降方向。

学习要点

• 理解信赖域方法“先定范围，再寻优”的核心思想。
• 掌握信赖域算法的基本流程：构建模型、求解子问题、评估、更新半径。
• 了解信赖域方法与线搜索方法的哲学区别。

实践应用

• 广泛用于求解非线性最小二乘问题和各种大规模优化问题。
• 许多优秀的开源和商业求解器都内置了信赖域算法。

关联知识点

• 前置知识: 12-核心概念-迭代算法, 60-理论方法-牛顿法
• 后续知识: 63-理论方法-非线性最小二乘算法
• 相关知识: 56-理论方法-线搜索方法