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.
What classes of mathematical programs can be solved exactly or approximately, in polynomial time?
ds.algorithms;optimization;linear programming;semidefinite programming;polynomial time