多面錐（凸多面錐）の定義と具体例

多面錐（凸多面錐）

変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する連立1次不等式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right.
\end{equation*}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。係数行列\(A\)と変数ベクトル\(\boldsymbol{x}\)および定数ベクトル\(\boldsymbol{b}\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\in M_{m,n}\left( \mathbb{R} \right) \\
\boldsymbol{x} &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in M_{n,1}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}\end{pmatrix}\in M_{m,1}\left( \mathbb{R} \right)
\end{eqnarray*}と定義すれば、先の連立1不等式は、\begin{equation*}
A\boldsymbol{x}\leq \boldsymbol{b}
\end{equation*}と表現できるため、その解集合は、\begin{equation*}
P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}となります。これを多面体と呼びます。多面体は凸集合であるため、多面体を凸多面体と呼ぶ場合もあります。

一方、ユークリッド空間の部分集合\(C\subset \mathbb{R} ^{n}\)が錐であることとは、\(C\)が非負のスカラー倍について閉じていること、すなわち、\begin{equation*}\forall \boldsymbol{x}\in C,\ \forall \lambda \geq 0:\lambda \boldsymbol{x}\in C
\end{equation*}が成り立つことを意味します。ちなみに、錐は凸集合であるとは限りません。凸集合であるような錐を凸錐と呼びます。集合\(C\)が凸錐であることと、以下の条件\begin{equation*}\forall \boldsymbol{x}_{1}\in C,\ \forall \boldsymbol{x}_{2}\in C,\ \forall
\lambda _{1}\geq 0,\ \forall \lambda _{2}\geq 0:\lambda _{1}\boldsymbol{x}_{1}+\lambda _{2}\boldsymbol{x}_{2}\in C
\end{equation*}が成り立つことは必要十分です。

多面体は錐であるとは限りません。まずは、錐ではない有界な多面体の例を挙げます。

続いて、錐ではない非有界な多面体の例を挙げます。

多面体は錐であるとは限らないことが明らかになりました。そこで、錐であるような多面体を多面錐（polyhedral cone）と呼びます。多面体は凸集合であるため、多面錐もまた凸集合です。したがって、多面錐を凸多面錐（convex polyhedral
cone）と呼ぶ場合もあります。

多面錐の代替的な定義

繰り返しになりますが、ユークリッド空間の部分集合\(P\subset \mathbb{R} ^{n}\)が多面錐であることは、\(P\)が多面体かつ錐であることを意味します。つまり、以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ \exists A\in M_{m,n}\left( \mathbb{R} \right) ,\ \exists \boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) :P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\} \\
&&\left( b\right) \ \forall \boldsymbol{x}\in P,\ \forall \lambda \geq
0:\lambda \boldsymbol{x}\in P
\end{eqnarray*}が成り立つということです。ただし、\(\left(a\right) \)は\(P\)が多面体であることを意味し、\(\left( b\right) \)は\(P\)が錐であることを意味します。ただし、多面体は凸集合であるため、\(P\)が錐であるという条件\(\left( b\right) \)を、\(P\)が凸錐であるという条件\begin{equation*}\left( b\right) \ \forall \boldsymbol{x}_{1}\in C,\ \forall \boldsymbol{x}_{2}\in C,\ \forall \lambda _{1}\geq 0,\ \forall \lambda _{2}\geq 0:\lambda
_{1}\boldsymbol{x}_{1}+\lambda _{2}\boldsymbol{x}_{2}\in C
\end{equation*}に置き換えることもできます。

いずれにせよ、集合\(P\subset \mathbb{R} ^{n}\)が多面錐であることを表す以上の諸条件を、\begin{equation*}\exists A\in M_{m,n}\left( \mathbb{R} \right) :P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\geq \boldsymbol{0}\right\}
\end{equation*}とシンプルに表現することもできます。つまり、多面錐は変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する連立1次不等式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\geq 0 \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\geq 0\end{array}\right.
\end{equation*}の解集合であるということです。

演習問題