2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Have any references? $\endgroup$
    – Will Jagy
    Commented Jul 8, 2010 at 3:23
  • $\begingroup$ 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$). $\endgroup$
    – daniel
    Commented Jul 8, 2010 at 11:40
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Jul 9, 2010 at 1:23
  • $\begingroup$ 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. $\endgroup$
    – daniel
    Commented Jul 9, 2010 at 19:20
  • $\begingroup$ See ljk.imag.fr/membres/Anatoli.Iouditski/cours/convex/cours.pdf p54 $\endgroup$
    – robin girard
    Commented Nov 23, 2010 at 12:56

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .