# Complexity of the ellipsoid method in general convex problems

The ellipsoid method is often mentioned in relation to the complexity of solving linear programs. Is the method however polynomial in the general non-linear convex cases? Preferably I would like a reference to a work stating the complexity of the method in such cases.

Note: I had a look at this question, but could not find what I am looking for.

• Not all convex problems can be solved in polynomial time to best of my knowledge. I mean there can be a convex function that cannot be evaluated in polynomial time. See also co-positive programming. Mar 11, 2022 at 7:17
• @ErlingMOSEK Yeah, that Copositive Programming is funky stuff . 2011 book chapter on Copositive Programming by Sam Burer sburer.github.io/papers/033-cpchap.pdf in link.springer.com/chapter/10.1007/978-1-4614-0769-0_8 Nov 20, 2023 at 17:27

The following links refers to application of ellipsoidal algorithms with some variations to NLPs:

Paper by Drs. Rugenstein. E & Kupferschimd.M: presents results showing convergence by ellipsoidal algorithm to convex NLPs

Lecture notes from Univ of British Columbia: application of ellipsoids with separation Oracle method for nonlinear objective

Also helpful lecture notes from Georgia Tech: discussion on Dr. N.Karmakar's interior points methods.

• But what is the runtime complexity of the ellipsoid method in this case? Nov 26, 2023 at 18:10
• The first paper gives an indication using cpu time. Nov 26, 2023 at 19:27
• I read the first paper. They report cpu time in simulation experiments, but do not provide a theoretic guarantee for the run-time Nov 27, 2023 at 6:49

The original paper by Khachiyan (1980) talks about the application to other classes of convex problems in the conclusion. The author discusses:

1. Localization of the solutions,
2. measure of incompatibility, and
3. polynomial computability of functions and gradients. (like ErlingMOSEK mentions in the comments)

A more practical reference is perhaps Grötschel, Lovász, and Schrijver (1981). Here the authors seem to prove that there exists a polynomial algorithm to solve the convex problem, if and only if the separation problem can be solved in polynomial time.