0

I'm trying to prove the following.

Suppose $P\subset R^n$ is a polyhedral cone ($P=\{x\in R^n:Ax\leq0\}$). Sow that $P=cone\{ x_1,...,x_k\}$, for some $x_i\in R^n$, $i=1,...,k$.

My question is as follows.

The polyhedral cone is just the intersection of a finite number of halfspaces that cross the origin. So, to represent $P$, wouldn't it be sufficient to just choose two of the most extreme halfspaces (say the $i$th and $j$th halfspace), pick two vectors on the boundary of each halfspace (one vector orthogonal to $a_i^T$ and the other orthogonal to $a_j^T$th (with the right directions)) and, then, construct the polyhedral cone using the conical combination of these two vectors? Why is it required to choose $k$ such vectors to construct the cone?

Teodorism
  • 1,165

1 Answers1

1

If you choose two vectors on the most extreme halfspaces then you may generate a cone in the usual geometric sense (here), i.e. an n-dimensional convex body where intersections with planes are (n-1)-dimensional balls.

A polyhedral cone, however, is defined as a convex subset of a vector space under linear combinations with positive coefficients (here). As the name says, it is used in the representation theory of polyhedra. You may construct them from as many boundary vectors or halfplanes.

Here is a simple example in $n$ dimensions which shows that indeed $n$ conditions are needed: Let $e_i$ be the unit vector in dimension $i$, and let the cone be all positions $x$ with $x = \sum_{i=1}^n c_i e_i$ with $c_i \geq 0$. So your cone is the first orthant. Expressing the same in halfspaces, you have written (in your question) the conditions as $A x \leq 0$ and the matrix $A$ is

$$ \begin{aligned} A &= \begin{bmatrix} -1 & 0 & \dots & 0 \\0 & -1 & \dots & 0 \\ \vdots & \ \vdots & \ddots & \vdots \\ 0 & 0& \dots & -1 \end{bmatrix}\end{aligned} $$

Andreas
  • 15,175
  • In the question though the polyhedral cone is defined as ${x\in R^n: Ax\leq 0}$ with the standard ordering! – Teodorism Jan 22 '18 at 09:06
  • ok then k boundary vectors or k halfplanes. You can't get less. – Andreas Jan 22 '18 at 10:29
  • Okay. Here's why I'm confused. The feasible set of the polyhedral cone as defined in my problem statement lies between the two extreme halfspaces. If you think in 2-dim, it's an unbounded triangle. Every point in this triangle can be expressed as a conical comb. of the two vectors orthogonal to $a_i^T$ and $a_j^T$. So, I don't see why we need another $k-2$ vectors to get the feasible set. – Teodorism Jan 23 '18 at 14:48
  • In two dimensions you are right. In the main text I put a simple example in n dimensions which shows that you indeed need n conditions in any case. – Andreas Jan 25 '18 at 09:01