023-方法-模型法

知识点概述

基于模型的无导数优化方法是一类非常有效的DFO算法。其核心思想是在当前迭代点附近，通过一组采样点上的函数值来插值构建一个目标函数的近似模型（通常是二次模型）。然后，在一个信赖域内最小化这个模型来产生一个试探步。算法的成功关键在于维护一个几何构型良好的插值点集，以保证模型的准确性。

教材原文

Some of the most effective algorithms for … DFO … construct a linear or quadratic model of the objective function and define the next iterate by seeking to minimize this model inside a trust region. Suppose that at the current iterate $x_k$ we have a set of sample points $Y=y^1,\dots ,y^q$. We wish to construct a quadratic model of the form $m_k(x_k+p)=c+g^{T}p+\frac{1}{2}{p}^{T}Gp$ We determine the … coefficients … by imposing the interpolation conditions $m_k(y^l)=f(y^l),l=1,\dots ,q.$

详细解释

1. 模型构建

   • 插值: 算法不使用导数，而是通过函数值来推断曲率信息。它选取$q$个点$Y=y^1,...,y^q$，并要求二次模型$m_k$在这些点上的值与真实函数$f$的值完全相等。
   • 模型自由度: 一个n维二次模型有 $\frac{1}{2}(n+1)(n+2)$ 个待定系数（$c,g,G$）。因此，为了唯一确定一个二次模型，需要 $q=\frac{1}{2}(n+1)(n+2)$ 个插值点。
   • 线性模型: 作为简化，也可以构建线性模型 $m_k(p)=f(x_k)+g^{T}p$，此时只需要$n+1$个插值点。

2. 算法框架 (Algorithm 9.1)

   • 这是一个信赖域框架，结合了模型构建和插值点集管理。
   • 步骤:
     1. 构建模型: 利用当前的$q$个插值点，求解一个线性方程组来确定二次模型$m_k$的系数。
     2. 求解子问题: 在信赖域 $|p|\le {\Delta }_k$ 内最小化模型$m_k(x_k+p)$，得到试探步$p_k$。
     3. 评估步长: 计算实际下降与预测下降比${\rho }_k$。
        • 如果${\rho }_k$足够大（例如 $\ge \eta$），则接受步长$x_{k+1}=x_k+p_k$，并将新点$x_{k+1}$加入插值集$Y$，替换掉其中一个旧点。
        • 如果${\rho }_k$很小，则拒绝步长$x_{k+1}=x_k$。
     4. 管理插值集和信赖域:
        • 如果步长被接受，可能会扩大信赖域。
        • 如果步长被拒绝，需要判断是模型不够好还是信赖域太大。通过检查插值点集的“几何质量”（例如，基于拉格朗日多项式），如果几何构型不好，则调用一个几何改进程序来替换插值点以改善模型质量；如果几何构型良好，则说明是模型在当前信赖域内失效，此时应缩小信赖域。

3. 插值点集的管理

   • 重要性: 插值点集的几何构型直接决定了插值模型的质量和稳定性。如果所有点都共线或共面，模型将是退化的。
   • Poisedness: 一个好的插值点集被称为是“poised”的，这意味着由插值条件定义的线性系统是良态的（非奇异的）。
   • 更新策略: 当接受一个新点$x_{k+1}$时，需要从旧的插值集$Y$中移除一个点$y_{-}$。一个好的策略是选择那个使得新点$x_{k+1}$的拉格朗日函数$|L(x_{k+1},y_{-})|$最大的点$y_{-}$，这样可以最大化新点集$Y^{+}$的行列式，从而改善模型的几何质量。

4. 最小范数变化更新 (Minimum-Change Updating)

   • 这是一种降低模型构建成本的变体。它不要求$q=\frac{1}{2}(n+1)(n+2)$个点，而是使用较少的点（例如$2n+1$个）。
   • 为了确定模型，除了满足插值条件外，还增加了一个额外要求：新的Hessian模型$G_{k+1}$与旧的模型$G_k$之间的变化最小（在Frobenius范数意义下）。
   • 这使得算法更接近于传统的拟牛顿法，并降低了每次迭代的计算成本（从$O(n^4)$降至$O(n^3)$）。

学习要点

• 核心思想: 用函数值插值代替导数来构建二次模型。
• 与信赖域的结合: 模型法天然地与信赖域框架结合，通过求解信赖域子问题来产生步长。
• 插值点几何: 理解插值点集的几何构型（poisedness）对模型质量至关重要，是算法稳健性的关键。
• 成本: 认识到构建完整的二次模型需要$O(n^2)$个函数值，且每步迭代成本高昂（$O(n^4)$或$O(n^3)$），这限制了该方法只能用于中小型问题。

实践应用

• 基于模型的DFO方法是目前解决中小型黑箱优化问题的最有效和最可靠的方法之一。
• 著名的算法和软件包括Powell的UOBYQA和NEWUOA，以及Conn, Scheinberg, Toint的DFO。
• 它们被成功应用于航空航天设计、工程模拟参数校准等领域，在这些领域中，函数求值成本极高且导数不可用。

关联知识点

• 前置知识: 022-方法-无导数优化概述, 010-方法-信赖域方法概述
• 后续知识: 024-方法-坐标与模式搜索法