1 半正定値計画問題

$\Re^{n \times n}$ を $n \times n$ の実行列の集合、 $\mbox{${\cal S}$}^n$ を $n \times n$ の実対称行列の集合と定義する。 また、 $\mbox{${\cal S}$}_{+}^n$ を $n \times n$ の半正定値対称行列の集合、 $\mbox{${\cal S}$}_{++}^n$ を $n \times n$ の正定値対称行列の集合と定義する。

$\mbox{\boldmath$A$}_i \in \mbox{${\cal S}$}^n$ $(i = 0,1,\ldots, m)$, $b_i \in \Re$ $(i = 1,2,\ldots,m)$ とする。このとき、 半正定値計画(Semidefinite Programming, SDPと略) の主問題と双対問題は以下のように与えられる。

$$\left. \begin{array}{lclcll} {\bf 主問題：} & & & & \\ & &... ...math$X$}\in \mbox{${\cal S}$}_{+}^{n}. \\ \end{array}\right\}$$ (1)

$$\left. \begin{array}{lclcll} {\bf 双対問題：} & & & & \phan... ...math$Z$}\in \mbox{${\cal S}$}^{n}_{+}. \\ \end{array}\right\}$$ (2)

ただし， $\mbox{\boldmath$A$}\bullet \mbox{\boldmath$B$}$は行列 $\mbox{\boldmath$A$}$と $\mbox{\boldmath$B$}$の内積を意味し， $\mbox{\boldmath$A$}\bullet \mbox{\boldmath$B$}\equiv \sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}B_{ij}$ である． 本稿を通して、 $\mbox{\boldmath$A$}_i \in\mbox{${\cal S}$}^n (i = 1,2,\ldots,m)$ が線形独立であることを仮定する。 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ がSDP問題の実行可能解であるとは、 $\mbox{\boldmath$X$}$ が主問題の実行可能解であり、 $(\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ が双対問題の実行可能解である ことである。 また、 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ がSDP問題の実行可能内点解であるとは、 $\mbox{\boldmath$X$}$ が主問題の実行可能内点解（つまり、 $\mbox{\boldmath$X$}\in \mbox{${\cal S}$}_{++}^{n}$を満たす実行可能解） であり、 $(\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ が双対問題の実行可能内点解 （つまり、 $\mbox{\boldmath$Z$}\in \mbox{${\cal S}$}_{++}^{n}$を満たす実行可能解）である ことを意味する。 さらに、 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ がSDP問題の最適解であるとは、 $\mbox{\boldmath$X$}$ が主問題の最適解であり、 $(\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ が双対問題の最適解である ことを意味する。