Semidefinite Programming

定义 Definition

半正定规划（SDP）：一种凸优化问题。它通过优化一个线性目标函数，并要求某个对称矩阵变量满足半正定约束（即所有特征值都不小于 0），同时还可包含线性等式/不等式约束。它常用于控制、信号处理、机器学习、组合优化的松弛等。

发音 Pronunciation (IPA)

/ˌsɛmiˈdɛfɪnət ˈproʊɡræmɪŋ/

例句 Examples

Semidefinite programming can be solved efficiently with modern solvers.
半正定规划可以用现代求解器高效地求解。

We used semidefinite programming to obtain a tight relaxation of a hard combinatorial optimization problem and then rounded the solution to get a feasible discrete answer.
我们用半正定规划对一个困难的组合优化问题构造了较紧的松弛，并通过舍入把解转化为可行的离散答案。

词源 Etymology

semi- 意为“半、部分”；definite 在数学里与“（正/负）定”相关，指矩阵的二次型符号性质；semidefinite 因此指“半正定/半负定”（允许为 0）。programming 在“linear programming（线性规划）”等术语中表示“规划/优化求解”，并非“编程写代码”。合起来就是“带半正定矩阵约束的优化规划”。

相关词 Related Words

• Convex Optimization
• Linear Programming
• Quadratic Programming
• Positive Semidefinite
• LMI
• Duality
• Interior-Point Method
• Relaxation

文献与作品 Literary / Notable Works

• Convex Optimization（Stephen Boyd & Lieven Vandenberghe）：将半正定规划作为核心凸优化工具系统介绍。
• “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming”（Goemans & Williamson, 1995）：用 SDP 松弛推动了近似算法的经典结果。
• Interior-Point Polynomial Algorithms in Convex Programming（Nesterov & Nemirovskii）：为包括 SDP 在内的内点法理论奠基。
• Handbook of Semidefinite Programming（Wolkowicz, Saigal, Vandenberghe 编）：SDP 理论与应用的综述性参考书。