2
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2012 at 16:17

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ It seems to me that both the question and the answer are pretty vague. $\endgroup$
    – John Jiang
    Mar 25, 2012 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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