线性规划的原始-对偶势下降法求解示例 我将为您详细讲解线性规划中的原始-对偶势下降法。这个方法结合了原始-对偶思想和势函数下降策略，是内点法家族中的重要成员。 问题描述 考虑标准形式的线性规划问题： 最小化 cᵀx 满足 Ax = b, x ≥ 0 其中 A 是 m×n 矩阵，c 和 x 是 n 维向量，b 是 m 维向量。对偶问题为： 最大化 bᵀy 满足 Aᵀy + s = c, s ≥ 0 解题过程 第一步：理解原始-对偶势下降法的核心思想 原始-对偶势下降法通过在原始空间和对偶空间同时进行迭代，利用势函数来引导搜索方向。势函数结合了目标函数值和可行性度量，确保算法在保持内点的同时向最优解前进。 关键要素： 保持严格可行性：x > 0, s > 0 使用势函数平衡最优性和中心性 通过牛顿方向确定搜索方向 第二步：定义势函数 势下降法的核心是势函数，我们采用对数势函数： Φ(x,s) = q·ln(xᵀs) - ∑ln(xᵢ) - ∑ln(sᵢ) 其中 q > n 是势参数，xᵀs 是互补间隙，-∑ln(xᵢ) 和 -∑ln(sᵢ) 是障碍项，确保迭代点远离边界。 第三步：建立最优性条件 根据KKT条件，最优解满足： Ax = b, x ≥ 0 Aᵀy + s = c, s ≥ 0 xᵢsᵢ = 0, i = 1,...,n 我们引入中心参数 μ > 0，将互补松弛条件松弛为： xᵢsᵢ = μ, i = 1,...,n 第四步：推导搜索方向 我们求解以下扰动KKT系统： Ax = b Aᵀy + s = c XSe = μe 其中 X = diag(x), S = diag(s), e = (1,...,1)ᵀ 应用牛顿法，得到搜索方向 (Δx, Δy, Δs)： AΔx = 0 AᵀΔy + Δs = 0 SΔx + XΔs = μe - XSe 第五步：确定步长和更新策略 为保证严格可行性，采用阻尼步长： α = min(1, η·min{ -xᵢ/Δxᵢ | Δxᵢ < 0 }, η·min{ -sᵢ/Δsᵢ | Δsᵢ < 0 }) 其中 η ∈ (0,1) 是安全系数，通常取 0.9995 迭代更新： x ← x + αΔx y ← y + αΔy s ← s + αΔs 第六步：参数更新和收敛判断 中心参数 μ 的更新策略： μ = σ·(xᵀs)/n 其中 σ ∈ (0,1) 是中心参数，通常取 0.1 收敛准则： 原始可行性：‖Ax - b‖ ≤ ε₁ 对偶可行性：‖Aᵀy + s - c‖ ≤ ε₂ 互补间隙：xᵀs ≤ ε₃ 第七步：完整算法流程 初始化：选择初始内点 (x⁰,y⁰,s⁰)，设置参数 ε, σ, η 循环直到收敛： a. 计算当前互补间隙 μ = (xᵀs)/n b. 求解牛顿系统得到搜索方向 c. 计算步长 α d. 更新迭代点 e. 检查收敛条件 输出最优解 第八步：数值示例 考虑简单问题： 最小化 -x₁ - x₂ 满足 x₁ + 2x₂ ≤ 4, x₁, x₂ ≥ 0 转换为标准形式后，算法从内点开始，通过势函数引导，在原始空间和对偶空间同步推进，最终收敛到最优解 x* = (4,0)。 原始-对偶势下降法的优势在于同时处理原始和对偶变量，具有良好的理论性质和实际性能，是求解大规模线性规划问题的有效方法。