基于线性规划的仿射缩放内点法求解示例

我将为您详细讲解仿射缩放内点法的原理和求解过程。这是一种重要的线性规划内点法，通过仿射变换将当前点映射到单位球中心，沿可行方向移动以获得更优解。

问题描述

考虑标准形式的线性规划问题：

最小化：cᵀx
约束条件：Ax = b, x ≥ 0

其中A是m×n矩阵(m<n)，秩为m，c和x是n维向量，b是m维向量。

算法原理

核心思想：从严格内点(x>0)出发，通过仿射变换将当前点映射到单位球中心，然后在变换后的空间中找到目标函数下降方向，再映射回原空间进行迭代。

详细求解步骤

步骤1：初始化

• 选择初始点x⁰，满足Ax⁰=b且x⁰>0
• 设置精度阈值ε>0（如10⁻⁶）
• 设置步长参数α∈(0,1)（通常取0.9-0.995）
• 迭代计数器k=0

步骤2：检查终止条件

计算当前目标函数值cᵀxᵏ和对偶间隙：

• 如果所有xᵏ ≥ 0且|cᵀxᵏ| < ε，则停止迭代，输出最优解
• 否则继续下一步

步骤3：构造缩放矩阵

构造对角缩放矩阵：

Dᵏ = diag(x₁ᵏ, x₂ᵏ, ..., xₙᵏ)

这个矩阵将当前点xᵏ映射到全1向量：Dᵏ⁻¹xᵏ = 1（1是全1向量）

步骤4：计算仿射缩放方向

在变换后的空间中求解投影问题：

1. 计算变换后的向量：c̃ = Dᵏc
2. 计算变换后的矩阵：Ã = ADᵏ
3. 计算投影矩阵：P = I - Ãᵀ(ÃÃᵀ)⁻¹Ã
4. 计算仿射缩放方向：d̃ = -Pc̃

这个方向d̃是变换后空间中最速下降方向在零空间{Ax=0}上的投影。

步骤5：映射回原空间

将变换空间的方向映射回原空间：

dᵏ = Dᵏd̃

步骤6：确定步长

为保证迭代点始终在可行域内部，需要限制步长：

1. 计算最大步长：λ_max = min{-xᵢᵏ/dᵢᵏ | dᵢᵏ < 0, i=1,...,n}
2. 实际步长：λᵏ = α × λ_max（其中α是步长因子）

步骤7：更新迭代点

xᵏ⁺¹ = xᵏ + λᵏdᵏ

更新迭代计数器：k = k+1

步骤8：重复迭代

返回步骤2，直到满足终止条件。

数值示例

考虑简单线性规划问题：

最小化：-x₁ - x₂
约束条件：x₁ + 2x₂ ≤ 4
          x₁, x₂ ≥ 0

转换为标准形式：

最小化：-x₁ - x₂
约束条件：x₁ + 2x₂ + x₃ = 4
          x₁, x₂, x₃ ≥ 0

迭代过程：

1. 初始化：选择初始点x⁰=[1,1,1]ᵀ，满足约束条件

   • A=[1,2,1]，b=[4]，c=[-1,-1,0]ᵀ
   • 设置α=0.9，ε=10⁻⁶

2. 第一次迭代：

   • 构造D⁰=diag(1,1,1)
   • 计算c̃=D⁰c=[-1,-1,0]ᵀ
   • Ã=AD⁰=[1,2,1]
   • 计算投影方向d̃≈[-0.667,-0.333,0.333]ᵀ
   • 映射回原空间：d⁰=[-0.667,-0.333,0.333]ᵀ
   • 计算步长λ⁰=0.9×min{1/0.667,1/0.333}≈1.35
   • 更新点：x¹≈[0.1,0.55,2.45]ᵀ

3. 继续迭代：

   • 经过约10次迭代，解收敛到x*≈[4,0,0]ᵀ
   • 最优值：-4

算法特点

1. 全局收敛性：在适当条件下算法全局收敛
2. 多项式时间复杂度：相比单纯形法有更好的理论复杂度
3. 数值稳定性：需要处理矩阵求逆的数值稳定性问题
4. 实际效率：对于大规模稀疏问题表现良好

关键要点

• 仿射缩放法通过坐标变换将当前点置于中心位置
• 投影步骤确保搜索方向在可行域内
• 步长控制保证迭代点始终严格可行
• 相比单纯形法沿边界移动，内点法在可行域内部移动

这种方法为线性规划提供了重要的求解思路，是现代优化算法的重要组成部分。