Cristopher Knox

2022-07-15

Convex polyhedron $P$ is a subset of ${\mathbb{R}}^{n}$ that satisfies system of linear inequalities
$\begin{array}{rl}{a}_{11}{x}_{1}+\cdots +{a}_{1n}{x}_{n}& {\sim }_{1}\phantom{\rule{thinmathspace}{0ex}}{c}_{1}\\ & ⋮\\ {a}_{p1}{x}_{1}+\cdots +{a}_{pn}{x}_{n}& {\sim }_{p}\phantom{\rule{thinmathspace}{0ex}}{c}_{p},\end{array}$
where ${\sim }_{i}\in \left\{\le ,\ge \right\}$. It can be alternatively represented by two finite sets of generators $V,W\subseteq {\mathbb{R}}^{n}$:
$P=\text{conv}\left(V\right)+\text{cone}\left(W\right),$
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 $\left\{\ge ,>,\le ,<\right\}$. Is there some similar representation in terms of generating points for such sets?

Sophia Mcdowell

Expert

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 $\left(0,1\right)$. You can't take $V=\left\{0,1\right\}$ because then conv$\left(V\right)$ is the closed interval $\left[0,1\right]$. Taking $V$ to be any other two points between 0 and 1 would generate a conv$\left(V\right)$ that is a strict subset of $P$.

vortoca

Expert

Seems like such polyhedra are called not necessarily closed (NNC) and are usually represented as closed polyhedra with additional dimension $\epsilon$: every strict inequality ${a}_{i1}{x}_{1}+\dots +{a}_{in}{x}_{n}>{c}_{i}$ is replaced by ${a}_{i1}{x}_{1}+\dots +{a}_{in}{x}_{n}-\epsilon \ge {c}_{i}$ and two additional inequalities $0\le \epsilon \le 1$ are added to the system. If we call this polyhedron ${P}^{\prime }$, the desired polyhedron is the set $\left\{\left({x}_{1},\dots ,{x}_{n}\right)\mid \left({x}_{1},\dots ,{x}_{n},\epsilon \right)\in {P}^{\prime },\epsilon >0\right\}$. 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 }_{1}{r}_{1}+\dots +{\alpha }_{k}{r}_{k}+{\beta }_{1}{p}_{1}+\dots +{\beta }_{l}{p}_{l}+{\gamma }_{1}{c}_{1}+\dots +{\gamma }_{m}{p}_{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\le i\le l$ such that ${\beta }_{i}\ne 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.

Do you have a similar question?