線形相補性問題におけるQ行列の判定方法

はじめに

本記事では、線形相補性問題（linear complementarity problem; LCP）において重要な行列クラスであるQ行列の判定方法を紹介します。Q行列はLCPが解を持つための必要十分な条件となる行列クラスです。所与の行列がQ行列であるかを判定できるということは、その行列を入力とするLCPが解を持つかを判定できることになります。

前提知識

本記事では、以下に示す事柄を前提知識といたします。詳細は[1]をご参照ください。内容の復習と記号の確認のために、定義と定理のみを以下に記載いたします。

Q行列の判定方法

定理1より、行列$M$がQ行列であるかどうかは、$\mathcal{K} = \mathbb{R}^n$であるかどうかで判定できます。

これは、$n$が小さい場合（$n = 1, 2, 3$）には、相補錐を図示することで確認できます。例として、以下の行列$M_1, M_2 \in \mathbb{R}^{2 \times 2}$の相補錐を図1に示します。行列$M_1$は相補錐が$\mathbb{R}^n$全体を埋めているのでQ行列ですが、行列$M_2$は相補錐が埋まっていない領域があるのでQ行列ではありません。

\begin{align} M_1 = \begin{pmatrix} -0.67 & 0.82 \\ 0.74 & -0.55 \end{pmatrix}, M_2 = \begin{pmatrix} -0.61 & 0.98 \\ 0.78 & 0.19 \end{pmatrix} \end{align}

$n = 2$でのQ行列判定の例

一方で、$n$が大きい場合（$n \geq 4$）には、相補錐を図示することができません。したがって、同様の方法で確認することはできません。以降では、$n$が大きい場合にも適用できるQ行列の判定方法[2]を説明します。

方針としては、相補錐$\mathcal{K}$が$\mathbb{R}^n$であるかどうかを、その補集合$\bar{\mathcal{K}}$が空集合であるかどうかで判定します。$\bar{\mathcal{K}}$を補相補錐と呼ぶことにします。

ここで、補相補錐$\bar{\mathcal{K}}$は一般には非凸であり、これが空集合であるかを高速に判定できる方法は知られていません。そのため、補相補錐$\bar{\mathcal{K}}$を複数の凸集合に分割して、それぞれの集合が空集合であるかどうかを確認します。凸集合であれば、内点法や楕円体法などを用いて、空集合であるかを高速に判定できます。

補相補錐$\bar{\mathcal{K}}$を複数の凸集合に分割するために、定義式を変形していきます。まずは、元の相補錐$\mathcal{K}$の定義を再掲します。

\begin{align} \mathcal{K} = \bigcup_{\pi \in \Pi} \mathcal{C}_\pi \end{align}

各相補錐$\mathcal{C}_\pi$は以下のように半空間$\mathcal{H}_{\pi, i} (i \in \{ 1, ..., n \})$の積集合としても表現できます。ここで、ベクトル$h_{\pi, i} \in \mathbb{R}^n$は行列$A_\pi^{-1}$の$i$番目の行ベクトルです。

\begin{align} \mathcal{C}_\pi &= \bigcap_{i \in \{ 1, ..., n \}} \mathcal{H}_{\pi, i} \\ \mathcal{H}_{\pi, i} &= \{ \forall q \in \mathbb{R}^n : h_{\pi, i}^\top q \geq 0 \} \end{align}

ここで、相補錐が半空間の積集合として表現できるのは、相補錐が凸多面体であることに由来します。また、半空間を解析的に求められることは、相補錐が$n$次元空間上の$n$本のベクトルで生成される凸錐であることに由来します。詳細についての説明は省略させていただきます。

したがって、相補錐$\mathcal{K}$の定義式は以下のように変形できます。

\begin{align} \mathcal{K} = \bigcup_{\pi \in \{ 0, 1 \}^n} \bigcap_{i \in \{ 1, ..., n \}} \mathcal{H}_{\pi, i} \end{align}

このとき、その補集合$\bar{\mathcal{K}}$は以下となります。

\begin{align} \bar{\mathcal{K}} = \bigcap_{\pi \in \{ 0, 1 \}^n} \bigcup_{i \in \{ 1, ..., n \}} \bar{\mathcal{H}}_{\pi, i} \end{align}

最後に、テクニカルかつ本質的な変形になるのですが、和集合と積集合の分配法則を使うと、補相補錐$\bar{\mathcal{K}}$が凸多面体$\bar{\mathcal{H}}_{\sigma} \subseteq \mathbb{R}^n (\sigma \in \{ 1, ..., n \}^{2^n})$の和集合になります。したがって、補相補錐$\bar{\mathcal{K}}$を複数の凸集合に分割できました。

\begin{align} \bar{\mathcal{K}} &= \bigcup_{\sigma \in \{ 1, ..., n \}^{2^n}} \bar{\mathcal{H}}_{\sigma} \\ \bar{\mathcal{H}}_{\sigma} &= \bigcap_{\pi \in \{ 1, ..., n \}^n} \bar{\mathcal{H}}_{\pi, \sigma_\pi} \end{align}

最後の変形をイメージしやすいように、$n = 2$での例を以下に記載します。

\begin{align} \mathcal{K} = (\mathcal{H}_{(0,0), 1} \cap \mathcal{H}_{(0,0), 2}) \cup (\mathcal{H}_{(0,1), 1} \cap \mathcal{H}_{(0,1), 2}) \cup (\mathcal{H}_{(1,0), 1} \cap \mathcal{H}_{(1,0), 2}) \cup (\mathcal{H}_{(1,1), 1} \cap \mathcal{H}_{(1,1), 2}) \end{align}

\begin{align} \bar{\mathcal{K}} = (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 0} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 0} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 0} \cap \bar{\mathcal{H}}_{(1,1), 1}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 0}) \\ \cup (\bar{\mathcal{H}}_{(0,0), 1} \cap \bar{\mathcal{H}}_{(0,1), 1} \cap \bar{\mathcal{H}}_{(1,0), 1} \cap \bar{\mathcal{H}}_{(1,1), 1}) \end{align}

以上より、任意の$\sigma \in \{ 1, ..., n \}^{2^n}$に対して凸多面体$\bar{\mathcal{H}}_{\sigma}$が空集合であるかどうかを確認することで、行列$M$がQ行列であるかどうかを判定できます。

ここで、$\sigma$には$n^{2^n}$通りの組合せがありますので、高速な判定方法ではないことにご注意ください。

プログラム

上記の判定方法を実装したプログラムを ここ に置いておきます。is_q_matrixに判定したい行列を入力してください。また、show_complementary_coneで、$n = 2$の場合に限り、相補錐の可視化もできます。