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.

  • $\begingroup$ (@mmaann: I fixed the LaTeX problem.) $\endgroup$ – Joseph O'Rourke Mar 24 '12 at 15:57
  • $\begingroup$ @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 $\endgroup$ – mmaann Mar 25 '12 at 4:45
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ It seems to me that both the question and the answer are pretty vague. $\endgroup$ – John Jiang Mar 25 '12 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.