内点法
字数 2287 2025-10-26 19:16:22

内点法

内点法是一类用于求解线性规划和凸优化问题的迭代算法。与单纯形法在可行域顶点间移动不同，内点法从可行域内部出发，沿着一条中心路径逼近最优解。我将从基本思想开始，逐步讲解其核心原理和关键步骤。

  1. 基本思想与动机
    • 问题背景：考虑一个标准形式的线性规划问题：
      最小化 \(c^T x\)
      满足 \(Ax = b\)，且 \(x \ge 0\)。
      其中，\(x\) 是决策变量向量，\(c\) 是成本向量，\(A\) 是约束矩阵，\(b\) 是右端项向量。
    • 单纯形法的局限：单纯形法沿着可行域（一个多面体）的边界移动，从一个顶点跳到相邻顶点。虽然在实际中通常很高效，但在最坏情况下可能需要遍历指数数量的顶点。
  • 内点法的创新：内点法的核心思想是避免在边界上“爬行”，而是从可行域的内部（即所有变量都严格大于零的点，\(x > 0\)）开始，构造一条穿过内部的路径，并沿着这条路径收敛到边界上的最优解。这种方法通常具有多项式时间复杂度的理论保证。
  1. 核心概念：障碍函数与中心路径
  • 障碍函数：为了将算法“禁锢”在可行域内部，我们引入一个障碍函数。最常用的是对数障碍函数。对于非负约束 \(x \ge 0\)，障碍函数定义为：
    \(B(x) = - \sum_{j=1}^{n} \ln(x_j)\)
    其中，\(n\) 是变量 \(x\) 的维度。当任何一个变量 \(x_j\) 从内部接近边界（即 \(x_j \to 0^+\)）时，\(-\ln(x_j)\) 会趋向于正无穷大。这个函数就像一堵“墙”，阻止迭代点触及边界。
    • 障碍问题：我们将原问题与障碍函数结合，形成一个带参数的障碍问题：
      最小化 \(c^T x - \mu \sum_{j=1}^{n} \ln(x_j)\)
      满足 \(Ax = b\)。
      其中，\(\mu > 0\) 是一个正数，称为障碍参数。当 \(\mu\) 很大时，障碍函数的影响占主导，最优解会偏向于内部；当 \(\mu\) 减小时，目标函数 \(c^T x\) 的影响增大，最优解会向原问题的最优解移动。
  • 中心路径：对于每一个固定的 \(\mu > 0\)，障碍问题都有一个唯一的最优解，记为 \(x^*(\mu)\)。当 \(\mu\) 从正无穷大变到0时，这些最优解点 \(\{ x^*(\mu) \}\) 形成一条光滑的曲线，这条曲线被称为中心路径。内点法的目标就是沿着这条中心路径逼近原问题的最优解（即 \(\mu \to 0\) 时的点）。
  1. 算法步骤：原对偶内点法
    最常用和高效的内点法是原对偶内点法，它同时处理原问题和对偶问题。考虑原问题的对偶问题：
    最大化 \(b^T y\)
    满足 \(A^T y + s = c\)，且 \(s \ge 0\)。
    其中，\(y\) 是对偶变量，\(s\) 是对偶松弛变量。
  • 最优性条件（KKT条件）：在最优解处，除了原始可行（\(Ax = b, x \ge 0\)）和对偶可行（\(A^T y + s = c, s \ge 0\)）之外，还需要满足互补松弛条件：对于每一个 \(j\)，有 \(x_j s_j = 0\)。
  • 扰动KKT条件：内点法不要求迭代点严格在边界上（即 \(x_j s_j = 0\)），而是允许其为一个正数 \(\mu\)：
    \(Ax = b\),  \(x > 0\)   (原始可行性)
    \(A^T y + s = c\),  \(s > 0\)   (对偶可行性)
    \(x_j s_j = \mu\)，对于所有 \(j\)   (扰动互补松弛条件)
    这个方程组定义了点 \((x(\mu), y(\mu), s(\mu))\) 正好位于中心路径上。
  • 牛顿法求解：我们的策略是：给定一个当前迭代点 \((x, y, s)\)（在内部，即 \(x>0, s>0\)）和一个当前的障碍参数 \(\mu\)，我们使用牛顿法来求解上述扰动KKT条件。牛顿法的思想是线性化方程组，求解一个关于搜索方向 \((\Delta x, \Delta y, \Delta s)\) 的线性系统：
    \(A \Delta x = 0\)   (保持原始可行)
    \(A^T \Delta y + \Delta s = 0\)   (保持对偶可行)
    \(S \Delta x + X \Delta s = \mu e - X S e\)   (向中心路径靠拢)
    其中，\(X\) 和 \(S\) 是以 \(x\) 和 \(s\) 为对角元素的对角矩阵，\(e\) 是全1向量。解这个系统得到搜索方向。
  • 步长选择与迭代：得到搜索方向后，我们不能直接走到新点，因为可能会跑出可行域内部（导致 \(x\) 或 \(s\) 变为负值）。因此，我们需要计算一个步长 \(\alpha\)（通常略小于1），确保新点 \(x + \alpha \Delta x > 0\) 和 \(s + \alpha \Delta s > 0\)。然后更新迭代点，并适当减小障碍参数 \(\mu\)（例如，设置为当前互补间隙 \(x^T s / n\) 的一个比例），开始下一次迭代。这个过程持续直到解足够精确（互补间隙足够小）。
内点法 内点法是一类用于求解线性规划和凸优化问题的迭代算法。与单纯形法在可行域顶点间移动不同，内点法从可行域内部出发，沿着一条中心路径逼近最优解。我将从基本思想开始，逐步讲解其核心原理和关键步骤。 基本思想与动机 问题背景 ：考虑一个标准形式的线性规划问题： 最小化 \( c^T x \) 满足 \( Ax = b \)，且 \( x \ge 0 \)。 其中，\( x \) 是决策变量向量，\( c \) 是成本向量，\( A \) 是约束矩阵，\( b \) 是右端项向量。 单纯形法的局限 ：单纯形法沿着可行域（一个多面体）的边界移动，从一个顶点跳到相邻顶点。虽然在实际中通常很高效，但在最坏情况下可能需要遍历指数数量的顶点。 内点法的创新 ：内点法的核心思想是避免在边界上“爬行”，而是从可行域的内部（即所有变量都严格大于零的点，\( x > 0 \)）开始，构造一条穿过内部的路径，并沿着这条路径收敛到边界上的最优解。这种方法通常具有多项式时间复杂度的理论保证。 核心概念：障碍函数与中心路径 障碍函数 ：为了将算法“禁锢”在可行域内部，我们引入一个障碍函数。最常用的是对数障碍函数。对于非负约束 \( x \ge 0 \)，障碍函数定义为： \( B(x) = - \sum_ {j=1}^{n} \ln(x_ j) \) 其中，\( n \) 是变量 \( x \) 的维度。当任何一个变量 \( x_ j \) 从内部接近边界（即 \( x_ j \to 0^+ \)）时，\( -\ln(x_ j) \) 会趋向于正无穷大。这个函数就像一堵“墙”，阻止迭代点触及边界。 障碍问题 ：我们将原问题与障碍函数结合，形成一个带参数的障碍问题： 最小化 \( c^T x - \mu \sum_ {j=1}^{n} \ln(x_ j) \) 满足 \( Ax = b \)。 其中，\( \mu > 0 \) 是一个正数，称为障碍参数。当 \( \mu \) 很大时，障碍函数的影响占主导，最优解会偏向于内部；当 \( \mu \) 减小时，目标函数 \( c^T x \) 的影响增大，最优解会向原问题的最优解移动。 中心路径 ：对于每一个固定的 \( \mu > 0 \)，障碍问题都有一个唯一的最优解，记为 \( x^ (\mu) \)。当 \( \mu \) 从正无穷大变到0时，这些最优解点 \( \{ x^ (\mu) \} \) 形成一条光滑的曲线，这条曲线被称为中心路径。内点法的目标就是沿着这条中心路径逼近原问题的最优解（即 \( \mu \to 0 \) 时的点）。 算法步骤：原对偶内点法 最常用和高效的内点法是原对偶内点法，它同时处理原问题和对偶问题。考虑原问题的对偶问题： 最大化 \( b^T y \) 满足 \( A^T y + s = c \)，且 \( s \ge 0 \)。 其中，\( y \) 是对偶变量，\( s \) 是对偶松弛变量。 最优性条件（KKT条件） ：在最优解处，除了原始可行（\( Ax = b, x \ge 0 \)）和对偶可行（\( A^T y + s = c, s \ge 0 \)）之外，还需要满足互补松弛条件：对于每一个 \( j \)，有 \( x_ j s_ j = 0 \)。 扰动KKT条件 ：内点法不要求迭代点严格在边界上（即 \( x_ j s_ j = 0 \)），而是允许其为一个正数 \( \mu \)： \( Ax = b \),  \( x > 0 \)   (原始可行性) \( A^T y + s = c \),  \( s > 0 \)   (对偶可行性) \( x_ j s_ j = \mu \)，对于所有 \( j \)   (扰动互补松弛条件) 这个方程组定义了点 \( (x(\mu), y(\mu), s(\mu)) \) 正好位于中心路径上。 牛顿法求解 ：我们的策略是：给定一个当前迭代点 \( (x, y, s) \)（在内部，即 \( x>0, s>0 \)）和一个当前的障碍参数 \( \mu \)，我们使用牛顿法来求解上述扰动KKT条件。牛顿法的思想是线性化方程组，求解一个关于搜索方向 \( (\Delta x, \Delta y, \Delta s) \) 的线性系统： \( A \Delta x = 0 \)   (保持原始可行) \( A^T \Delta y + \Delta s = 0 \)   (保持对偶可行) \( S \Delta x + X \Delta s = \mu e - X S e \)   (向中心路径靠拢) 其中，\( X \) 和 \( S \) 是以 \( x \) 和 \( s \) 为对角元素的对角矩阵，\( e \) 是全1向量。解这个系统得到搜索方向。 步长选择与迭代 ：得到搜索方向后，我们不能直接走到新点，因为可能会跑出可行域内部（导致 \( x \) 或 \( s \) 变为负值）。因此，我们需要计算一个步长 \( \alpha \)（通常略小于1），确保新点 \( x + \alpha \Delta x > 0 \) 和 \( s + \alpha \Delta s > 0 \)。然后更新迭代点，并适当减小障碍参数 \( \mu \)（例如，设置为当前互补间隙 \( x^T s / n \) 的一个比例），开始下一次迭代。这个过程持续直到解足够精确（互补间隙足够小）。