Documentation on Markowitz Tolerance, Algorithm, and Citation

回答済み

Mitchal Dichter

2023年04月21日 18:30

• 
• 

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?

関連

• Parameters
• Attribute

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:44

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Maliheh Aramon

  • Gurobi Staff

  2023年04月21日 22:30

  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
• 

  Robert Fourer

  2023年04月22日 15:34

  • 
  • 

  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

投稿コメントは受け付けていません。