Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a polytope given by some equalities and inequalities, how can I get all the vertices of the polytope? If there's a way to deal with the one given by inequalities only, how can I reduce the equalities and inequalities to inequalities only?

--Updated 2013.12.11--

m=SparseArray[Automatic,{28,56},0,{1,{{0,6,12,18,24,39,50,61,67,73,79,94,105,116,122,128,143,154,165,185,205,234,257,268,279,302,313,324,335},{{1},{2},{3},{4},{5},{6},{1},{7},{8},{9},{10},{11},{2},{7},{12},{13},{14},{15},{3},{8},{12},{16},{17},{18},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{13},{14},{16},{17},{19},{1},{2},{3},{5},{7},{8},{10},{12},{14},{17},{20},{1},{2},{3},{4},{7},{8},{9},{12},{13},{16},{21},{1},{22},{23},{24},{25},{26},{2},{22},{27},{28},{29},{30},{3},{23},{27},{31},{32},{33},{1},{2},{3},{4},{5},{22},{23},{24},{25},{27},{28},{29},{31},{32},{34},{1},{2},{3},{5},{22},{23},{25},{27},{29},{32},{35},{1},{2},{3},{4},{22},{23},{24},{27},{28},{31},{36},{7},{22},{37},{38},{39},{40},{8},{23},{37},{41},{42},{43},{1},{7},{8},{9},{10},{22},{23},{24},{25},{37},{38},{39},{41},{42},{44},{1},{7},{8},{10},{22},{23},{25},{37},{39},{42},{45},{1},{7},{8},{9},{22},{23},{24},{37},{38},{41},{46},{1},{2},{3},{4},{7},{8},{9},{12},{13},{16},{22},{23},{24},{27},{28},{31},{37},{38},{41},{47},{1},{2},{3},{5},{7},{8},{10},{12},{14},{17},{22},{23},{25},{27},{29},{32},{37},{39},{42},{48},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{13},{14},{16},{17},{22},{23},{24},{25},{27},{28},{29},{31},{32},{37},{38},{39},{41},{42},{49},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{16},{17},{22},{23},{24},{25},{27},{31},{32},{37},{41},{42},{50},{1},{3},{5},{8},{10},{17},{23},{25},{32},{42},{51},{1},{3},{4},{8},{9},{16},{23},{24},{31},{41},{52},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{13},{14},{22},{23},{24},{25},{27},{28},{29},{37},{38},{39},{53},{1},{2},{5},{7},{10},{14},{22},{25},{29},{39},{54},{1},{2},{4},{7},{9},{13},{22},{24},{28},{38},{55},{1},{2},{3},{7},{8},{12},{22},{23},{27},{37},{56}}},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-2,-2,-2,-1,-1,-2,-2,-1,-1,-1,-1,-1,-1,-1,-2,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-2,-1,-2,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-2,-2,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}]; b={-(2/7),-(2/7),-(2/7),-(2/7),-(5/7),3/7,3/7,-(2/7),-(2/7),-(2/7),-(5/7),3/7,3/7,-(2/7),-(2/7),-(5/7),3/7,3/7,-(20/21),-(20/21),34/21,25/21,-(11/21),-(11/21),25/21,-(11/21),-(11/21),-(11/21)};

The equalities are m.x==b and the inequalities are x>=0

share|improve this question
1  
Wikipedia article: Vertex enumeration problem. MATLAB code that purports to solve the problem: Representing Polyhedral Convex Hulls by Vertices or (In)Equalities. –  Rahul Dec 7 '13 at 8:23
    
a little related plot the boundaries of piecewise function –  Kuba Dec 7 '13 at 9:18
    
Please post one example of such a polytope (defined by both equalities and inequalities) so we can work on some real object. –  belisarius Dec 7 '13 at 19:46
    
Related, but only inequalities and convex polytopes: stackoverflow.com/questions/3815496/… –  belisarius Dec 7 '13 at 19:50
    
You can use the equalities to eliminate variables. Then you are left with just inequalities, in fewer variables. –  Daniel Lichtblau Dec 7 '13 at 21:01

1 Answer 1

To put Daniel's comment into code:

x = Array[C, Length@First@m];
constr = First@Solve[m.x == b]
(*
  {C[6] -> -(2/7) - C[1] - C[2] - C[3] - C[4] - C[5], <<26>>,
   C[56] -> -(11/21)-C[1]-C[2]-C[3]-C[7]-C[8]-C[12]-C[22]-C[23]-C[27]-C[37]}
*)

Reduce[Thread[x >= 0] /. constr, Variables[x /. constr]]
(*  False  *)

Easy, fast, and disappointing. The polytope is an empty set.

The closest point to the origin consists of the vector with coordinates all equal to -1/21:

PseudoInverse[m].b
(*  {-(1/21), -(1/21), <<25>>, -(1/21)}  *)

This vector is normal to the affine subspace m.x == b, so the subspace does not intersect the positive orthant.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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