半正定値計画問題

【 はんせいていちけいかくもんだい (semidefinite programming problem) 】

実対称行列を変数とし， 線形の目的関数と制約式に加え， 変数の半正定値条件が付加された数理計画問題． 対称錐計画問題の一種であり， 線形計画問題を特殊ケースとして含む． 組合せ最適化問題や非凸計画問題に対する緩和として使われる （半正定値計画緩和）． その他に， 制御理論，構造設計，統計学等への応用例がある． 内点法によって多項式時間で解くことができ， ソフトウェアも数多く開発されている．