知识点：半定规划

知识点概述

半定规划（Semidefinite Programming, SDP）是线性规划的推广，它将LP中的非负变量约束推广为矩阵变量的半正定约束。SDP是一类强大的凸优化问题，能为许多困难的组合优化问题提供有效的松弛。

标准形式: $X min ⟨ C, X ⟩$ $s.t. ⟨ A_{i}, X ⟩ = b_{i}, i = 1, \dots, m$ $X ⪰ 0$ 其中决策变量 $X$ 是一个对称矩阵， $C$ 和 $A_{i}$ 是已知的对称矩阵， $⟨ A, X ⟩ = Tr (A^{T} X)$ 是矩阵内积， $X ⪰ 0$ 表示矩阵 $X$ 是半正定的。
与LP的关系: 如果所有矩阵都是对角矩阵，SDP就退化为一个LP问题。因此，SDP是LP的推广，其可行域（半正定锥与仿射空间的交集）是比多面体更一般的凸集。
应用（凸松弛）: 许多非凸的组合优化问题（如最大割问题）可以被松弛（relax）为一个SDP问题。虽然松弛后得到的是原问题的近似解，但这个近似解往往质量很高，且SDP可以被内点法等算法在多项式时间内求解。