Semidefinite Programming

释义 Definition

半定规划（SDP）：一种凸优化问题。它通常以矩阵变量为对象，在满足矩阵半正定约束（如 \(X \succeq 0\)）的条件下，最小化或最大化一个线性目标函数。常用于控制、组合优化近似、机器学习、信号处理等领域。（该术语也常写作 semidefinite optimization。）

发音 Pronunciation (IPA)

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

例句 Examples

Semidefinite programming is a type of convex optimization.
半定规划是一种凸优化。

Using semidefinite programming, we can relax a hard combinatorial problem into a tractable convex form with provable bounds.
通过半定规划，我们可以把困难的组合优化问题放松为可计算的凸形式，并获得可证明的界。

词源 Etymology

Semidefinite 由 semi-（“半、部分”）+ definite（“确定的”）构成，源于线性代数中的“半正定矩阵”（eigenvalues 非负）。Programming 在优化语境中表示“规划/优化建模”，并非“编程写代码”。合在一起即“带半正定约束的优化规划”。

相关词 Related Words

• Convex Optimization
• Linear Programming
• Quadratic Programming
• Second-Order Cone Programming
• Positive Semidefinite
• Lagrangian Duality
• Relaxation
• Interior-Point Method

文献与作品 Literary / Notable Works

• Convex Optimization（Stephen Boyd, Lieven Vandenberghe）——以 SDP 作为核心凸优化模型之一进行讲解与应用示例。
• Handbook of Semidefinite Programming: Theory, Algorithms, and Applications（Henry Wolkowicz, Romesh Saigal, Lieven Vandenberghe 编）——专门系统综述半定规划理论与算法。
• Semidefinite Optimization and Convex Algebraic Geometry（Grigoriy Blekherman, Pablo Parrilo, Rekha Thomas）——讨论 SDP 与和平方（SOS）等工具在代数几何与优化中的联系。
• Interior-Point Polynomial Algorithms in Convex Programming（Yurii Nesterov, Arkadi Nemirovskii）——涉及与 SDP 相关的内点法理论框架。