双対錐
ユークリッド空間の非空な部分集合\(C\subset \mathbb{R} ^{n}\)が与えられたとき、\(C\)に属するすべてのベクトルとの内積が非負の実数になるようなベクトルを集めることにより得られる集合を、\begin{equation*}C^{\ast }=\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{x}\in C:\boldsymbol{x}\cdot \boldsymbol{y}\geq
0\right\}
\end{equation*}で表記し、これを\(C\)の双対錐（dual cone of \(C\)）と呼びます。定義より、以下の関係\begin{equation*}\forall \boldsymbol{y}\in \mathbb{R} ^{n}:\left( \boldsymbol{y}\in C^{\ast }\Leftrightarrow \forall \boldsymbol{x}\in C:\boldsymbol{x}\cdot \boldsymbol{y}\geq 0\right)
\end{equation*}が成り立ちます。
列ベクトル\(\boldsymbol{x},\boldsymbol{y}\in M_{n,1}\left( \mathbb{R} \right) \)を任意に選んだとき、内積と行列積の関係より、\begin{equation*}\boldsymbol{x}\cdot \boldsymbol{y}=\boldsymbol{x}^{t}\boldsymbol{y}
\end{equation*}が成り立つため、集合\(C\subset \mathbb{R} ^{n}\)の双対錐を、\begin{equation*}C^{\ast }=\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{x}\in C:\boldsymbol{x}^{t}\boldsymbol{y}\geq
0\right\}
\end{equation*}と表現することもできます。このとき、以下の関係\begin{equation*}
\forall \boldsymbol{y}\in \mathbb{R} ^{n}:\left( \boldsymbol{y}\in C^{\ast }\Leftrightarrow \forall \boldsymbol{x}\in C:\boldsymbol{x}^{t}\boldsymbol{y}\geq 0\right)
\end{equation*}が成り立ちます。
2つのベクトルの内積が非負であることは、それらのベクトルのなす角が鋭角であることを意味します（直角を含む）。したがって、集合\(C\)の双対錐\(C^{\ast }\)とは、\(C\)に属するすべてのベクトルとなす角が鋭角であるようなベクトルを集めることにより得られる集合です。
双対錐\(C^{\ast }\)を定義するもととなる集合\(C\)は錐である必要はありません。ただ、後ほど示すように、錐であるとは限らない非空の集合\(C\)を任意に選んだとき、その双対錐\(C^{\ast }\)は必ず錐になります。
\end{equation*}を構成すると、その双対錐は、\begin{eqnarray*}
\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast } &=&\left\{
\boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{x}^{\prime }\in \left\{ \boldsymbol{x}\right\} :\boldsymbol{x}^{\prime }\cdot \boldsymbol{y}\geq 0\right\} \quad \because
\text{双対錐の定義} \\
&=&\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \boldsymbol{x}\cdot \boldsymbol{y}\geq 0\right\} \\
&=&H^{+}\left( \boldsymbol{x},0\right) \quad \because \text{上半空間の定義}
\end{eqnarray*}となります。ただし、\(H^{+}\left( \boldsymbol{x},0\right) \)は上半空間です（下図）。
\left\{ \boldsymbol{0}\right\} \subset \mathbb{R} ^{n}
\end{equation*}を構成すると、その双対錐は、\begin{eqnarray*}
\left( \left\{ \boldsymbol{0}\right\} \right) ^{\ast } &=&\left\{
\boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{x}\in \left\{ \boldsymbol{0}\right\} :\boldsymbol{x}\cdot \boldsymbol{y}\geq 0\right\} \quad \because \text{双対錐の定義} \\
&=&\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \boldsymbol{0}\cdot \boldsymbol{y}\geq 0\right\} \\
&=&\mathbb{R} ^{n}
\end{eqnarray*}となります。
\end{equation*}の双対錐は、\begin{equation*}
\left( \mathbb{R} _{+}^{n}\right) ^{\ast }=\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{x}\in \mathbb{R} _{+}^{n}:\boldsymbol{x}\cdot \boldsymbol{y}\geq 0\right\}
\end{equation*}と定義しますが、以下の関係\begin{equation*}
\left( \mathbb{R} _{+}^{n}\right) ^{\ast }=\mathbb{R} _{+}^{n}
\end{equation*}が成り立ちます（演習問題）。つまり、\(\mathbb{R} _{+}^{n}\)の双対錐は\(\mathbb{R} _{+}^{n}\)自身と一致します。
&&\left( b\right) \ \forall \boldsymbol{x},\boldsymbol{y}\in V:\boldsymbol{x}+\boldsymbol{y}\in V \\
&&\left( c\right) \ \forall \lambda \in \mathbb{R} ,\ \forall \boldsymbol{x}\in V:\lambda \boldsymbol{x}\in V
\end{eqnarray*}がすべて成り立つということです。その双対錐は、\begin{equation*}
V^{\ast }=\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{v}\in V:\boldsymbol{v}\cdot \boldsymbol{y}\geq
0\right\}
\end{equation*}となります。その一方で、部分空間\(V\)の直交補空間は、\(V\)に属するすべてのベクトルと直交するベクトルからなる集合\begin{equation*}V^{\perp }=\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{v}\in V:\boldsymbol{v}\cdot \boldsymbol{y}=0\right\}
\end{equation*}として定義されますが、このとき、以下の関係\begin{equation*}
V^{\ast }=V^{\perp }
\end{equation*}が成り立つことが保証されます（演習問題）。部分空間の双対錐は直交補空間と一致するということです。
双対錐を特定する方法
集合\(C\subset \mathbb{R} ^{n}\)の双対錐は、\begin{equation*}C^{\ast }=\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{x}\in C:\boldsymbol{x}\cdot \boldsymbol{y}\geq
0\right\}
\end{equation*}と定義されるため、以下の関係\begin{equation}
\forall \boldsymbol{y}\in \mathbb{R} ^{n}:\left( \boldsymbol{y}\in C^{\ast }\Leftrightarrow \forall \boldsymbol{x}\in C:\boldsymbol{x}\cdot \boldsymbol{y}\geq 0\right) \quad \cdots (2)
\end{equation}が成り立ちます。
ゼロベクトル\(\boldsymbol{0}\in \mathbb{R} ^{n}\)については、\begin{equation*}\forall \boldsymbol{x}\in C:\boldsymbol{x}\cdot \boldsymbol{0}\geq 0
\end{equation*}が明らかに成り立つため、\(\left( 2\right) \)より、\begin{equation*}\boldsymbol{0}\in C^{\ast }
\end{equation*}を得ます。つまり、ゼロベクトルは必ず双対錐\(C^{\ast }\)の要素であるということです。
非ゼロベクトル\(\boldsymbol{y}\in \mathbb{R} ^{n}\backslash \left\{ \boldsymbol{0}\right\} \)については、\(\boldsymbol{y}\)を法線ベクトルとするとともに原点を通過する上半空間\begin{equation*}H\left( \boldsymbol{y},0\right) =\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ \boldsymbol{x}\cdot \boldsymbol{y}\geq 0\right\}
\end{equation*}を定義することにより、\(\left( 2\right) \)より、\begin{equation*}\boldsymbol{y}\in C^{\ast }\Leftrightarrow \forall \boldsymbol{x}\in C:\boldsymbol{x}\in H\left( \boldsymbol{y},0\right)
\end{equation*}すなわち、\begin{equation*}
\boldsymbol{y}\in C^{\ast }\Leftrightarrow C\subset H\left( \boldsymbol{y},0\right)
\end{equation*}を得ます。以上の議論より、非ゼロベクトル\(\boldsymbol{y}\)が双対錐\(C^{\ast }\)の要素であることを判定するためには、上半空間\(H\left( \boldsymbol{y},0\right) \)を作った上で、もとの集合\(C\)が上半空間\(H\left( \boldsymbol{y},0\right) \)の部分集合であることを確認すればよいことが明らかになりました。逆に、\(C\)が\(H\left( \boldsymbol{y},0\right) \)の部分集合ではない場合、\(\boldsymbol{y}\)は\(C^{\ast }\)の要素ではありません。
図中の点\(\boldsymbol{y}\)は双対錐\(C^{\ast }\)の要素でしょうか。法線ベクトルが\(\boldsymbol{y}\)であり原点を通過する上半空間\(H\left( \boldsymbol{y},0\right) \)は上図中のブルーの領域として描かれています。\(C\)が\(H\left( \boldsymbol{y},0\right) \)の部分集合であることを図より確認できるため、先の議論より、\begin{equation*}\boldsymbol{y}\in C^{\ast }
\end{equation*}であることが明らかになりました。
図中の点\(\boldsymbol{y}\)は双対錐\(C^{\ast }\)の要素でしょうか。法線ベクトルが\(\boldsymbol{y}\)であり原点を通過する上半空間\(H\left( \boldsymbol{y},0\right) \)は上図中のブルーの領域として描かれています。\(C\)が\(H\left( \boldsymbol{y},0\right) \)の部分集合ではないことを図より確認できるため、先の議論より、\begin{equation*}\boldsymbol{y}\not\in C^{\ast }
\end{equation*}であることが明らかになりました。
双対錐は錐
非空の集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、その双対錐\(C^{\ast }\)は錐になることが保証されます。つまり、\begin{equation*}\forall \boldsymbol{x}\in C^{\ast },\ \forall \lambda \geq 0:\lambda
\boldsymbol{x}\in C^{\ast }
\end{equation*}が成り立つということです。以上の主張は任意の集合\(C\)について成り立つため、錐ではない集合\(C\)についても、その双対錐\(C^{\ast }\)は錐になります。
\end{equation*}を構成すると、先に示したように、その双対錐は、\begin{equation*}
\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast }=H^{+}\left(
\boldsymbol{x},0\right)
\end{equation*}となります。ただし、\(H^{+}\left( \boldsymbol{x},0\right) \)は上半空間です。先の命題より\(\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast }\)は錐です。実際、上半空間は錐であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\left\{ \boldsymbol{x}\right\} \)は錐ではありません。
\left\{ \boldsymbol{0}\right\} \subset \mathbb{R} ^{n}
\end{equation*}を構成すると、先に示したように、その双対錐は、\begin{equation*}
\left( \left\{ \boldsymbol{0}\right\} \right) ^{\ast }=\mathbb{R} ^{n}
\end{equation*}となります。先の命題より\(\left( \left\{ \boldsymbol{0}\right\} \right)^{\ast }\)は錐です。実際、\(\mathbb{R} ^{n}\)は錐であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\left\{ \boldsymbol{0}\right\} \)は錐ではありません。
\end{equation*}の双対錐は、先に示したように、\begin{equation*}
\left( \mathbb{R} _{+}^{n}\right) ^{\ast }=\mathbb{R} _{+}^{n}
\end{equation*}です。先の命題より\(\left( \mathbb{R} _{+}^{n}\right) ^{\ast }\)は錐です。実際、\(\mathbb{R} _{+}^{n}\)は錐であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\mathbb{R} _{+}^{n}\)も錐です。
&&\left( b\right) \ \forall \boldsymbol{x},\boldsymbol{y}\in V:\boldsymbol{x}+\boldsymbol{y}\in V \\
&&\left( c\right) \ \forall \lambda \in \mathbb{R} ,\ \forall \boldsymbol{x}\in V:\lambda \boldsymbol{x}\in V
\end{eqnarray*}がすべて成り立つということです。先に示したように、その双対錐は、\begin{equation*}
V^{\ast }=V^{\perp }
\end{equation*}です。ただし、\(V^{\perp }\)は\(V\)の直交補空間です。先の命題より\(V^{\ast }\)は錐です。したがって、直交補空間\(V^{\perp }\)は錐です。
双対錐は凸集合
非空の集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、その双対錐\(C^{\ast }\)は凸集合になることが保証されます。つまり、\begin{equation*}\forall \boldsymbol{x}_{1}\in C^{\ast },\ \forall \boldsymbol{x}_{2}\in
C^{\ast },\ \forall \lambda \in \left[ 0,1\right] :\lambda \boldsymbol{x}_{1}+\left( 1-\lambda \right) \boldsymbol{x}_{2}\in C^{\ast }
\end{equation*}が成り立つということです。以上の主張は任意の集合\(C\)について成り立つため、錐ではない集合\(C\)についても、その双対錐\(C^{\ast }\)は凸集合になります。
ユークリッド空間の非空の部分集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、その双対錐\(C^{\ast }\)は凸集合である。
\end{equation*}を構成すると、先に示したように、その双対錐は、\begin{equation*}
\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast }=H^{+}\left(
\boldsymbol{x},0\right)
\end{equation*}となります。ただし、\(H^{+}\left( \boldsymbol{x},0\right) \)は上半空間です。先の命題より\(\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast }\)は凸集合です。実際、上半空間は凸集合であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\left\{ \boldsymbol{x}\right\} \)も凸集合です。
\left\{ \boldsymbol{0}\right\} \subset \mathbb{R} ^{n}
\end{equation*}を構成すると、先に示したように、その双対錐は、\begin{equation*}
\left( \left\{ \boldsymbol{0}\right\} \right) ^{\ast }=\mathbb{R} ^{n}
\end{equation*}となります。先の命題より\(\left( \left\{ \boldsymbol{0}\right\} \right)^{\ast }\)は凸集合です。実際、\(\mathbb{R} ^{n}\)は凸集合であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\left\{ \boldsymbol{0}\right\} \)も凸集合です。
\end{equation*}の双対錐は、先に示したように、\begin{equation*}
\left( \mathbb{R} _{+}^{n}\right) ^{\ast }=\mathbb{R} _{+}^{n}
\end{equation*}です。先の命題より\(\left( \mathbb{R} _{+}^{n}\right) ^{\ast }\)は凸集合です。実際、\(\mathbb{R} _{+}^{n}\)は凸集合であるため、以上の事実は先の命題の主張と整合的です。
&&\left( b\right) \ \forall \boldsymbol{x},\boldsymbol{y}\in V:\boldsymbol{x}+\boldsymbol{y}\in V \\
&&\left( c\right) \ \forall \lambda \in \mathbb{R} ,\ \forall \boldsymbol{x}\in V:\lambda \boldsymbol{x}\in V
\end{eqnarray*}がすべて成り立つということです。先に示したように、その双対錐は、\begin{equation*}
V^{\ast }=V^{\perp }
\end{equation*}です。ただし、\(V^{\perp }\)は\(V\)の直交補空間です。先の命題より\(V^{\ast }\)は凸集合です。したがって、直交補空間\(V^{\perp }\)は凸集合です。
非空の集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、その双対錐\(C^{\ast }\)は錐かつ凸集合であることが明らかになりました。集合が錐かつ凸集合であることは、その集合が凸錐であることと必要十分です。したがって、双対錐\(C^{\ast }\)は凸錐です。つまり、\begin{equation*}\forall \boldsymbol{x}_{1}\in C^{\ast },\ \forall \boldsymbol{x}_{2}\in
C^{\ast },\ \forall \lambda _{1}\geq 0,\ \forall \lambda _{2}\geq 0:\lambda
_{1}\boldsymbol{x}_{1}+\lambda _{2}\boldsymbol{x}_{2}\in C^{\ast }
\end{equation*}が成り立ちます。
双対錐は閉集合
非空の集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、その双対錐\(C^{\ast }\)は\(\mathbb{R} ^{n}\)上の閉集合になることが保証されます。以上の主張は任意の集合\(C\)について成り立つため、閉集合ではない集合\(C\)についても、その双対錐\(C^{\ast }\)は閉集合になります。
ユークリッド空間の非空の部分集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、その双対錐\(C^{\ast }\)は\(\mathbb{R} ^{n}\)上の閉集合である。
\end{equation*}を構成すると、先に示したように、その双対錐は、\begin{equation*}
\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast }=H^{+}\left(
\boldsymbol{x},0\right)
\end{equation*}となります。ただし、\(H^{+}\left( \boldsymbol{x},0\right) \)は上半空間です。先の命題より\(\left( \left\{ \boldsymbol{x}\right\} \right) ^{\ast }\)は閉集合です。実際、上半空間は閉集合であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\left\{ \boldsymbol{x}\right\} \)も閉集合です。
\left\{ \boldsymbol{0}\right\} \subset \mathbb{R} ^{n}
\end{equation*}を構成すると、先に示したように、その双対錐は、\begin{equation*}
\left( \left\{ \boldsymbol{0}\right\} \right) ^{\ast }=\mathbb{R} ^{n}
\end{equation*}となります。先の命題より\(\left( \left\{ \boldsymbol{0}\right\} \right)^{\ast }\)は閉集合です。実際、\(\mathbb{R} ^{n}\)は凸集合であるため、以上の事実は先の命題の主張と整合的です。ちなみに、もとの集合\(\left\{ \boldsymbol{0}\right\} \)も閉集合です。
\end{equation*}の双対錐は、先に示したように、\begin{equation*}
\left( \mathbb{R} _{+}^{n}\right) ^{\ast }=\mathbb{R} _{+}^{n}
\end{equation*}です。先の命題より\(\left( \mathbb{R} _{+}^{n}\right) ^{\ast }\)は閉集合です。実際、\(\mathbb{R} _{+}^{n}\)は閉集合であるため、以上の事実は先の命題の主張と整合的です。
&&\left( b\right) \ \forall \boldsymbol{x},\boldsymbol{y}\in V:\boldsymbol{x}+\boldsymbol{y}\in V \\
&&\left( c\right) \ \forall \lambda \in \mathbb{R} ,\ \forall \boldsymbol{x}\in V:\lambda \boldsymbol{x}\in V
\end{eqnarray*}がすべて成り立つということです。先に示したように、その双対錐は、\begin{equation*}
V^{\ast }=V^{\perp }
\end{equation*}です。ただし、\(V^{\perp }\)は\(V\)の直交補空間です。先の命題より\(V^{\ast }\)は閉集合です。したがって、直交補空間\(V^{\perp }\)は閉集合です。
双対錐と包含関係
非空の集合\(C,D\subset \mathbb{R} ^{n}\)を任意に選んだとき、以下の関係\begin{equation*}C\subset D\Rightarrow D^{\ast }\subset C^{\ast }
\end{equation*}が成り立ちます。つまり、双対錐をとると包含関係が逆転します。
\end{equation*}が成り立つ。
双対錐と凸包の双対錐は一致する
集合\(C\subset \mathbb{R} ^{n}\)が与えられたとき、\(C\)を部分集合として持つ凸集合の中でも最小のものを\(A\)の凸包と呼びます。集合\(C\)の凸包は、\(C\)の要素の凸結合からなる集合\begin{equation*}\mathrm{Conv}\left( C\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\ |\ k\in \mathbb{N} \wedge \sum_{i=1}^{k}\lambda _{i}=1\wedge \forall i\in \left\{ 1,\cdots
,k\right\} :\left( \lambda _{i}\geq 0\wedge \boldsymbol{x}_{i}\in C\right)
\right\}
\end{equation*}と一致します。
非空の集合\(C\subset \mathbb{R} ^{n}\)を任意に選んだとき、以下の関係\begin{equation*}C^{\ast }=\left( \mathrm{Conv}\left( C\right) \right) ^{\ast }
\end{equation*}が成り立つことが保証されます。つまり、集合\(C\)の双対錐と、\(C\)の凸包の双対錐は一致します。
\end{equation*}が成り立つ。ただし、\(C^{\ast }\)は\(C\)の双対錐であり、\(\mathrm{Conv}\left( C\right) \)は\(C\)の凸包であり、\(\left( \mathrm{Conv}\left(C\right) \right) ^{\ast }\)はその双対錐である。
演習問題
\end{equation*}の双対錐は、\begin{equation*}
\left( \mathbb{R} _{+}^{n}\right) ^{\ast }=\mathbb{R} _{+}^{n}
\end{equation*}であることを示してください。
\end{equation*}が成り立つことを示してください。ただし、\(V^{\ast }\)は\(V\)の双対錐であり、\(V^{\perp }\)は\(V\)の直交補空間です。つまり、\begin{eqnarray*}V^{\ast } &=&\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{v}\in V:\boldsymbol{v}\cdot \boldsymbol{y}\geq
0\right\} \\
V^{\perp } &=&\left\{ \boldsymbol{y}\in \mathbb{R} ^{n}\ |\ \forall \boldsymbol{v}\in V:\boldsymbol{v}\cdot \boldsymbol{y}=0\right\}
\end{eqnarray*}です。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】