Convex polyhedron P is a subset of R n that satisfies system of linear inequalities a 11 x 1 + ⋯ + a 1 n x n ∼ 1 c 1 ⋮ a p 1 x 1 + ⋯ + a p n x n ∼ p c p , where ∼ i ∈ { ≤ , ≥ }. It can be alternatively represented by two finite sets of generators V , W ⊆ R n : P = conv ( V ) + 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 ∼ i to be from { ≥ , &gt; , ≤ , &lt; }. Is there some similar representation in terms of generating points for such sets?

Question

Convex polyhedron   P is a subset of         R    n   that satisfies system of linear inequalities                              a                  11                          x          1                +        ⋯        +                  a                      1            n                                    x          n                                              ∼          1                                  c          1                                                  ⋮                                      a                      p            1                                    x          1                +        ⋯        +                  a                      p            n                                    x          n                                              ∼          p                                  c          p                ,            where       ∼    i    ∈  {  ≤  ,  ≥  }. It can be alternatively represented by two finite sets of generators   V  ,  W  ⊆        R    n  :  P  =  conv  (  V  )  +  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       ∼    i   to be from   {  ≥  ,  &amp;gt;  ,  ≤  ,  &amp;lt;  }. Is there some similar representation in terms of generating points for such sets?

Sophia Mcdowell · Accepted Answer

No. Unfortunately, it can&#039;t even be done in the 1D case. For instance, consider the inequalities   x  &amp;gt;  0 and   x  &amp;lt;  1. Then   P is the open interval   (  0  ,  1  ). You can&#039;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 · Accepted Answer

Seems like such polyhedra are called not necessarily closed (NNC) and are usually represented as closed polyhedra with additional dimension   ε: every strict inequality       a          i      1            x    1    +  …  +      a          i      n            x    n    &amp;gt;      c    i   is replaced by       a          i      1            x    1    +  …  +      a          i      n            x    n    −  ε  ≥      c    i   and two additional inequalities   0  ≤  ε  ≤  1 are added to the system. If we call this polyhedron       P    ′  , the desired polyhedron is the set   {  (      x    1    ,  …  ,      x    n    )  ∣  (      x    1    ,  …  ,      x    n    ,  ε  )  ∈      P    ′    ,  ε  &amp;gt;  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  ∈        R    n   i.e. every point can be obtained as      α    1        r    1    +  …  +      α    k        r    k    +      β    1        p    1    +  …  +      β    l        p    l    +      γ    1        c    1    +  …  +      γ    m        p    m    ,where       r    i    ∈  R  ,      p    i    ∈  P  ,      c    i    ∈  C and       α    i    ,      β    i    ,      γ    i    ∈        R    +   and       ∑          i      =      1        l        β    i    +      ∑          i      =      1        m        γ    i    =  1 and there is   1  ≤  i  ≤  l such that       β    i    ≠  0. The trick here is that points in   C don&#039;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.

Convex polyhedron P is a subset of <mi mathvariant="double-struck">R n </msup>

Answered question

Answer & Explanation

New Questions in Algebra I