In the Ellipsoid method wikipedia entry under the performance section, it is mentioned that the Ellipsoid method often times is numerically unstable in practice: "On even "small"-sized problems, it suffers from numerical instability and poor performance in practice". I am wondering if there are any theoretical justifications of this? I implemented the algorithm just for fun, and it seems to perform fine on even "large" instances that I threw at it.

Of course I understand that it is not as fast as interior-point algorithms in practice, but I read from many sources about the "numerical instability" of the Ellipsoid algorithm, so I am a bit confused about the difference between what I am observing in my code and the consensus of instability. In addition, the Ellipsoid method is very useful when you have an exponential number of constraints, but a polynomial time separability oracle, which is something practical solvers cannot deal with in practice but which the Ellipsoid method can.

Is there any theoretical justification on why, and when, it is numerically unstable?



Your Answer

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

Browse other questions tagged or ask your own question.