Are all convex optimization problems easy to solve?

Question

Or can I say that, if I can prove it is a convex optimization problem, there must be an efficient method to solve it using the convex optimization technique? To be specific, the problem I considered is $$\min_x f(x),\ f(x)\ is \ convex,\ continuously \ differenciable$$ $$constraint: x\ is\ probability\ vector.$$ Does a problem in this form always have an efficient (mayebe $O(1/\epsilon)$ iteration complexity) method to solve?

Answer 1

No, not all convex programs are easy to solve. There are intractable convex programs.

Roughly speaking, for an optimization problem over a convex set $X$ to be easy, you have to have some kind of machinery available (an oracle) which efficiently can decide if a given solution $x$ is in $X$.

As an example, optimization over the cone of co-positive matrices is convex, but intractable. Given a matrix $A(x)$, it is hard to decide of $A(x)$ is co-positive ($z^TA(x)z\geq 0 ~\forall z\geq 0$). Compare this to the tractable problem of optimizing over the semidefinite cone $z^TA(x)z\geq 0 ~\forall z$