线性规划的路径跟踪内点法求解示例
字数 3619 2025-10-26 23:21:19

线性规划的路径跟踪内点法求解示例

题目描述
考虑以下线性规划问题：
最小化：\(c^T x\)
满足：\(Ax = b\)，\(x \geq 0\)
其中，\(c = \begin{bmatrix} -1 \\ -2 \end{bmatrix}\)，\(A = \begin{bmatrix} 1 & 1 \end{bmatrix}\)，\(b = \begin{bmatrix} 5 \end{bmatrix}\)，决策变量 \(x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\)。路径跟踪内点法通过引入障碍参数，将约束优化问题转化为一系列无约束问题，并沿中心路径逼近最优解。本题将演示该算法的完整迭代过程。

解题过程

1. 问题重构与障碍函数引入
原始问题包含非负约束 \(x \geq 0\)。路径跟踪法使用对数障碍函数将其转化为：
最小化：\(c^T x - \mu \sum_{j=1}^n \ln x_j\)
满足：\(Ax = b\)
其中 \(\mu > 0\) 是障碍参数。当 \(\mu \to 0\)，障碍问题的最优解逼近原始问题的最优解。中心路径由不同 \(\mu\) 对应的最优解构成。

2. 最优性条件推导
通过拉格朗日函数 \(L(x, \lambda) = c^T x - \mu \sum \ln x_j - \lambda^T (Ax - b)\)，导出KKT条件：

  1. \(c - \mu X^{-1} e - A^T \lambda = 0\)（梯度条件）
  2. \(Ax = b\)（原始可行性）
  3. \(x > 0\)（严格内点性）
    其中 \(X = \text{diag}(x)\)，\(e = [1, \dots, 1]^T\)。引入对偶变量 \(s = \mu X^{-1} e > 0\)，条件1改写为：
  • \(A^T \lambda + s = c\)
  • \(X S e = \mu e\)（互补松弛条件，\(S = \text{diag}(s)\)）

3. 牛顿方向计算
当前迭代点 \((x, \lambda, s)\) 满足 \(x > 0, s > 0\)。定义残差：

  • \(r_c = A^T \lambda + s - c\)（对偶可行性残差）
  • \(r_b = Ax - b\)（原始可行性残差）
  • \(r_\mu = X S e - \mu e\)（中心性残差）
    牛顿步方向 \((\Delta x, \Delta \lambda, \Delta s)\) 通过解线性系统求得：

\[\begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta s \end{bmatrix} = - \begin{bmatrix} r_c \\ r_b \\ r_\mu \end{bmatrix} \]

本例中，\(A = [1, 1]\)，系统简化为：

  1. \(\Delta \lambda + \Delta s_1 = -r_{c1}\)
  2. \(\Delta \lambda + \Delta s_2 = -r_{c2}\)
  3. \(\Delta x_1 + \Delta x_2 = -r_b\)
  4. \(s_1 \Delta x_1 + x_1 \Delta s_1 = -r_{\mu1}\)
  5. \(s_2 \Delta x_2 + x_2 \Delta s_2 = -r_{\mu2}\)

4. 迭代初始化
选取初始点 \(x^{(0)} = [2, 3]^T\)（满足 \(Ax = 5\)），\(\lambda^{(0)} = 0\)，\(s^{(0)} = c - A^T \lambda = [-1, -2]^T\)。但 \(s\) 需为正，故调整：设 \(s^{(0)} = [1, 1]^T\)，重新计算 \(\lambda\) 使 \(r_c\) 最小化（最小二乘解）：
\(A^T \lambda = c - s = [-2, -3]^T\)，解得 \(\lambda = -2.5\)。验证：\(A^T \lambda + s = [1.5, 1.5]^T\)，与 \(c\) 有偏差，但可通过迭代修正。

5. 迭代步骤详解（以第1轮为例）
设 \(\mu = 0.1\)，当前点 \(x = [2, 3]^T\)，\(\lambda = -2.5\)，\(s = [1, 1]^T\)：

  • 残差计算：
    • \(r_c = A^T \lambda + s - c = [1.5, 1.5]^T - [-1, -2]^T = [2.5, 3.5]^T\)
    • \(r_b = Ax - b = 5 - 5 = 0\)
    • \(r_\mu = X S e - \mu e = [2, 3]^T - [0.1, 0.1]^T = [1.9, 2.9]^T\)
  • 解牛顿系统：
    由方程1-2得：\(\Delta s_1 = -r_{c1} - \Delta \lambda = -2.5 - \Delta \lambda\)，\(\Delta s_2 = -3.5 - \Delta \lambda\)
    代入方程4-5：\(s_1 \Delta x_1 + x_1 (-2.5 - \Delta \lambda) = -1.9\) → \(\Delta x_1 - 2 \Delta \lambda = 0.6\)
    \(s_2 \Delta x_2 + x_2 (-3.5 - \Delta \lambda) = -2.9\) → \(\Delta x_2 - 3 \Delta \lambda = 7.6\)
    结合方程3：\(\Delta x_1 + \Delta x_2 = 0\)，解得：
    \(\Delta \lambda = -1.4\)，\(\Delta x_1 = -2.2\)，\(\Delta x_2 = 2.2\)，\(\Delta s_1 = -1.1\)，\(\Delta s_2 = -2.1\)
  • 步长选择：保证 \(x, s > 0\)。计算最大步长 \(\alpha_{\max} = \min( \min(-x_i / \Delta x_i \text{ for } \Delta x_i < 0), \min(-s_i / \Delta s_i \text{ for } \Delta s_i < 0) ) = \min(2/2.2, 1/1.1, 1/2.1) \approx 0.476\)。取 \(\alpha = 0.9 \times 0.476 \approx 0.428\)。
  • 更新点：
    \(x^{(1)} = [2, 3]^T + 0.428 \times [-2.2, 2.2]^T \approx [1.06, 3.94]^T\)
    \(\lambda^{(1)} = -2.5 + 0.428 \times (-1.4) \approx -3.10\)
    \(s^{(1)} = [1, 1]^T + 0.428 \times [-1.1, -2.1]^T \approx [0.53, 0.10]^T\)

6. 收敛判断与参数更新
检查残差范数 \(\|r_b\|, \|r_c\|\) 和互补间隙 \(\mu = x^T s / n\)。若未达容差（如 \(10^{-6}\)），则减小 \(\mu\)（如 \(\mu_{\text{new}} = 0.1 \times \mu_{\text{old}}\)），继续迭代。经多轮迭代后，解收敛至 \(x^* \approx [0, 5]^T\)，目标值 \(-10\)，与单纯形法结果一致。

关键点总结

  • 路径跟踪法通过中心路径保持内点性，避免边界震荡。
  • 牛顿步提供快速收敛方向，步长控制保证严格可行性。
  • 障碍参数 \(\mu\) 逐步减小，平衡收敛速度与数值稳定性。
线性规划的路径跟踪内点法求解示例 题目描述 考虑以下线性规划问题： 最小化：\( c^T x \) 满足：\( Ax = b \)，\( x \geq 0 \) 其中，\( c = \begin{bmatrix} -1 \\ -2 \end{bmatrix} \)，\( A = \begin{bmatrix} 1 & 1 \end{bmatrix} \)，\( b = \begin{bmatrix} 5 \end{bmatrix} \)，决策变量 \( x = \begin{bmatrix} x_ 1 \\ x_ 2 \end{bmatrix} \)。路径跟踪内点法通过引入障碍参数，将约束优化问题转化为一系列无约束问题，并沿中心路径逼近最优解。本题将演示该算法的完整迭代过程。 解题过程 1. 问题重构与障碍函数引入 原始问题包含非负约束 \( x \geq 0 \)。路径跟踪法使用对数障碍函数将其转化为： 最小化：\( c^T x - \mu \sum_ {j=1}^n \ln x_ j \) 满足：\( Ax = b \) 其中 \( \mu > 0 \) 是障碍参数。当 \( \mu \to 0 \)，障碍问题的最优解逼近原始问题的最优解。中心路径由不同 \( \mu \) 对应的最优解构成。 2. 最优性条件推导 通过拉格朗日函数 \( L(x, \lambda) = c^T x - \mu \sum \ln x_ j - \lambda^T (Ax - b) \)，导出KKT条件： \( c - \mu X^{-1} e - A^T \lambda = 0 \)（梯度条件） \( Ax = b \)（原始可行性） \( x > 0 \)（严格内点性） 其中 \( X = \text{diag}(x) \)，\( e = [ 1, \dots, 1 ]^T \)。引入对偶变量 \( s = \mu X^{-1} e > 0 \)，条件1改写为： \( A^T \lambda + s = c \) \( X S e = \mu e \)（互补松弛条件，\( S = \text{diag}(s) \)） 3. 牛顿方向计算 当前迭代点 \( (x, \lambda, s) \) 满足 \( x > 0, s > 0 \)。定义残差： \( r_ c = A^T \lambda + s - c \)（对偶可行性残差） \( r_ b = Ax - b \)（原始可行性残差） \( r_ \mu = X S e - \mu e \)（中心性残差） 牛顿步方向 \( (\Delta x, \Delta \lambda, \Delta s) \) 通过解线性系统求得： \[ \begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta \lambda \\ \Delta s \end{bmatrix} = - \begin{bmatrix} r_ c \\ r_ b \\ r_ \mu \end{bmatrix} \] 本例中，\( A = [ 1, 1 ] \)，系统简化为： \( \Delta \lambda + \Delta s_ 1 = -r_ {c1} \) \( \Delta \lambda + \Delta s_ 2 = -r_ {c2} \) \( \Delta x_ 1 + \Delta x_ 2 = -r_ b \) \( s_ 1 \Delta x_ 1 + x_ 1 \Delta s_ 1 = -r_ {\mu1} \) \( s_ 2 \Delta x_ 2 + x_ 2 \Delta s_ 2 = -r_ {\mu2} \) 4. 迭代初始化 选取初始点 \( x^{(0)} = [ 2, 3]^T \)（满足 \( Ax = 5 \)），\( \lambda^{(0)} = 0 \)，\( s^{(0)} = c - A^T \lambda = [ -1, -2]^T \)。但 \( s \) 需为正，故调整：设 \( s^{(0)} = [ 1, 1]^T \)，重新计算 \( \lambda \) 使 \( r_ c \) 最小化（最小二乘解）： \( A^T \lambda = c - s = [ -2, -3]^T \)，解得 \( \lambda = -2.5 \)。验证：\( A^T \lambda + s = [ 1.5, 1.5 ]^T \)，与 \( c \) 有偏差，但可通过迭代修正。 5. 迭代步骤详解（以第1轮为例） 设 \( \mu = 0.1 \)，当前点 \( x = [ 2, 3]^T \)，\( \lambda = -2.5 \)，\( s = [ 1, 1 ]^T \)： 残差计算： \( r_ c = A^T \lambda + s - c = [ 1.5, 1.5]^T - [ -1, -2]^T = [ 2.5, 3.5 ]^T \) \( r_ b = Ax - b = 5 - 5 = 0 \) \( r_ \mu = X S e - \mu e = [ 2, 3]^T - [ 0.1, 0.1]^T = [ 1.9, 2.9 ]^T \) 解牛顿系统： 由方程1-2得：\( \Delta s_ 1 = -r_ {c1} - \Delta \lambda = -2.5 - \Delta \lambda \)，\( \Delta s_ 2 = -3.5 - \Delta \lambda \) 代入方程4-5：\( s_ 1 \Delta x_ 1 + x_ 1 (-2.5 - \Delta \lambda) = -1.9 \) → \( \Delta x_ 1 - 2 \Delta \lambda = 0.6 \) \( s_ 2 \Delta x_ 2 + x_ 2 (-3.5 - \Delta \lambda) = -2.9 \) → \( \Delta x_ 2 - 3 \Delta \lambda = 7.6 \) 结合方程3：\( \Delta x_ 1 + \Delta x_ 2 = 0 \)，解得： \( \Delta \lambda = -1.4 \)，\( \Delta x_ 1 = -2.2 \)，\( \Delta x_ 2 = 2.2 \)，\( \Delta s_ 1 = -1.1 \)，\( \Delta s_ 2 = -2.1 \) 步长选择：保证 \( x, s > 0 \)。计算最大步长 \( \alpha_ {\max} = \min( \min(-x_ i / \Delta x_ i \text{ for } \Delta x_ i < 0), \min(-s_ i / \Delta s_ i \text{ for } \Delta s_ i < 0) ) = \min(2/2.2, 1/1.1, 1/2.1) \approx 0.476 \)。取 \( \alpha = 0.9 \times 0.476 \approx 0.428 \)。 更新点： \( x^{(1)} = [ 2, 3]^T + 0.428 \times [ -2.2, 2.2]^T \approx [ 1.06, 3.94 ]^T \) \( \lambda^{(1)} = -2.5 + 0.428 \times (-1.4) \approx -3.10 \) \( s^{(1)} = [ 1, 1]^T + 0.428 \times [ -1.1, -2.1]^T \approx [ 0.53, 0.10 ]^T \) 6. 收敛判断与参数更新 检查残差范数 \( \|r_ b\|, \|r_ c\| \) 和互补间隙 \( \mu = x^T s / n \)。若未达容差（如 \( 10^{-6} \)），则减小 \( \mu \)（如 \( \mu_ {\text{new}} = 0.1 \times \mu_ {\text{old}} \)），继续迭代。经多轮迭代后，解收敛至 \( x^* \approx [ 0, 5 ]^T \)，目标值 \( -10 \)，与单纯形法结果一致。 关键点总结 路径跟踪法通过中心路径保持内点性，避免边界震荡。 牛顿步提供快速收敛方向，步长控制保证严格可行性。 障碍参数 \( \mu \) 逐步减小，平衡收敛速度与数值稳定性。