Cristopher Knox

Answered

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}\\ & \vdots \\ {a}_{p1}{x}_{1}+\cdots +{a}_{pn}{x}_{n}& {\sim}_{p}\phantom{\rule{thinmathspace}{0ex}}{c}_{p},\end{array}$

where ${\sim}_{i}\in \{\le ,\ge \}$. 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 $\{\ge ,>,\le ,<\}$. Is there some similar representation in terms of generating points for such sets?

$\begin{array}{rl}{a}_{11}{x}_{1}+\cdots +{a}_{1n}{x}_{n}& {\sim}_{1}\phantom{\rule{thinmathspace}{0ex}}{c}_{1}\\ & \vdots \\ {a}_{p1}{x}_{1}+\cdots +{a}_{pn}{x}_{n}& {\sim}_{p}\phantom{\rule{thinmathspace}{0ex}}{c}_{p},\end{array}$

where ${\sim}_{i}\in \{\le ,\ge \}$. 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 $\{\ge ,>,\le ,<\}$. Is there some similar representation in terms of generating points for such sets?

Answer & Explanation

Sophia Mcdowell

Expert

2022-07-16Added 14 answers

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$.

vortoca

Expert

2022-07-17Added 2 answers

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 $\{({x}_{1},\dots ,{x}_{n})\mid ({x}_{1},\dots ,{x}_{n},\epsilon )\in {P}^{\prime},\epsilon >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}_{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.

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.

Most Popular Questions