高斯-赛德尔迭代法收敛性分析

本章节深入分析了高斯-赛德尔迭代法在解决优化问题时的收敛特性。具体而言，我们关注以下形式的优化问题：

min f(x) = 1/2 * x^T * A * x - b^T * x

s.t. x ≥ 0

其中 A 是一个对称正定矩阵。

高斯-赛德尔迭代过程可以表示为：

x^(k+1) = (D-L)^(-1) * (Ux^(k) + b)

D, L, U 分别代表矩阵 A 的对角线、下三角和上三角部分。

模型KKT条件

在深入研究收敛性之前，我们需要理解与优化问题相关的KKT条件。对于非负约束的极小化问题，其一般形式为：

min h(x)

s.t. g_i(x) ≥ 0, i = 1, ..., m

构建拉格朗日函数：

L(x, λ) = h(x) - ∑_{i=1}^m λ_i * g_i(x)

KKT条件提供了一组用于检查候选解是否为最优解的必要条件。这些条件包括：

  • 平稳性: ∇_x L(x, λ) = 0
  • 原始可行性: g_i(x) ≥ 0, i = 1, ..., m
  • 对偶可行性: λ_i ≥ 0, i = 1, ..., m
  • 互补松弛条件: λ_i * g_i(x) = 0, i = 1, ..., m

通过分析模型的KKT条件，我们可以深入理解其最优解的特性，并为收敛性分析提供理论基础。