半正定値計画

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

線形計画を実対称行列の空間に拡張したもの.等質自己双対錐上の線形計画問題の1つでもある.半正定値計画は

\[ \begin{array}{ll}

 \displaystyle{ \mathop{\mbox{min.}}_X } &  \mbox{trace}(CX) \\
 \mbox{s.t.} &  \mbox{trace}(A_i X) = b_i, \: i=1,\ldots,m,  \\
 &     X\succeq0,

\end{array} \]

で表される.ただし, $C, A_i\ (i=1, \ldots, m), X$ は $n\times n$ 実対称行列,$\mbox{trace}(\cdot)$ は行列のトレース,$X\succeq0$ は $X$ が半正定値であることを表す.