线性规划的原始-对偶内点法求解示例
题目描述
考虑以下线性规划问题：
最大化：\(z = 4x_1 + 6x_2\)
约束条件：
\(x_1 + 2x_2 \leq 10\)
\(2x_1 + x_2 \leq 10\)
\(x_1 \geq 0, x_2 \geq 0\)
我们将使用原始-对偶内点法来求解这个问题。与单纯形法在可行域顶点间移动不同，内点法从可行域内部出发，沿着一条中心路径逼近最优解。原始-对偶方法是其中最有效和广泛应用的内点法之一。
解题过程
第一步：将问题转化为标准形式
原始-对偶内点法通常处理等式约束的非负问题。因此，我们首先引入松弛变量 \(x_3\) 和 \(x_4\)，将不等式转化为等式。
标准形式如下：
最大化：\(z = 4x_1 + 6x_2 + 0 \cdot x_3 + 0 \cdot x_4\)
约束条件：
\(x_1 + 2x_2 + x_3 = 10\)
\(2x_1 + x_2 + x_4 = 10\)
\(x_1, x_2, x_3, x_4 \geq 0\)
我们可以用矩阵形式表示：
最大化：\(\mathbf{c}^T \mathbf{x}\)
满足：\(A\mathbf{x} = \mathbf{b}\), \(\mathbf{x} \geq 0\)
其中，
\(\mathbf{c} = \begin{bmatrix} 4 \\ 6 \\ 0 \\ 0 \end{bmatrix}\),
\(A = \begin{bmatrix} 1 & 2 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{bmatrix}\),
\(\mathbf{b} = \begin{bmatrix} 10 \\ 10 \end{bmatrix}\),
\(\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}\).
第二步：写出对偶问题并引入互补松弛条件
对于上述标准形式的原始问题，其对偶问题为：
最小化：\(\mathbf{b}^T \mathbf{y}\)
满足：\(A^T \mathbf{y} \geq \mathbf{c}\), \(\mathbf{y}\) 无符号限制（因为原始约束是等式）。
引入对偶松弛变量 \(\mathbf{s} \geq 0\)，将对偶不等式约束转化为等式：
\(A^T \mathbf{y} - \mathbf{s} = \mathbf{c}\)
其中，\(\mathbf{y} = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}\), \(\mathbf{s} = \begin{bmatrix} s_1 \\ s_2 \\ s_3 \\ s_4 \end{bmatrix}\).
现在，原始可行性（PF）、对偶可行性（DF）和互补松弛条件是问题取得最优解的必要和充分条件：
- 原始可行性 (PF): \(A\mathbf{x} = \mathbf{b}\), \(\mathbf{x} \geq 0\)
- 对偶可行性 (DF): \(A^T \mathbf{y} - \mathbf{s} = \mathbf{c}\), \(\mathbf{s} \geq 0\)
- 互补松弛条件: \(x_i s_i = 0\), 对于所有 \(i = 1, 2, 3, 4\). (这可以写成矩阵形式 \(X S \mathbf{e} = 0\)，其中 \(X\) 和 \(S\) 是以 \(\mathbf{x}\) 和 \(\mathbf{s}\) 为对角元素的对角矩阵，\(\mathbf{e}\) 是全1向量)。
第三步：修改互补松弛条件并定义中心路径
互补松弛条件 \(x_i s_i = 0\) 是非线性的，是求解的主要困难。原始-对偶内点法的核心思想是将其“松弛”，用一个参数 \(\mu > 0\) 来修正它。
我们将互补松弛条件修改为：
\(x_i s_i = \mu\), 对于所有 \(i\). (矩阵形式：\(X S \mathbf{e} = \mu \mathbf{e}\))
现在，我们要求解的系统方程是：
\(A\mathbf{x} = \mathbf{b}\) ... (1)
\(A^T \mathbf{y} - \mathbf{s} = \mathbf{c}\) ... (2)
\(X S \mathbf{e} = \mu \mathbf{e}\) ... (3)
\(\mathbf{x} > 0\), \(\mathbf{s} > 0\)
对于每一个 \(\mu > 0\)，这个系统都有唯一解 \((\mathbf{x}(\mu), \mathbf{y}(\mu), \mathbf{s}(\mu))\)。当 \(\mu\) 从无穷大变化到0时，这些解的轨迹称为“中心路径”。当 \(\mu \to 0\) 时，中心路径上的点趋近于原始和对偶问题的最优解。我们的策略是跟随这条路径。
第四步：应用牛顿法求搜索方向
对于给定的当前点 \((\mathbf{x}^k, \mathbf{y}^k, \mathbf{s}^k)\) 和参数 \(\mu_k\)，我们希望找到一个新的点更接近 \((\mathbf{x}(\mu_k), \mathbf{y}(\mu_k), \mathbf{s}(\mu_k))\)。我们通过求解该非线性系统的线性近似（牛顿法）来实现。
定义残差：
\(\mathbf{r}_b = A\mathbf{x} - \mathbf{b}\) (原始可行性残差)
\(\mathbf{r}_c = A^T \mathbf{y} - \mathbf{s} - \mathbf{c}\) (对偶可行性残差)
\(\mathbf{r}_\mu = X S \mathbf{e} - \mu \mathbf{e}\) (互补松弛条件残差)
在理想点，所有残差都为0。牛顿法通过求解以下线性系统来寻找位移 \((\Delta \mathbf{x}, \Delta \mathbf{y}, \Delta \mathbf{s})\)：
\[\begin{bmatrix} 0 & A^T & -I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta \mathbf{x} \\ \Delta \mathbf{y} \\ \Delta \mathbf{s} \end{bmatrix} = - \begin{bmatrix} \mathbf{r}_c \\ \mathbf{r}_b \\ \mathbf{r}_\mu \end{bmatrix} \]
代入我们的具体问题：
\(A = \begin{bmatrix} 1 & 2 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{bmatrix}\), \(I\) 是4x4单位矩阵。
假设在迭代中某点，\(X = \begin{bmatrix} x_1 & 0 & 0 & 0 \\ 0 & x_2 & 0 & 0 \\ 0 & 0 & x_3 & 0 \\ 0 & 0 & 0 & x_4 \end{bmatrix}\), \(S\) 类似。
第五步：迭代求解（示例步骤）
我们无法在此完成所有迭代，但可以展示第一步的逻辑。关键在于选择初始点、参数 \(\mu\) 和步长。
-
选择初始点：我们通常选择一个严格的可行内点，即满足 \(\mathbf{x} > 0\), \(\mathbf{s} > 0\), \(A\mathbf{x} = \mathbf{b}\), \(A^T \mathbf{y} - \mathbf{s} = \mathbf{c}\)。一个简单的初始点可以是 \(\mathbf{x}^0 = (1, 1, 7, 7)^T\) (代入原约束验证: 1+21+7=10, 21+1+7=10)，\(\mathbf{y}^0 = (1, 1)^T\)，然后根据对偶约束 \(A^T \mathbf{y} - \mathbf{s} = \mathbf{c}\) 计算 \(\mathbf{s}^0\)。
计算 \(A^T \mathbf{y}^0 = \begin{bmatrix} 1*1+2*1=3 \\ 2*1+1*1=3 \\ 1*1+0*1=1 \\ 0*1+1*1=1 \end{bmatrix}\)，所以 \(\mathbf{s}^0 = A^T \mathbf{y}^0 - \mathbf{c} = \begin{bmatrix} 3-4=-1 \\ 3-6=-3 \\ 1-0=1 \\ 1-0=1 \end{bmatrix}\)。这里 \(s_1, s_2 < 0\)，不满足 \(\mathbf{s} > 0\)。因此需要更复杂的初始点构造方法（如使用人工变量），为简化，我们假设经过处理得到了一个可行的初始点 \(\mathbf{x}^0 = (2, 2, 4, 4)^T\), \(\mathbf{y}^0 = (1, 2)^T\), \(\mathbf{s}^0 = (1, 1, 1, 2)^T\) (此点需满足对偶约束，这里仅为示意)。
-
设定参数 \(\mu\)：一个常见选择是 \(\mu = \frac{\mathbf{x}^T \mathbf{s}}{n}\) 的某个比例，其中 \(n\) 是变量个数（这里是4）。这度量了平均互补性乘积。假设我们计算得 \(\mu^0 = 2\)。
-
计算牛顿方向：将当前点 \((\mathbf{x}^0, \mathbf{y}^0, \mathbf{s}^0)\) 和 \(\mu^0\) 代入第四步的线性系统，求解出位移 \((\Delta \mathbf{x}, \Delta \mathbf{y}, \Delta \mathbf{s})\)。这涉及求解一个线性方程组。
-
计算步长：我们需要确保新点 \((\mathbf{x}^0 + \alpha_p \Delta \mathbf{x}, \mathbf{y}^0 + \alpha_d \Delta \mathbf{y}, \mathbf{s}^0 + \alpha_d \Delta \mathbf{s})\) 满足 \(\mathbf{x} > 0\), \(\mathbf{s} > 0\)。我们选择最大可能的步长 \(\alpha_p \in (0, 1]\) 和 \(\alpha_d \in (0, 1]\)，使得正性得以保持。通常取略小于1的分数（如0.995）来避免触及边界。
-
更新迭代点：用计算出的步长和方向更新所有变量。
\(\mathbf{x}^1 = \mathbf{x}^0 + \alpha_p \Delta \mathbf{x}\)
\(\mathbf{y}^1 = \mathbf{y}^0 + \alpha_d \Delta \mathbf{y}\)
\(\mathbf{s}^1 = \mathbf{s}^0 + \alpha_d \Delta \mathbf{s}\) -
检查收敛：计算残差 \(\mathbf{r}_b\), \(\mathbf{r}_c\) 和对偶间隙 \(\mathbf{x}^T \mathbf{s}\)。如果它们都小于一个预设的很小容差（如 \(10^{-8}\)），则停止迭代，当前点即为近似最优解。否则，更新参数 \(\mu\)（通常随着迭代减小，例如 \(\mu^{k+1} = \sigma \mu^k\), \(\sigma \in (0, 1)\)），然后回到第3步。
最终结果
通过多次迭代，原始-对偶内点法将生成一个点列，收敛到最优解。对于这个具体问题，最优解是 \(x_1^* = 10/3, x_2^* = 10/3\)，最优目标函数值 \(z^* = 100/3\)。内点法得到的解将无限逼近这个值。