Can all convex optimization problems be solved in polynomial time using interior-point algorithms?

No, this is not true (unless P=NP). There are examples of convex optimization problems which are NP-hard. Several NP-hard combinatorial optimization problems can be encoded as convex optimization problems over cones of co-positive (or completely positive) matrices. See e.g. "Approximation of the stability number of a graph via copositive programming", SIAM J. Opt. 12(2002) 875-892 (which I wrote jointly with Etienne de Klerk).

Moreover, even for semidefinite programming problems (SDP) in its general setting (without extra assumptions like strict complementarity) no polynomial-time algorithms are known, and there are examples of SDPs for which every solution needs exponential space. See Leonid Khachiyan, Lorant Porkolab. "Computing Integral Points in Convex Semi-algebraic Sets". FOCS 1997: 162-171 and Leonid Khachiyan, Lorant Porkolab "Integer Optimization on Convex Semialgebraic Sets". Discrete & Computational Geometry 23(2): 207-224 (2000).

M.Ramana in "An Exact duality Theory for Semidefinite Programming and its Complexity Implications" Mathematical Programming, 77(1995) shows that SDP lies either in the intersection of NP and co-NP, or outside the union of NP and coNP, and nothing better than this is known.

In "Semidefinite programming and arithmetic circuit evaluation" Discrete Applied Mathematics, 156(2008) Sergey P. Tarasov and Mikhail N. Vyalyi show that SDP can be used to compare numbers represented by arithmetic circuits. (The latter is regarded as one of hard problems).


As mentioned by another poster, the work of Nesterov and Nemirovski summarized in Interior-Point Polynomial Algorithms in Convex Programming showed that many convex optimization problems (including linear programming (LP), second order cone programming (SOCP) and semidefinite programming (SDP) problems) can be solved in polynomial time by interior point methods. These methods are hugely important both in theory and in practice.

An earlier approach that is equally important in its theoretical consequences was the work in the 1980's on the ellipsoid algorithm. Khachian showed that the ellipsoid algorithm can solve linear programming problems in polynomial time. Later, Groetschel, Lovasz, and Schrijver showed that the ellipsoid algorithm could also be applied to certain combinatorial optimization problems and proved the polynomial equivalence of separation and optimization. This work appears in their book, Geometric Algorithms and Combinatorial Optimization. Although the ellipsoid method was very important from a theoretical point of view it isn't useful in practice.

The phrase "convex optimization" is often used by authors to refer to the class of convex optimization problems that can be formulated as conic form LP, SOCP, or SDP problems. It isn't strictly true that all optimization problems involving the minimization of a convex objective function over a convex feasible set can be formulated as LP, SOCP, or SDP problems. You can even imagine mathematical instances of convex optimization problems for which there is no reasonably structured problem representation that you could use in saying "I have a polynomial time algorithm for this problem."

Thus it's not really correct to say that "all convex optimization problems can be solved in polynomial time." However, as Nesterov and Nemirovski show, many convex optimization problems can be formulated as LP, SOCP, or SDP and this technique is enormously important in both theory and practice.


You should check out Boyd-Vanderberghe's convex optimization, available for free on Boyd's web page at Stanford. This has a discussion of the "easy" classes of convex optimization problems (google "self concordant", for slightly quicker satisfaction). Even for linear problems interior point methods are slow if the condition number is very bad (which sometimes occurs in practice; what occurs even more frequently is that the condition number cannot be PROVED to be small, so your program runs fast in practice, but cannot be proved to be polynomial time).