高斯-赛德尔迭代法收敛性分析
本章节深入分析了高斯-赛德尔迭代法在解决优化问题时的收敛特性。具体而言，我们关注以下形式的优化问题：
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条件，我们可以深入理解其最优解的特性，并为收敛性分析提供理论基础。