Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?



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](http://dx.doi.org/10.1137/S1052623401383248)", 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](https://doi.org/10.1109/SFCS.1997.646105)". FOCS 1997: 162-171 and Leonid Khachiyan, Lorant Porkolab "[Integer Optimization on Convex Semialgebraic Sets](https://doi.org/10.1007/PL00009496)". Discrete & Computational Geometry 23(2): 207-224 (2000).


M.Ramana in "[An Exact duality Theory for Semidefinite Programming and its Complexity Implications](https://doi.org/10.1007/BF02614433)" 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](https://doi.org/10.1016/j.dam.2007.04.023)" 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).


