Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Convex polyhedron $P$ is a subset of $\mathbb{R}^n$ that satisfies system of linear inequalities \begin{align} a_{11}x_1 + \cdots + a_{1n}x_n & \sim_1\, c_1 \\ & \vdots \\ a_{p1}x_1 + \cdots + a_{pn}x_n & \sim_p\, c_p, \end{align} where $\sim_i \in \{\leq,\geq\}$. It can be alternatively represented by two finite sets of generators $V, W \subseteq \mathbb{R}^n$: $$P = \text{conv}(V) + \text{cone}(W),$$ where conv(V) denotes all convex combinations of points in V and cone(W) all nonnegative linear combinations of points in W.

Now, what if we allow $\sim_i$ to be from $\{\geq,>,\leq,<\}$. Is there some similar representation in terms of generating points for such sets?

(I possess no knowledge of this area of mathematics, so I apologize if I got the terminology wrong or if this question is just plain stupid.)

share|improve this question
2  
I may misunderstand the question because it seems trivially false -- take 0<x<1, what would V,W be? –  Yaroslav Bulatov Oct 8 '10 at 17:21
    
I didn't mean that the set must neccessarily be defined as P = conv(V) + cone(W) for some V and W. What I wanted to know is if the set can be described /somehow/ similarly, in terms of generating points. I am aware that it is rather vague question, but there is always chance that it may be something obvious or something almost everyone knows. Anyway, my mistake, I'll try to rephrase the question. –  aats Oct 8 '10 at 17:40

2 Answers 2

No. Unfortunately, it can't even be done in the 1D case. For instance, consider the inequalities $x > 0$ and $x < 1$. Then $P$ is the open interval $(0,1)$. You can't take $V = \{0,1\}$ because then conv$(V)$ is the closed interval $[0,1]$. Taking $V$ to be any other two points between 0 and 1 would generate a conv$(V)$ that is a strict subset of $P$.

share|improve this answer
1  
Looks like Yaroslav posted while I was typing up my answer. :) –  Mike Spivey Oct 8 '10 at 17:24
1  
(I don't have enough reputation points to comment on the original question, so I have to comment on mine.) I think this is a fine question as stated. The counterexample Yaroslav and I give has to do with the fact that a convex polyhedron with open faces does not contain its boundary (a fundamental property of the reals) and thus doesn't contain any extreme (generating) points. P must have extreme points to get P = conv(V) + cone(W). –  Mike Spivey Oct 8 '10 at 20:16

Seems like such polyhedra are called not necessarily closed (NNC) and are usually represented as closed polyhedra with additional dimension $\varepsilon$: every strict inequality $a_{i1}x_1 + \ldots + a_{in}x_n > c_i$ is replaced by $a_{i1}x_1 + \ldots + a_{in}x_n - \varepsilon \geq c_i$ and two additional inequalities $0 \leq \varepsilon \leq 1$ are added to the system. If we call this polyhedron $P'$, the desired polyhedron is the set $\{ (x_1,\ldots,x_n) \mid (x_1,\ldots,x_n,\varepsilon) \in P', \varepsilon > 0 \}$. Such a system of constraints can be converted to representation by generators.

Alternatively, they can be characterized directly by three sets of generators $R,P,C \in \mathbb{R}^n$, i.e. every point can be obtained as

$$\alpha_1r_1 + \ldots + \alpha_kr_k + \beta_1p_1 + \ldots + \beta_lp_l + \gamma_1c_1 + \ldots + \gamma_mp_m,$$

where $r_i \in R, p_i \in P, c_i \in C$ and $\alpha_i, \beta_i, \gamma_i \in \mathbb{R}^+$ and $\sum_{i=1}^l \beta_i + \sum_{i=1}^m \gamma_i = 1$ and there is $1 \leq i \leq l$ such that $\beta_i \neq 0$. The trick here is that points in $C$ don't have to lie within the NNC polyhedron, but its closure, and whenever they appear in the sum, there must also be point from $P$ with nonzero coefficient. This representation can easily be converted to the one mentioned above.

References:
R. Bagnara, P. M. Hill, E. Zaffanella: A New Encoding of Not Necessarily Closed Convex Polyhedra
R. Bagnara, E. Ricci, E. Zaffanella, P. M. Hill: Possibly Not Closed Convex Polyhedra and the Parma Polyhedra Library

Seems like this stuff is used mostly in static analysis/verification and is not interesting to mathematicians, maybe I should have asked on cstheory instead? Any feedback regarding the question welcome, as well as corrections regarding my misuse of terminology/notation.

share|improve this answer
    
I still think this is a fine question for this forum. I was also interested to read your follow-up here. It sounds like what you really wanted was a way to use a set of generators to describe an open convex polyhedron. Your answer here gives that. Nice. –  Mike Spivey Oct 13 '10 at 13:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.