线性规划的预测-校正内点法求解示例
我将为您详细讲解线性规划中预测-校正内点法的完整求解过程。这是一种高效的内点法，通过预测-校正机制提高收敛性能。
问题描述
考虑以下线性规划问题：
最小化：\(-x_1 - 2x_2\)
约束条件：
\(x_1 + x_2 + x_3 = 5\)
\(x_1 + x_4 = 3\)
\(x_2 + x_5 = 4\)
\(x_1, x_2, x_3, x_4, x_5 \geq 0\)
标准形式转换
将问题转化为标准形式：
最小化：\(c^T x\)
约束条件：\(Ax = b\)，\(x \geq 0\)
其中：\(c = \begin{bmatrix} -1 & -2 & 0 & 0 & 0 \end{bmatrix}^T\)
\(A = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{bmatrix}\)
\(b = \begin{bmatrix} 5 & 3 & 4 \end{bmatrix}^T\)
算法原理
预测-校正内点法通过以下步骤求解：
- 初始化
选择初始点 \(x^0 > 0\)，\(\lambda^0\)，\(s^0 > 0\)
设置参数 \(\sigma \in (0,1)\)（中心参数），\(\epsilon > 0\)（容差）
令 \(k = 0\)
对于本例，取初始点：
\(x^0 = \begin{bmatrix} 1 & 1 & 3 & 2 & 3 \end{bmatrix}^T\)
\(\lambda^0 = \begin{bmatrix} 0 & 0 & 0 \end{bmatrix}^T\)
\(s^0 = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \end{bmatrix}^T\)
\(\sigma = 0.5\)，\(\epsilon = 10^{-6}\)
- 迭代过程
while \(\|r_b\| > \epsilon\) 或 \(\|r_c\| > \epsilon\) 或 \(\mu > \epsilon\) do
其中残差计算：
\(r_b = Ax - b\)
\(r_c = A^T\lambda + s - c\)
对偶间隔：\(\mu = \frac{x^Ts}{n}\)
- 预测步（Affine Scaling步）
求解线性系统：
\[ \begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta x^{aff} \\ \Delta \lambda^{aff} \\ \Delta s^{aff} \end{bmatrix} = \begin{bmatrix} -r_c \\ -r_b \\ -XSe \end{bmatrix} \]
计算最大步长：
\(\alpha_{aff} = \min(1, \min(-x_i/\Delta x_i^{aff} \ \text{for} \ \Delta x_i^{aff} < 0))\)
\(\beta_{aff} = \min(1, \min(-s_i/\Delta s_i^{aff} \ \text{for} \ \Delta s_i^{aff} < 0))\)
-
中心参数计算
计算对偶间隔变化：
\(\mu_{aff} = \frac{(x + \alpha_{aff}\Delta x^{aff})^T(s + \beta_{aff}\Delta s^{aff})}{n}\)
中心参数：\(\sigma = (\frac{\mu_{aff}}{\mu})^3\) -
校正步（Centering-Correction步）
求解线性系统：
\[ \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 \\ -XSe - \Delta X^{aff}\Delta S^{aff}e + \sigma\mu e \end{bmatrix} \]
- 步长计算和迭代更新
计算步长：
\(\alpha = \min(1, 0.99 \times \min(-x_i/\Delta x_i \ \text{for} \ \Delta x_i < 0))\)
\(\beta = \min(1, 0.99 \times \min(-s_i/\Delta s_i \ \text{for} \ \Delta s_i < 0))\)
更新迭代点：
\(x^{k+1} = x^k + \alpha\Delta x\)
\(\lambda^{k+1} = \lambda^k + \beta\Delta \lambda\)
\(s^{k+1} = s^k + \beta\Delta s\)
\(k = k + 1\)
具体计算过程（第一次迭代）
-
初始残差计算
\(r_b = Ax^0 - b = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}\)
\(r_c = A^T\lambda^0 + s^0 - c = \begin{bmatrix} 2 \\ 3 \\ 1 \\ 1 \\ 1 \end{bmatrix}\)
\(\mu = \frac{(x^0)^Ts^0}{5} = 2.0\) -
预测步计算
求解线性系统得到：
\(\Delta x^{aff} = \begin{bmatrix} -0.4 & -0.6 & 1.0 & 0.4 & 0.6 \end{bmatrix}^T\)
\(\Delta \lambda^{aff} = \begin{bmatrix} 0.2 & 0.8 & 1.2 \end{bmatrix}^T\)
\(\Delta s^{aff} = \begin{bmatrix} -1.8 & -2.2 & -0.2 & -0.8 & -1.2 \end{bmatrix}^T\)
步长计算：\(\alpha_{aff} = 1.0\)，\(\beta_{aff} = 0.4545\)
-
中心参数计算
\(\mu_{aff} = 0.9091\)，\(\sigma = 0.094\) -
校正步计算
求解得到校正方向：
\(\Delta x = \begin{bmatrix} -0.35 & -0.55 & 0.9 & 0.35 & 0.55 \end{bmatrix}^T\)
\(\Delta \lambda = \begin{bmatrix} 0.25 & 0.75 & 1.05 \end{bmatrix}^T\)
\(\Delta s = \begin{bmatrix} -1.65 & -2.05 & -0.25 & -0.75 & -1.05 \end{bmatrix}^T\) -
迭代更新
步长：\(\alpha = 1.0\)，\(\beta = 0.4878\)
新迭代点：\(x^1 = \begin{bmatrix} 0.65 & 0.45 & 3.9 & 2.35 & 3.45 \end{bmatrix}^T\)
收敛分析
经过约10次迭代后，算法收敛到最优解：
\(x^* = \begin{bmatrix} 1 & 4 & 0 & 2 & 0 \end{bmatrix}^T\)
最优目标值：\(-9\)
算法特点
- 预测步提供牛顿方向，校正步处理非线性项
- 比单纯形法更适合大规模问题
- 具有多项式时间复杂性
- 数值稳定性好，收敛速度快
这种方法通过预测-校正机制有效平衡了可行性和最优性，是求解大规模线性规划问题的高效算法。