6
$\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

2 Answers 2

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
    Commented Nov 26, 2023 at 18:10
  • $\begingroup$ The first paper gives an indication using cpu time. $\endgroup$
    – Sutanu Majumdar
    Commented Nov 26, 2023 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
    Commented Nov 27, 2023 at 6:49
0
$\begingroup$

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.

Improve this answer
$\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.