5

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.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
gmn
  • 666
  • 4
  • 10
  • 1
    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. – ErlingMOSEK Mar 11 '22 at 07:17
  • @ErlingMOSEK Yeah, that Copositive Programming is funky stuff . 2011 book chapter on Copositive Programming by Sam Burer https://sburer.github.io/papers/033-cpchap.pdf in https://link.springer.com/chapter/10.1007/978-1-4614-0769-0_8 – Mark L. Stone Nov 20 '23 at 17:27

1 Answers1

0

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.

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11