31
$\begingroup$

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The continuous optimization community seems to claim that all convex programs can be solved efficiently, but I believe their definition of "efficient" does not coincide with the TCS definition.

This question has been bothering me a lot in the last few years, and I can not seem to find a clear answer to it. I hope you could help me settle this once and for all: Which classes of MPs can be solved exactly in polynomial time, and by which means; and what is known about approximating the optimal solution of MPs that we can not solve exactly in polynomial time?

Below, I give an incomplete answer to this question that is also possibly incorrect at some places, so I hope you could verify and correct me at the points where I'm wrong. It also states some questions that I cannot answer.

We all know that linear programming can be solved exactly in polynomial time, by running the ellipsoid method or an interior point method, and subsequently running some rounding procedure. Linear programming can even be solved in time polynomial in the number of variables when facing a family of LPs with any super large amount of linear constraints, as long as one can provide a "separation oracle" for it: an algoritm that, given a point, either determines whether that point is feasible or outputs a hyperplane that separates the point from the polyhedron of feasible points. Similarly, linear programming in time polynomial in the number of constraints when facing a family of LPs with any super large amount of variables, if one provides a separation algorithm for the duals of these LPs.

The ellipsoid method is also able to solve quadratic programs in polynomial time, in case the matrix in the objective function is positive (semi?)definite. I suspect that, by using the separation oracle trick, we can in some cases also do this if we are dealing with an incredible number of constraints. Is that true?

Lately semidefinite programming (SDP) has gained a lot of popularity in the TCS community. One can solve them up to arbitrary precision by using interior point methods, or the ellipsoid method. I think, SDPs cannot be solved exactly due to the problem that square roots can not be computed exactly. (?) Would it then be correct if I say there is an FPTAS for SDP? I have not seen that stated anywhere, so that's probably not right. But why?

We can solve LPs exactly and SDPs up to arbitrary precision. What about other classes of conic programs? Can we solve second-order cone programs up to arbitrary precision, using the ellipsoid method? I don't know.

On which classes of MPs can we use the ellipsoid method? What properties does such an MP need to satisfy such that an answer can be given up to arbitrary precision, and what additional properties do we need in order to be able to obtain an exact solution in polynomial time? Same questions for interior point methods.

Oh, and finally, what is it that causes continuous optimizers to say that convex programs can be solved efficiently? Is it true that an arbitrary-precision answer to a convex program can be found in polynomial time? I believe not, so in what aspects does their definition of "efficient" differ from ours?

Any contribution is appreciated! Thanks in advance.

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ The title of this question is much too broad; it seems that what you really want to know is whether convex programs can really be solved in polynomial time. $\endgroup$
    – Peter Shor
    Commented Jun 1, 2011 at 15:00
  • $\begingroup$ Seconded. Bart, maybe you can break things down into specific questions ? $\endgroup$
    – Suresh Venkat
    Commented Jun 1, 2011 at 22:43
  • $\begingroup$ Peter and Suresh, thanks for these suggestions. From what I wrote it is supposed to follow that I am not only interested in the question of whether convex programs can be solved or approximated in poly-time. I am basically interested in the limits of the ellipsoid and interior point methods, and I'm hoping that someone knows on precisely which classes of MPs they work efficiently. I ask this because the current body of literature on it is not clear about this (to me). $\endgroup$
    – Bart
    Commented Jun 2, 2011 at 9:20
  • $\begingroup$ Personally, I think it would be good to have a nice overview of this on one place (like as an answer to this stackexchange question). Also to me this is seems like quite a coherent question. However, as I'm new to stackexchannge, I am not familiar with the culture and ethics here.. so in case you insist, I will try to find out how to split this question up into multiple smaller questions. $\endgroup$
    – Bart
    Commented Jun 2, 2011 at 9:26
  • 1
    $\begingroup$ I think the scope of this question is much too broad to have an answer. The limits of the ellipsoid and interior point methods would be a good question, and what can be done for convex programs is a good question, but if you don't specify the type of algorithm or the type of program, you're basically asking for a summary of the entire field of continuous optimization in your answer, and this is pretty much impossible. It's not a small field. However, if you leave your question as it is, it's quite possible you'll get another good partial answer. $\endgroup$
    – Peter Shor
    Commented Jun 2, 2011 at 23:33

2 Answers 2

Reset to default
18
$\begingroup$

I can answer this part:

Would it then be correct if I say there is an FPTAS for SDP? I have not seen that stated anywhere, so that's probably not right. But why?

The statement is correct, but we do not often see it because a stronger statement holds and is more important than this weaker statement.

An FPTAS is a polynomial-time algorithm which, given a problem and an accuracy parameter 1k, outputs a (1+1/k)-approximate solution.

But for SDP, the ellipsoid method and the interior-point method provide polynomial-time algorithms which, given a problem and an accuracy parameter 1k, output a (1+2−k)-approximate solution. Note that the approximation factor is much better than what is required for an FPTAS.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ This needs some more care since the ellipsoid method and the interior-point methods need additional conditions to run in polynomial time. $\endgroup$
    – Yoshio Okamoto
    Commented Jun 2, 2011 at 4:12
  • $\begingroup$ Thanks for this, Tsuyoshi! Yoshio, could you clarify what you mean by this? Do you really mean that there are conditions on the particular SDP needed, because otherwise the SDP cannot be approximated like that in poly-time? This is a surprise to me in that case, and I would be interested in knowing about these conditions. Thanks. $\endgroup$
    – Bart
    Commented Jun 2, 2011 at 9:41
  • $\begingroup$ @Bart: For example, if you look at lecture notes by Lovasz cs.elte.hu/~lovasz/semidef.ps, you can find Theorem 3.7 (Page 19) talks about the running-time bound of the ellipsoid method for convex minimization. There, some technical assumptions are imposed. $\endgroup$
    – Yoshio Okamoto
    Commented Jun 3, 2011 at 13:24
  • 4
    $\begingroup$ @Bart: do look at the notes which are very nice, but just to put it here as well: the conditions are basically that the feasible region contains a ball of radius $r$, is contained in a ball of radius $R$, and $\log R/r$ is polynomially bounded. Together with a weak separation oracle those conditions give a polytime algorithm for any convex program (via the ellipsoid method) $\endgroup$
    – Sasho Nikolov
    Commented Jun 3, 2011 at 20:31
  • $\begingroup$ Thanks a lot for this. This answers a very big portion of my question. It seems like this knowledge can be a very useful tool to theoretical computer scientists, while still it seems to me that it is not well-known at all, and stated almost nowhere. Weird. $\endgroup$
    – Bart
    Commented Jun 6, 2011 at 9:43
5
$\begingroup$

I don't know if all convex problems are in P, but I can answer a related question: nonconvex optimization is NP-hard. See "Quadratic programming with one negative eigenvalue is NP-hard".

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.