Convex polyhedron
P
is a subset of
<mi mathvariant="double-struck">R
n
</msup>
Cristopher Knox
Answered question
2022-07-15
Convex polyhedron is a subset of that satisfies system of linear inequalities
where . It can be alternatively represented by two finite sets of generators :
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 to be from . Is there some similar representation in terms of generating points for such sets?
Answer & Explanation
Sophia Mcdowell
Beginner2022-07-16Added 14 answers
No. Unfortunately, it can't even be done in the 1D case. For instance, consider the inequalities and . Then is the open interval . You can't take because then conv is the closed interval . Taking to be any other two points between 0 and 1 would generate a conv that is a strict subset of .
vortoca
Beginner2022-07-17Added 2 answers
Seems like such polyhedra are called not necessarily closed (NNC) and are usually represented as closed polyhedra with additional dimension : every strict inequality is replaced by and two additional inequalities are added to the system. If we call this polyhedron , the desired polyhedron is the set . Such a system of constraints can be converted to representation by generators. Alternatively, they can be characterized directly by three sets of generators i.e. every point can be obtained as
where and and and there is such that . The trick here is that points in 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 with nonzero coefficient. This representation can easily be converted to the one mentioned above.