原始-对偶内点法
字数 4294 2025-12-14 15:33:15

好的，这次我们来详细讲解一个新的运筹学重要词条：

原始-对偶内点法

第一步：基本概念与问题背景

首先，我们明确“原始-对偶内点法”所要解决的问题。它是一种用于求解凸优化问题的多项式时间算法。为了让你能清晰理解，我们从最经典、最基础的应用场景——线性规划入手。

考虑一个标准形式的线性规划问题：

  • 原始问题 (Primal Problem, P)：
    最小化： \(c^T x\)
    满足约束：
  1. \(A x = b\)
  2. \(x \ge 0\)
    其中， \(x \in \mathbb{R}^n\) 是决策变量， \(c \in \mathbb{R}^n\)， \(A \in \mathbb{R}^{m \times n}\)， \(b \in \mathbb{R}^{m}\)。

它的对偶问题 (Dual Problem, D)：
最大化： \(b^T y\)
满足约束：

  1. \(A^T y + s = c\)
  2. \(s \ge 0\)
    其中， \(y \in \mathbb{R}^m\) 是对偶变量， \(s \in \mathbb{R}^n\) 是对偶松弛变量。

原始-对偶内点法的目标，就是同时求解原始问题 \(P\) 和对偶问题 \(D\)，找到一个满足特定最优性条件的点 \((x^*, y^*, s^*)\)。

第二步：最优性条件——核心的KKT系统

为什么需要同时求解原始和对偶？因为对于线性规划（以及更一般的凸优化问题），有一组刻画最优解的充要条件，称为Karush-Kuhn-Tucker条件。对于线性规划，KKT条件可以写成：

  1. 原始可行性 (Primal Feasibility): \(A x = b, \quad x \ge 0\)
  2. 对偶可行性 (Dual Feasibility): \(A^T y + s = c, \quad s \ge 0\)
  3. 互补松弛条件 (Complementary Slackness): \(x_i s_i = 0, \quad \text{对于} i = 1, 2, ..., n\)

这里的互补松弛条件 \(x_i s_i = 0\) 是核心。它意味着对于最优解，要么 \(x_i^* = 0\)（第 \(i\) 个原始变量处于边界），要么 \(s_i^* = 0\)（第 \(i\) 个对偶约束是紧的），两者不能同时为正。

因此，求解线性规划等价于寻找一组 \((x, y, s)\)，满足以下非线性方程组：

\[\begin{aligned} A x &= b, \quad x \ge 0 \\ A^T y + s &= c, \quad s \ge 0 \\ x_i s_i &= 0, \quad i=1,...,n \end{aligned} \]

这个方程组是非线性的，因为包含了乘积项 \(x_i s_i\)。

第三步：核心思想——内点法哲学与扰动KKT条件

内点法 的核心哲学是：从可行域内部出发，沿着一条“中心路径”趋近于最优解（位于边界上）。这与“单纯形法”沿着可行域的顶点（边界）跳跃形成对比。

为了构造这条“中心路径”，我们引入一个关键技巧：扰动互补松弛条件。我们将苛刻的 \(x_i s_i = 0\) 替换为一个“软化”的版本：

\[x_i s_i = \mu, \quad i=1,...,n \]

其中， \(\mu > 0\) 是一个扰动参数，也叫中心参数。

现在我们得到一个“扰动KKT系统”：

\[F(x, y, s; \mu) = \begin{bmatrix} A x - b \\ A^T y + s - c \\ X S e - \mu e \end{bmatrix} = 0, \quad x > 0, s > 0 \]

这里， \(X = \text{diag}(x_1, ..., x_n)\)， \(S = \text{diag}(s_1, ..., s_n)\)， \(e = (1,1,...,1)^T\)。条件 \(x>0, s>0\) 保证了我们严格在可行域内部（内点）。

  • 中心路径 (Central Path): 对于每一个 \(\mu > 0\)，扰动KKT系统理论上有一个唯一解 \((x(\mu), y(\mu), s(\mu))\)。当 \(\mu\) 从正无穷逐渐减小到0时，这些解的轨迹形成一条光滑的曲线，称为中心路径。
  • 路径的性质： 在中心路径上，所有互补乘积 \(x_i s_i\) 都相等 (\(=\mu\))，这意味着所有的变量都“均匀地”远离边界 (\(x_i=0\) 或 \(s_i=0\))。当 \(\mu \to 0\) 时，中心路径上的点趋近于原始问题的最优解。

第四步：算法框架——牛顿步与迭代过程

原始-对偶内点法是一个迭代算法，其基本思路是：

  1. 给定一个当前内点 \((x^k, y^k, s^k)\) 和一个中心参数 \(\mu_k\)。
  2. 我们希望找到牛顿方向 \((\Delta x, \Delta y, \Delta s)\)，使得沿着这个方向走，能更接近满足 \(F(x, y, s; \mu_k) = 0\) 的点。
  3. 通过解一个线性方程组来获得牛顿方向。

牛顿方程推导：
我们对 \(F(x, y, s; \mu) = 0\) 在当前点 \((x, y, s)\) 处做一阶泰勒展开，并忽略高阶项：

\[F(x+\Delta x, y+\Delta y, s+\Delta s; \mu) \approx F(x,y,s;\mu) + J_F \cdot (\Delta x, \Delta y, \Delta s)^T = 0 \]

其中 \(J_F\) 是雅可比矩阵。代入 \(F\) 的表达式，我们可以得到具体的线性系统：

\[\begin{bmatrix} A & 0 & 0 \\ 0 & A^T & I \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \\ \Delta s \end{bmatrix} = \begin{bmatrix} b - A x \\ c - A^T y - s \\ \mu e - X S e \end{bmatrix} \]

这个系统通常会被进一步化简（例如消去 \(\Delta s\)），得到一个更小的对称方程组来求解。

迭代步骤：

  1. 求解方向： 解上述牛顿方程，得到搜索方向 \((\Delta x, \Delta y, \Delta s)\)。
  2. 步长选择： 为了保证迭代后点仍为内点 (\(x>0, s>0\))，我们需要选择一个步长 \(\alpha \in (0, 1]\)。通常采用分数到边界规则：

\[ \alpha_{\text{pri}} = \min(1, \gamma \cdot \min_{\Delta x_i < 0} (-x_i / \Delta x_i)), \quad \alpha_{\text{dual}} = \min(1, \gamma \cdot \min_{\Delta s_i < 0} (-s_i / \Delta s_i)) \]

其中 \(\gamma\) 是一个小于1的安全系数（如0.995）。然后取 \(\alpha = \min(\alpha_{\text{pri}}, \alpha_{\text{dual}})\)。这一步确保新点不会“撞”到边界。
3. 更新迭代点：

\[ x^{k+1} = x^k + \alpha \Delta x, \quad y^{k+1} = y^k + \alpha \Delta y, \quad s^{k+1} = s^k + \alpha \Delta s \]

  1. 更新中心参数 \(\mu\)： 这是算法的艺术所在。常用的启发式方法是根据当前互补间隙的大小来设定 \(\mu\)：

\[ \mu_{k+1} = \sigma \cdot \frac{(x^{k+1})^T s^{k+1}}{n} \]

其中，\((x^{k+1})^T s^{k+1}\) 是当前的对偶间隙，\(n\) 是变量维度，\(\sigma \in (0,1)\) 是一个中心参数。较小的 \(\sigma\) 会使下一步更强调减少对偶间隙（向最优解靠拢），较大的 \(\sigma\) 会使下一步更强调靠近中心路径（保持内点性质）。
5. 收敛判断： 检查原始残差 \(||Ax-b||\)、对偶残差 \(||A^T y + s - c||\) 和对偶间隙 \(x^T s\) 是否都小于预设的容差。若满足，则停止迭代，输出近似最优解。

第五步：总结、扩展与意义

总结流程：
原始-对偶内点法 = 内点法哲学 (在内部逼近) + 扰动KKT条件 (定义中心路径) + 牛顿法 (沿路径搜索方向) + 谨慎的步长与参数更新 (保持内点性与收敛性)。

扩展：

  1. 凸二次规划与半定规划： 该方法的框架可以很自然地推广到凸二次规划（QP）、二阶锥规划（SOCP）和半定规划（SDP），只需修改对应的互补松弛条件（如 \(XS = \mu I\) 用于SDP）和牛顿方程。
  2. 非可行启动： 上述描述从可行内点开始。实际算法（如Mehrotra预测-校正算法）通常从任意一个正点 (\(x>0, s>0\)) 开始，即使不满足等式约束。牛顿方向会同时致力于减少可行性误差和互补间隙，具有更强的实用性。

重要意义：

  1. 多项式时间复杂性： 理论上，原始-对偶内点法可以在多项式步骤内找到问题的一个近似最优解，这是它在理论上的巨大优势。
  2. 高效实践： 对于大规模稀疏线性/凸优化问题，原始-对偶内点法通常比单纯形法更高效、更稳定，成为现代优化求解器（如Gurobi, CPLEX, MOSEK）的核心算法之一。
  3. 统一框架： 它为解决一大类凸优化问题提供了一个强大而统一的数值计算框架。
好的，这次我们来详细讲解一个新的运筹学重要词条： 原始-对偶内点法 第一步：基本概念与问题背景 首先，我们明确“原始-对偶内点法”所要解决的问题。它是一种用于求解 凸优化问题 的 多项式时间算法 。为了让你能清晰理解，我们从最经典、最基础的应用场景—— 线性规划 入手。 考虑一个标准形式的线性规划问题： 原始问题 (Primal Problem, P)： 最小化： \( c^T x \) 满足约束： \( A x = b \) \( x \ge 0 \) 其中， \( x \in \mathbb{R}^n \) 是决策变量， \( c \in \mathbb{R}^n \)， \( A \in \mathbb{R}^{m \times n} \)， \( b \in \mathbb{R}^{m} \)。 它的 对偶问题 (Dual Problem, D)： 最大化： \( b^T y \) 满足约束： 1. \( A^T y + s = c \) 2. \( s \ge 0 \) 其中， \( y \in \mathbb{R}^m \) 是对偶变量， \( s \in \mathbb{R}^n \) 是 对偶松弛变量 。 原始-对偶内点法的目标，就是同时求解原始问题 \(P\) 和对偶问题 \(D\)，找到一个满足特定最优性条件的点 \((x^ , y^ , s^* )\)。 第二步：最优性条件——核心的KKT系统 为什么需要同时求解原始和对偶？因为对于线性规划（以及更一般的凸优化问题），有一组刻画最优解的充要条件，称为 Karush-Kuhn-Tucker条件 。对于线性规划，KKT条件可以写成： 原始可行性 (Primal Feasibility): \( A x = b, \quad x \ge 0 \) 对偶可行性 (Dual Feasibility): \( A^T y + s = c, \quad s \ge 0 \) 互补松弛条件 (Complementary Slackness): \( x_ i s_ i = 0, \quad \text{对于} i = 1, 2, ..., n \) 这里的互补松弛条件 \( x_ i s_ i = 0 \) 是核心。它意味着对于最优解，要么 \( x_ i^* = 0 \)（第 \(i\) 个原始变量处于边界），要么 \( s_ i^* = 0 \)（第 \(i\) 个对偶约束是紧的），两者不能同时为正。 因此，求解线性规划等价于寻找一组 \((x, y, s)\)，满足以下 非线性方程组 ： \[ \begin{aligned} A x &= b, \quad x \ge 0 \\ A^T y + s &= c, \quad s \ge 0 \\ x_ i s_ i &= 0, \quad i=1,...,n \end{aligned} \] 这个方程组是非线性的，因为包含了乘积项 \(x_ i s_ i\)。 第三步：核心思想——内点法哲学与扰动KKT条件 内点法 的核心哲学是： 从可行域内部出发，沿着一条“中心路径”趋近于最优解（位于边界上） 。这与“单纯形法”沿着可行域的顶点（边界）跳跃形成对比。 为了构造这条“中心路径”，我们引入一个关键技巧： 扰动互补松弛条件 。我们将苛刻的 \( x_ i s_ i = 0 \) 替换为一个“软化”的版本： \[ x_ i s_ i = \mu, \quad i=1,...,n \] 其中， \( \mu > 0 \) 是一个 扰动参数 ，也叫 中心参数 。 现在我们得到一个“扰动KKT系统”： \[ F(x, y, s; \mu) = \begin{bmatrix} A x - b \\ A^T y + s - c \\ X S e - \mu e \end{bmatrix} = 0, \quad x > 0, s > 0 \] 这里， \( X = \text{diag}(x_ 1, ..., x_ n) \)， \( S = \text{diag}(s_ 1, ..., s_ n) \)， \( e = (1,1,...,1)^T \)。条件 \( x>0, s>0 \) 保证了我们严格在可行域内部（内点）。 中心路径 (Central Path): 对于每一个 \( \mu > 0 \)，扰动KKT系统理论上有一个唯一解 \((x(\mu), y(\mu), s(\mu))\)。当 \( \mu \) 从正无穷逐渐减小到0时，这些解的轨迹形成一条光滑的曲线，称为 中心路径 。 路径的性质： 在中心路径上，所有互补乘积 \( x_ i s_ i \) 都相等 (\(=\mu\))，这意味着所有的变量都“均匀地”远离边界 (\(x_ i=0\) 或 \(s_ i=0\))。当 \( \mu \to 0 \) 时，中心路径上的点趋近于原始问题的最优解。 第四步：算法框架——牛顿步与迭代过程 原始-对偶内点法是一个迭代算法，其基本思路是： 给定一个当前内点 \((x^k, y^k, s^k)\) 和一个中心参数 \( \mu_ k \)。 我们希望找到牛顿方向 \((\Delta x, \Delta y, \Delta s)\)，使得沿着这个方向走，能更接近满足 \( F(x, y, s; \mu_ k) = 0 \) 的点。 通过解一个线性方程组来获得牛顿方向。 牛顿方程推导： 我们对 \( F(x, y, s; \mu) = 0 \) 在当前点 \((x, y, s)\) 处做一阶泰勒展开，并忽略高阶项： \[ F(x+\Delta x, y+\Delta y, s+\Delta s; \mu) \approx F(x,y,s;\mu) + J_ F \cdot (\Delta x, \Delta y, \Delta s)^T = 0 \] 其中 \(J_ F\) 是雅可比矩阵。代入 \(F\) 的表达式，我们可以得到具体的线性系统： \[ \begin{bmatrix} A & 0 & 0 \\ 0 & A^T & I \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \\ \Delta s \end{bmatrix} = \begin{bmatrix} b - A x \\ c - A^T y - s \\ \mu e - X S e \end{bmatrix} \] 这个系统通常会被进一步化简（例如消去 \(\Delta s\)），得到一个更小的对称方程组来求解。 迭代步骤： 求解方向： 解上述牛顿方程，得到搜索方向 \((\Delta x, \Delta y, \Delta s)\)。 步长选择： 为了保证迭代后点仍为内点 (\(x>0, s>0\))，我们需要选择一个步长 \(\alpha \in (0, 1]\)。通常采用 分数到边界规则 ： \[ \alpha_ {\text{pri}} = \min(1, \gamma \cdot \min_ {\Delta x_ i < 0} (-x_ i / \Delta x_ i)), \quad \alpha_ {\text{dual}} = \min(1, \gamma \cdot \min_ {\Delta s_ i < 0} (-s_ i / \Delta s_ i)) \] 其中 \(\gamma\) 是一个小于1的安全系数（如0.995）。然后取 \(\alpha = \min(\alpha_ {\text{pri}}, \alpha_ {\text{dual}})\)。这一步确保新点不会“撞”到边界。 更新迭代点： \[ x^{k+1} = x^k + \alpha \Delta x, \quad y^{k+1} = y^k + \alpha \Delta y, \quad s^{k+1} = s^k + \alpha \Delta s \] 更新中心参数 \( \mu \)： 这是算法的艺术所在。常用的启发式方法是根据当前互补间隙的大小来设定 \( \mu \)： \[ \mu_ {k+1} = \sigma \cdot \frac{(x^{k+1})^T s^{k+1}}{n} \] 其中，\( (x^{k+1})^T s^{k+1} \) 是当前的 对偶间隙 ，\(n\) 是变量维度，\(\sigma \in (0,1)\) 是一个 中心参数 。较小的 \(\sigma\) 会使下一步更强调 减少对偶间隙 （向最优解靠拢），较大的 \(\sigma\) 会使下一步更强调 靠近中心路径 （保持内点性质）。 收敛判断： 检查原始残差 \(||Ax-b||\)、对偶残差 \(||A^T y + s - c||\) 和对偶间隙 \(x^T s\) 是否都小于预设的容差。若满足，则停止迭代，输出近似最优解。 第五步：总结、扩展与意义 总结流程： 原始-对偶内点法 = 内点法哲学 (在内部逼近) + 扰动KKT条件 (定义中心路径) + 牛顿法 (沿路径搜索方向) + 谨慎的步长与参数更新 (保持内点性与收敛性)。 扩展： 凸二次规划与半定规划： 该方法的框架可以很自然地推广到凸二次规划（QP）、二阶锥规划（SOCP）和半定规划（SDP），只需修改对应的互补松弛条件（如 \(XS = \mu I\) 用于SDP）和牛顿方程。 非可行启动： 上述描述从可行内点开始。实际算法（如Mehrotra预测-校正算法）通常从 任意一个正点 (\(x>0, s>0\)) 开始，即使不满足等式约束。牛顿方向会同时致力于减少可行性误差和互补间隙，具有更强的实用性。 重要意义： 多项式时间复杂性： 理论上，原始-对偶内点法可以在多项式步骤内找到问题的一个近似最优解，这是它在理论上的巨大优势。 高效实践： 对于大规模稀疏线性/凸优化问题，原始-对偶内点法通常比单纯形法更高效、更稳定，成为现代优化求解器（如Gurobi, CPLEX, MOSEK）的核心算法之一。 统一框架： 它为解决一大类凸优化问题提供了一个强大而统一的数值计算框架。