5
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But what is the runtime complexity of the ellipsoid method in this case? $\endgroup$
    – Erel Segal-Halevi
    Nov 26 at 18:10
  • $\begingroup$ The first paper gives an indication using cpu time. $\endgroup$
    – Sutanu Majumdar
    Nov 26 at 19:27
  • $\begingroup$ I read the first paper. They report cpu time in simulation experiments, but do not provide a theoretic guarantee for the run-time $\endgroup$
    – Erel Segal-Halevi
    Nov 27 at 6:49

Your Answer

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

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