好的，我注意到列表中尚未出现过 二次插值法。这是一个经典的一维线搜索方法，常用于非线性规划中确定无约束问题的步长，或者在约束优化中作为线搜索子步骤。我将为你详细讲解。
非线性规划中的二次插值法基础题
题目描述
考虑一个无约束的单变量最小化问题：
\[\min_{\alpha > 0} \phi(\alpha) \]
其中，\(\phi(\alpha) = f(x^k + \alpha d^k)\)，\(f: \mathbb{R}^n \to \mathbb{R}\) 是我们要最小化的目标函数，\(x^k\) 是当前迭代点，\(d^k\) 是给定的下降搜索方向（例如，负梯度方向）。函数 \(\phi(\alpha)\) 是 \(\alpha\) 的一维函数。
我们的目标：找到步长 \(\alpha^* > 0\)，使得 \(\phi(\alpha^*)\) 在搜索方向上尽可能小。二次插值法的核心思想是，利用三个已知点的函数值，构造一个二次多项式来逼近 \(\phi(\alpha)\)，然后取这个二次插值函数的最小点作为下一次迭代的候选步长。
给定条件：假设我们已经有了三个点 \(a, b, c\)（满足 \(a < b < c\)）以及对应的函数值 \(\phi_a = \phi(a), \phi_b = \phi(b), \phi_c = \phi(c)\)，并且满足 \(\phi_b < \phi_a\) 和 \(\phi_b < \phi_c\)。这意味着 \(b\) 点对应的函数值是三个点中最小的，从而保证我们能拟合出一个开口向上的抛物线，其最小值点必然位于区间 \((a, c)\) 内。
任务：推导出二次插值公式，并详细解释其计算步骤、几何意义以及在非线性规划线搜索中的应用流程。
解题过程
第一步：建立二次插值模型
我们假设函数 \(\phi(\alpha)\) 在三点 \((a, \phi_a), (b, \phi_b), (c, \phi_c)\) 附近的行为可以用一个二次函数来近似：
\[q(\alpha) = p_0 + p_1 \alpha + p_2 \alpha^2 \]
其中 \(p_0, p_1, p_2\) 是待定系数。\(p_2\) 必须为正，抛物线才开口向上，有最小值。
第二步：代入点建立方程组
将三个点代入 \(q(\alpha)\)：
\[\begin{cases} q(a) = p_0 + p_1 a + p_2 a^2 = \phi_a \\ q(b) = p_0 + p_1 b + p_2 b^2 = \phi_b \\ q(c) = p_0 + p_1 c + p_2 c^2 = \phi_c \end{cases} \]
第三步：求解插值点（抛物线顶点）
二次函数 \(q(\alpha)\) 的顶点（最小值点） \(\alpha^*\) 可通过求导得到：
\[q'(\alpha) = p_1 + 2p_2 \alpha = 0 \quad \Rightarrow \quad \alpha^* = -\frac{p_1}{2p_2} \]
但我们不需要显式求出 \(p_1\) 和 \(p_2\)。我们可以利用 拉格朗日插值多项式 或直接解方程组消去 \(p_0\) 和 \(p_1\)，得到一个更简洁、数值更稳定的公式。
一个常用的推导方法是利用 重心公式 或 差商。这里我们用更直观的几何/代数方法：
由 \(q(\alpha) - q(b) = p_1(\alpha - b) + p_2(\alpha^2 - b^2) = (\alpha - b)[p_1 + p_2(\alpha + b)]\)。
计算 \(\phi_a - \phi_b\) 和 \(\phi_c - \phi_b\)：
\[\phi_a - \phi_b = q(a) - q(b) = (a - b)[p_1 + p_2(a + b)] \quad \text{(1)} \]
\[ \phi_c - \phi_b = q(c) - q(b) = (c - b)[p_1 + p_2(c + b)] \quad \text{(2)} \]
我们的目标是 \(\alpha^*\) 满足 \(p_1 + 2p_2 \alpha^* = 0\)，即 \(p_1 = -2p_2 \alpha^*\)。将 \(p_1 = -2p_2 \alpha^*\) 代入方程 (1) 和 (2)：
\[\phi_a - \phi_b = (a - b)[-2p_2 \alpha^* + p_2(a + b)] = p_2 (a - b)(a + b - 2\alpha^*) \]
\[ \phi_c - \phi_b = (c - b)[-2p_2 \alpha^* + p_2(c + b)] = p_2 (c - b)(c + b - 2\alpha^*) \]
将上面两式相除，可以消去 \(p_2\)：
\[\frac{\phi_a - \phi_b}{(a - b)(a + b - 2\alpha^*)} = \frac{\phi_c - \phi_b}{(c - b)(c + b - 2\alpha^*)} \]
解这个关于 \(\alpha^*\) 的方程，经过整理（交叉相乘，合并同类项），可以得到最终的 二次插值公式：
\[\boxed{\alpha^* = b - \frac{1}{2} \frac{ (b-a)^2(\phi_b - \phi_c) - (b-c)^2(\phi_b - \phi_a) }{ (b-a)(\phi_b - \phi_c) - (b-c)(\phi_b - \phi_a) }} \]
这个公式就是通过三点 \((a, \phi_a), (b, \phi_b), (c, \phi_c)\) 进行二次插值所得抛物线的最小值点。
第四步：几何解释与数值稳定性
- 几何意义：我们在平面 \((\alpha, \phi)\) 上过三个点画了一条抛物线。如果这三个点的函数值呈现“高-低-高”的模式（即 \(b\) 在中间且函数值最小），那么这条抛物线开口向上，其顶点 \(\alpha^*\) 就是一个对真实最小值 \(\phi(\alpha)\) 的很好估计。
- 分母的含义：公式的分母部分正比于抛物线的二阶导数（曲率）的估计。如果分母接近于零，说明三个点几乎共线，抛物线非常平坦，此时插值结果可能不可靠，需要特别处理（例如，退回使用黄金分割法）。
- 计算顺序：在实际编程中，为了避免重复计算，通常先计算几个中间变量：
\[ \begin{aligned} s_{ab} &= \phi_b - \phi_a \\ s_{cb} &= \phi_b - \phi_c \\ d_{ab} &= b - a \\ d_{cb} &= b - c \\ \text{分子} &= d_{ab}^2 * s_{cb} - d_{cb}^2 * s_{ab} \\ \text{分母} &= d_{ab} * s_{cb} - d_{cb} * s_{ab} \\ \alpha^* &= b - 0.5 * (\text{分子} / \text{分母}) \end{aligned} \]
如果分母的绝对值非常小（小于一个很小的正数，如 $ 10^{-12} $），则算法应报错或采用备用策略。
第五步：在非线性规划线搜索中的应用流程
二次插值法通常不单独使用，而是嵌入到一个 划界（Bracketing） 过程中，与另一个方法（如 三次插值 或 进退法/黄金分割法）结合，形成高效的线搜索算法。一个典型流程如下：
-
初始划界：首先，使用 进退法 找到一个包含最小值点的初始区间 \([\alpha_l, \alpha_u]\)，并在此区间内找到一个中间点 \(\alpha_m\)，使得 \(\phi(\alpha_m) < \phi(\alpha_l)\) 且 \(\phi(\alpha_m) < \phi(\alpha_u)\)。此时，\(a = \alpha_l, b = \alpha_m, c = \alpha_u\)。
-
迭代插值：
- 使用公式计算插值点 \(\alpha^*\)。
- 计算 \(\phi(\alpha^*)\)。
- 更新三点：比较 \(\alpha^*\) 与 \(a, b, c\) 的位置和对应的函数值，丢弃原三点中函数值最大的那个点，将 \(\alpha^*\) 作为新的中间点 \(b\)，并重新排序，得到新的 \(a, b, c\)。
- 例如，如果 \(\alpha^*\) 在 \((b, c)\) 之间且 \(\phi(\alpha^*) < \phi(b)\)，则新的三点变为 \((b, \alpha^*, c)\)。如果 \(\phi(\alpha^*) > \phi(b)\)，则新的三点变为 \((a, b, \alpha^*)\)。
-
收敛判断：检查区间长度 \(|c - a|\) 是否小于给定的容差 \(\epsilon\)，或者连续几次迭代目标函数值下降非常小。若满足，则停止，输出 \(b\)（当前三点中函数值最小的点）作为最终步长 \(\alpha_k\)。
-
保障措施：为了防止插值点过于接近边界点导致收敛缓慢，或者因函数非二次性导致插值效果差，通常会对 \(\alpha^*\) 的位置加以限制，例如要求它必须落在当前区间 \((a, c)\) 的内部分（如 \(a + 0.1*(c-a)\) 到 \(a + 0.9*(c-a)\) 之间），否则就采用 黄金分割法 在区间内取一个新点。
总结：
二次插值法是一种局部收敛速度快的线搜索技术，因为它利用了函数的曲率信息。它的效率很大程度上依赖于初始三点是否很好地“包围”了最小值点。在实际的非线性规划算法（如最速下降法、拟牛顿法）中，它常作为精确线搜索或强Wolfe条件线搜索的核心子程序，与划界算法配合，能够以较少的函数求值次数，高效地找到满足收敛条件的步长。