most recent 30 from http://mathoverflow.net 2013-06-19T01:35:22Z http://mathoverflow.net/feeds/question/30976 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30976/condition-number-for-ellipsoid-method-matrix daniel 2010-07-07T23:22:05Z 2010-11-21T16:22:13Z

<p>Hello,</p> <p>When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$.</p> <p>What can you say about the condition number of the ellipsoid? Specifically, a good result would guarantee a slow increase in the condition number (maybe depending on volume decrease).</p> <p>Thanks,</p> <p>Daniel</p>

http://mathoverflow.net/questions/30976/condition-number-for-ellipsoid-method-matrix/45178#45178 Sergey 2010-11-07T15:52:09Z 2010-11-07T15:52:09Z

<p>Hi,</p> <p>As far as I understand your question, a partial answer may be recovered from the Khachiyan's original covergence proof of the ellipsoid algorithm. Namely, Khachiyan used the volume as an intermadiate parameter and expressed it via, what he called, the thickness $r(E)$ that is equal to $\lambda_{min}$ of the current ellipsoid $E$. The following inequality holds $r(E_{next})\geq \frac{d}{d+1} r(E_{previous})$. And $\lambda_{max}$ can be upperbounded by the inequality $\lambda_{max-next}\leq 2^{\frac1{d^2}}\lambda_{max-previous}$. Thus, the condition number increases not faster than $[\frac{d}{d+1} 2^{\frac1{d^2}}]^n$. It seems that you can check this exponential rate in your toy example (just consider the plane case $d=2$ to simplify the computations). By the way, precisely the fact that the ellipsoid algorithm USUALLY operates according to the theoretical estimates is a main reason for claims of it's ``practical'' impracticallity. But it's another story.</p> <p>Sergey</p>