数值优化
字数 3228 2025-10-26 09:01:43

数值优化

数值优化是计算数学中研究通过迭代计算寻找函数最小值或最大值（通常称为极值）的方法的领域。其核心问题是：给定一个目标函数，找到一组变量取值，使得目标函数的值达到最小（或最大）。

第一步：问题表述与基本概念

  1. 标准形式：数值优化问题通常表述为最小化问题：

\[ \min_{x \in \mathbb{R}^n} f(x) \]

其中，\(f: \mathbb{R}^n \to \mathbb{R}\) 称为目标函数，\(x\) 是一个 \(n\) 维向量，称为决策变量。我们的目标是找到一个点 \(x^*\)，使得对于所有 \(x\) 邻域内的点，都有 \(f(x^*) \leq f(x)\)。这样的点 \(x^*\) 称为局部极小点。如果 \(f(x^*) \leq f(x)\) 对于所有可行的 \(x\) 都成立，则 \(x^*\) 是全局极小点。

  1. 极值的必要条件：对于可微函数，如果 \(x^*\) 是一个局部极小点，并且在 \(x^*\) 处可微，那么必须满足：

\[ \nabla f(x^*) = 0 \]

这里，\(\nabla f(x)\) 是 \(f\) 的梯度，它是一个向量，包含了 \(f\) 对所有变量的一阶偏导数：\(\nabla f(x) = \left[ \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n} \right]^T\)。满足 \(\nabla f(x) = 0\) 的点 \(x\) 称为驻点或临界点（它可能是极小点、极大点或鞍点）。

第二步：单变量优化（一维搜索）

在讲解复杂的多维优化之前，我们先从最简单的一维情况（\(n=1\)）开始。许多多维优化算法的核心步骤都包含一个一维搜索子问题。

  1. 问题：找到单变量函数 \(\phi(t)\) 的极小点，即 \(\min_{t} \phi(t)\)。
  2. 方法思想：我们无法直接找到精确解，但可以通过迭代不断缩小包含极小点的区间。
  3. 黄金分割法：
    • 适用条件：函数是单峰函数（在区间内只有一个极小点）。
  • 核心思想：在当前的搜索区间 \([a, b]\) 内，对称地选取两个内点 \(t_1 < t_2\)，并计算函数值 \(\phi(t_1)\) 和 \(\phi(t_2)\)。
  • 如果 \(\phi(t_1) < \phi(t_2)\)，说明极小点位于区间 \([a, t_2]\) 内，于是我们将搜索区间更新为 \([a, t_2]\)。
  • 如果 \(\phi(t_1) > \phi(t_2)\)，说明极小点位于区间 \([t_1, b]\) 内，于是我们将搜索区间更新为 \([t_1, b]\)。
    • 黄金比例：为了高效，我们希望每次迭代只需计算一个新的函数值。通过将内点取为区间的黄金分割点（约0.618），可以确保每次迭代后，其中一个内点恰好是新区间的内点，从而只需计算一个新点的函数值。这个过程不断重复，直到区间长度小于预设的容差。

第三步：无约束多变量优化的基本方法

现在我们进入核心部分：最小化多变量函数 \(f(x)\)。

  1. 下降算法框架：绝大多数迭代算法都遵循一个基本模式：
  • 步骤1：给定当前迭代点 \(x_k\)。
  • 步骤2：确定一个搜索方向 \(p_k\)。这个方向应该是一个“下山”方向，即满足 \(\nabla f(x_k)^T p_k < 0\)（梯度方向是函数上升最快的方向，其反方向是下降最快的方向）。
  • 步骤3：确定一个步长 \(\alpha_k > 0\)。这通常通过一维搜索（第二步介绍的方法）来求解子问题 \(\min_{\alpha > 0} \phi(\alpha) = f(x_k + \alpha p_k)\)。
  • 步骤4：更新迭代点：\(x_{k+1} = x_k + \alpha_k p_k\)。
  • 步骤5：检查收敛条件（例如，梯度范数 \(\|\nabla f(x_{k+1})\|\) 是否足够小）。若满足，则停止；否则，返回步骤1。
  1. 最速下降法：
  • 搜索方向：这是最直观的选取方法，即选择当前点梯度向量的反方向作为搜索方向：\(p_k = -\nabla f(x_k)\)。
    • 优缺点：方法简单，只需计算一阶导数。但收敛速度通常较慢（线性收敛），尤其在接近极小点时，可能会产生“锯齿现象”。

第四步：更高效的方法——牛顿法

为了获得更快的收敛速度，我们需要利用目标函数的二阶导数信息。

  1. 牛顿方向：我们的目标是解方程 \(\nabla f(x) = 0\)。牛顿法是将这个非线性方程进行线性化求解。
  • 在当前点 \(x_k\) 处，对梯度 \(\nabla f(x)\) 进行一阶泰勒展开：\(\nabla f(x_k + p) \approx \nabla f(x_k) + \nabla^2 f(x_k) p\)。
  • 令其等于零，得到线性方程组：\(\nabla^2 f(x_k) p = -\nabla f(x_k)\)。
  • 这个方程的解 \(p_k\) 就称为牛顿方向。其中 \(\nabla^2 f(x_k)\) 是 \(f\) 在 \(x_k\) 处的Hessian矩阵，其元素是二阶偏导数 \([\nabla^2 f(x)]_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}\)。
  1. 牛顿法步骤：迭代更新为 \(x_{k+1} = x_k + p_k\)（这里步长 \(\alpha_k\) 默认为1）。
  2. 优缺点：如果初始点足够好，且Hessian矩阵正定，牛顿法具有极快的收敛速度（二阶收敛）。但缺点也很明显：
    • 需要计算二阶导数（Hessian矩阵）。
    • 需要求解一个可能很大规模的线性方程组。
    • 如果Hessian矩阵非正定，牛顿方向可能不是下降方向。

第五步：约束优化简介

现实问题中，变量往往需要满足各种限制，这就引出了约束优化。

  1. 问题表述：标准形式为：

\[ \begin{align} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E} \quad \text{(等式约束)}\\ & c_i(x) \geq 0, \quad i \in \mathcal{I} \quad \text{(不等式约束)} \end{align} \]

其中“s.t.”代表“受限于”。
  1. 拉格朗日乘子法：这是处理约束优化的基础理论。通过引入拉格朗日乘子 \(\lambda_i\)，将约束优化问题转化为一个无约束的拉格朗日函数求驻点的问题：

\[ \mathcal{L}(x, \lambda) = f(x) - \sum_{i} \lambda_i c_i(x) \]

在一定的约束规格下，原问题的局部最优解 \(x^*\) 必须满足KKT条件（Karush-Kuhn-Tucker条件），这是一阶必要性条件，是驻点条件在有约束情况下的推广。

数值优化算法（如序列二次规划法、内点法）的核心思想，就是通过一系列精巧的迭代，使得解在收敛过程中逐渐满足KKT条件。

数值优化 数值优化是计算数学中研究通过迭代计算寻找函数最小值或最大值（通常称为极值）的方法的领域。其核心问题是：给定一个目标函数，找到一组变量取值，使得目标函数的值达到最小（或最大）。 第一步：问题表述与基本概念 标准形式 ：数值优化问题通常表述为最小化问题： \[ \min_ {x \in \mathbb{R}^n} f(x) \] 其中，\( f: \mathbb{R}^n \to \mathbb{R} \) 称为 目标函数 ，\( x \) 是一个 \( n \) 维向量，称为 决策变量 。我们的目标是找到一个点 \( x^* \)，使得对于所有 \( x \) 邻域内的点，都有 \( f(x^ ) \leq f(x) \)。这样的点 \( x^ \) 称为 局部极小点 。如果 \( f(x^ ) \leq f(x) \) 对于所有可行的 \( x \) 都成立，则 \( x^ \) 是 全局极小点 。 极值的必要条件 ：对于可微函数，如果 \( x^* \) 是一个局部极小点，并且在 \( x^* \) 处可微，那么必须满足： \[ \nabla f(x^* ) = 0 \] 这里，\( \nabla f(x) \) 是 \( f \) 的梯度，它是一个向量，包含了 \( f \) 对所有变量的一阶偏导数：\( \nabla f(x) = \left[ \frac{\partial f}{\partial x_ 1}, \frac{\partial f}{\partial x_ 2}, \dots, \frac{\partial f}{\partial x_ n} \right]^T \)。满足 \( \nabla f(x) = 0 \) 的点 \( x \) 称为 驻点 或 临界点 （它可能是极小点、极大点或鞍点）。 第二步：单变量优化（一维搜索） 在讲解复杂的多维优化之前，我们先从最简单的一维情况（\( n=1 \)）开始。许多多维优化算法的核心步骤都包含一个一维搜索子问题。 问题 ：找到单变量函数 \( \phi(t) \) 的极小点，即 \( \min_ {t} \phi(t) \)。 方法思想 ：我们无法直接找到精确解，但可以通过迭代不断缩小包含极小点的区间。 黄金分割法 ： 适用条件 ：函数是 单峰函数 （在区间内只有一个极小点）。 核心思想 ：在当前的搜索区间 \([ a, b]\) 内，对称地选取两个内点 \( t_ 1 < t_ 2 \)，并计算函数值 \( \phi(t_ 1) \) 和 \( \phi(t_ 2) \)。 如果 \( \phi(t_ 1) < \phi(t_ 2) \)，说明极小点位于区间 \([ a, t_ 2]\) 内，于是我们将搜索区间更新为 \([ a, t_ 2 ]\)。 如果 \( \phi(t_ 1) > \phi(t_ 2) \)，说明极小点位于区间 \([ t_ 1, b]\) 内，于是我们将搜索区间更新为 \([ t_ 1, b ]\)。 黄金比例 ：为了高效，我们希望每次迭代只需计算一个新的函数值。通过将内点取为区间的黄金分割点（约0.618），可以确保每次迭代后，其中一个内点恰好是新区间的内点，从而只需计算一个新点的函数值。这个过程不断重复，直到区间长度小于预设的容差。 第三步：无约束多变量优化的基本方法 现在我们进入核心部分：最小化多变量函数 \( f(x) \)。 下降算法框架 ：绝大多数迭代算法都遵循一个基本模式： 步骤1 ：给定当前迭代点 \( x_ k \)。 步骤2 ：确定一个 搜索方向 \( p_ k \)。这个方向应该是一个“下山”方向，即满足 \( \nabla f(x_ k)^T p_ k < 0 \)（梯度方向是函数上升最快的方向，其反方向是下降最快的方向）。 步骤3 ：确定一个 步长 \( \alpha_ k > 0 \)。这通常通过一维搜索（第二步介绍的方法）来求解子问题 \( \min_ {\alpha > 0} \phi(\alpha) = f(x_ k + \alpha p_ k) \)。 步骤4 ：更新迭代点：\( x_ {k+1} = x_ k + \alpha_ k p_ k \)。 步骤5 ：检查收敛条件（例如，梯度范数 \( \|\nabla f(x_ {k+1})\| \) 是否足够小）。若满足，则停止；否则，返回步骤1。 最速下降法 ： 搜索方向 ：这是最直观的选取方法，即选择当前点梯度向量的反方向作为搜索方向：\( p_ k = -\nabla f(x_ k) \)。 优缺点 ：方法简单，只需计算一阶导数。但收敛速度通常较慢（线性收敛），尤其在接近极小点时，可能会产生“锯齿现象”。 第四步：更高效的方法——牛顿法 为了获得更快的收敛速度，我们需要利用目标函数的二阶导数信息。 牛顿方向 ：我们的目标是解方程 \( \nabla f(x) = 0 \)。牛顿法是将这个非线性方程进行线性化求解。 在当前点 \( x_ k \) 处，对梯度 \( \nabla f(x) \) 进行一阶泰勒展开：\( \nabla f(x_ k + p) \approx \nabla f(x_ k) + \nabla^2 f(x_ k) p \)。 令其等于零，得到线性方程组：\( \nabla^2 f(x_ k) p = -\nabla f(x_ k) \)。 这个方程的解 \( p_ k \) 就称为 牛顿方向 。其中 \( \nabla^2 f(x_ k) \) 是 \( f \) 在 \( x_ k \) 处的 Hessian矩阵 ，其元素是二阶偏导数 \( [ \nabla^2 f(x)]_ {ij} = \frac{\partial^2 f}{\partial x_ i \partial x_ j} \)。 牛顿法步骤 ：迭代更新为 \( x_ {k+1} = x_ k + p_ k \)（这里步长 \( \alpha_ k \) 默认为1）。 优缺点 ：如果初始点足够好，且Hessian矩阵正定，牛顿法具有极快的收敛速度（二阶收敛）。但缺点也很明显： 需要计算二阶导数（Hessian矩阵）。 需要求解一个可能很大规模的线性方程组。 如果Hessian矩阵非正定，牛顿方向可能不是下降方向。 第五步：约束优化简介 现实问题中，变量往往需要满足各种限制，这就引出了约束优化。 问题表述 ：标准形式为： \[ \begin{align} \min_ {x} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E} \quad \text{(等式约束)}\\ & c_ i(x) \geq 0, \quad i \in \mathcal{I} \quad \text{(不等式约束)} \end{align} \] 其中“s.t.”代表“受限于”。 拉格朗日乘子法 ：这是处理约束优化的基础理论。通过引入 拉格朗日乘子 \( \lambda_ i \)，将约束优化问题转化为一个无约束的拉格朗日函数求驻点的问题： \[ \mathcal{L}(x, \lambda) = f(x) - \sum_ {i} \lambda_ i c_ i(x) \] 在一定的约束规格下，原问题的局部最优解 \( x^* \) 必须满足 KKT条件 （Karush-Kuhn-Tucker条件），这是一阶必要性条件，是驻点条件在有约束情况下的推广。 数值优化算法（如序列二次规划法、内点法）的核心思想，就是通过一系列精巧的迭代，使得解在收敛过程中逐渐满足KKT条件。