Semidefinite programming

半正定规划（Semidefinite programming，SDP）是凸优化问题的一个分支，它具有线性目标函数（由用户指定的最大化或最小化函数），且其定义在半正定矩阵构成的凸锥与仿射空间的交集上，即光谱面（英语：spectrahedron）。 在最佳化理論中，半正定規劃是一個相對較年輕的領域，並且

式。线性矩阵不等式也可以應用在Polynomial SOS（英语：Polynomial SOS）中。原型的原始半定規劃（英语：semidefinite programming）及對偶半定規劃都是實線性函數的最小化，分別屬於控制此LMI的原始凸錐及對偶凸錐。 凸優化的主要突破是導入了内点法。這個方法是

成熟的理論，因為所有情境最佳化的結果都和分佈無關，因此可以應用在沒有不確定性模型或是缺乏類似資訊的情形下。 針對凸拘束（也就是和线性矩阵不等式有關的半定問題（英语：semidefinite programming）），已有深入的理論分析說明新的拘束無法滿足的機率是依照以β分布為主的分布。針對所有凸優化問題的結果也是如此。再繼續擴展，有許

approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 1995, 42 (6): 1115–1145, doi:10.1145/227683

（原始内容存档于2021-10-15）.  Mittelmann, Hans D.; Vallentin, Frank. High accuracy semidefinite programming bounds for kissing numbers. Experimental Mathematics. 2009, 19: