# faces of a polytope

Let $a_1,a_2,..,a_n\in\mathbb{R}^m$, $n>m$ and the points are in general position meaning, no hyperplane contains more than $m$ points. Define a polyhedron $$P=\{x\in\mathbb{R}^m:a_1'x\leq0, a_2'x\leq0,.., a_k'x\leq0, a_{k+1}'x\leq1,.., a_n'x\leq1\} \; .$$ Notice that $k$ inequalities are with $0$ and $n-k$ inequalities are with $1$. Assume that $k < m$ and $P$ is bounded so that $P$ is a polytope. My question is how do I characterize all the faces of this polytope? Is the information given enough to do that?

More Info: I have a function that I want to optimize but it depends only on certain variables. So I thought, info should help than hinder. Incorporating the info in the problem brings me to the polytope above. Also I don't need all the faces. some face of this polytope whose dimension includes this $k$ some how does the job. What have I tried: Let $$Q=Conv\{a_1, a_2,.., a_n\} \; .$$ The polar of $Q$ turns out to be $$Q^*=\{x\in\mathbb{R}^m:a_1'x\leq1, a_2'x\leq1,.., a_n'x\leq1\} \; .$$ and If $0\in Q$ then $Q^*$ is also a polytope which is also dual to $Q$ and hence faces are related by dual relationship. The polytope $P$ above, is a face of this polar polytope right? If so, then I have to relate an r dimensional face $F$ of $Q$ using duality to a face of some dimensional face of $P$. Don't know from here.

• (@mmaann: I fixed the LaTeX problem.) – Joseph O'Rourke Mar 24 '12 at 15:57
• @Joseph.Thanks for the response and also for your latex tip. May be I was asking too much with little information. I have added more info and also my attempt to the problem. T – mmaann Mar 25 '12 at 4:45
• By setting $k=0$ and choosing the vectors $a'_i$ appropriately, you can obtain any $m$-dimensional convex polytope with this construction. So there's unlikely to be a simple answer. – JeffE Apr 8 '12 at 16:17

This is not an answer, just an example to help visualize the polytope for $m=3$, so in $\mathbb{R}^3$. I used $n=6$ and $k=2$, with $a_1$ and $a_2$ marked in blue, and $\{a_3,a_4,a_5,a_6\}$ in red (the displayed vectors are $10{\times}$-enlarged for clarity). I clipped the display to a $\pm 10$ box. It seems that the combinatorial structure of the polytope depends very much on the $a_i$, so any characterization of its structure must depend on those vectors. The $k$ ${\le} 0$-constraints form a cone of at most $k$ facets at the origin, and the other, ${\le} 1$-constraints clip this cone.