0. はじめに

半正定値計画は線形計画も解けることが知られている。簡単に確認するために、例を用いて説明する。式（１）で与えられた線形計画について半正定値計画に帰着することができることを確認する。

\begin{eqnarray}
\min &  & -5x_1 - 4x_2  + 0 x_3 + 0 x_4\\

s.t. & &     5x_1 + 2x_2 +1x_3+0x_4= 30\\
     &  & \ \ x_1 + 2x_2 +0x_3+1x_4= 14\\
     &  & \ \ x_1\geq 0, x_2\geq 0, x_3\geq 0, x_4\geq 0
\end{eqnarray}
\tag{1}

式（１）は式変形すれば、式（２）のように半正定値計画に帰着できる。

\begin{eqnarray}
\min &  & C \bullet X\\

s.t. &  & \ \ A_{1}\bullet X = b_{1}\\
     &  & \ \ A_{2}\bullet X = b_{2}\\
     &  & \ \ X\succeq 0
\end{eqnarray}
\tag{2}

ここで、演算子$\bullet$は下記のように定義される。

A \bullet B := trace(AB^T)

式（２）の変数とパラメータは下記のように与えられる。

\begin{eqnarray}
&X = \left(
    \begin{array}{cccc}
     x_{11} & x_{12} & x_{13} & x_{14}\\
     x_{21} & x_{22} & x_{23} & x_{24}\\
     x_{31} & x_{32} & x_{33} & x_{34}\\
     x_{41} & x_{42} & x_{43} & x_{44}\\
    \end{array}
  \right),\\

&C = \left(
    \begin{array}{cccc}
     -5 & 0 & 0 & 0\\
      0 &-4 & 0 & 0\\
      0 & 0 & 0 & 0\\
      0 & 0 & 0 & 0
    \end{array}
  \right),

A_{1} = \left(
    \begin{array}{cccc}
      5 & 0 & 0 & 0\\
      0 &2 & 0 & 0\\
      0 & 0 & 1 & 0\\
      0 & 0 & 0 & 0
    \end{array}
  \right),

A_{2} = \left(
    \begin{array}{cccc}
      1 & 0 & 0 & 0\\
      0 &2 & 0 & 0\\
      0 & 0 & 0 & 0\\
      0 & 0 & 0 & 1
    \end{array}
  \right),\\
&b_1 = 30,
b_2 = 14
\end{eqnarray}

\tag{3}

ただし、線形計画と変数を対応させた場合、変数$X$の要素は以下の対応関係となる。また、変数$X$は正定値対称行列であることに注意する。

x_{11}=x_{1},x_{22}=x_{2},x_{33}=x_{3},x_{44}=x_{4}

線形計画を解くには、式（１）に基づいて主双対内点法で解く方法（以下では線形計画と書く）と、式（２）に基づいて主双対内点法で解く方法（以下では半正定値計画と書く）がある。線形計画に基づく主双対内点法と半正定値計画に基づく主双対内点法での性能を比較する。各イテレーション毎の実行時間と双対ギャップを比較する。

1. 数値実験

1.1 実験環境

使用するライブラリは、以前自前で実装したライブラリを使用する。

実装されている線形計画の主双対内点法と半正定値計画の主双対内点法は下記の通りである。


線形計画	主双対内点法	主双対アフィンスケーリング法
線形計画	主双対内点法	主双対パス追跡法
線形計画	主双対内点法	主双対ポテンシャル減少法
半正定値計画	主双対内点法	主双対パス追跡法	XZ method
半正定値計画	主双対内点法	主双対パス追跡法	XZ+ZX method

1.2 実行時間と双対ギャップの比較

線形計画の主双対内点法のほうが半正定値計画の主双対内点法より早く収束していることがわかる。また、１イテレーション毎の実行時間も短いことがわかる。

1.3 生成される点列の比較

1.3.1 線形計画(主双対パス追跡法)

主双対パス追跡法の実行結果を示す。左図は実行可能領域における各イテレーションにおける内点の位置を表している。右上図は各イテレーションにおける主問題と双対問題の目的関数値を示す。右下図は各イテレーションにおける双対ギャップを示す。

1.3.2半正定値計画（XZ+ZX method）

半正定値計画のXZ+ZX methodのみ記載する。XZ+ZX methodの実行結果を示す。左図は実行可能領域における各イテレーションにおける内点の位置を表している。右上図は各イテレーションにおける主問題と双対問題の目的関数値を示す。右下図は各イテレーションにおける双対ギャップを示す。

線形計画より双対ギャップの収束が遅いことがわかる。

3. おわりに

線形計画の主双対内点法のほうが効率よく解けていることがわかった。また、半正定値計画のXZ+ZX methodはリアプノフ方程式をといたり、ステップ幅の算出で逆行列を計算、固有値の計算をするので演算時間が長くかかったと思われる。