半正定値計画問題
線形計画問題はある空間上で多面体に含まれるような実数の組に対して,線形の目的関数を最小化・最大化する問題である.ここで,多面体というのは,より厳密には凸集合であるということを指す.一方で,半正定値計画問題においては,ベクトルの内積を最適化する.特に,一般的な半正定値最適化問題は,数理計画問題の形式として,以下のように定義される (ただし, x i ⋅ x j {\displaystyle x_{i}\cdot x_{j}} は内積を表す).
min x 1 , ... , x n ∈ R n ∑ i , j ∈ [ n ] c i , j ( x i ⋅ x j ) subject to ∑ i , j ∈ [ n ] a i , j , k ( x i ⋅ x j ) ≤ b k ∀ k . {\displaystyle {\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}}}
半正定値計画問題 (semidefinite programming) とは半正定値行列全体によって作られる凸錐体上での凸最適化問題 (convex optimization) の一つである.
半正定値計画問題は近年いくつかの理由で成長している最適化の一分野である.その理由として多くの実用例が考えられることがあげられるが,特にオペレーションズ・リサーチや組み合わせ最適化などの分野で広く研究が行われている.自動制御理論の分野では半正定値計画問題が線形不等式制約のもとで行われることが多い.半正定値計画問題は,凸錐体上の凸最適化問題の一種であり,内点法などにより効率よく解を与えることが可能であることも,応用が期待される一要因となっている.また半正定値計画問題の階層化により多項式最適化問題が近似的に解けるほか,複雑系の最適化にも応用が可能である.
弱双対定理とは,半正定値計画問題の主問題と双対問題の許容解の関係を表す定理であり,主問題の許容解が双対問題の上界となり,双対問題の許容解が主問題の下界となるというものである. これは,次の式により示される.
⟨ C , X ⟩ − ⟨ b , y ⟩ = ⟨ C , X ⟩ − ∑ i = 1 m y i b i = ⟨ C , X ⟩ − ∑ i = 1 m y i ⟨ A i , X ⟩ = ⟨ C − ∑ i = 1 m y i A i , X ⟩ ≥ 0 , {\displaystyle \langle C,X\rangle -\langle b,y\rangle =\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0,}
最後の不等式が成立するのは,行列の内積を取っている2つの行列が,どちらも半正定値行列であるためである.