半正定値計画問題

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

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

定義

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

{\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}\qquad \forall k}.\\\end{array}}

さらに、この問題は半正定値行列の作る凸錐体上の問題として書き直すことができる。大きさが $n\times n$ の行列 $M$ が $n$ 本のベクトル $x^{1},\ldots ,x^{n}$ を用いて $m_{i,j}=x_{i}\cdot x_{j}$ で表されるとき、行列 $M$ をグラム行列といい、この行列は半正定値となることが知られている。

ここで、 $\mathbb {S} ^{n}$ を実対称行列全体の空間とする。この空間では内積を $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}$ （ただし、tr は行列の跡を表す）と定義することができて、これを用いると、前述のベクトルを用いた半正定値計画問題が次の形で書き直せる。