线性规划的势能函数法求解示例 我将为您详细讲解线性规划中的势能函数法（Potential Reduction Method），这是一种基于内点法的优化算法，通过构造势能函数来同时优化目标函数和中心路径。 题目描述 考虑以下线性规划问题： 最小化：cᵀx 约束条件：Ax = b, x ≥ 0 其中c = [ 2, 3]ᵀ, A = [ 1, 1], b = [ 4]，初始点x₀ = [ 1, 3 ]ᵀ 对偶问题为： 最大化：bᵀy 约束条件：Aᵀy + s = c, s ≥ 0 解题过程 第一步：理解势能函数法的基本思想 势能函数法的核心是构造一个势能函数，该函数同时考虑： 目标函数值cᵀx的优化 当前点与中心路径的距离（通过互补间隙度量） 常用的势能函数为：Φ(x, s) = q·ln(xᵀs) - ∑ln(xᵢsᵢ) 其中q > n是参数，xᵀs是互补间隙，∑ln(xᵢsᵢ)保证点不会太靠近边界。 第二步：构造具体问题的势能函数 对于我们的2维问题，取q = n+√n ≈ 3.414 势能函数为：Φ(x, s) = 3.414·ln(x₁s₁ + x₂s₂) - [ ln(x₁s₁) + ln(x₂s₂) ] 从对偶条件可得：s = c - Aᵀy = [ 2, 3]ᵀ - [ 1, 1 ]ᵀy 第三步：计算初始点的势能值 在x₀ = [ 1, 3 ]ᵀ处： 由Ax = b ⇒ [ 1,1]·[ 1,3 ]ᵀ = 4 ✓ 计算对偶变量：s₀ = c - Aᵀy₀，其中y₀需满足s₀ > 0 取y₀ = 1，则s₀ = [ 2-1, 3-1]ᵀ = [ 1, 2 ]ᵀ 初始互补间隙：x₀ᵀs₀ = 1×1 + 3×2 = 7 势能值：Φ₀ = 3.414×ln(7) - [ ln(1) + ln(6)] = 3.414×1.946 - [ 0 + 1.792 ] ≈ 6.642 - 1.792 = 4.85 第四步：计算搜索方向 势能函数法的搜索方向通过求解以下线性系统得到： [ 0 Aᵀ I; A 0 0; S 0 X]·[ Δx; Δy; Δs] = [ -ξ₁; -ξ₂; -ξ₃ ] 其中X = diag(x), S = diag(s) ξ₁ = Aᵀy + s - c（对偶可行性残差） ξ₂ = Ax - b（原始可行性残差） ξ₃ = XSe - σμe（中心化条件，σ∈(0,1)是中心参数） 在我们的例子中，μ = xᵀs/n = 7/2 = 3.5，取σ = 0.5 第五步：迭代求解 第一次迭代： 在x₀ = [ 1,3]ᵀ, s₀ = [ 1,2 ]ᵀ处： ξ₁ = [ 1,1]ᵀ×1 + [ 1,2]ᵀ - [ 2,3]ᵀ = [ 0,0 ]ᵀ ξ₂ = [ 1,1]·[ 1,3 ]ᵀ - 4 = 0 ξ₃ = [ 1×1, 3×2]ᵀ - 0.5×3.5×[ 1,1]ᵀ = [ 1,6]ᵀ - [ 1.75,1.75]ᵀ = [ -0.75,4.25 ]ᵀ 求解线性系统得到搜索方向[ Δx, Δy, Δs ] 第六步：线搜索和更新 沿搜索方向进行线搜索，保证x > 0, s > 0 最大步长α_ max = min{min(-xᵢ/Δxᵢ), min(-sᵢ/Δsᵢ)}（对于负分量） 实际取α = 0.9×α_ max 更新点：x₁ = x₀ + αΔx, y₁ = y₀ + αΔy, s₁ = s₀ + αΔs 第七步：收敛判断 重复迭代直到： 原始可行性：‖Ax - b‖ < ε 对偶可行性：‖Aᵀy + s - c‖ < ε 互补间隙：xᵀs < ε 取ε = 10⁻⁶，通常需要10-50次迭代。 最终结果 最优解：x* = [ 1, 3 ]ᵀ（本例中初始点即为最优解） 最优值：cᵀx* = 2×1 + 3×3 = 11 势能函数法通过平衡目标函数优化和中心路径跟踪，保证了算法的全局收敛性和多项式时间复杂度。