半正定値計画問題
さらに,この問題は半正定値行列の作る凸錐体上の問題として書き直すことができる.大きさが n × n {\displaystyle n\times n} の行列 M {\displaystyle M} が n {\displaystyle n} 本のベクトル x 1 , ... , x n {\displaystyle x^{1},\ldots ,x^{n}} を用いて m i , j = x i ⋅ x j {\displaystyle m_{i,j}=x_{i}\cdot x_{j}} で表されるとき,行列 M {\displaystyle M} をグラム行列といい,この行列は半正定値となることが知られている.
ここで, S n {\displaystyle \mathbb {S} ^{n}} を実対称行列全体の空間とする.この空間では内積を ⟨ A , B ⟩ S n = t r ( A T B ) = ∑ i = 1 , j = 1 n A i j B i j {\displaystyle \langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}} (ただし,trは行列の跡を表す) と定義することができて,これを用いると,前述のベクトルを用いた半正定値計画問題が次の形で書き直せる.