convex polytopeとは何？わかりやすく解説 Weblio辞書

凸多面体

読み方：とつためんたい
【英】：convex polyhedron, convex polytope

概要

有限個の閉半空間の共通部分を凸多面体と呼ぶ. すなわち, $n\,$ 次元実線形空間 ${\mathbf R}^n\,$ 内の凸多面体 $P\,$ は, 適当な $m \times n\,$ 実行列 $A\,$ と $m\,$ 次元ベクトル $b\,$ を用いて

$P=\{ x \in {\mathbf R}^n \mid A x \leq b \} \,$

と表現できる. 特に有界な凸多面体は, convex polytope と英語では区別して呼ばれ, 有限個の点からなる集合の凸包であり, 逆も成り立つ.

詳説

　 $n\,$ 次元実ベクトル $a=(a_1,\cdots,a_n)^{\rm T} \in {\mathbf R}^n\,$ と実数 $a_0{\in}{\mathbf R}\,$ により定まる 1次不等式 (線形不等式) $(a_1 x_1 + \cdots + a_n x_n \leq a_0)\,$ を満たす点 $x = (x_1,\cdots,x_n)^{\rm T}\,$ 全体からなる集合を閉半空間(closed halfspace)とよぶ. 有限個の閉半空間の共通部分を凸多面体 (convex polyhedron) とよぶ. すなわち, ${\mathbf R}^n\,$ 内の凸多面体は, 適当な $m{\times}n\,$ 実行列 $A\,$ と $m\,$ 次元ベクトル $b\,$ を用いて

$P = \{ x \in {\mathbf R}^n \mid Ax \leq b \}\,$ 　　　　 $(1)\,$

と表現できる. 凸多面体 $P\,$ が, ある正の実数 $M\,$ に対して

$x \in P \;\Longrightarrow\; |x_i| \leq M \quad(i=1,\cdots,n)\,$

をみたすとき有界である(bounded)とよばれ, 英語では convex polytopeと区別してよばれることが多い. 凸多面体の例としては, 線形計画問題での実行可能多面体, TSP多面体, マトロイドの基多面体, ポリマトロイドなどがある.

　凸多面体には不等式表現以外にもう一つ有益な表現方法がある. $v^1,\cdots,v^\ell \in {\mathbf R}^n\,$ に対して, 適当な $\alpha_1,\cdots,\alpha_\ell \in {\mathbf R}\,$ によって

$v = \alpha_1v^1 + \cdots + \alpha_\ell v^\ell\,$

と表現されるベクトル $v\,$ を $v^1,\cdots,v^\ell\,$ の一次結合(線形結合) (linear combination) とよぶ. 係数 $\alpha_1,\cdots,\alpha_\ell\,$ が非負条件

$\alpha_1 \geq 0, \cdots , \alpha_\ell \geq 0\,$ 　　　　 $(2)\,$

をみたす場合には $v\,$ は非負結合(nonnegative combination), 和が1という条件

$\alpha_1 + \cdots + \alpha_\ell = 1\,$ 　　　　 $(3)\,$

をみたす場合には $v\,$ はアフィン結合 (affine combination), さらに (2) と (3) の両方をみたすとき $v\,$ は $v^1,\cdots,v^\ell\,$ の凸結合 (convex combination) とよばれる. 有限個の $v^1,\cdots,v^\ell \in {\mathbf R}^n\,$ と $r^1,\cdots,r^d \in {\mathbf R}^n\,$ に対して, $v^1,\cdots,v^\ell\,$ の凸結合と $r^1,\cdots,r^d\,$ の非負結合の和として表される点全体, すなわち

$\left\{ x=\sum_{i=1}^\ell \alpha_iv^i + \sum_{j=1}^d \beta_jd^j \;\; \begin{array}{|l} \sum_{i=1}^\ell \alpha_i = 1 \\ \alpha_i \geq 0 \;(i=1,\cdots,\ell) \\ \beta_j \geq 0 \;(j=1,\cdots,d) \end{array} \right\} \,$ 　　　　 $(4)\,$

と定義される集合は凸多面体となり, 逆に (1) で定義される凸多面体については (4) をみたす有限個の $v^1,\cdots,v^\ell \in {\mathbf R}^n\,$ と $r^1,\cdots,r^d \in {\mathbf R}^n\,$ が存在することが知られている. 特に, 有界な凸多面体に対しては有限個の点 $v^1,\cdots,v^\ell \in {\mathbf R}^n\,$ の凸結合全体, すなわち,

$P = \left\{ x=\sum_{i=1}^\ell \alpha_iv^i \;\; \right| \left. \sum_{i=1}^\ell \alpha_i = 1,\;\; \alpha_i \geq 0 \;(i=1,\cdots,\ell) \right\}\,$ 　　　　 $(5)\,$

と表現でき, (5)で定義される集合は, 点集合 $V=\{v^1,\cdots,v^\ell\}\,$ を含む (集合の包含関係の意味で) 最小な凸集合 (convex set)として定義される $V\,$ の凸包 (convex hull) と一致する. 例えば, ${(0,0,0),(1,0,0),(0,1,0),(0,0,1)} \subset {\mathbf R}^3\,$ の凸包である有界な凸多面体は

$x_1+x_2+x_3 \leq 1,\quad x_1 \geq 0, \quad x_2 \geq 0, \quad x_3 \geq 0\,$

という４本の不等式で表現できる三角錐である.

　点集合 $V=\{v^1,\cdots,v^\ell\} \subseteq {\mathbf R}^n\,$ について, どの要素も他の要素たちのアフィン結合で表現できないとき, すなわち,

$\alpha_1v^1 + \cdots + \alpha_\ell v^\ell = 0 \;\Longrightarrow\; \alpha_1 = \cdots = \alpha_\ell = 0\,$

をみたすとき, $V\,$ はアフィン独立(affinely independent)であるという. ${\mathbf R}^n\,$ からは高々 $n{+}1\,$ 個のアフィン独立な点しか取れない. 集合 $S \subseteq {\mathbf R}^n\,$ に含まれるアフィン独立な点集合で要素数最大のものを $V=\{v^1,\cdots,v^\ell\}\,$ としたとき, $S\,$ の次元は $\ell{-}1\,$ と定義する(次元は $V\,$ の選び方に依存しないことを付記しておく). 先の例では, ${(0,0,0),(1,0,0),(0,1,0),(0,0,1)}\,$ はアフィン独立であり, この凸包である三角錐の次元は $3\,$ となる. 凸多面体 $P \subseteq {\mathbf R}^n\,$ の次元が $n\,$ であるとき全次元的(full dimensional)という.

　凸多面体 $P \subseteq {\mathbf R}^n\,$ に対して, 超平面(hyperplane) $H\,$ , すなわち, 非ゼロベクトル $(a_1,\cdots,a_n)^{\rm T} \in {\mathbf R}^n\,$ と $a_0 \in {\mathbf R}\,$ を用いて