半正定规划
維基百科,自由的 encyclopedia
半正定规划(Semidefinite programming,SDP)是凸优化问题的一个分支,它具有线性目标函数(由用户指定的最大化或最小化函数),且其定义在半正定矩阵构成的凸锥与仿射空间的交集上,即光谱面(英语:spectrahedron)。
在最佳化理論中,半正定規劃是一個相對較年輕的領域,並且基於各種原因,學界不斷的增加對它的興趣:許多作業研究和組合最佳化的問題都能建模成半正定規劃問題,或以半正定規劃的方式得到近似解;在自動控制理論中,半正定規劃用於處理线性矩阵不等式。此外,半正定規劃是錐規劃(英语:conic programming)的特例,因此實際上可以內點法快速解掉。所有線性規劃問題都可以表示成半正定規劃,此外,多項式最佳化問題的解也可以透由半正定規劃逼近。
半正定規劃經常用於處理複雜系統的最佳化,而近年來,量子查詢複雜性理論的問題也經常被建模成半正定規劃。