The unhelpful suggestion is to perform the complete dual cone calculation (using available software) and then see if the answer matches your initial guess. Unfortunately, my pessimistic intuition is that in the general case, you cannot expect to do much better than this, even in the case where the initial guess is correct. You might get lucky optimizing in random directions in the dual space and find a hyperplane you missed, but in high dimensions there are too many directions and things are just subtle and elusive.
Three things that make the problem easier:
- If the polytope P is known to be simple,
- if the intersection of half-spaces Q is known to be simplicial, or
- if the dimension is small.
The first case was covered by the answer given by Hugh Thomas: just verify that each vertex is a vertex of Q. In the second case the same verification suffices by duality, where the roles of facet-defining hyperplanes and extreme points (genuine vertices) are exchanged. In the third case you can construct the entire face lattice inductively. The hard case is when the dimension is high, which means that even if there are relatively few vertices and facets, the number of intermediate faces can be unmanageable.
Unfortunately it is not even easy in general to verify whether one of the first two conditions holds. An instructive example is the case where Q is a cube and P is obtained by deleting a pair of opposite vertices from Q (giving a flattened octahedron). In this case every vertex of P is a vertex of Q, every facet of Q restricts to a facet of P, P looks simple when checked by Q, and Q looks simplicial when checked by P, but they are not equal, P is not simple, and Q is not simplicial. (Fortunately, the dimension is low!)
Having expressed pessimism about there being any good solution, let me at least offer a bad onelikely to run much too slowly on any interesting examplethat essentially does construct the face lattice (inefficiently) as suggested for low dimensions. We assume that it has already been verified (not difficult) that every vertex defining P does lie within Q (and therefore that every hyperplane defining Q lies outside the interior of P) but for the purposes of induction we will not insist that every every "vertex" is an extreme point of P or that every hyperplane gives a facet of Q; when we encounter such redundancies we will silently discard them for the purposes of that stage of the algorithm. (On the other hand, we do require that vertices are distinct and hyperplanes are distinct, and we delete repetitions before doing anything else.) What we will verify instead is that every vertex of Q is in the list for P, and that every facet of P comes from the list of hyperplanes for Q. If that ever fails, we report it and quit.
Firstly, every polygon is both simple and simplicial, which makes the case of two dimensions easy: Recursively eliminate any vertex of P that does not lie on two lines of Q, or any line of Q that does not contain two vertices of P. If anything is left when you are done (again, assuming P was contained in Q), they were always equal.
Now, suppose you have a solution in dimension d with which you are happy. In dimension
$d+1$, you do as follows: For each hyperplane H in turn, identify the set of vertices incident to it, and verify that they span it affinely. (Otherwise H is redundant, so just continue on to the next hyperplane.) The convex hull of these vertices defines a polytope P' of dimension d within H, and the (largely redundant) intersection of all other halfspaces with H defines a polytope Q' which contains P'. The polytopes P and Q are equal if and only if P' and Q' are equal for every non-redundant hyperplane H.
Lather, rinse, repeat.