Convex polyhedron with open faces

Convex polyhedron $P$ is a part of $\mathbb{R}^n$ that satisfies system of straight 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 conversely stood for by 2 limited collections of generators $V, W \subseteq \mathbb{R}^n$: $$P = \text{conv}(V) + \text{cone}(W),$$ where conv (V) represents all convex mixes of factors in V and also cone (W) all nonnegative straight mixes of factors in W.

Now, what happens if we permit $\sim_i$ to be from $\{\geq,>,\leq,<\}$. Exists some comparable depiction in regards to creating factors for such collections?

(I have no expertise of this location of maths, so I ask forgiveness if I obtained the terminology incorrect or if this inquiry is simply simple foolish.)

2019-05-18 23:09:47
Source Share
Answers: 2

No. However, it can not also be carried out in the 1D instance. As an example, take into consideration the inequalities $x > 0$ and also $x < 1$. After that $P$ is the open period $(0,1)$. You can not take $V = \{0,1\}$ due to the fact that after that conv$(V)$ is the shut period $[0,1]$. Taking $V$ to be any kind of various other 2 factors in between 0 and also 1 would certainly create a conv$(V)$ that is a rigorous part of $P$.

2019-05-21 09:43:03

Seems like such polyhedra are called not always shut (NNC) and also are generally stood for as shut polyhedra with added measurement $\varepsilon$: every rigorous inequality $a_{i1}x_1 + \ldots + a_{in}x_n > c_i$ is changed by $a_{i1}x_1 + \ldots + a_{in}x_n - \varepsilon \geq c_i$ and also 2 added inequalities $0 \leq \varepsilon \leq 1$ are included in the system. If we call this polyhedron $P'$, the wanted polyhedron is the set $\{ (x_1,\ldots,x_n) \mid (x_1,\ldots,x_n,\varepsilon) \in P', \varepsilon > 0 \}$. Such a system of restraints can be transformed to depiction by generators.

Conversely, they can be identified straight by 3 collections of generators $R,P,C \in \mathbb{R}^n$, i.e. every factor can be gotten 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 also $\alpha_i, \beta_i, \gamma_i \in \mathbb{R}^+$ and also $\sum_{i=1}^l \beta_i + \sum_{i=1}^m \gamma_i = 1$ and also there is $1 \leq i \leq l$ such that $\beta_i \neq 0$. The method below is that factors in $C$ do not need to exist within the NNC polyhedron, yet its closure, and also whenever they show up in the amount, there have to additionally be factor from $P$ with nonzero coefficient. This depiction can conveniently be transformed to the one stated above.

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:

Seems like this things is made use of primarily in fixed analysis/verification and also is not intriguing to mathematicians, possibly I should have asked on cstheory rather? Any kind of responses pertaining to the inquiry welcome, along with improvements concerning my abuse of terminology/notation.

2019-05-21 03:05:57