线性规划的原始-对偶势函数法求解示例 我将为您详细讲解线性规划的原始-对偶势函数法，这是一种重要的内点法变种。 问题描述 考虑标准形式的线性规划问题： 最小化 cᵀx 满足 Ax = b, x ≥ 0 其中 A ∈ ℝ^(m×n), c ∈ ℝ^n, b ∈ ℝ^m，且假设问题有界且可行。 算法原理 原始-对偶势函数法通过构造势函数来同时优化原始问题和对偶问题，在保持可行性的同时逐步逼近最优解。 解题步骤详解 第一步：构造对偶问题 对偶问题为： 最大化 bᵀy 满足 Aᵀy + s = c, s ≥ 0 其中 y ∈ ℝ^m 是对偶变量，s ∈ ℝ^n 是松弛变量。 第二步：定义势函数 势函数是关键创新，定义为： Φ(x,s) = q·ln(xᵀs) - ∑ln(xᵢ) - ∑ln(sᵢ) 其中 q > n 是参数，控制收敛速度。 第三步：建立最优性条件 KKT最优性条件为： Ax = b, x ≥ 0 Aᵀy + s = c, s ≥ 0 xᵢsᵢ = 0, i = 1,...,n 第四步：设计迭代方向 在当前点(x,y,s)，通过求解线性系统确定搜索方向： ⎡ A 0 0 ⎤ ⎡ Δx ⎤ ⎡ 0 ⎤ ⎢ 0 Aᵀ I ⎥ ⎢ Δy ⎥ = ⎢ 0 ⎥ ⎣ S 0 X ⎦ ⎣ Δs ⎦ ⎣ -XSe + μe ⎦ 其中 X = diag(x), S = diag(s), e是全1向量，μ是中心参数。 第五步：计算步长 为保证严格可行性(x > 0, s > 0)，采用自适应步长： α = min(1, γ·min{ -xᵢ/Δxᵢ | Δxᵢ < 0 }, γ·min{ -sᵢ/Δsᵢ | Δsᵢ < 0 }) 其中 γ ∈ (0,1) 是安全系数。 第六步：迭代更新 x ← x + αΔx y ← y + αΔy s ← s + αΔs 第七步：收敛判断 当满足以下条件时停止： xᵀs < ε 且 ||Ax - b|| < ε 且 ||Aᵀy + s - c|| < ε 其中 ε > 0 是预设精度。 算法特点 多项式时间复杂度：O(√n·ln(1/ε))次迭代 保持严格可行性：始终满足x > 0, s > 0 自适应步长：自动调整以保证收敛 对偶间隙监控：通过xᵀs监控收敛进度 这种方法通过势函数巧妙平衡了减少对偶间隙和保持中心路径的关系，是内点法家族中的重要成员。