半正定値計画問題のソースを表示

'''半正定値計画問題'''（はんせいていちけいかくもんだい、{{Lang-en-short|semidefinite programming}}）とは、[[固有値#正定値と半正定値|半正定値行列]]全体によって作られる凸錐体上での凸最適化問題（convex optimization）の一つである。

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

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

:<math>
\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}
</math>

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

ここで、<math>\mathbb{S}^n</math>を実対称行列全体の空間とする。この空間では内積を
<math>
  \langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n
  A_{ij}B_{ij}
</math>
（ただし、tr は行列の[[跡 (線型代数学)|跡]]を表す）と定義することができて、これを用いると、前述のベクトルを用いた半正定値計画問題が次の形で書き直せる。

:<math>
\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}
</math>

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

== 双対性 ==
=== 双対問題の定義 ===
[[線形計画問題]]と同様、半正定値計画問題も双対問題を考えることが可能で、

:<math>
\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}
</math>

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

:<math>
\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}
</math>

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

=== 弱双対性 ===
弱双対定理とは、半正定値計画問題の主問題と双対問題の許容解の関係を表す定理であり、主問題の許容解が双対問題の[[最小上界|上界]]となり、双対問題の許容解が主問題の[[最小上界|下界]]となるというものである。
これは、次の式により示される。

:<math>
\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,
</math>

最後の不等式が成立するのは、行列の[[内積]]を取っている2つの行列が、どちらも半正定値行列であるためである。

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

# 主問題が下に有界であり、かつ内点許容解をもつとき、双対問題が最適解<math>y^*</math>を持つ。
# 双対問題が上に有界であり、かつ内点許容解をもつとき、主問題が最適解<math>X^*</math>を持つ。

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

<!-- 
== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}
 -->

== 参考文献 ==
* 田村明久, 村松正和, 『最適化法』, [[共立出版|共立出版株式会社]], pp. 176-194, 2002年.

{{主要な最適化問題の分類}}

{{DEFAULTSORT:はんせいていちけいかくもんたい}}
[[Category:線型代数学]]
[[Category:物理数学]]
[[Category:線型計画法]]
[[Category:数学に関する記事]]