If $n$ (and/or the number of linear pieces $m$) is extremely large and you are happy with approximate solutions you can try a subgradient method. The advantage is that their complexity does not depend on $n$, $m$ but only on the target accuracy $\varepsilon$, and the cost per iteration is linear in $n\times m$ (so it's at least as good as simplex).

The convergence rate in this case is $R/\sqrt{T}$ (where $R$ is an estimate on the distance from your starting point to the optimum, and $T$ is the number of iterations) and this algorithm is optimal when $n$ is large (see Nesterov's book Introductory Lectures on Convex Optimization, Theorem 3.2.2.

If $n$ (and/or the number of linear pieces $m$) is extremely large and you are happy with approximate solutions you can try a subgradient method. The advantage is that their complexity does not depend on $n$, $m$ but only on the target accuracy $\varepsilon$, and the cost per iteration is linear in $n\times m$ (so it's at least as good as simplex).

The convergence rate in this case is $R/\sqrt{T}$ (where $R$ is an estimate on the distance from your starting point to the optimum, and $T$ is the number of iterations) and this algorithm is optimal when $n$ is large (see Nesterov's book Introductory Lectures on Convex Optimization, Theorem 3.2.2).