基于线性规划的原始-对偶路径跟踪内点法求解示例

字数 2703 2025-11-04 20:47:20

基于线性规划的原始-对偶路径跟踪内点法求解示例

题目描述
考虑以下线性规划问题：
最小化：\(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} 3 \end{bmatrix}\)，\(x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\)。

原始-对偶路径跟踪内点法通过同时更新原始变量和对偶变量，并沿中心路径逼近最优解。

解题过程

1. 构造对偶问题与互补松弛条件

对偶问题为：最大化 \(b^T y\)，满足 \(A^T y + s = c\)，\(s \geq 0\)，其中 \(y\) 是对偶变量，\(s\) 是对偶松弛变量。
互补松弛条件：\(x_i s_i = 0\)（对于每个 \(i\)），\(x, s \geq 0\)。

2. 引入扰动参数与中心路径方程

定义扰动参数 \(\mu > 0\)，将互补松弛条件松弛为：\(x_i s_i = \mu\)（对于每个 \(i\)）。
中心路径方程：
- 原始可行性：\(Ax = b\)，\(x \geq 0\)。
- 对偶可行性：\(A^T y + s = c\)，\(s \geq 0\)。
- 扰动互补松弛：\(X s = \mu e\)，其中 \(X = \text{diag}(x)\)，\(e = (1,1)^T\)。

3. 初始化与参数设置

初始点选择：取 \(x^{(0)} = (1, 2)^T\)（满足 \(Ax = b\)），\(y^{(0)} = 0\)，\(s^{(0)} = c - A^T y = (-1, -2)^T\)（不满足 \(s \geq 0\)，需通过添加偏移量修正，此处直接进入迭代框架）。
实际计算中，需通过启发式选择严格可行内点。本例为简化，从近似点开始迭代。
设置参数：\(\mu_0 = \frac{x^{(0)T} s^{(0)}}{n} = \frac{(1)(-1) + (2)(-2)}{2} = -2.5\)（负数，说明初始点不可行，但算法可通过迭代调整）。

4. 迭代步骤（以第一次迭代为例）

步骤 4.1：计算当前对偶间隔与 \(\mu\)
对偶间隔 \(\delta = x^T s\)。初始 \(\delta = -5\)，目标是将 \(\mu\) 减小到 0。
设置 \(\mu = \sigma \cdot \frac{\delta}{n}\)，其中 \(\sigma \in (0,1)\) 是中心参数，取 \(\sigma = 0.5\)。则 \(\mu = 0.5 \times (-5)/2 = -1.25\)。
步骤 4.2：求解牛顿方向
牛顿系统为：

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

代入值：

\(A = [1, 1]\)，\(S = \text{diag}(s) = \text{diag}(-1, -2)\)，\(X = \text{diag}(1, 2)\)。
右端项：\(\mu e - X s = (-1.25) - [1 \times (-1), 2 \times (-2)]^T = [-1.25 - (-1), -1.25 - (-4)]^T = [-0.25, 2.75]^T\)。
解得牛顿方向（详细计算略）：\(\Delta x \approx (0.083, -0.083)^T\)，\(\Delta y \approx -0.5\)，\(\Delta s \approx (0.5, 0.5)^T\)。
步骤 4.3：计算步长并更新点
步长 \(\alpha \in (0,1]\) 需保证 \(x + \alpha \Delta x \geq 0\)，\(s + \alpha \Delta s \geq 0\)。取 \(\alpha = 0.9 \times \min\left( \min_i \left( \frac{-x_i}{\Delta x_i} \text{ 若 } \Delta x_i < 0 \right), \min_i \left( \frac{-s_i}{\Delta s_i} \text{ 若 } \Delta s_i < 0 \right) \right)\)。
计算得 \(\alpha \approx 0.9\)。更新：
- \(x^{(1)} = x^{(0)} + \alpha \Delta x \approx (1.075, 1.925)^T\)。
- \(y^{(1)} = y^{(0)} + \alpha \Delta y \approx -0.45\)。
- \(s^{(1)} = s^{(0)} + \alpha \Delta s \approx (-0.55, -1.55)^T\)。

5. 收敛判断与后续迭代

检查对偶间隔 \(\delta^{(1)} = x^{(1)T} s^{(1)} \approx -3.63\)（仍为负，因初始点不可行）。继续迭代，逐步调整 \(\mu\) 并向可行域靠近。
经过多次迭代（通常 10-20 步），点列将收敛到最优解 \(x^* = (0, 3)^T\)，\(y^* = -2\)，\(s^* = (1, 0)^T\)，目标函数值 \(-6\)。

6. 算法特点

路径跟踪法通过控制 \(\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} 3 \end{bmatrix} \)，\( x = \begin{bmatrix} x_ 1 \\ x_ 2 \end{bmatrix} \)。原始-对偶路径跟踪内点法通过同时更新原始变量和对偶变量，并沿中心路径逼近最优解。解题过程 1. 构造对偶问题与互补松弛条件对偶问题为：最大化 \( b^T y \)，满足 \( A^T y + s = c \)，\( s \geq 0 \)，其中 \( y \) 是对偶变量，\( s \) 是对偶松弛变量。互补松弛条件：\( x_ i s_ i = 0 \)（对于每个 \( i \)），\( x, s \geq 0 \)。 2. 引入扰动参数与中心路径方程定义扰动参数 \( \mu > 0 \)，将互补松弛条件松弛为：\( x_ i s_ i = \mu \)（对于每个 \( i \)）。中心路径方程：原始可行性：\( Ax = b \)，\( x \geq 0 \)。对偶可行性：\( A^T y + s = c \)，\( s \geq 0 \)。扰动互补松弛：\( X s = \mu e \)，其中 \( X = \text{diag}(x) \)，\( e = (1,1)^T \)。 3. 初始化与参数设置初始点选择：取 \( x^{(0)} = (1, 2)^T \)（满足 \( Ax = b \)），\( y^{(0)} = 0 \)，\( s^{(0)} = c - A^T y = (-1, -2)^T \)（不满足 \( s \geq 0 \)，需通过添加偏移量修正，此处直接进入迭代框架）。实际计算中，需通过启发式选择严格可行内点。本例为简化，从近似点开始迭代。设置参数：\( \mu_ 0 = \frac{x^{(0)T} s^{(0)}}{n} = \frac{(1)(-1) + (2)(-2)}{2} = -2.5 \)（负数，说明初始点不可行，但算法可通过迭代调整）。 4. 迭代步骤（以第一次迭代为例）步骤 4.1：计算当前对偶间隔与 \( \mu \) 对偶间隔 \( \delta = x^T s \)。初始 \( \delta = -5 \)，目标是将 \( \mu \) 减小到 0。设置 \( \mu = \sigma \cdot \frac{\delta}{n} \)，其中 \( \sigma \in (0,1) \) 是中心参数，取 \( \sigma = 0.5 \)。则 \( \mu = 0.5 \times (-5)/2 = -1.25 \)。步骤 4.2：求解牛顿方向牛顿系统为： \[ \begin{bmatrix} 0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \\ \Delta s \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ \mu e - X s \end{bmatrix} \] 代入值： \( A = [ 1, 1 ] \)，\( S = \text{diag}(s) = \text{diag}(-1, -2) \)，\( X = \text{diag}(1, 2) \)。右端项：\( \mu e - X s = (-1.25) - [ 1 \times (-1), 2 \times (-2)]^T = [ -1.25 - (-1), -1.25 - (-4)]^T = [ -0.25, 2.75 ]^T \)。解得牛顿方向（详细计算略）：\( \Delta x \approx (0.083, -0.083)^T \)，\( \Delta y \approx -0.5 \)，\( \Delta s \approx (0.5, 0.5)^T \)。步骤 4.3：计算步长并更新点步长 \( \alpha \in (0,1] \) 需保证 \( x + \alpha \Delta x \geq 0 \)，\( s + \alpha \Delta s \geq 0 \)。取 \( \alpha = 0.9 \times \min\left( \min_ i \left( \frac{-x_ i}{\Delta x_ i} \text{ 若 } \Delta x_ i < 0 \right), \min_ i \left( \frac{-s_ i}{\Delta s_ i} \text{ 若 } \Delta s_ i < 0 \right) \right) \)。计算得 \( \alpha \approx 0.9 \)。更新： \( x^{(1)} = x^{(0)} + \alpha \Delta x \approx (1.075, 1.925)^T \)。 \( y^{(1)} = y^{(0)} + \alpha \Delta y \approx -0.45 \)。 \( s^{(1)} = s^{(0)} + \alpha \Delta s \approx (-0.55, -1.55)^T \)。 5. 收敛判断与后续迭代检查对偶间隔 \( \delta^{(1)} = x^{(1)T} s^{(1)} \approx -3.63 \)（仍为负，因初始点不可行）。继续迭代，逐步调整 \( \mu \) 并向可行域靠近。经过多次迭代（通常 10-20 步），点列将收敛到最优解 \( x^* = (0, 3)^T \)，\( y^* = -2 \)，\( s^* = (1, 0)^T \)，目标函数值 \( -6 \)。 6. 算法特点路径跟踪法通过控制 \( \mu \) 减小速度，平衡最优性与可行性。每步需解线性系统，计算成本高，但迭代次数少于单纯形法。适用于大规模稀疏问题。