半正定値計画問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

半正定値計画問題 (semidefinite programming) とは半正定値行列全体によって作られる凸錐体上での凸最適化問題 (convex optimization) 手法の一つである。

半正定値計画問題は近年いくつかの理由で成長している最適化の一分野である。その理由として多くの実用例が考えられることがあげられるが、特にオペレーションズ・リサーチ組み合わせ最適化などの分野で広く研究が行われている。自動制御理論の分野では半正定値計画問題が線形不等式制約のもとで行われることが多い。半正定値計画問題は、錐体上の凸最適化問題の一種であり、内点法などにより効率よく解を与えることが可能であることも、応用が期待される一要因となっている。また半正定値計画問題の階層化により多項式最適化問題が近似的に解けるほか、複雑系の最適化にも応用が可能である。

定義[編集]

線形計画問題はある空間上で多面体に含まれるような実数の集合に対して、線形の目的関数を最小化・最大化する問題である。ここで、多面体というのは、より厳密には凸集合であるということを指す。一方で、半正定値計画問題においては、ベクトルの内積を最適化する。特に、一般的な半正定値最適化問題は、数理計画問題の形式として、以下のように定義される。


\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}

さらに、この問題は半正定値行列の作る凸錐体上の問題として書き直すことができる。大きさがn \times nの行列Mn本のベクトルx^1, \ldots, x^nを用いてm_{i,j} = x_i \cdot x_j (ただし、x_i \cdot x_j内積を表す) で表されるとき、行列Mをグラム行列といい、この行列は半正定値となることが知られている。

ここで、\mathbb{S}^nを実対称行列全体の空間とする。この空間では内積を 
  \langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n
  A_{ij}B_{ij}.

(ただし、trは行列のを表す) と定義することができて、これを用いると、前述のベクトルを用いた半正定値計画問題が次の形で書き直せる。


\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\
\text{subject to} & \langle A_k, X \rangle_{\mathbb{S}^n} \leq b_k, \quad k = 1,\ldots,m \\
& X \succeq 0
\end{array}

ただし、X \succeq 0とは行列Xが半正定値行列であることを表す。この式においてCc_{i,j}を、A_kn \times nの行列でa_{i,j,k}を成分に持つ。

双対性[編集]

双対問題の定義[編集]

線型計画問題と同様,半正定値計画問題も双対問題を考えることが可能で,


\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\
\text{subject to} & \langle A_k, X \rangle_{\mathbb{S}^n} \leq b_k, \quad k = 1,\ldots,m \\
& X \succeq 0
\end{array}

という半正定値計画問題の双対問題は


\begin{array}{rl}
{\displaystyle\max_{y \in \mathbb{R}^m}} & \langle b, y \rangle_{\mathbb{R}^m} \\
\text{subject to} & {\displaystyle\sum_{i=1}^m} y_i A_i \preceq C
\end{array}

という形で与えられる.なお大きさが等しい2つの正方行列P, Qに対して,P \succeq Qとは,P - Q \succeq 0と同義である.

弱双対性[編集]

弱双対定理とは,半正定値計画問題の主問題と双対問題の許容解の関係を表す定理であり,主問題の許容解の下限が双対問題の許容解の上限と一致するというものである. これは,次の式により示される.


\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つの行列が,どちらも半正定値行列であるためである.

強双対性[編集]

スレーター条件と呼ばれる条件の下では,主問題と双対問題の最適解が一致することが知られている.これを強双対性という.線形計画問題と違い,半正定値問題は,すべての問題が強双対性を満たすわけではなく,一般には双対問題の最適解は主問題の最適解よりも小さい.強双対性は次の2つの性質により言い表される.

  1. 主問題が下界であり,かつ内点許容解をもつとき,双対問題が最適解y^*を持つ.
  2. 双対問題が上界であり,かつ内点許容解をもつとき,主問題が最適解X^*を持つ.

この2つの性質から,主問題と双対問題の両方が最適解を持ち,それらが一致することが言える.

参考文献[編集]

  • 田村明久,村松正和,『最適化法』,共立出版株式会社,pp. 176-194,2002年.