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
    Commented 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
    Commented Mar 25, 2012 at 3:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .