Hi,

...

Thanks Le Verge's paper and other goodies arrived this morning.

[...]

I have had a look through the papers you sent although I have not read them all carefully...

Let me know if there is something I should look at and comment on today...

-----------------------------------------------------------------

Previously, the meaning of the word "stable" on page 9 of LeVerge was in question. I found a definition of this in a book I borrowed from the library by Christopher Witzgall "Convexity and Optimization in Finite Dimensions" BUT I haven't managed to work out what "stable" really means! The book says (page 187/8):

"We call the point X_0 \in K(f) stable if every linear (nonvertical) manifold N in R^{n+1} lying below [f] and satisfying X_0 \in \pi(N) can be separated from [f] by a nonvertical plane

E:= {(X,z) | Y^T X - z = b} in R^{n+1}:

Y^T X_1 - z_1 \leq b \leq Y^T X_2 - z_2 for all (X_1,z_1) \in [f], (X_2,z_2) \in N."

(X,z) is my ascii representation for the column vector X z Also it says that "\pi is a projection from R^{n+1} to R^n in the direction of the z-axes" "f" is a convex function and "K(f) denotes the domain of finiteness of f: K(f) := {X | f(X) < +\infty}." I'm afraid that "lying below" has another complicated definition. The definition relies on lots of other definitions (eg [f] denotes an "epigraph") and the book is not easy to read.

(The author thinks all this is easy... eg "As is easily seen every linear manifold N covering M and lying below [f] is nonvertical.")

I need help here... The stability concept was first invented by R T Rockafellar in 1963. It may be best to see how he explains it. Does anyone feels up to rewriting a specialised version of this definition just for its application to rational polyhedra?

-----------------------------------------------------------------

In our devref.tex file it says:

- The dimension of the \f$\mathop{\mathrm{lin. space}}\f$ is the number of irredundant lines.

I still do not like talking about individual lines being "irredundant". I think it only has meaning in terms of an "irredundant set" Meaning that no vector can be removed without changing the system it is generating. I think that something like

- The dimension of the \f$\mathop{\mathrm{lin. space}}\f$ is the rank of any set of lines that span the space.

would be better.

-------------------------

Unfortunately (or fortunately, I don't know!) my work here is almost finished. I mean that from Monday I will not work for University of Parma.

Sorry you are going! But all the best for the future.

However I will read my mail every day and I will happy to help anyone of you!

I miss you much!

Do keep in touch and tell us of all your adventures in the outside/real world.

ciao, Pat

Hi Angela,

I think that it need to add the notion of duality in the initial page of the documentation, but I only find this definition for polytope (Wilde - A library for doing polyhedra operations - publication interne 785 - december 1993 - page 12). Can we use the same definition for general polyhedra, too?

I have been looking at the definition in Wilde for dual. Comparing this with the definition of a polar, makes me think that what we want is to talk about a polar (also defined by Wilde) rather than a dual. When the polyhedra is a polytope that includes the origin, then it is likely that a polar and a dual (wrt LP) are the same thing. I'm not certain. However, if we want to generalise to any polyhedra, the polar seems what we want. It is also clearly defined and illustrated in the text books.

Looking in Schrijver (do you have a copy of this book?) chapter 9, page 112/3, if P* is a polar of a polyhedron P, then the face-lattice of P* is the reverse of the face-lattice of P.

Also, If C \sseq R^n is a polyhedral cone, then the polar C* is also a polyhedra cone in R^n such that there is a 1-1 correspondence between the faces of C and C* In this case, a face of dimension k in C is mapped to a face in C* of dimension n-k. This means that there is a correspondence between the extreme rays of P with the facets of P* and vice-versa.

In Nemhauser, page 99, there is a theorem 5.2 that says that if the dimension of P = {x | Ax =< b} is n and rank of A is n and pi \in R^n not= 0, then (pi,pi_0) is an extreme ray of P* iff (pi,pi_0) defines a facet of P.

Also, that if P is a full-dimensional polytope, then after normalising, P* is also a full-dimensional polytope. There is a nice illustration on page 102 of two such polytopes.

[...]

...

Does anyone feels up to rewriting a specialised version of this definition just for its application to rational polyhedra?

??? I can't answer this question for two reasons:

• first I have not clear the meaning of "feels up" (sorry!)
• moreover I don't understand what does it means that a ray is stable (even

it seems to be very easy! ;-))

Sorry, I should be more careful in using colloquial expressions... "feels up to" means (approximately) "is able to" but it also implies that the task is hard and you may not want to... I am sure it is hard - but maybe one of you young mathematicians can show us an easy way to understand this - just in the context of polyhedra.

ciao, Pat

Hi,

I'm a bit confused, maybe because I never think carefully enough about use of duality in PPL. I can tell you what we do in the implementation: do you help me to decide what we need?

Several function in the PPL are used both to work on constraints and generators without any difference (look, for example, at conversion.cc) and we justify this with duality. In other words we treat lines like equalities and rays like inequalities. I think this is allowed for double representation and duality, but I can't put these things together. Can you help me?

The concept of "dual" has a generic meaning and of course, there is a kind of duality between the two representations. But, in LP, the term "dual" has a very specific meaning converting between a max and a min computation. This does not seem to correspond exactly to the implicit duality observed in the DD method. I think it only corresponds when we have a polytope that includes the origin. I think I have read that somewhere. (Also, it is clear that a polytope always has a finite max and a min but a cone does not.)

In the paper by Fukuda and Prodin you sent me, page 2, (A,R) is a DD pair iff (R^T,A^T) is a DD pair. So, of course, the same algorithms can be used to go from A to R and from R^T to A^T.

However, if (A,R) is a DD pair, this is not saying that P(A) is a dual of P(R).

...

...

• first I have not clear the meaning of "feels up" (sorry!)
• moreover I don't understand what does it means that a ray is stable (even

it seems to be very easy! ;-))

Sorry, I should be more careful in using colloquial expressions... "feels up to" means (approximately) "is able to" but it also implies that the task is hard and you may not want to... I am sure it is hard - but maybe one of you young mathematicians can show us an easy way to understand this - just in the context of polyhedra.

Well, in italian we say:"Posso parlare solo per me stessa"... in english maybe:"I'm sure I'm not able to..., but maybe the others guys do!".

Esattamente ;)

If you have an idea of how it can be done, please let me know it. I will think about it and I will try to improve the documentation.

I will check the actual documentation and see if I can be of more direct help.

ciao, Pat

...

I will check the actual documentation and see if I can be of more direct help.

Angela,

In conversion.cc, it says

\param source The matrix to convert: it may will be modified. \param start The index of \p source row from which conversion begin. \param dest The result of the conversion. \param sat The matrix that tell us which lines of \p source is saturated (or is only satisfied) by which lines of \p dest. \param num_lines_or_equalities The number of lines of the polyhedron or the number of equality constraints in given \p dest matrix. \return The number of lines of the polyhedron or the number of equality constraints in the result of conversion.

I have tried to simplify this, but am not sure if there is a bug or just that I do not understand this yet. In num_lines_or_equalities, it says this is for the dest matrix. I would expect it to be the source matrix as you also give this value as the result returned. This is my modified description for conversion.cc parameters, It assumes that the 5th argument is intended to be wrt the source matrix and not the dest,

\param source The matrix to convert: it may be modified. \param start The index of \p source row where the conversion begins. \param dest The result of the conversion. \param sat The saturation matrix between \p source and \p dest. \param num_lines_or_equalities The number of lines or the number of equality constraints in the given \p source matrix. \return The number of lines or the number of equality constraints in the computed \p dest matrix.

I will look at the description next.

ciao, Pat