Suppose that we are in a finite-dimensional real vector space $\Bbb R^n$, and we are on a flat $F \subset \Bbb R^n$ (aka, an affine translation of a subspace of $\Bbb R^n$). We want to minimize some $\ell_p$ norm $\|\ldots\|_p$ on $F$.
This is a fairly typical unconstrained convex minimization problem. In practice, most numeric optimization routines that are commonly available can easily solve this problem fairly quickly.
It is fairly easy to visualize why these problems are easy to solve. Something like gradient descent, for instance, converges fairly quickly to the answer. All of these norms are fairly smooth except for $p=1$ and $p=\infty$, and can easily be smoothed by just minimizing $p=1+\epsilon$ to approximate $p=1$ or some large $p$ to approximate $\infty$. So they are fairly well-behaved.
My question is: do these problems fit into some subclass of convex programming that is always known to be fast? All I know is that I have not yet run into an unconstrained norm-minimization problem that has been slow, but I don't know how to place these within some subclass of convex programming that is known to be fast (like SDP, for instance).