Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

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}$.

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).

Thanks,

Daniel

share|improve this question
    
Have any references? –  Will Jagy Jul 8 '10 at 3:23
    
Not an explicit reference. But I can try and make the problem clearer. First an ellipsoid can be defined as: $ E = \{ x | (x-c)^{T} S^{-1} (x-c) < 1 \} $ with $c$ the center and $S$ a positive semi-definite matrix. The condition number of $S$ can be given as $\lambda_{max}/\lambda_{min}$. It is an expression of how elongated the ellipsoid is. Furthermore, in the ellipsoid algorithm, the ellipsoid is updated every iteration to a new one covering the intersection of the old ellipsoid with a half plane (to keep things simple, let us assume the half-plane goes through the center $c$). –  daniel Jul 8 '10 at 11:40
    
See sma.epfl.ch/~eisenbra/OptInFinance/Slides/ellipsoid.pdf and references at the end. Be careful about the phrase "condition number," Renegar defined a separate meaning. But I am not seeing anything myself on the eccentricity for the ellipsoids. –  Will Jagy Jul 9 '10 at 1:23
    
I've had a look at the reference (will have to dig deeper though). Since I am looking for a worst-case bound, a specific run would provide a lower bound for the worst-case. Intuitively, I think the case which cuts the ellipsoid in the same direction each iteration, will increase condition number maximally. Starting from a ball, this produces a single sequence of ellipses, with exponentially rising condition number (but a smaller exponent than the one controlling volume). Again, no calculation, just intuitive guessing. –  daniel Jul 9 '10 at 19:20
    
add comment

1 Answer

Hi,

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.

Sergey

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.