非线性规划中的仿射缩放内点法基础题

我将为你讲解仿射缩放内点法（Affine Scaling Interior Point Method）的基本原理和应用。这是一个经典的线性与非线性规划内点法，以其相对简单的实现和良好的理论性质而闻名。

问题描述

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

最小化： cᵀx
满足： Ax = b
       x ≥ 0

其中：

• x ∈ ℝⁿ 是决策变量
• c ∈ ℝⁿ 是成本向量
• A ∈ ℝ^(m×n) 是约束矩阵（假设行满秩，即 rank(A)=m）
• b ∈ ℝ^m 是右端向量
• 假设问题存在严格内点（即存在 x > 0 满足 Ax=b）

你的任务：使用仿射缩放内点法求解此问题，理解其迭代过程、缩放变换原理以及收敛条件。

解题过程循序渐进讲解

步骤1：理解算法核心思想

仿射缩放内点法的核心思想是：

1. 始终保持迭代点在可行域内部（x > 0），因此称为“内点法”。
2. 通过仿射变换（缩放）将当前点映射到中心位置，使得搜索方向更有效。
3. 在变换后的空间中进行梯度下降，然后逆变换回原始空间。
4. 通过中心参数控制靠近边界的程度，确保不会过早触碰到边界。

简单来说，想象你在一片有边界的区域内寻找最低点。你不仅想找到最低点，还想保持离边界一定距离，避免“撞墙”。通过缩放变换，你把当前点变成这个区域的“中心”，然后朝着下降最快的方向走一步，再缩放回去。

步骤2：关键变换——仿射缩放

假设当前迭代点为 xᵏ > 0（所有分量严格为正）。定义缩放矩阵：

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

即一个对角矩阵，对角线元素就是当前点的各个分量。

进行变量变换：

y = Dₖ⁻¹x   ⇔   x = Dₖy

在这个变换下：

• 当前点 xᵏ 对应 yᵏ = Dₖ⁻¹xᵏ = (1,1,...,1)ᵀ = e（全1向量）
• 非负约束 x ≥ 0 变为 y ≥ 0
• 等式约束 Ax = b 变为 ADₖy = b
• 目标函数 cᵀx 变为 cᵀDₖy

为什么这个变换有用？
因为 yᵏ = e 位于正象限的“中心”（所有分量相等且为正）。在 y 空间中，从中心点出发的搜索方向可以更自由地选择，而不用担心某些分量立即变为负值。

步骤3：计算搜索方向

在 y 空间中，问题变为：

最小化： (Dₖc)ᵀy
满足： (ADₖ)y = b
       y ≥ 0

我们希望从 yᵏ = e 出发，找到一个下降方向。但直接沿负梯度方向移动可能破坏等式约束 ADₖy = b。因此，我们需要将负梯度投影到等式约束的零空间中。

具体计算：

1. 定义变换后的约束矩阵： Ã = ADₖ
2. 计算投影矩阵： P = I - Ãᵀ(ÃÃᵀ)⁻¹Ã
   （这个矩阵将任何向量投影到 Ã 的零空间，即满足 Ãv = 0 的子空间）
3. 计算变换后的梯度： g = Dₖc
4. 投影梯度方向： d_y = -P g
   这就是在 y 空间中，既下降（因为与负梯度相关）又保持等式约束的方向。

重要细节：

• d_y 是可行方向：Ã(d_y) = 0，所以沿 d_y 移动不会破坏等式约束。
• d_y 是下降方向：gᵀd_y = -gᵀP g ≤ 0，当 P g ≠ 0 时严格小于0。

步骤4：确定步长并逆变换

在 y 空间中，沿方向 d_y 移动： y = e + α d_y

但必须保证 y ≥ 0（因为 x = Dₖy ≥ 0）。由于 d_y 可能有些分量为负，步长 α 需要满足：

1 + α (d_y)ᵢ ≥ 0  对所有 i

最大允许步长为：

α_max = min{ -1/(d_y)ᵢ : (d_y)ᵢ < 0 }

为了保持内点性质（避免触碰边界），我们取一个略小的步长：

α = γ · α_max

其中 γ ∈ (0,1) 是中心参数，通常取 0.9~0.999。γ 越接近1，步长越大，但越接近边界；γ 越小，越保持在中心区域。

得到新 y 后，逆变换回原始变量：

xᵏ⁺¹ = Dₖ y = Dₖ(e + α d_y) = xᵏ + α Dₖ d_y

所以原始空间的搜索方向是 d_x = Dₖ d_y。

步骤5：检查收敛条件

算法迭代直到满足以下某个条件：

1. 相对目标值变化： |cᵀxᵏ⁺¹ - cᵀxᵏ| / max(1, |cᵀxᵏ|) < ε₁
2. 对偶间隙： 对于线性规划，最优性条件包括互补松弛。内点法的对偶间隙估计为 xᵏᵀsᵏ，其中 sᵏ 是对偶变量的估计。当 xᵏᵀsᵏ < ε₂ 时停止。
   （简单实现中，可以只用原始可行性、目标值稳定等条件）

通常设置 ε₁=10⁻⁶, ε₂=10⁻⁸ 等。

步骤6：完整算法流程

1. 初始化：选择严格内点 x⁰ > 0 满足 Ax⁰ = b，设置 k=0，精度 ε>0，中心参数 γ∈(0,1)。
2. 循环直到收敛：
   a. 计算缩放矩阵 Dₖ = diag(xᵏ)
   b. 计算变换后矩阵 Ã = ADₖ
   c. 计算投影矩阵 P = I - Ãᵀ(ÃÃᵀ)⁻¹Ã
   d. 计算变换后梯度 g = Dₖc
   e. 计算 y 空间方向 d_y = -P g
   f. 若 ‖d_y‖ 很小，则停止（接近最优）
   g. 计算最大步长 α_max = min{ -1/(d_y)ᵢ : (d_y)ᵢ < 0 }（若所有 d_y ≥ 0，则 α_max = ∞，但取一个较大值如 1/‖d_y‖）
   h. 取实际步长 α = γ · α_max
   i. 更新 xᵏ⁺¹ = xᵏ + α Dₖ d_y
   j. 检查收敛条件，若不满足则 k ← k+1 继续循环

步骤7：简单数值例子（理解用）

考虑问题：

最小化： -x₁ - x₂
满足： x₁ + x₂ ≤ 1
       x₁, x₂ ≥ 0

转化为标准形式（引入松弛变量 x₃）：

最小化： -x₁ - x₂ + 0·x₃
满足： x₁ + x₂ + x₃ = 1
       x₁, x₂, x₃ ≥ 0

这里 c = (-1,-1,0)ᵀ, A = [1,1,1], b = 1。

取初始内点 x⁰ = (0.4, 0.3, 0.3)ᵀ（满足和为1且全正）。

1. D₀ = diag(0.4, 0.3, 0.3)
2. Ã = AD₀ = [0.4, 0.3, 0.3]
3. P = I - Ãᵀ(ÃÃᵀ)⁻¹Ã （计算略）
4. g = D₀c = (-0.4, -0.3, 0)ᵀ
5. d_y = -P g
6. 计算步长 α
7. x¹ = x⁰ + α D₀ d_y

经过多次迭代，会收敛到最优解 x* = (1,0,0)ᵀ 或 (0,1,0)ᵀ，目标值 -1。

步骤8：算法特性和注意事项

1. 全局收敛性：在适当条件下，仿射缩放法全局收敛到最优解。
2. 多项式时间性：原始仿射缩放法不是多项式时间算法，但后来发展的路径跟踪法是。
3. 数值稳定性：需要求解 (ÃÃᵀ)⁻¹，当 Ã 条件数大时可能不稳定。通常使用 Cholesky 分解或 QR 分解。
4. 扩展性：可以扩展到凸二次规划和某些非线性规划，通过类似的缩放思想。
5. 与简单方法的对比：相比单纯形法（沿着边界顶点移动），内点法穿过可行域内部，对于大规模稀疏问题有时更高效。

总结

仿射缩放内点法通过巧妙的坐标变换，将当前点置于“中心”，从而能够更自由地选择下降方向。其核心步骤——缩放、投影、步长控制、逆变换——构成了一个清晰而有效的优化框架。虽然现代内点法更多使用路径跟踪或原对偶方法，但仿射缩放法仍然是理解内点法原理的经典起点，并且对于中等规模的线性规划问题仍然实用。