非线性规划中的割线法（Secant Method）
字数 2480 2025-12-08 04:38:29

非线性规划中的割线法（Secant Method）

我将为你详细讲解非线性规划中用于求解无约束优化问题的一种重要一维搜索方法——割线法。这是一个经典且实用的方法，尤其适用于导数难以计算的情形。

第一步：核心思想与基本形式

割线法用于求解一元非线性方程 \(f(x) = 0\) 的根。在优化中，当我们寻找可导单变量函数 \(\phi(\alpha)\) 的驻点（即极小值点）时，问题转化为求解其导数方程 \(\phi'(\alpha) = 0\)。为简化，设 \(g(\alpha) = \phi'(\alpha)\)，则目标就是求 \(g(\alpha) = 0\) 的根。

割线法的核心思想是用割线近似代替切线（牛顿法），从而避免计算二阶导数。它利用函数 \(g(\alpha)\) 上最近的两个已知点 \((\alpha_{k-1}, g(\alpha_{k-1}))\) 和 \((\alpha_k, g(\alpha_k))\)，构造一条通过这两点的割线，并用这条割线与横轴的交点作为下一个迭代点 \(\alpha_{k+1}\)。

其迭代公式直接从几何推导：

\[\alpha_{k+1} = \alpha_k - g(\alpha_k) \cdot \frac{\alpha_k - \alpha_{k-1}}{g(\alpha_k) - g(\alpha_{k-1})} \]

其中，分母是函数值之差，分子是自变量之差。这个公式只需两个初始点 \(\alpha_0, \alpha_1\) 和对应的函数值 \(g(\alpha_0), g(\alpha_1)\) 即可启动，无需计算导数 \(g'(\alpha)\)。

第二步：算法步骤与收敛性

标准的割线法求解 \(g(\alpha)=0\) 的步骤为：

  1. 选择两个初始点 \(\alpha_0, \alpha_1\)，满足 \(g(\alpha_0) \neq g(\alpha_1)\)。
  2. 对于 \(k = 1, 2, \ldots\)，计算：

\[ \alpha_{k+1} = \alpha_k - \frac{g(\alpha_k)(\alpha_k - \alpha_{k-1})}{g(\alpha_k) - g(\alpha_{k-1})} \]

  1. 重复迭代，直到满足停止条件，例如 \(|\alpha_{k+1} - \alpha_k| < \epsilon\) 或 \(|g(\alpha_{k+1})| < \epsilon\)。

收敛性分析：割线法的收敛速度是超线性的，其收敛阶约为 \(p \approx 1.618\)（即黄金分割率），这比线性收敛快，但比牛顿法的二阶收敛慢。收敛性要求初始点足够靠近真根，且函数在该邻域内二阶连续可导且 \(g'(\alpha^*) \neq 0\)。

第三步：在非线性规划一维搜索中的应用

在非线性规划中，我们通常进行线搜索以确定步长 \(\alpha\)，即最小化 \(\phi(\alpha) = f(x_k + \alpha d_k)\)，其中 \(d_k\) 是搜索方向（如负梯度方向）。最优步长应满足一维最优性条件 \(\phi'(\alpha) = 0\)。

割线法在此的应用流程是：

  1. 计算导数函数 \(g(\alpha) = \nabla f(x_k + \alpha d_k)^T d_k\)。
  2. 使用割线法迭代公式求解 \(g(\alpha) = 0\)，得到近似最优步长 \(\alpha^*\)。
  3. 更新迭代点：\(x_{k+1} = x_k + \alpha^* d_k\)。

由于只需要计算一维方向导数 \(g(\alpha)\) 的值，而无需计算二阶导数（即 \(\phi''(\alpha)\)），割线法在每一步大迭代中避免了海瑟矩阵的计算，降低了计算成本。

第四步：与牛顿法、抛物线法的比较

  • 与牛顿法比较：牛顿法用切线 \(g(\alpha_k) + g'(\alpha_k)(\alpha - \alpha_k) = 0\) 求根，需计算 \(g'(\alpha)\)。割线法用割线代替切线，省去了导数计算，但收敛速度略慢。
  • 与抛物线法（二次插值法）比较：抛物线法直接对原函数 \(\phi(\alpha)\) 进行二次插值求其极小点，需要三个点的函数值。割线法是对导数方程 \(g(\alpha)=0\) 进行线性插值求根，只需要两个点的导数值。两者都是拟牛顿思想在一维的体现。

第五步：变体与注意事项

  • 割线法可能出现分母为零的情况 \(g(\alpha_k) = g(\alpha_{k-1})\)，导致迭代失败。此时需要加入安全措施，如采用一个小扰动或切换为其他方法。
  • 另一种等价的推导是：用差商近似导数，即 \(g'(\alpha_k) \approx \frac{g(\alpha_k)-g(\alpha_{k-1})}{\alpha_k - \alpha_{k-1}}\)，然后代入牛顿迭代公式 \(\alpha_{k+1} = \alpha_k - g(\alpha_k)/g'(\alpha_k)\)，即可得到割线法公式。这清晰地显示了割线法是一种“拟牛顿法”。
  • 割线法也可用于直接优化函数（不通过导数方程），即用差商近似导数的梯度下降/牛顿法，但这与上述求根的割线法有所不同，需注意区分。

总结：割线法是一种简单高效的一维求根方法，通过线性插值避免导数计算，是连接牛顿法与直接搜索法的重要桥梁。在非线性规划中，它常作为线搜索的内层求解器，平衡了计算复杂度和收敛速度，是无导数优化或导数计算昂贵时的实用选择。

非线性规划中的割线法（Secant Method） 我将为你详细讲解非线性规划中用于求解无约束优化问题的一种重要一维搜索方法——割线法。这是一个经典且实用的方法，尤其适用于导数难以计算的情形。 第一步：核心思想与基本形式 割线法用于求解一元非线性方程 \( f(x) = 0 \) 的根。在优化中，当我们寻找可导单变量函数 \( \phi(\alpha) \) 的驻点（即极小值点）时，问题转化为求解其导数方程 \( \phi'(\alpha) = 0 \)。为简化，设 \( g(\alpha) = \phi'(\alpha) \)，则目标就是求 \( g(\alpha) = 0 \) 的根。 割线法的核心思想是 用割线近似代替切线（牛顿法） ，从而避免计算二阶导数。它利用函数 \( g(\alpha) \) 上最近的两个已知点 \( (\alpha_ {k-1}, g(\alpha_ {k-1})) \) 和 \( (\alpha_ k, g(\alpha_ k)) \)，构造一条通过这两点的割线，并用这条割线与横轴的交点作为下一个迭代点 \( \alpha_ {k+1} \)。 其迭代公式直接从几何推导： \[ \alpha_ {k+1} = \alpha_ k - g(\alpha_ k) \cdot \frac{\alpha_ k - \alpha_ {k-1}}{g(\alpha_ k) - g(\alpha_ {k-1})} \] 其中，分母是函数值之差，分子是自变量之差。这个公式只需两个初始点 \( \alpha_ 0, \alpha_ 1 \) 和对应的函数值 \( g(\alpha_ 0), g(\alpha_ 1) \) 即可启动，无需计算导数 \( g'(\alpha) \)。 第二步：算法步骤与收敛性 标准的割线法求解 \( g(\alpha)=0 \) 的步骤为： 选择两个初始点 \( \alpha_ 0, \alpha_ 1 \)，满足 \( g(\alpha_ 0) \neq g(\alpha_ 1) \)。 对于 \( k = 1, 2, \ldots \)，计算： \[ \alpha_ {k+1} = \alpha_ k - \frac{g(\alpha_ k)(\alpha_ k - \alpha_ {k-1})}{g(\alpha_ k) - g(\alpha_ {k-1})} \] 重复迭代，直到满足停止条件，例如 \( |\alpha_ {k+1} - \alpha_ k| < \epsilon \) 或 \( |g(\alpha_ {k+1})| < \epsilon \)。 收敛性分析 ：割线法的收敛速度是 超线性 的，其收敛阶约为 \( p \approx 1.618 \)（即黄金分割率），这比线性收敛快，但比牛顿法的二阶收敛慢。收敛性要求初始点足够靠近真根，且函数在该邻域内二阶连续可导且 \( g'(\alpha^* ) \neq 0 \)。 第三步：在非线性规划一维搜索中的应用 在非线性规划中，我们通常进行线搜索以确定步长 \( \alpha \)，即最小化 \( \phi(\alpha) = f(x_ k + \alpha d_ k) \)，其中 \( d_ k \) 是搜索方向（如负梯度方向）。最优步长应满足一维最优性条件 \( \phi'(\alpha) = 0 \)。 割线法在此的应用流程是： 计算导数函数 \( g(\alpha) = \nabla f(x_ k + \alpha d_ k)^T d_ k \)。 使用割线法迭代公式求解 \( g(\alpha) = 0 \)，得到近似最优步长 \( \alpha^* \)。 更新迭代点：\( x_ {k+1} = x_ k + \alpha^* d_ k \)。 由于只需要计算一维方向导数 \( g(\alpha) \) 的值，而无需计算二阶导数（即 \( \phi''(\alpha) \)），割线法在每一步大迭代中避免了海瑟矩阵的计算，降低了计算成本。 第四步：与牛顿法、抛物线法的比较 与牛顿法比较：牛顿法用切线 \( g(\alpha_ k) + g'(\alpha_ k)(\alpha - \alpha_ k) = 0 \) 求根，需计算 \( g'(\alpha) \)。割线法用割线代替切线，省去了导数计算，但收敛速度略慢。 与抛物线法（二次插值法）比较：抛物线法直接对原函数 \( \phi(\alpha) \) 进行二次插值求其极小点，需要三个点的函数值。割线法是对导数方程 \( g(\alpha)=0 \) 进行线性插值求根，只需要两个点的导数值。两者都是拟牛顿思想在一维的体现。 第五步：变体与注意事项 割线法可能出现分母为零的情况 \( g(\alpha_ k) = g(\alpha_ {k-1}) \)，导致迭代失败。此时需要加入安全措施，如采用一个小扰动或切换为其他方法。 另一种等价的推导是：用差商近似导数，即 \( g'(\alpha_ k) \approx \frac{g(\alpha_ k)-g(\alpha_ {k-1})}{\alpha_ k - \alpha_ {k-1}} \)，然后代入牛顿迭代公式 \( \alpha_ {k+1} = \alpha_ k - g(\alpha_ k)/g'(\alpha_ k) \)，即可得到割线法公式。这清晰地显示了割线法是一种“拟牛顿法”。 割线法也可用于直接优化函数（不通过导数方程），即用差商近似导数的梯度下降/牛顿法，但这与上述求根的割线法有所不同，需注意区分。 总结 ：割线法是一种简单高效的一维求根方法，通过线性插值避免导数计算，是连接牛顿法与直接搜索法的重要桥梁。在非线性规划中，它常作为线搜索的内层求解器，平衡了计算复杂度和收敛速度，是无导数优化或导数计算昂贵时的实用选择。