半正定値計画

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

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

${\mbox{min.}}_{X}\,$	${\mbox{trace}}(CX)\,$
${\mbox{s.t.}}\,$	${\mbox{trace}}(A_{i}X)=b_{i},i=1,\ldots ,m,\,$
	$X\succeq 0,\,$

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