半定规划
半定规划是线性规划的推广，其中决策变量从向量扩展为对称矩阵，并且约束条件包含矩阵的半正定性要求。下面逐步介绍其核心概念：
- 从线性规划到半定规划
- 线性规划的标准形式为：
\[ \min \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b}, \ \mathbf{x} \geq 0, \]
其中 \(\mathbf{x}\) 是向量，约束条件为分量的非负性。
- 半定规划将变量推广为对称矩阵 \(X \in \mathbb{S}^n\)（\(n \times n\) 实对称矩阵集合），并要求 \(X\) 是半正定矩阵（记作 \(X \succeq 0\)），即所有特征值非负。
- 半定规划的标准形式
- 一般形式为：
\[ \min \langle C, X \rangle \quad \text{s.t.} \quad \langle A_i, X \rangle = b_i \ (i=1,\dots,m), \ X \succeq 0, \]
其中 \(\langle C, X \rangle = \operatorname{tr}(C^T X)\) 表示矩阵内积（即对应元素乘积之和），\(C, A_i\) 为已知对称矩阵，\(b_i\) 为标量。
-
为什么需要半定规划？
- 许多非线性问题可转化为半定规划。例如，二次约束优化问题（如二次型的非负性）可通过舒尔补条件转化为半定约束。
- 应用包括：控制系统的李雅普诺夫稳定性分析、图划分问题（如最大割问题的近似求解）、矩阵完备化问题。
-
半定规划的对偶理论
- 对偶问题为：
\[ \max \mathbf{b}^T \mathbf{y} \quad \text{s.t.} \quad C - \sum_{i=1}^m y_i A_i \succeq 0, \]
其中 \(\mathbf{y} \in \mathbb{R}^m\) 是对偶变量。弱对偶定理保证原问题最优值不小于对偶问题最优值，在严格可行点存在时强对偶成立。
-
数值求解方法
- 内点法是主流算法，通过将半定约束转换为障碍函数（如 \(\log \det X\)），在可行域内迭代求解。复杂度通常为 \(O(n^{3.5})\)，受矩阵维度和约束数量影响。
-
示例：最大特征值最小化
- 问题：\(\min \lambda_{\max}(A(x))\)，其中 \(A(x) = A_0 + \sum x_i A_i\)。
- 等价半定规划形式：
\[ \min t \quad \text{s.t.} \quad tI - A(x) \succeq 0, \]
利用特征值定义将非线性问题转化为线性矩阵不等式。
半定规划通过矩阵变量和半正定约束，将经典优化扩展到更复杂的结构，成为处理凸优化和非凸问题近似的重要工具。