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

$\endgroup$
5
  • $\begingroup$ Have any references? $\endgroup$
    – Will Jagy
    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
    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
    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
    Jul 9, 2010 at 19:20
  • $\begingroup$ See ljk.imag.fr/membres/Anatoli.Iouditski/cours/convex/cours.pdf p54 $\endgroup$ Nov 23, 2010 at 12:56

1 Answer 1

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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