ポリトープのエッジベクトルを見つけるアルゴリズムはありますか？[複製]

Question

質問：

いくつかのポイントを考える $x^1,\dots,x^m \in \mathbb R^n$、ポリトープのエッジに沿ってベクトルを見つけるアルゴリズムはありますか $$P = \mathrm{conv}(x^1,\dots,x^n)$$ これらの点の凸包によって形成されますか？

定義：

多面体は、有限個の点の凸包であります$\mathbb R^n$。しましょう$P \subset \mathbb R^n$ポリトープになります。顔の$P$ サブセットです $F \subset P$ フォームの $$F = \arg \max\{c^Tx : x \in P\}$$ いくつかのための $c \in \mathbb R^n$。の顔の寸法$P$アフィン包の寸法です。頂点は、ディメンションゼロの顔であり、エッジは、寸法一方の面です。場合$E$ のエッジです $P$ その後 $E = \mathrm{conv}(x, y)$ 一部の頂点の場合 $x$、 $y$。ポリトープのエッジベクトル$P$ ベクトルです $v \in \mathbb R^n$ そのような $v=x-y$ 一部の頂点の場合 $x$ そして $y$ そのために $\mathrm{conv}(x,y)$ エッジです。

例：

しましょう $x^1=(0,0), x^2=(1,0), x^3=(0,1), x^4=(1,1)$。これらの点の凸包は正方形です$$P=\mathrm{conv}(x^1, x^2, x^3, x^4)$$ そのエッジベクトルはによって与えられます $$\{(1,0), (0,1), (-1, 0), (0, -1)\}.$$ ご了承ください $(1,1)=x^4-x^1$ 2つの頂点の差ですが、はエッジベクトルではありません。

Answer 1

最初のステップでは、どの点が凸包の頂点であるかを判別する必要があります。次のステップでは、コメントのキムチが説明しているように進めることができます。

点数 $x_i$ の頂点です $\mathrm{conv}\{x_1,...,x_n\}$ もし

$$\max \{p^\top\! x_i\mid p^\top\! x_j \le 1 \text{ for all $j \ not = i$}\}$$

無制限です。

場合 $x_i,x_j$ は頂点であり、 $\mathrm{conv}\{x_i,x_j\}$は、この回答で説明されているように進めることができる凸包のエッジです。これをすべて繰り返す必要があります${n\choose 2}$頂点ペア。エッジの場合は、計算するだけです$x_i-x_j$ その方向性を得るために。

これらすべての場合に最大値を計算するには、標準であり、多くの十分に開発された実装（MathematicaやMATLABなど）を持つ線形計画法アルゴリズムを使用する必要があります。