Documentation on Markowitz Tolerance, Algorithm, and Citation
Answered
I'm trying to find some documentation on what the Markowitz tolerance is and the algorithm employing the Markowitz tolerance value. I've found the original paper by Markowitz dating back to the 1950s, "The Elimination form of the Inverse and its Application to Linear Programming", which was written on a typewriter. The scanned pages weren't entirely legible, but I didn't see any mention of a tolerance.
The idea of Markowitz is about pivoting to decrease the number of computations in the simplex algorithm, but the tolerance value used by modern solvers appears to go a step further and balances the computational complexity of optimal pivoting with numerical benefits. Other sources I've found imply the tolerance may be controlling the sparsity from pivoting, but I'm not at all certain of that.
I'm sure there's been some in house research on the algorithm using the Markowitz tolerance, but other solvers employ the Markowitz tolerance as well, so I assume there's some underlying academic source explaining what the Markowitz tolerance actually does. Could you please point me to that publication?
-
Hi Mitchal,
Thank you for the question. Since you have a commercial license with us, I will transfer this into a ticket in our Help Center to better help you with the question.
Best regards,
Maliheh
0 -
The paper by Markowitz was published as
Harry M. Markowitz, The Elimination Form of the Inverse and Its Application to Linear Programming. Management Science 3 (1957) 255-269.
The situation in which a tolerance would be needed is described by the author in this passage:
Later the paper proposes a heuristic for dynamically choosing the "agenda" and cites an implementation. There must have been a tolerance used in that implementation, but its role is not mentioned.
Much later, Markowitz's ideas were incorporated into the Harwell sparse matrix package MA28, described in
I.S. Duff and J.K. Reid, Some Design Features of a Sparse Matrix Code. ACM Transactions on Mathematical Software 5 (1979) 18-35.
Here the tolerance appears explicitly as the parameter u in the authors' description:
MA28 was incorporated into some implementations of the simplex method, and the presence of a "Markowitz tolerance" option suggests that Gurobi is using the same ideas.
0
Please sign in to leave a comment.
Comments
2 comments