半正定値計画問題

OR事典

半正定値計画問題

読み方：はんせいていちけいかくもんだい
【英】：semidefinite programming problem

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

ウィキペディア

半正定値計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/12 03:47 UTC 版)

半正定値計画問題（はんせいていちけいかくもんだい、英: semidefinite programming）とは、半正定値行列全体によって作られる凸錐体上での凸最適化問題（convex optimization）の一つである。

半正定値計画問題は近年いくつかの理由で成長している最適化の一分野である。その理由として多くの実用例が考えられることがあげられるが、特にオペレーションズ・リサーチや組み合わせ最適化などの分野で広く研究が行われている。自動制御理論の分野では半正定値計画問題が線形不等式制約のもとで行われることが多い。半正定値計画問題は、凸錐体上の凸最適化問題の一種であり、内点法などにより効率よく解を与えることが可能であることも、応用が期待される一要因となっている。また半正定値計画問題の階層化により多項式最適化問題が近似的に解けるほか、複雑系の最適化にも応用が可能である。

定義

線形計画問題はある空間上で多面体に含まれるような実数の組に対して、線形の目的関数を最小化・最大化する問題である。ここで、多面体というのは、より厳密には凸集合であるということを指す。一方で、半正定値計画問題においては、ベクトルの内積を最適化する。特に、一般的な半正定値最適化問題は、数理計画問題の形式として、以下のように定義される（ただし、${\displaystyle x_{i}\cdot x_{j}}$