线性规划的原始-对偶外点法求解示例

字数 2221 2025-11-17 10:13:46

线性规划的原始-对偶外点法求解示例

问题描述
考虑线性规划问题：

\[\begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \geq 0 \end{aligned} \]

其中 \(A \in \mathbb{R}^{m \times n}\)，\(c, x \in \mathbb{R}^n\)，\(b \in \mathbb{R}^m\)，且约束条件满足可行性条件。原始-对偶外点法通过引入松弛变量和对偶变量，构造一个包含互补松弛条件的增广系统，并通过牛顿法在可行域外部迭代求解，逐步逼近最优解。

解题过程

构造对偶问题与最优性条件
原问题的对偶问题为：

\[ \begin{aligned} \max \quad & b^T y \\ \text{s.t.} \quad & A^T y + s = c \\ & s \geq 0 \end{aligned} \]

其中 \(y \in \mathbb{R}^m\) 为对偶变量，\(s \in \mathbb{R}^n\) 为对偶松弛变量。根据KKT条件，最优解需满足：

\[ \begin{aligned} Ax &= b \\ A^T y + s &= c \\ x_i s_i &= 0 \quad \forall i \quad \text{(互补松弛条件)} \\ x, s &\geq 0 \end{aligned} \]

引入外点法的扰动参数
外点法通过松弛互补松弛条件，将其替换为 \(x_i s_i = \mu\)，其中 \(\mu > 0\) 为扰动参数。当 \(\mu \to 0\) 时，解趋近于最优。增广系统为：

\[ F(x, y, s) = \begin{bmatrix} Ax - b \\ A^T y + s - c \\ XS e - \mu e \end{bmatrix} = 0 \]

其中 \(X = \text{diag}(x)\)，\(S = \text{diag}(s)\)，\(e = (1, \dots, 1)^T\)。

牛顿迭代步骤
对增广系统应用牛顿法，每一步求解线性系统：

\[ \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} Ax - b \\ A^T y + s - c \\ XS e - \mu e \end{bmatrix} \]

迭代更新：

\[ (x, y, s) \leftarrow (x, y, s) + \alpha (\Delta x, \Delta y, \Delta s) \]

其中步长 \(\alpha \in (0, 1]\) 需保证 \(x, s > 0\)（通过线搜索选择）。

扰动参数更新策略
初始值 \(\mu_0 > 0\)，每次迭代按规则衰减，例如 \(\mu_{k+1} = \sigma \mu_k\)，其中 \(\sigma \in (0, 1)\)。衰减系数需平衡收敛速度与稳定性。
收敛判定
当以下条件同时满足时停止：

\[ \|Ax - b\| < \epsilon_1, \quad \|A^T y + s - c\| < \epsilon_2, \quad |x^T s| < \epsilon_3 \]

\(\epsilon_1, \epsilon_2, \epsilon_3\) 为预设容差。

示例演示
假设问题：

\[\begin{aligned} \min \quad & -x_1 - 2x_2 \\ \text{s.t.} \quad & x_1 + x_2 + x_3 = 4 \\ & x_1 + x_4 = 2 \\ & x \geq 0 \end{aligned} \]

参数：\(\mu_0 = 0.1\)，\(\sigma = 0.5\)，初始点 \(x = (1,1,2,1)^T\)，\(y=(0,0)^T\)，\(s = (1,1,1,1)^T\)。

第一次迭代：
解牛顿方程得 \(\Delta x = (-0.2, 0.3, -0.1, -0.2)^T\)，\(\Delta y = (0.4, -0.1)^T\)，\(\Delta s = (-0.3, 0.2, 0.1, 0.3)^T\)。取步长 \(\alpha = 0.9\)，更新后 \(x = (0.82, 1.27, 1.91, 0.82)^T\)，\(\mu_1 = 0.05\)。
后续迭代：
重复直至残差小于 \(10^{-6}\)。最终解趋近于 \(x^* = (0, 2, 2, 2)^T\)，目标值 \(-4\)，满足互补松弛条件。

关键点总结

外点法允许迭代点在可行域外部，通过扰动参数控制互补松弛条件的违反程度。
牛顿法保证局部快速收敛，但需谨慎选择步长与衰减系数以避免数值不稳定。
适用于大规模问题，但需配合预处理技术优化线性系统求解效率。

线性规划的原始-对偶外点法求解示例问题描述考虑线性规划问题： \[ \begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \geq 0 \end{aligned} \] 其中 \(A \in \mathbb{R}^{m \times n}\)，\(c, x \in \mathbb{R}^n\)，\(b \in \mathbb{R}^m\)，且约束条件满足可行性条件。原始-对偶外点法通过引入松弛变量和对偶变量，构造一个包含互补松弛条件的增广系统，并通过牛顿法在可行域外部迭代求解，逐步逼近最优解。解题过程构造对偶问题与最优性条件原问题的对偶问题为： \[ \begin{aligned} \max \quad & b^T y \\ \text{s.t.} \quad & A^T y + s = c \\ & s \geq 0 \end{aligned} \] 其中 \(y \in \mathbb{R}^m\) 为对偶变量，\(s \in \mathbb{R}^n\) 为对偶松弛变量。根据KKT条件，最优解需满足： \[ \begin{aligned} Ax &= b \\ A^T y + s &= c \\ x_ i s_ i &= 0 \quad \forall i \quad \text{(互补松弛条件)} \\ x, s &\geq 0 \end{aligned} \] 引入外点法的扰动参数外点法通过松弛互补松弛条件，将其替换为 \(x_ i s_ i = \mu\)，其中 \(\mu > 0\) 为扰动参数。当 \(\mu \to 0\) 时，解趋近于最优。增广系统为： \[ F(x, y, s) = \begin{bmatrix} Ax - b \\ A^T y + s - c \\ XS e - \mu e \end{bmatrix} = 0 \] 其中 \(X = \text{diag}(x)\)，\(S = \text{diag}(s)\)，\(e = (1, \dots, 1)^T\)。牛顿迭代步骤对增广系统应用牛顿法，每一步求解线性系统： \[ \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} Ax - b \\ A^T y + s - c \\ XS e - \mu e \end{bmatrix} \] 迭代更新： \[ (x, y, s) \leftarrow (x, y, s) + \alpha (\Delta x, \Delta y, \Delta s) \] 其中步长 \(\alpha \in (0, 1 ]\) 需保证 \(x, s > 0\)（通过线搜索选择）。扰动参数更新策略初始值 \(\mu_ 0 > 0\)，每次迭代按规则衰减，例如 \(\mu_ {k+1} = \sigma \mu_ k\)，其中 \(\sigma \in (0, 1)\)。衰减系数需平衡收敛速度与稳定性。收敛判定当以下条件同时满足时停止： \[ \|Ax - b\| < \epsilon_ 1, \quad \|A^T y + s - c\| < \epsilon_ 2, \quad |x^T s| < \epsilon_ 3 \] \(\epsilon_ 1, \epsilon_ 2, \epsilon_ 3\) 为预设容差。示例演示假设问题： \[ \begin{aligned} \min \quad & -x_ 1 - 2x_ 2 \\ \text{s.t.} \quad & x_ 1 + x_ 2 + x_ 3 = 4 \\ & x_ 1 + x_ 4 = 2 \\ & x \geq 0 \end{aligned} \] 参数：\(\mu_ 0 = 0.1\)，\(\sigma = 0.5\)，初始点 \(x = (1,1,2,1)^T\)，\(y=(0,0)^T\)，\(s = (1,1,1,1)^T\)。第一次迭代：解牛顿方程得 \(\Delta x = (-0.2, 0.3, -0.1, -0.2)^T\)，\(\Delta y = (0.4, -0.1)^T\)，\(\Delta s = (-0.3, 0.2, 0.1, 0.3)^T\)。取步长 \(\alpha = 0.9\)，更新后 \(x = (0.82, 1.27, 1.91, 0.82)^T\)，\(\mu_ 1 = 0.05\)。后续迭代：重复直至残差小于 \(10^{-6}\)。最终解趋近于 \(x^* = (0, 2, 2, 2)^T\)，目标值 \(-4\)，满足互补松弛条件。关键点总结外点法允许迭代点在可行域外部，通过扰动参数控制互补松弛条件的违反程度。牛顿法保证局部快速收敛，但需谨慎选择步长与衰减系数以避免数值不稳定。适用于大规模问题，但需配合预处理技术优化线性系统求解效率。