Computing the dual of a polytope

Questions and problems about using polymake go here.
Phillip
Posts: 2
Joined: 21 Nov 2013, 14:43

Computing the dual of a polytope

Postby Phillip » 21 Nov 2013, 14:49

Dear Polymake Community,

I just started using polymake. Thank you very much to the creators. It is a great tool.

I have a problem with calculating the dual of polytopes. Am I right that you do this with polarize()?

Please take a look at the attached PDF file. In this example I have used polarize(). From my understanding the result is not the dual though.

What's wrong? My understanding or the function that I use.

Thank you in advance,
Phillip
Attachments

[The extension pdf has been deactivated and can no longer be displayed.]


herr
Developer
Posts: 40
Joined: 30 Dec 2010, 13:15

Re: Computing the dual of a polytope

Postby herr » 21 Nov 2013, 16:38

Dear Phillip,

thanks for the nice description of your example. You've chosen the correct function polarize() for the task, and the result is consistent with the definition of the polarized polytope used in polymake. A polytope P in polymake is of the form
P = {x|b + Ax >= 0}
The polarized polytope (of a polytope P which contains 0) is given by
{y| <y,u> >= -1 for all u in P}
which is equal to
{y| <y,v> >= -1 for all vertices v of P}.
If you compare the vertices of your original polytope $p1 with the facets of the polarized polytope $p1Pol, you see that the entries coincide, just as required by the definition.

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Computing the dual of a polytope

Postby gawrilow » 21 Nov 2013, 18:35

A small side remark: you don't need to `prime' the variable p1Pol with an empty Polytope, when you are anyway going to overwrite it in the next line. polymake is based on perl, and like many other scripting languages, its variables are dynamically typed.

Phillip
Posts: 2
Joined: 21 Nov 2013, 14:43

Re: Computing the dual of a polytope

Postby Phillip » 21 Nov 2013, 21:33

Dear all,

Thank you very much for your quick responses.
For a polytope P with vertices V = {v1, v2, ..., vn}, the set
a) {y | <y,v> >= -1 for all vertices v of P}
is different from the set
b) {y | <y,v> <= 1 for all vertices v of P}.

I thought b) is the definition of a polar set. That's what I can read in Ziegler's Lectures on Polytopes section 2.3.
Did I miss something? What is the reason for the use of a) in polymake?

Again thank you very much!
Phillip

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: Computing the dual of a polytope

Postby paffenholz » 22 Nov 2013, 00:14

One is just the negative of the other, so up to a reflection the two definitions produce the same set.

Ziegler also defines a polytope as the set of all x such that Ax<=b for some matrix A and right hand side b. polymake uses 0\le b+Ax. Again, that just differs by a reflection in the origin. For both definitions you will find many books using them. Mathematically this is just a matter of taste (but you should be ocnsistent, if you use Ziegler's definition for a polytope, you should also use his definition of the polar, and vice versa).

For polymake there is actually a reason to use the definition it uses. polymake doesn't really work with polytopes, it operates on the homogenization cone of the polytope, i.e. if your polytope is the convex hull of v1, ..., vk, then polymake looks at the cone spanned by (1,v1), ..., (1,vk). See here. In our representation, if 0<= b+Ax is an exterior description of your polytope, then 0<=bx0+Ax is one for the homogenization of P (in coordinates (x0,x). This makes the transfer fomr polytope to cone quite convenient.

Also, with our representation, if 0<=b_i+<a_i,x> is a facet defining inequality of P, then 1/b_i*a_i is the corresponding vertex of the polar, and if v_i is a vertex of P, then 0<=1+<v_i,x> is the corresponding facet of the polar. Thus, polarization in polymake is easy: Just exchange the matrices stored in FACETS and VERTICES (and scale each row such that the first entry is 1).

Hope that clarifies this. Feel free to ask again if not...
Andreas

lbossing

Re: Computing the dual of a polytope

Postby lbossing » 16 Sep 2016, 09:53

Hi,

I have a question related to this discussion, so I will post it here. I am computing polytopes and their polar dual in polymake, but while doing so I recognized that the polar dual of a bounded polytope is not bounded (in general). I thought however, that this is true, i.e. the polar dual of a bounded polyhedron is a bounded polyhedron. Where am I wrong?

In my particular case, I have two cones that are polar dual to each other. I cut out a polytope of each and expect that these polytopes are dual. Unfortunately I fail in confirming this so far.

Thanks a lot in advance!
Lara

User avatar
joswig
Main Author
Posts: 280
Joined: 24 Dec 2010, 11:10

Re: Computing the dual of a polytope

Postby joswig » 18 Sep 2016, 14:12

I have a question related to this discussion, so I will post it here. I am computing polytopes and their polar dual in polymake, but while doing so I recognized that the polar dual of a bounded polytope is not bounded (in general). I thought however, that this is true, i.e. the polar dual of a bounded polyhedron is a bounded polyhedron. Where am I wrong?
This is not a polymake but a math question. Essentially, everything has already been explained in the posts above. Let me answer nonetheless.

The polar dual of a polytope is a polytope if and only if the polytope is full-dimensional and the origin is an interior point. If you want to see polytope duality as a a special case of cone duality as you are alluding to above, you need to make sure that the point (1,0,0,...,0) is an interior point of your cone. At least this is the case if the homogenization is chosen as in polymake. Notice that there is no canonical choice here.

If it is only about the combinatorics you can always translate such that the origin becomes a (relatively) interior point. In the literature there is sometimes the distinction between "polar dual" and "dual" where the latter refers to something which is only defined up to (depending on the context) projective or even combinatorial equivalence. In this less restricted sense the "dual" of a polytope is always a polytope (with the face lattice reversed).

Here is an example, how to deal with this in polymake. We produce a 3-dimensional cube with 0/1-coordinates. Clearly the origin is not an interior point. Hence the polar dual is not a polytope.

Code: Select all

> $c=cube(3,0); > print polarize($c)->BOUNDED;
Now, if you are only interested in the combinatorics, the following gives you, e.g., the f-vector of the dual (which is an octahedron):

Code: Select all

> print polarize($c,no_coordinates=>1)->F_VECTOR; 6 12 8
Yet, this comes without coordinates (as that option tells), which is why the following fails

Code: Select all

> print polarize($c,no_coordinates=>1)->BOUNDED; polymake: WARNING: available properties insufficient to compute 'BOUNDED'
Combinatorially, polymake only knows about polytopes. If you have an unbounded polyhedron the combinatorics is determined by the quotient modulo the lineality space, which is always a pointed polyhedron. This is projectively equivalent to a polytope with a marked face (which gathers the vertices at infinity). See also https://polymake.org/doku.php/tutorial/ ... _semantics.


Return to “Helpdesk”