Time - Complexity Convex Optimization and Eigen Decomposition
Regarding the eigen-decomposition, often it is enough to just compute the first few eigenvalue/eigenvector pairs. In the case, Krylow-subspace methods can be blazingly fast.

For the convex minimization under linear constraints, the (preconditioned) Uzawa iteration is a typical Krylow-subspace method, which is often not bad. There exist probably more advanced algorithms for this problem now, but http://scicomp.stackexchange.com would be a better place to ask about these.  Also Schur-complement methods, or just parameterization of the linear sub-space might work fine too. And in case the linear constraints is actually a bunch of linear inequalities, a state of the art linear/convex programming solver might be the way to go.